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

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

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

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

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

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

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

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

在歐式距離下表示為

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

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

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

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

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

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

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

1 PCA相關概念

1.1 PCA處理步驟

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

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

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

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

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

1.2 PCA的實質

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

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

1.3 PCA運用到K均值合理性

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

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

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

2 算法設計

本部分主要對基于PCA的K均值方法的算法進行描述，給出相應的算法流程，同時對程序的算法復雜度進行分析，并根據算法復雜度對降維成本與減少的計算復雜度的關聯進行討論．

2.1 算法描述

2.1.1 Main函數的算法描述

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

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

2.1.2 數據產生的算法描述

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

表1 數據集示例

2.1.3 PCA方法的算法描述

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

程序中根據所產生的數據集的特點，采用以下2種標準對維度進行選擇．

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

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

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

2.2 降維成本與時間收益

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

2.2.1 算法復雜度分析

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

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

2.2.2 時間收益分析

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

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

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

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

3 實驗研究

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

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

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

3.1 差異性影響因素實驗

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

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

表2 COL后變動程序執行的結果

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

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

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

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

表3 隨機擾動因子變動程序執行的結果

隨機擾動因子越小，差異比率越小．也就是說，當數據之間線性關系越強時，降維聚類的結果越接近直接聚類的結果．

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

3.2 時間節省因素實驗

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

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

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

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

表4 數據量變動程序的執行結果

表5 列數變動時程序執行的結果

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

表6 COL2前與T降的變化關系

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

3.3 迭代次數實驗

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

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

表7 迭代次數

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

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

表8 完全線性時迭代次數

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

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

表9 隨機擾動因子為0.1時迭代次數

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

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

4 小結

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

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

參考文獻：

[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]范明, 孟小峰. 數據挖掘概念與技術[M]. 北京: 機械工業出社, 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-均值聚類的有監督分裂層次聚類方法[J]. 計算機應用研究, 2008, 25(5): 1412-1414.

[13]劉可新, 包為民, 闕家駿, 等. 基于主成分分析的K均值聚類法在洪水預報中的應用[J]. 武漢大學學報: 工學版, 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]彭敏, 傅慧, 黃濟民, 等. 基于核主成分分析與小波變換的高質量微博提取[J]. 計算機工程,2016, 42(1): 180-186.

[16]傅榮林. 主成分綜合評價模型的探討[J]. 系統工程理論與實踐, 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

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

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