一種基于降維思想的K均值聚類方法

徐 勇，陳 亮(安徽財經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 蚌埠 233000)

一種基于降維思想的K均值聚類方法

徐 勇，陳 亮
(安徽財經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 蚌埠 233000)

維數(shù)災(zāi)難是數(shù)據(jù)挖掘過程中的重要問題．為解決K均值聚類過程中的維數(shù)災(zāi)難問題，本文以歐式距離作為距離的計算方式，采用主成分(PCA)方法對數(shù)據(jù)源進行降維，實驗獲得在不同數(shù)據(jù)規(guī)模、特征下的K均值方法的聚類時間．設(shè)置對照組對時間、差異性、迭代次數(shù)三個方面進行比較．通過實驗總結(jié)出，數(shù)據(jù)源的大小與維數(shù)共同影響降維聚類的時間效益：數(shù)據(jù)數(shù)量越大，降維聚類的時間收益越大，數(shù)據(jù)維數(shù)越大，降維聚類的時間收益越小；數(shù)據(jù)源的線性程度影響降維聚類與非降維聚類結(jié)果的差異大?。簲?shù)據(jù)線性程度越高，兩次聚類結(jié)果差異性越?。粗町愋栽酱?；K均值算法收斂速度很快，兩次聚類都能在Sqrt(Row)次數(shù)內(nèi)完成程序的收斂．

聚類算法；降維；K均值；主成分分析

隨著無線遙感、GPS技術(shù)的發(fā)展，給人們帶來便捷的生活．人們在享受著位置服務(wù)的同時，也面臨著位置隱私的泄露問題．位置隱私中的軌跡隱私包含了人們的日?；顒有畔?，通過軌跡隱私可以推測出人們的宗教信仰、出行計劃等隱私信息．攻擊者可以通過這些信息對用戶進行廣告的精準投放、詐騙等行為，給用戶帶來財產(chǎn)上的安全隱患．所以，有必要對用戶的軌跡隱私進行保護．軌跡隱私保護常用的方法是位置信息的泛化，通過K均值聚類的方法，對軌跡數(shù)據(jù)采樣并聚類，然后發(fā)布模糊的軌跡數(shù)據(jù)．

K均值算法是一種非監(jiān)督實時聚類算法[1]，算法的核心思想是根據(jù)到中心點的距離，把所有的對象分配到不同的類別當中去．其中，根據(jù)問題的不同，距離的計算方式也會不同．對兩個被n個數(shù)值屬性描述的對象i,j，令用曼哈頓距離表示為

在歐式距離下表示為

K均值算法的時間復(fù)雜度為O(nmkt),其中n是對象數(shù)目，m是對象屬性數(shù)，k是聚類數(shù)目，t是迭代次數(shù)．對于給定數(shù)據(jù)集，在用K均值算法進行聚類的時候，要把每個對象的每個屬性參與運算．如果屬性過多、數(shù)據(jù)量較大，消耗的時間是難以忍受的．在軌跡隱私保護中，軌跡泛化需要對大量軌跡與大量采樣點進行聚類，需要進行多個維度大量數(shù)據(jù)的矩陣運算，傳統(tǒng)的K均值聚類計算時間過長，面臨維度災(zāi)難問題．

現(xiàn)實事物的屬性或者因素之間很多都是存在某種線性或者非線性的關(guān)系．在K均值算法中，如果參與運算的屬性之間存在某種函數(shù)關(guān)系，那就可以考慮通過降維方法對數(shù)據(jù)進行降維，減少參與運算數(shù)據(jù)的維數(shù)，從而達到減少算法運算量，縮短運行時間的目的．

在解決維數(shù)災(zāi)難問題上，國內(nèi)外學(xué)者提出了很多方法．在提取線性特征方面，主成分分析(PCA)[3]和 Fisher 線性判別分析(FLDA)[4]得到廣泛的運用．對于非線性的特征提取，核方法[5]是運用最廣泛的方法之一，核主成分分析(KPCA)[6]、核 Fisher 線性判別分析(KFLDA)[7]等核方法已經(jīng)獲得了較廣泛的使用．特別地，以 ISOMAP[8]、LLE[9]等為代表的方法，針對非線性、數(shù)據(jù)流形的特征提取有著較好的效果．

國內(nèi)外有很多運用降維思想解決實際問題的研究，針對數(shù)據(jù)不同的特點，也會采用不同的降維方法．例如，主成分分析算法對基因表達數(shù)據(jù)進行聚類[10]、把加入主成分分析的K均值聚類法運用于洪水預(yù)報[11]等是基于數(shù)據(jù)之間存在線性關(guān)系；KPCA與SVM相結(jié)合的分類[12]、基于核主成分分析與小波變換的高質(zhì)量微博提取[13]等是基于數(shù)據(jù)之間存在非線性關(guān)系．

對于每種降維方式，都有其的適用場景與不足．如PCA、KPCA具有良好的去除噪聲的功能，但是PCA降維時間復(fù)雜度較高，當維數(shù)較大時，需要大量的時間降維．FLDA對特征抽取效果非常好，但是在高維、小樣本情況下如何抽取Fisher最優(yōu)鑒別特征仍是個難題．

把降維思想與其他方法結(jié)合是解決問題的一個思路．當前，已經(jīng)有很多研究把降維和K均值聚類結(jié)合解決實際問題．例如，文獻[11，14-15]都是將 PCA與 K均值結(jié)合運用到各個應(yīng)用中去．目前這些研究是基于降維思想的K均值聚類方法在某一方面的運用，對降維帶來時間收益沒有一個定量的認識，對降維效果的影響因素比較含糊，沒有一般性地討論降維K均值聚類的步驟以及降維可能帶來的問題．

為解決類似軌跡隱私保護中的維數(shù)災(zāi)難問題，本文以基于主成分分析方法的K均值聚類為例，討論了降維思想在K均值聚類的運用以及可能出現(xiàn)的問題．為了方便說明，文中的數(shù)據(jù)集存在完全或者近似線性關(guān)系，采用歐式距離作為距離計算的標準．相對于其他文獻工作，本文的不同之處在于，更加一般性地討論運用降維方法進行K均值聚類的方法、步驟，并通過實驗討論降維聚類的時間節(jié)省、差異性、迭代次數(shù)3個層次的各種影響因素．

1 PCA相關(guān)概念

1.1 PCA處理步驟

(1)將原始數(shù)據(jù)按照行的方式組成n行m列的矩陣X；

(2)求X每列的平均值，然后讓該列的每個數(shù)減去平均值，得到矩陣D；

(4)求出協(xié)方差矩陣的特征值及其對應(yīng)的特征向量；

(5)將特征向量按照對應(yīng)的特征值大小進行排列，取前p個特征向量組成矩陣P；

Y是降維后的數(shù)據(jù)，該方法把冗余、無關(guān)的屬性去掉，得到最重要的屬性的組成矩陣排列，是原有數(shù)據(jù)信息很好的保留．

1.2 PCA的實質(zhì)

由上面的描述可以看出，主成分分析法的實質(zhì)就是原矩陣在新的標準正交基上的變換．存在線性相關(guān)的幾個維度會導(dǎo)致1個或者多個對應(yīng)的特征值為0或者相對較小，這些維度的數(shù)據(jù)經(jīng)過標準正交變換之后，基本都落在一個常數(shù)c上，這樣這個維度對全局的影響就很?。@時候用0向量替代方差貢獻率比較小的特征向量，消去這些維度，達到降維的目的，同時平滑了噪聲．

變化過程中，原矩陣會和變換后的矩陣有很大的差異，例如 A(1,3)，B(2,6)兩點組成的矩陣經(jīng)過降維之后的矩陣為與原始數(shù)據(jù)集相比存在如此大的差異的情況下，降維聚類的結(jié)果是否貼近實際的結(jié)果還需證明．

1.3 PCA運用到K均值合理性

當K均值采用歐式距離作為距離的計算標準時，特征值比較小的維度上的數(shù)據(jù)基本落在了常數(shù)c上，這樣數(shù)據(jù)對歐式距離的貢獻很小，舍去以后幾乎不會影響類別的劃分，同時也降低了異常點對聚類結(jié)果的影響，讓數(shù)據(jù)變得更加平滑，這些是 PCA運用到 K均值聚類的必要條件之一．只要證明經(jīng)過標準正交變換之后，對象與對象之間的距離不變，那么主成分分析法就可以運用到K均值算法中去．下面給出數(shù)學(xué)證明．

設(shè)空間中的兩點A、B與坐標原點O之間組成的向量為X，Y．則A、B兩點之間的距離的平方為設(shè)新的正交基為C，則A、B兩點在新的正交基下與原點之間的組成的向量為XC、YC．根據(jù)矩陣運算的結(jié)合律可知，A、B兩點在新的正交基下的距離的平方為

通過上述證明可以得出，經(jīng)過標準正交變換之后，對象與對象之間的距離不變．

2 算法設(shè)計

本部分主要對基于PCA的K均值方法的算法進行描述，給出相應(yīng)的算法流程，同時對程序的算法復(fù)雜度進行分析，并根據(jù)算法復(fù)雜度對降維成本與減少的計算復(fù)雜度的關(guān)聯(lián)進行討論．

2.1 算法描述

2.1.1 Main函數(shù)的算法描述

在一次試驗中，首先按照要求產(chǎn)生數(shù)據(jù)．為了與非降維聚類比較，同一數(shù)據(jù)集聚類2次，并記錄下聚類結(jié)果和聚類時間，最后比較這2個指標的差異．

首先，按照行數(shù)、列數(shù)、線性程度3個參數(shù)產(chǎn)生相應(yīng)的數(shù)據(jù)，并將產(chǎn)生的數(shù)據(jù)存放到txt文檔中，用于反復(fù)實驗．然后將產(chǎn)生的數(shù)據(jù)讀入內(nèi)存，并用矩陣Source對象存放，之后記下此時毫秒數(shù)為T0．直接聚類，聚類結(jié)果出來時，再次記下此時毫秒數(shù)為T1，同時把聚類結(jié)果1臨時存放在內(nèi)存中，用List集合保存起來．然后對Source進行降維，得到中間結(jié)果的矩陣對象 Target，記下此時毫秒數(shù)為T2，再對矩陣Target進行聚類，得到降維聚類的結(jié)果2，同時記下此時的毫秒數(shù)T3．第1次聚類時間為T前=T1-T0，第2次聚類時間T后=T3-T1，降維的時間為T降=T2-T1，降維后聚類的時間為T聚=T3-T2．比較T前與T后的大小就可以得出哪種方式的聚類時間少，分析T降與T后可以獲得原因；分析結(jié)果1與結(jié)果2每一類中相同的對象數(shù)目，可以得到兩次聚類結(jié)果的差異．

2.1.2 數(shù)據(jù)產(chǎn)生的算法描述

實驗數(shù)據(jù)前 10列的數(shù)值由隨機函數(shù)隨機生成，數(shù)據(jù)的生成公式為 source[i][j]=random. nextInt(maxSize)，10列以后的數(shù)據(jù)按照下面的公式 生成： source[i][j]=(1+r)*source[i][j%10]±r* source [i][j%10]．其中，source [i][j]是矩陣第i行第j列的值，maxSize是隨機函數(shù)產(chǎn)生的最大的數(shù)，r為0-1之間的1個隨機的小數(shù)．r*source [i][j%10]用于生成隨機擾動項，r一般很小，定義為隨機擾動因子，可以作為衡量數(shù)據(jù)之間的線性程度．r越小，表示線性程度越強．該公式生成的數(shù)是矩陣中第i行第j%10列的數(shù)乘以1個隨機倍數(shù)，再加上1個隨機擾動項．如表1中的5*20的數(shù)據(jù)，第11列的每行數(shù)據(jù)是第1列的每行數(shù)據(jù)的1.1倍加上1個隨機擾動項，第12列每行的數(shù)據(jù)是第2列每行數(shù)據(jù)的1.3倍加上1個隨機擾動項．隨機擾動項是為了模擬現(xiàn)實中可能出現(xiàn)非完全線性的數(shù)據(jù)．這種非線性將很大程度影響降維后的聚類結(jié)果．這樣就保證了第11列以后的數(shù)據(jù)和前10列具有近似線性關(guān)系．

表1 數(shù)據(jù)集示例

2.1.3 PCA方法的算法描述

PCA實現(xiàn)的算法，可以參考1.1節(jié)中的步驟進行．在算出特征值以后，對特征值進行累加，然后對這些特征值進行排序．根據(jù)數(shù)據(jù)特點，選取不同的標準對維度進行保留，獲得理想的效果．維度選擇的標準影響降維后的維數(shù)，進而影響數(shù)據(jù)之間距離信息的損失．數(shù)據(jù)特征不同的特點決定了維度選擇的標準并非單一．

程序中根據(jù)所產(chǎn)生的數(shù)據(jù)集的特點，采用以下2種標準對維度進行選擇．

一種以方差貢獻率大小為選取標準．定義方差貢獻率閥值為Q，當方差貢獻率rate≥Q時，保留該維，當rate＜Q時，舍去該維，其中Q小于總維數(shù)的倒數(shù)．通過控制方差貢獻率的閥值，可以控制降維后的維數(shù)．但是這種方式在近似線性的情況下，容易出現(xiàn)降維過度的情況，即大部分的維度被舍去，造成兩次聚類結(jié)果差異較大．

一種是直接指定降維后的維數(shù)．例如原來的數(shù)據(jù)是100維，人工指定降維到60維．這種方式是為了彌補上一種方式的降維過度的情況．但是這種方式依賴于人的經(jīng)驗，當數(shù)據(jù)量比較大的時候，很難把握合適的降維維數(shù)．

當數(shù)據(jù)集存在完全線性、完全非線性關(guān)系時，以方差貢獻率大小為選取標準可取得很好的效果．當存在數(shù)據(jù)集存在近似線性關(guān)系時，直接指定降維后的維數(shù)的方式會取得很好的效果．當然，沒有絕對標準，維度保留的標準要依據(jù)需求選?。?/p>

2.2 降維成本與時間收益

降維聚類的時間包含降維和聚類2個部分，要了解能否通過降維減少聚類時間帶來時間上的收益，需要分析PCA的時間復(fù)雜與K均值時間復(fù)雜度之間的關(guān)系．

2.2.1 算法復(fù)雜度分析

根據(jù)1.1節(jié)的步驟，求步驟(2)的時間復(fù)雜度為O(nm)，求協(xié)方差矩陣C需要進行矩陣相乘，所以步驟(3)的時間復(fù)雜度為O(nm2)．分析JAMA源碼可知，步驟(4)的時間復(fù)雜度為O(m2)，步驟(5)的時間復(fù)雜度為O(mlogm)，步驟(6)的時間復(fù)雜度為O(nmk)．所以PCA降維總的時間復(fù)雜度為O(nm2)，降維的時間與行數(shù)正比，與列數(shù)的平方成正比．

降維前，K均值算法的時間復(fù)雜度為O(nmkt) (k是聚類數(shù)目，t是迭代次數(shù))，降維后的時間復(fù)雜度為O(npkt)(p為降維后的維數(shù))．所以降維聚類總的時間復(fù)雜度為O(npkt) +O(nm2)，與降維前的O(nmkt)相比，兩者都在1個數(shù)量級上．

2.2.2 時間收益分析

假設(shè)降維前的聚類與降維后的聚類迭代次數(shù)相同，保持維數(shù)m不變，降維后的維數(shù)為p，同時滿足m=bp(b＞1)．那么降維前聚類的時間復(fù)雜度可以簡化為O(nkt)，降維后的聚類時間復(fù)雜度可以簡化為(C/b)O(n(m+kt))，其中C為兩種聚類方法時間復(fù)雜度的系數(shù)之比．因為m為常數(shù)，當數(shù)據(jù)量不斷增大時，k與t也會變大，T前/T后的值也會增大，當k與t的乘積遠大于m2時，T前/T后的值會趨近于定數(shù)F，其中F=Cb．可以通過實驗求得T前/T后的值F，進而求得常數(shù)C．通過這個性質(zhì)來預(yù)測降維后的時間縮減，即指定維數(shù)后，便可估算出降維聚類的運行時間為原來的T后/T前倍．事實上降維前的聚類與降維后的聚類迭代次數(shù)不一致，所以T前/T后趨近的值不會這么準確．所以，在維數(shù)不變的情況下，數(shù)量越大，降維聚類越能減少聚類總時間．

假設(shè)降維前的聚類與降維后的聚類迭代次數(shù)相同，保持行數(shù)n不變, 那么降維前聚類的時間復(fù)雜度可以簡化為O(m)，降維后的聚類時間復(fù)雜度可以簡化為O(m2)．所以，當數(shù)據(jù)行數(shù)不變，維數(shù)增大時，非降維組聚類的時間消耗成線性增長，降維聚類的時間消耗為2次函數(shù)形式增長，會更加消耗降維總時間，具體增長形式會受到迭代次數(shù)的影響．

降維聚類會導(dǎo)致迭代次數(shù)的變化，當數(shù)據(jù)集完全線性的時，保留全部非0特征值時，降維前后對象之間的距離不變，兩次聚類的迭代次數(shù)一致；當數(shù)據(jù)近似線性時，不保留全部特征值，會出現(xiàn)距離信息損失，對象之間距離會發(fā)生變化，兩次聚類的迭代次數(shù)會不一致．因為降維并不會一定減少迭代次數(shù)，而且K均值算法具有收斂速度快的特點，迭代次數(shù)很少，所以迭代次數(shù)并不是影響程序執(zhí)行時間的主要因素．

綜上所述，降維聚類能否節(jié)省時間主要受到數(shù)據(jù)行數(shù)與列數(shù)共同的影響．降維聚類總的時間復(fù)雜度為O(npkt)+O(nm2)，不進行降維的聚類的時間復(fù)雜度為O(nmkt)，當數(shù)據(jù)量很大時，聚類數(shù)目很多、和迭代次數(shù)很大，可考慮用降維聚類．

3 實驗研究

為了檢驗基于降維方法的算法優(yōu)劣，以及不同數(shù)據(jù)特征的數(shù)據(jù)集對降維聚類結(jié)果的影響，下面的所有數(shù)據(jù)都是通過計算機程序所造．所以本文只討論降維算法的實現(xiàn)和評價，降維聚類的實際應(yīng)用不在本文討論內(nèi)容之內(nèi)．程序的硬件環(huán)境為 AMD A6-3420M APU with Radeom(tm) HD Graphics 1.5GHz，運行環(huán)境為jdk1.8．

為了衡量降維效果，考察隨機擾動因子R、矩陣行數(shù)(條目數(shù))ROW、矩陣列數(shù)(維數(shù))3個變量，觀察其他條件不變時，某個條件變動對程序的執(zhí)行時間和聚類差異比率的影響．設(shè)降維前的列數(shù)為COL前，降維后列數(shù)為COL后，降維前程序執(zhí)行時間為T前，降維后程序執(zhí)行總時間為T后，其中降維所用時間為T降，降維后聚類的時間T聚，程序執(zhí)行減少的時間為ΔT，滿足T后=T降+T聚，ΔT=T降-T后．實驗中，時間的單位為毫秒(ms)．定義差異率DR為2次聚類的結(jié)果中存在差異的數(shù)目/總數(shù)目*100%．

最終的聚類數(shù)目k采用經(jīng)驗值并且每隔個數(shù)據(jù)選取一個初始中心點．

3.1 差異性影響因素實驗

本部分主要分別考察降維后的維數(shù)(COL后)、隨機擾動因子(R)對降維聚類與直接聚類結(jié)果的差異．第1部分研究COL后對差異性的影響，第2部分研究R對差異性的影響．

(1)選取數(shù)據(jù)集為10 000行，100列，聚成100個類．控制隨機擾動因子為0.01，這樣造出來的數(shù)據(jù)近似線性，所以采用指定降維維數(shù)COL后．當COL后在80、60、40、20變動時，結(jié)果見表2．

表2 COL后變動程序執(zhí)行的結(jié)果

由表2可知指定降維后的維度越小，程序執(zhí)行的時間顯著減少，同時伴隨著差異率的上升．程序減少的時間主要來源于T聚相對于T前的減少．數(shù)據(jù)集的維度下降了，等同于數(shù)據(jù)量減少了．

實驗中，每減少 20維，降維時間大約減少100毫秒．在2.2.1小節(jié)的分析中，PCA降維的過程中只有步驟(6)是和降維后維數(shù)相關(guān)，時間復(fù)雜度為O(mnk),與降維后的維數(shù)是線性關(guān)系，其他步驟都和m、n有關(guān)系．本次試驗中，只是變化了降維后的維，k,m,n并沒有變化，所以，降維的時間會呈現(xiàn)線性減少．

程序確實減少了聚類時間，同時，兩次聚類結(jié)果也存在一定的差異．造成這個原因的有2個，一是降維會造成信息丟失；二是程序在矩陣運算過程中，四舍五入的情況會導(dǎo)致精度的損失．

(2)選取數(shù)據(jù)集同樣為10 000行100列，聚成100個類．指定降維維數(shù)COL后為60．讓隨機擾動因子按照0.1、0.05、0.01、0.005變動，生成4個數(shù)據(jù)集，程序執(zhí)行的結(jié)果見表2.

表3 隨機擾動因子變動程序執(zhí)行的結(jié)果

隨機擾動因子越小，差異比率越?。簿褪钦f，當數(shù)據(jù)之間線性關(guān)系越強時，降維聚類的結(jié)果越接近直接聚類的結(jié)果．

從上面的兩個實驗結(jié)果可以總結(jié)出，隨機擾動因子R與選取的降維后維數(shù)COL后對降維差異率DR有很大影響．當數(shù)據(jù)集的R一定的情況下，如果要減小這種差異率，可以增大COL后．

3.2 時間節(jié)省因素實驗

本部分主要分別考察數(shù)據(jù)集行數(shù)、數(shù)據(jù)集列數(shù)對降維聚類結(jié)果的影響．為了演示效果，控制數(shù)據(jù)集為完全線性，根據(jù)方差貢獻率獲得最終降維維數(shù)．第1部分研究數(shù)據(jù)行數(shù)對節(jié)省實驗的影響，第2部分研究列數(shù)對時間節(jié)省的影響．

(1)把數(shù)據(jù)保持100維，隨機擾動因子為0，控制為完全線性，差異率控制為 0，最終降維為10維，條目按100，1 000，10 000，20 000，40 000變化時，程序的節(jié)省時間見表4．從表4可知，當數(shù)據(jù)量增大時，受迭代次數(shù)影響，無論是T前還是T聚，并不是隨著條目數(shù)的增長而線性增長，聚類時間增長的倍數(shù)要大于條目數(shù)增長的倍數(shù)，而且聚類時間增速非?？欤?/p>

原數(shù)據(jù)集為100維，最終降維為10維，根據(jù)2.2.2小節(jié)的結(jié)論，T前/T后的值會不斷增大，并趨近與1個定值．觀察表中T前/T后值的變化，前面4組值在不斷增大，最后4組在4.84～5.96波動，驗證了此理論．COL后/COL前的值為10，根據(jù)可以根據(jù)這幾組實驗估算出C的值為4.84～5.96之間．即在數(shù)據(jù)量比較大的情況下，維度每降低 1倍，聚類時間減少0.484～0.596倍．這是實驗測的C值，真實的 C值會有所差距，因為在試驗中，每組的數(shù)據(jù)都不一樣，迭代次數(shù)也不一樣，并且在執(zhí)行過程中還要受到CPU狀態(tài)、運行期優(yōu)化等影響．

(2)把數(shù)據(jù)保持10 000行，隨機擾動因子為0，控制為完全線性，差異率控制為 0，最終降維為10維，列數(shù)按照50，100，200，400，800變化時，程序的節(jié)省時間如表5所示．

表4 數(shù)據(jù)量變動程序的執(zhí)行結(jié)果

表5 列數(shù)變動時程序執(zhí)行的結(jié)果

從表5可知，在行數(shù)不變的情況下，T前隨著列數(shù)的增長而線性增長．T后最初小于T前，但是當列數(shù)增長至800時，T后遠遠大于T前．ΔT/T前逐漸減小直至為負可知，在列數(shù)不斷增長時，程序節(jié)省時間效果逐漸減小．因為數(shù)據(jù)的條目沒有變化，所以T聚幾乎沒有變化．T降增長速度也不斷增大，通過少量計算，如表6，得出與COL前的平方近似成線性關(guān)系．雖然COL2前/T降的大小沒有穩(wěn)定在 4，但是可以看出，降維時間和列數(shù)平方之間的關(guān)系為相同數(shù)量級上，與也符合前面分析的PCA的時間復(fù)雜度為O(nm2)．PCA降維過程中，第6步的時間復(fù)雜度為O(nm2)，省略了其他5步的時間復(fù)雜度，所以，COL2前/T降沒有穩(wěn)定在4波動．ΔT先增長，后下降為負，原因是降維花的時間隨著列數(shù)的增加而變得很長，降維的時間成為程序執(zhí)行最主要的消耗時間．

表6 COL2前與T降的變化關(guān)系

從上面2個實驗可以總結(jié)出，列數(shù)不變的情況下，數(shù)據(jù)量越大，降維節(jié)省的時間效果越好．這是因為一方面降維的時間增加的比較緩慢；另一方面，降維會導(dǎo)致參與運算的數(shù)據(jù)的減少，從而聚類運算時間極大減少．在行數(shù)不變的情況下，列數(shù)的增加會降低降維聚類帶來的時間紅利．這是因為隨著列數(shù)的增長，降維的時間將成為主要的運算時間．當列數(shù)達到一定的數(shù)目之后，降維聚類將耗費更多的時間．T降與T聚到底哪個成為運算的主要時間，取決于數(shù)據(jù)行數(shù)和數(shù)據(jù)列數(shù)的相對大?。?/p>

3.3 迭代次數(shù)實驗

本部分討論數(shù)據(jù)量的大小、數(shù)據(jù)非線性程度對兩種聚類方式的迭代次數(shù)的影響．第1部分研究數(shù)據(jù)量的上升迭代次數(shù)的變化．第2、第3部分為對照組，研究非線性程度對兩種降維方式迭代次數(shù)的影響．

(1)把數(shù)據(jù)保持100列，隨機擾動因子為0，控制為完全線性，差異率控制為 0，最終降維為10維，行數(shù)按100，1 000，5 000，10 000，20 000變化時，迭代次數(shù)見表7．

表7 迭代次數(shù)

由表7可知，雖然迭代次數(shù)隨著數(shù)據(jù)規(guī)模的增長而增長，但是卻沒有想象中的那么迅速，基本能在Sqrt(Row)次數(shù)完成程序收斂．這也體現(xiàn)了K均值算法良好的收斂性．

(2)把數(shù)據(jù)保持100列，隨機擾動因子為0，控制為完全線性，差異率控制為0，行數(shù)按照100, 500, 1 000, 2 000, 10 000變化時，2次聚類的迭代次數(shù)見表8．

表8 完全線性時迭代次數(shù)

由表8可以看出，在數(shù)據(jù)完全線性時，2次迭代次數(shù)一樣．這是因為完全線性導(dǎo)致只有 10個非0特征值，導(dǎo)致前10個特征值已經(jīng)包含了對象與對象之間所有的距離信息，所以迭代次不會改變，只也驗證了1.3小節(jié)中“變化標準正交基不改變對象之間距離”的理論．

(3)把數(shù)據(jù)保持100列，隨機擾動因子為0.1，控制為近似線性，降維后維度指定為50維，行數(shù)按100，1 000，10 000變化時，2次聚類的迭代次數(shù)如表9所示：

表9 隨機擾動因子為0.1時迭代次數(shù)

由表9可以看出，在數(shù)據(jù)近似線性時，兩次迭代次數(shù)不一致．這是因為近似線性導(dǎo)致只非 0特征值大50個，而程序之選取了前50個特征值，導(dǎo)致了對象之間部分距離信息的損失．降維的數(shù)據(jù)之間的距離發(fā)生變化，所以迭代次數(shù)也就發(fā)生了變化．

從實驗可以得出，K均值算法的收斂速度優(yōu)良，程序的執(zhí)行時間與迭代次數(shù)之間關(guān)系較小．在完全線性時，在充分保留所有非0特征值的情況下，降維不影響迭代次數(shù)．在近似線性情況下，保留大部分的維度，由于距離信息的損失，會導(dǎo)致2次迭代次數(shù)不一致．

4 小結(jié)

K均值算法中使用降維方法與不使用降維方法可以從時間節(jié)省、差異性、迭代次數(shù)3個方面比較．數(shù)據(jù)數(shù)量越大，降維聚類的時間收益越大，數(shù)據(jù)維數(shù)越大，降維聚類時間收益越小；數(shù)據(jù)源的線性程度影響降維聚類與非降維聚類結(jié)果的差異大小：數(shù)據(jù)線性程度越高，2次聚類結(jié)果差異性越小．反之，差異性越大．K均值算法收斂速度很快，2次聚類都以相對于數(shù)據(jù)量極小的次數(shù)完成收斂．

在定義降維前后2次聚類結(jié)果的不同的時候，措辭是“差異率”而不是“錯誤率”或者“差錯率”．因為這種降維帶來的差異并不能說它是不好，經(jīng)過PCA降維處理后，會平滑原數(shù)據(jù)中的噪聲，減少因為噪聲數(shù)據(jù)對聚類結(jié)果的影響．每種方法都有它的限制，不會對所有問題都適應(yīng)，降維聚類效果的好壞應(yīng)該由實踐來檢驗．關(guān)于降維聚類還有很多問題需要去研究，例如如何降低PCA的時間復(fù)雜度；當行數(shù)與列數(shù)形成什么關(guān)系時適合降維聚類．文中的數(shù)據(jù)為人工所造，不能準確反映真實情況，采用颶風(fēng)軌跡數(shù)據(jù)進行深入的測試驗證和研究．

參考文獻：

[1]Macqueen J. Some methods for classification and analysis of multivariate observations[C]// Proc. of, Berkeley Symposium on Mathematical Statistics and Probability. 1967: 281-297.

[2]范明, 孟小峰. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 北京: 機械工業(yè)出社, 2012: 48.

[3]Turk M, Pentland A. Eigenfaces for recognition[J]. Journal of Cognitive Neuroscience, 1991, 3(1): 71-86.

[4]Belhymeur P N, Hespanha J P, Kriegman D J. Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1997, 19(7): 711-720.

[5]Shawe-Taylor J, Cristianini N. Kernel methods for pattern analysis[J]. Journal of the American Statistical Association, 2004, 101(476): 1730-1730.

[6]Mika S, R?tsch G, Weston J,et al.Fisher discriminant analysis with kernels[C]// Proceedings of the 1999 IEEE Signal Processing Society Workshop. Madison, WI: IEEE, 1999: 41-48. [7]Sch?lkopf B, Smola A, Müller K. Nonlinear component analysis as a kernel eigenvalue problem[J]. Neural Computation, 1998, 10(5): 1299-1319.

[8]Tenenbaum J B, De S V, Langford J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500): 2319-2323.

[9]Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5500): 2323-2326.

[10]Yeung K Y, Ruzzo W L. Principal component analysis for clustering gene expression data[J]. Bioinformatics, 2001, 17(9): 763-774.

[11]師黎, 楊振興, 王治忠, 等. 基于PCA和改進K均值算法的動作電位分類[J]. 計算機工程, 2011, 37(16): 182-184.

[12]浦路平, 趙鵬大, 胡光道, 等. 基于PCA和K-均值聚類的有監(jiān)督分裂層次聚類方法[J]. 計算機應(yīng)用研究, 2008, 25(5): 1412-1414.

[13]劉可新, 包為民, 闕家駿, 等. 基于主成分分析的K均值聚類法在洪水預(yù)報中的應(yīng)用[J]. 武漢大學(xué)學(xué)報: 工學(xué)版, 2015, 48(4): 447-450.

[14]Kallas M, Francis C, Kanaan L,et al. Multi-class SVM classification combined with kernel PCA feature extraction of ECG signals[C]//International Conference on Telecommunications. IEEE, 2012: 1-5.

[15]彭敏, 傅慧, 黃濟民, 等. 基于核主成分分析與小波變換的高質(zhì)量微博提取[J]. 計算機工程,2016, 42(1): 180-186.

[16]傅榮林. 主成分綜合評價模型的探討[J]. 系統(tǒng)工程理論與實踐, 2001, 21(11): 68-74.

(責任編校：蔣冬初)

A K-means Clustering Method Based on Dimension Reduction

XU Yong,CHEN Liang
(School of management science and Engineering, Anhui University of Finance and Economics, Bengbu, Anhui 233000, China)

The curse of dimensionality is an important problem in the process of data mining. In order to solve the dimension disaster problem in K means clustering process, this paper uses the Euclidean distance as the way of the distance calculation, employing the principal component method (PCA) of the data source to reduce dimensionality, to acquire clustering time of the K means method in different scales and the characteristics of data by the experiment. And compare both the time and difference with the control group. It is concluded from the experiments that the size and the dimension of the data source combined effect of time benefit of dimension reduction in clustering: the greater the number of data dimensionality reduction is, the bigger the clustering time income is. The greater the data dimension is, the smaller the dimension reduction clustering time income is. The difference degree of linear data source to reduce the influence on difference comparison between clustering by reducing dimension and the another: the higher the linearity degree of data is, the smaller is the two clustering results difference is. On the contrary, the difference is greater. K means algorithm convergence rate is very fast, two clusters can complete convergence with respect to the number of data.

clustering algorithm; dimensionality reduction; K means; PCA

N32

A

10.3969/j.issn.1672-7304.2017.01.12

1672–7304(2017)01–0054–08

2016-02-10

國家社會科學(xué)基金項目(15BTQ043)；安徽省自然科學(xué)基金項目(1408085MF127)；安徽省高校省級優(yōu)秀青年人才基金重點項目(2013SQRL031ZD)；教育部人文社會科學(xué)研究規(guī)劃基金項目(12YJA630136)

徐勇(1978-)，男，安徽涇縣人，教授，博士，主要從事社會計算、信息安全、數(shù)據(jù)挖掘研究．Email：uxyong@sina.com