K-Means聚類算法的改進和研究

王佩科，趙 馳

（1.淮海工學院計算機工程學院，連云港 222000；2.延安大學數學與計算機科學學院，延安 716000）

1 引言

在數據挖掘和處理方面，聚類分析是非常常見的一種方法。聚類算法中按照不同的標準分類眾多，k-均值算法屬于其中之一。其中的K-均值算法，又叫做K-Means聚類法，是聚類算法中的經典算法，是一種簡單、容易實現且具有明確易于理解的幾何意義。

2 基于K-means算法改進

傳統的K-Means的k值是隨機的，而數據集中包含有孤立點（和其他數據點相似度低且處在邊緣），若選擇在了這些特殊的點，算法的結果會和實際結果有著較大的出入，這樣就會使得算法在計算結果上嚴重偏離預想，因此，剔除“孤立點”無疑是K-Means改進的有效方法。

2.1 改進算法的基本思想

首先，計算出數據集中每兩個數據點之間的距離，輸出結果為dist矩陣，然后對其行進行遞增排列，列遞減排列，在每行找到與數據點距離最近的n個距離，接著找到m個距離數據點的最鄰近點。每如此處理，找到每一列的最鄰近點，隨后進行唯一化去重，通過向量中的元素計算出最近鄰距離差并找到max減數作為密度半徑。與人工給出的閾值進行比較，判別出“孤立點”并在輸入集中剔除。

2.2 改進算法的描述

輸入：輸入集 Input_Data，定義n為鄰距離的個數，定義m為與其相距最大距離的個數。

輸出：檢測到的孤立點Outier。

步驟：

（1）首先計算輸入集Input_Data中兩兩數據點的距離dist，把輸出結果記為Dist矩陣，定義Dist的對角線的值為∞，表示它與自己的距離。

（2）將Dist矩陣的行元素按照遞增順序排列。

（3）將矩陣的每一列按照遞減順序排列，取前n個數據元素，并存在孤立點向量Outier_ Data里。

（4）對Outier _Data 做唯一化處理，再對Outier_Data內的每個數據點對間隔矩陣Dist計較，找到最近鄰距離差ΔD（i，j），并將最大的ΔD（i，j）記為maxΔD，幾下此時相應的密度半徑為E。

（5）計算每個數據點在Dist矩陣在E下的在矩陣Dist中的密度記為r。

（6）用r與人共設置的閾值進行比較，若大，則保留，反之視為孤立點剔除。

2.3 改進算法的效果

改進算法和k-Means的準確率對比見表1。

表1 改進算法和k-Means的準確率對比

3 結束語

本文提出了孤立點對K-Means算法的結果和精準性的干擾，并在此基礎上做出優化，剔除一種通過剔除孤立點來提高算法精準度的思想。■