王佩科，趙 馳

（1.淮海工學(xué)院計(jì)算機(jī)工程學(xué)院，連云港 222000；2.延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，延安 716000）

1 引言

在數(shù)據(jù)挖掘和處理方面，聚類(lèi)分析是非常常見(jiàn)的一種方法。聚類(lèi)算法中按照不同的標(biāo)準(zhǔn)分類(lèi)眾多，k-均值算法屬于其中之一。其中的K-均值算法，又叫做K-Means聚類(lèi)法，是聚類(lèi)算法中的經(jīng)典算法，是一種簡(jiǎn)單、容易實(shí)現(xiàn)且具有明確易于理解的幾何意義。

2 基于K-means算法改進(jìn)

傳統(tǒng)的K-Means的k值是隨機(jī)的，而數(shù)據(jù)集中包含有孤立點(diǎn)（和其他數(shù)據(jù)點(diǎn)相似度低且處在邊緣），若選擇在了這些特殊的點(diǎn)，算法的結(jié)果會(huì)和實(shí)際結(jié)果有著較大的出入，這樣就會(huì)使得算法在計(jì)算結(jié)果上嚴(yán)重偏離預(yù)想，因此，剔除“孤立點(diǎn)”無(wú)疑是K-Means改進(jìn)的有效方法。

2.1 改進(jìn)算法的基本思想

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

2.2 改進(jìn)算法的描述

輸入：輸入集 Input_Data，定義n為鄰距離的個(gè)數(shù)，定義m為與其相距最大距離的個(gè)數(shù)。

輸出：檢測(cè)到的孤立點(diǎn)Outier。

步驟：

（1）首先計(jì)算輸入集Input_Data中兩兩數(shù)據(jù)點(diǎn)的距離dist，把輸出結(jié)果記為Dist矩陣，定義Dist的對(duì)角線(xiàn)的值為∞，表示它與自己的距離。

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

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

（4）對(duì)Outier _Data 做唯一化處理，再對(duì)Outier_Data內(nèi)的每個(gè)數(shù)據(jù)點(diǎn)對(duì)間隔矩陣Dist計(jì)較，找到最近鄰距離差ΔD（i，j），并將最大的ΔD（i，j）記為maxΔD，幾下此時(shí)相應(yīng)的密度半徑為E。

（5）計(jì)算每個(gè)數(shù)據(jù)點(diǎn)在Dist矩陣在E下的在矩陣Dist中的密度記為r。

（6）用r與人共設(shè)置的閾值進(jìn)行比較，若大，則保留，反之視為孤立點(diǎn)剔除。

2.3 改進(jìn)算法的效果

改進(jìn)算法和k-Means的準(zhǔn)確率對(duì)比見(jiàn)表1。

表1 改進(jìn)算法和k-Means的準(zhǔn)確率對(duì)比

3 結(jié)束語(yǔ)

本文提出了孤立點(diǎn)對(duì)K-Means算法的結(jié)果和精準(zhǔn)性的干擾，并在此基礎(chǔ)上做出優(yōu)化，剔除一種通過(guò)剔除孤立點(diǎn)來(lái)提高算法精準(zhǔn)度的思想?！?/p>