[發明專利]基于冗余距離消除和極端點優化的并行k-means聚類方法

在審

• 申請號: 201610044881.6
• 申請日: 2016-01-22
• 公開（公告）號: CN105740604A
• 公開（公告）日: 2016-07-06
• 發明（設計）人: 李肯立;肖錦波;唐卓;劉錫洋;魯彬;陳俊杰
• 申請（專利權）人: 湖南大學
• 主分類號: G06F19/00
• 分類號: G06F19/00;G06K9/62
• 代理公司: 深圳市興科達知識產權代理有限公司 44260
• 代理人: 王翀

1.一種基于冗余距離消除和極端點優化的并行k-means聚類方法，其特征在于，使用正弦定理和余弦定理，找出每個聚類中的冗余距離并消除每個聚類中的冗余距離；對極端點與極端點所在聚類的中心點之間距離采用曼哈頓距離進行計算；在迭代過程中，采用平均值的計算方式選取K-means聚類方法中的中心點。

2.如權利要求1所述的基于冗余距離消除和極端點優化的并行k-means聚類方法，其特征在于，包括如下步驟：

步驟一、在多臺物理服務器上構建完全分布式系統，將醫療數據及中心點數據導入完全分布式系統；

步驟二、用戶向完全分布式系統提交作業，完全分布式系統將整個作業分解成多個分塊；

步驟三、完全分布式系統啟動映射任務辨別分塊的數據，將分塊的數據按中心點進行聚類，將離中心點距離最近的點聚為一類；中心點集合形成當前的中心點集；

步驟四、消除每個聚類中的冗余距離計算：使用正弦定理和余弦定理，找出每個聚類中的冗余距離，消除每個聚類中的冗余距離；采用曼哈頓距離計算聚類中的極端點與其相應中心點的距離；

步驟五、對于k個聚類分別分配1～k個編號；對于每個聚類中的任意一點生成鍵值對，所述鍵值對包括鍵名和值；鍵名為聚類的中心點所在的聚類編號，值為此點所有的列值；按照鍵名進行分割，產生分區；

步驟六、每個分區由一個規約任務進行處理，依次統計規約任務接收到每一個鍵名對應的值；這個值通常包含一個或多個列，然后求出對應列的平均值，這個平均值作為新的聚類中心點，新的中心點集合形成新的中心點集；

步驟七、對比新的中心點集與當前的中心點集，如果新的中心點集與當前的中心點集相同，則將規約任務產生的鍵值對作為最終的聚類結果；否則，用新產生的中心點代替當前的中心點，重復步驟二～步驟六進行迭代運算，直至獲得最終的聚類結果。

3.如權利要求2所述的基于冗余距離消除和極端點優化的并行k-means聚類方法，其特征在于，所述步驟四中，冗余距離計算的方法為：首先，對于聚類中的某一點p點，計算p點與p點所在聚類的中心點o1的距離，該距離記為d(p,o1)；其次，找出p點所在的聚類中離中心點o1最遠的一個點b點，b點與o1的距離記為d(b,o1)；然后p點所在聚類的中心點o1與剩余的k-1個聚類的中心點進行距離計算，與剩余的k-1個聚類的中心點中的中心點o2進行距離計算，中心點o1和中心點o2的距離記為d(o1,o2)，p點與o2的距離記為d(p,o2)；若d(o1,o2)≥2*d(b,o1)，或d(o1,o2)≥d(p,o1)+d(b,o1)，則d(p,o2)是冗余距離。

4.如權利要求2所述的基于冗余距離消除和極端點優化的并行k-means聚類方法，其特征在于，所述步驟四中，極端點的定義如下：

K=Σi=1n(Xi-X‾)4(n-1)D2]]>

其中，n表示某一聚類中有n個點，X表示某一聚類中非中心點到中心點的距離，表示某一聚類中所有非中心點到中心點的距離平均值，D表示某一聚類中所有非中心點到中心點的距離的方差，i表示某一聚類中第i個非中心點；如果某一聚類中某個點的K值大于8.4595，則此點是極端點；對于極端點，采用曼哈頓距離計算該點與其相應中心點的距離。

5.根據權利要求2所述的基于冗余距離消除和極端點優化的并行k-means聚類方法，其特征在于，所述完全分布式系統為Hadoop完全分布式系統。