鄭　誠(chéng)，俞青云（安徽大學(xué)　計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽　合肥　230601）

?

基于kNN的聚類算法研究

鄭誠(chéng)，俞青云
（安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽合肥230601）

摘要：聚類分析在數(shù)據(jù)挖掘領(lǐng)域中占有重要地位，到目前為止學(xué)者們提出了許多的聚類算法.本文提出了一種基于kNN的聚類算法k-NearestNeighborCluster（kNNC）.該算法首先找到每個(gè)數(shù)據(jù)點(diǎn)的k個(gè)鄰居點(diǎn)，然后設(shè)置匹配點(diǎn)數(shù)n，通過(guò)使用每個(gè)點(diǎn)的鄰居點(diǎn)進(jìn)行匹配進(jìn)而達(dá)到聚類效果.本文通過(guò)三個(gè)實(shí)驗(yàn)去驗(yàn)證該算法，并且與k-means算法進(jìn)行比較.實(shí)驗(yàn)結(jié)果表明，該算法具有穩(wěn)定的正確率，而其最大的優(yōu)點(diǎn)是不需要預(yù)先設(shè)定聚類簇?cái)?shù)，它可以大致的找到聚類的簇?cái)?shù).

關(guān)鍵詞：kNN算法；k-means算法；聚類分析；微博文本聚類

1　引言

在數(shù)據(jù)挖掘中，有兩個(gè)重要的研究方向，一類是聚類算法的研究，還有一類是分類算法的研究.對(duì)于分類就是將貼過(guò)標(biāo)簽的對(duì)象按標(biāo)簽進(jìn)行分類，而聚類則是指事先沒(méi)有“標(biāo)簽”而通過(guò)某種成團(tuán)分析找出事物之間存在聚集性原因的過(guò)程.

聚類分析又稱為群分析，它是研究（樣品或指標(biāo)）分類問(wèn)題的一種統(tǒng)計(jì)分析方法.當(dāng)前，聚類（Cluster）分析的算法可以分為劃分為以下幾個(gè)大類：

（1）劃分法（Partitioning Methods）.它的代表算法為k-means算法[1]，k-means算法通過(guò)隨機(jī)的選取k個(gè)中心點(diǎn)，然后計(jì)算每個(gè)點(diǎn)到k個(gè)中心點(diǎn)的距離，進(jìn)而達(dá)到聚類的效果.它的缺點(diǎn)是需要事先輸入聚類簇?cái)?shù)k，并且聚類的好壞與中心點(diǎn)的選取密切相關(guān).

（2）層次法（Hierarchical Methods）.層次聚類算法又分為層次凝聚和層次分裂，層次凝聚的代表算法為AGNES算法[2]，該算法首先將每個(gè)對(duì)象看成一個(gè)類，然后通過(guò)合并直到達(dá)到要求的簇類數(shù).而層次分裂的代表算法為DIANA算法[3]，該算法首先將所有對(duì)象看成是一個(gè)簇類，然后通過(guò)分裂直到達(dá)到要求的簇類數(shù).然而他們都需要事先輸入簇類數(shù).

（3）基于密度的方法（density-based methods）.它的代表算法為DBSCAN算法[4]，該算法將具有足夠密度的區(qū)域劃分為簇.然而當(dāng)對(duì)象空間分布的不均勻是，它的聚類效果會(huì)很差.

（4）基于網(wǎng)格的方法（grid-based methods）.它的代表算法是CLIQUE算法[5]，該算法把每個(gè)維度劃分為不重疊的空間，然后把數(shù)據(jù)分布在這些區(qū)間中劃分成單元，然后通過(guò)設(shè)置的密度閾值識(shí)別稠密單元，從而達(dá)到聚類效果.然而該算法的效率和聚類質(zhì)量不高.

（5）基于模型的方法（Model-Based Methods）.它的代表算法為SOM算法[6]，該算法通過(guò)將數(shù)據(jù)（n維）輸出到平面（2維）的降維映射，其映射具有拓?fù)涮卣鞅３中再|(zhì)，使用競(jìng)爭(zhēng)式學(xué)習(xí)網(wǎng)絡(luò)實(shí)現(xiàn)聚類.但是該算法對(duì)數(shù)據(jù)的處理時(shí)間較長(zhǎng)，所以不適合大量數(shù)據(jù)集.

本文提出了一種基于kNN的聚類算法.通過(guò)實(shí)驗(yàn)我們計(jì)算了實(shí)驗(yàn)的準(zhǔn)確率(Precision)、召回率(Recall)以及F值(F-Measure),并且與k-means進(jìn)行比較，表明該算法可以大致的找到聚類簇?cái)?shù).

2　相關(guān)工作

K最近鄰(kNN，k-NearestNeighbor)算法是屬于數(shù)據(jù)挖掘的分類算法之一，kNN算法的核心思想是計(jì)算出每個(gè)待分類對(duì)象的k個(gè)鄰近對(duì)象，如果該帶分類對(duì)象的k個(gè)鄰近對(duì)象大部分屬于一個(gè)類，那么該對(duì)象就屬于那個(gè)類.近年來(lái)，學(xué)者們對(duì)kNN算法的研究層出不窮，kNN也被運(yùn)用到不少聚類中. 2007年翁芳菲等人提出了一種基于KNN的融合聚類算法(KNNCE)[7]，該算法首先對(duì)數(shù)據(jù)集運(yùn)行N 次KNN算法構(gòu)造similarity矩陣，然后對(duì)該矩陣使用single-link算法確定最終的聚類劃分，該算法能夠自動(dòng)確定最佳聚類數(shù).2013年廖禮等人提出了一種KNN-Potential-based算法[8]，該算法首相對(duì)數(shù)據(jù)集使用KNN算法得到初始的密度圖，然后在對(duì)初始的密度用Potential-based算法進(jìn)行調(diào)整，最終確定聚類劃分.2015年牛秦洲等人提出了一種基于MCL與kNN的混合聚類算法[9]，該算法首先對(duì)數(shù)據(jù)集使用MCL算法進(jìn)行聚類，然后對(duì)聚類結(jié)果中的小聚類簇使用KNN分類算法進(jìn)行再分類，以提高聚類質(zhì)量.2015年仰孝富等人提出了一種CF樹(shù)結(jié)合kNN圖劃分的文本聚類算法[10]，該算法首先使用KNN算法得到數(shù)據(jù)集初始的最小簇集合，然后對(duì)這些最小簇集合使用BIRCH聚類過(guò)程進(jìn)行聚類.

對(duì)于kNN的研究基本上是結(jié)合其他算法進(jìn)行的，而本文提出了一種不依賴于其他算法的kNN聚類算法.

3　k-NearestNeighborCluster（kNNC）

3.1基本定義

定義1待聚類集合S：S={X1，X2，…，Xn}，其中Xi集合S的第i個(gè)對(duì)象，n為對(duì)象的個(gè)數(shù).

定義2對(duì)象Xi={ai1,ai2,…,aij,…,aim}，其中aij為對(duì)象Xi的第j個(gè)屬性，m為每個(gè)對(duì)象屬性的個(gè)數(shù).

定義3對(duì)象之間的距離公式：D(Xi,Xb)=

定義4第i個(gè)對(duì)象的k個(gè)最鄰近對(duì)象集合：

MAXk表示第i個(gè)對(duì)象與所有其他對(duì)象的距離按從小到大排序的第k個(gè)距離值.

定義5聚類輸出集合SC={C1,C2,…,Ct,…,CK}，其中K為聚類的簇?cái)?shù)，Ct表示第t個(gè)類的對(duì)象集合.

3.2基本思想

k-NearestNeighborCluster（kNNC）的基本思想是通過(guò)每個(gè)點(diǎn)的鄰居點(diǎn)的匹配，當(dāng)兩個(gè)點(diǎn)匹配數(shù)達(dá)到設(shè)置數(shù)目時(shí)，那么就判定它們是一個(gè)類的.

kNNC算法思想描述如下：

確定鄰居點(diǎn)個(gè)數(shù)k和匹配點(diǎn)數(shù)目n.

（1）通過(guò)距離算法確定每個(gè)點(diǎn)的k個(gè)最進(jìn)的鄰居點(diǎn).

（2）取出沒(méi)有被劃分的一個(gè)數(shù)據(jù)點(diǎn)，設(shè)定為類Cj的第一個(gè)點(diǎn)，并且把它的鄰居點(diǎn)設(shè)為該類的初始鄰居點(diǎn).

（3）依次取出沒(méi)有被劃分?jǐn)?shù)據(jù)點(diǎn)，用該點(diǎn)的鄰居點(diǎn)與Cj的鄰居點(diǎn)進(jìn)行匹配，如果匹配到點(diǎn)的個(gè)數(shù)大于匹配點(diǎn)數(shù)目n，那么就將該點(diǎn)加入Cj類.

（4）重復(fù)步驟3，知道所有的點(diǎn)都被劃分到一個(gè)類.

在該算法中，我們使用歐氏距離來(lái)計(jì)算兩個(gè)點(diǎn)之間的相似度，歐氏距離公式如下：

其中D(Xi,Xb)表示點(diǎn)Xi到點(diǎn)Xb的距離.

算法kNNC(S,nn,nnm),S={X1，X2，…，Xn};

輸入：n個(gè)數(shù)據(jù)對(duì)象集合S；

輸出：K個(gè)聚類數(shù)據(jù)對(duì)象集合SC={C1,C2,…,Ct, …,CK}；

Begin

Set nn,nnm;

k=1;

allcoord=n;//剩余需要聚類的點(diǎn)的個(gè)數(shù)

For i=1 to n do

begin

For b=1 to n do

Computer MAXk D;

Ui={Xa|Xa∈S&&D(Xi,Xa)≤MAXk&&a∈{1,2, …,n}};//找到所有點(diǎn)的k個(gè)最近鄰居點(diǎn)

end;

Repeat

For i=1 to n do

If Xi?Cj|| k=1 then

begin

Cj=Cj+Xi;

CNj=Ui;

allcoord--;

Break;

end;

for i=1 to n do

begin

if Xi?Cjthen

begin

mn=match(CNj,Ui);

if mn＞=nnm then

begin

Cj=Cj+Xi;

CNj=CNj+Xi;

allcoord--;

end;

end;

end;

until allcoord=0;

End;

在上面的算法中，nn為鄰居點(diǎn)數(shù)目，nnm兩個(gè)點(diǎn)鄰居點(diǎn)匹配數(shù).MINk為距離最小的k個(gè)對(duì)象.CNj為第j個(gè)類的鄰居點(diǎn)集合.match(CNj,Ui)為第j個(gè)類的鄰居點(diǎn)與第i個(gè)點(diǎn)的鄰居點(diǎn)一一匹配的匹配數(shù).

4　實(shí)驗(yàn)

4.1實(shí)驗(yàn)的數(shù)據(jù)集

數(shù)據(jù)集1：

從數(shù)據(jù)堂下載來(lái)的6200條微博數(shù)據(jù).其中1—1000條是馬航數(shù)據(jù)，1001-2000是昆明暴恐?jǐn)?shù)據(jù)，2001-3000是反腐數(shù)據(jù)，3001-4000是兩會(huì)數(shù)據(jù)，4001-5000是轉(zhuǎn)基因食品數(shù)據(jù)，5001-6000是烏克蘭事件數(shù)據(jù)，另外我們還加入了200條噪音數(shù)據(jù).

處理數(shù)據(jù)：

（1）去除數(shù)據(jù)的無(wú)用符號(hào)，網(wǎng)址等；

（2）對(duì)數(shù)據(jù)進(jìn)行分詞；

（3）去除停用詞；

（4）用BTM對(duì)數(shù)據(jù)進(jìn)行建模；

數(shù)據(jù)集2：從UCI上下載的聚類數(shù)據(jù)集，一共有210條5維數(shù)據(jù)，數(shù)據(jù)分為3個(gè)類，每70條為一個(gè)類.

數(shù)據(jù)集3：從UCI上下載的聚類數(shù)據(jù)集，一共有600條60維數(shù)據(jù)，數(shù)據(jù)分為6個(gè)類，每100條為一個(gè)類.

實(shí)驗(yàn)采用準(zhǔn)確率(Precision)、召回率(Recall)以及F值(F-Measure)來(lái)對(duì)比兩個(gè)算法.

4.2鄰居數(shù)與匹配數(shù)對(duì)kNNC的影響

我們首先使用數(shù)據(jù)堂下載的6200條微博數(shù)據(jù)對(duì)該算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果在下圖中展示出來(lái).

從圖1、圖2、圖3中可以知道對(duì)于不同的鄰居點(diǎn)數(shù)，匹配點(diǎn)數(shù)對(duì)他們的影響趨勢(shì)是大致相同的.都是先隨著匹配點(diǎn)數(shù)的增加然后達(dá)到一個(gè)最高點(diǎn)，最后下降.從上圖中可以知道當(dāng)鄰居點(diǎn)為500時(shí)，匹配點(diǎn)數(shù)為130時(shí)，準(zhǔn)確率達(dá)到最高.當(dāng)鄰居點(diǎn)為600時(shí)，匹配點(diǎn)數(shù)為150時(shí)，準(zhǔn)確率達(dá)到最高.當(dāng)鄰居點(diǎn)為700時(shí)，匹配點(diǎn)數(shù)為160時(shí)，準(zhǔn)確率達(dá)到最高.

圖1　鄰居點(diǎn)為500時(shí)的匹配數(shù)對(duì)算法的影響

圖2　鄰居點(diǎn)為600時(shí)的匹配數(shù)對(duì)算法的影響

圖3　鄰居點(diǎn)為700時(shí)的匹配數(shù)對(duì)算法的影響

圖4　鄰居點(diǎn)數(shù)對(duì)算法的影響

圖4給出了鄰居點(diǎn)數(shù)對(duì)算法的影響，我們選取在各個(gè)不同的鄰居點(diǎn)數(shù)下，最好的結(jié)果作為最終顯示結(jié)果.從圖中可知，隨著鄰居點(diǎn)數(shù)的增加算法的準(zhǔn)確率成上升趨勢(shì)，然后達(dá)到最高點(diǎn)以后，開(kāi)始成下降趨勢(shì).從上圖可知，當(dāng)鄰居點(diǎn)數(shù)設(shè)為600時(shí)，算法的準(zhǔn)確率達(dá)到最大（0.801333）.

4.3主題數(shù)的影響

對(duì)于微博6200條數(shù)據(jù)集我們使用BTM對(duì)其建模，我們對(duì)6200條數(shù)據(jù)，選取了不同的主題數(shù)用BTM建模.然后通過(guò)實(shí)驗(yàn)我們發(fā)現(xiàn)主題數(shù)對(duì)實(shí)驗(yàn)結(jié)果有著較大的影響.

從圖5、圖6、圖7中可以看到隨著主題數(shù)的增加，算法的準(zhǔn)確率、召回率、F值都是先上升，達(dá)到一個(gè)最高點(diǎn)，然后下降.綜合上圖可知，在微博數(shù)據(jù)集上，當(dāng)主題數(shù)達(dá)到7時(shí)，各項(xiàng)數(shù)值達(dá)到最優(yōu).

4.4其他實(shí)驗(yàn)

對(duì)于我們的算法能否正確的找到聚類簇?cái)?shù)，我們做了下面三個(gè)實(shí)驗(yàn)：

1.對(duì)數(shù)據(jù)堂下載的6000條微博數(shù)據(jù)（weibodata）進(jìn)行的實(shí)驗(yàn)（自己加入了200條雜數(shù)據(jù)）.

2.對(duì)UCI下載的210條5維（uci210_5）數(shù)據(jù)進(jìn)行實(shí)驗(yàn).

3.對(duì)UCI下載的600條60維(uci600_60)數(shù)據(jù)進(jìn)行實(shí)驗(yàn).

實(shí)驗(yàn)結(jié)果在表1中給出了：

表1　算法確定的聚類簇?cái)?shù)

從上表可知，該算法可以大致的找到數(shù)據(jù)的簇?cái)?shù).

圖5　主題數(shù)對(duì)準(zhǔn)確率的影響

圖6　主題數(shù)對(duì)召回率的影響

圖7　主題數(shù)對(duì)F值的影響

表2　算法的聚類準(zhǔn)確率

在表2中uci210_5_20_8中的20_8表示當(dāng)鄰居點(diǎn)數(shù)設(shè)為20，匹配數(shù)設(shè)為8時(shí)，實(shí)驗(yàn)結(jié)果最佳.從表2可知，該算法的準(zhǔn)確率很穩(wěn)定，適合大部分的數(shù)據(jù)集.

5　結(jié)論

在這篇文章中，我們提出了一種基于kNN的聚類算法，該算法不需要預(yù)先設(shè)點(diǎn)聚類簇?cái)?shù)，算法通過(guò)確定鄰居點(diǎn)數(shù)和匹配點(diǎn)數(shù)，可以大致的找到聚類簇?cái)?shù).通過(guò)實(shí)驗(yàn)證明了該算法可以準(zhǔn)確的將數(shù)據(jù)分類，并且具有穩(wěn)定的準(zhǔn)確率.該算法與k-means算法相比較，召回率有所提高，具有一定的實(shí)際應(yīng)用價(jià)值.

參考文獻(xiàn)：

〔1〕尹成祥,張宏軍,張睿,等.一種改進(jìn)的K-Means算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014（10）:30-33.

〔2〕姚寧,馬青蘭,張晶,等.基于AGNES算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)和GIS系統(tǒng)的大氣污染物濃度預(yù)測(cè)[J].中國(guó)環(huán)境監(jiān)測(cè),2015(03)：3-5.

〔3〕徐克圣,王瀾.一種自動(dòng)獲得k值的聚類算法[J].大連交通大學(xué)學(xué)報(bào),2007（4）:68-71.

〔4〕李雙慶,慕升弟.一種改進(jìn)的DBSCAN算法及其應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2014（08）:72-76.

〔5〕項(xiàng)響琴,汪萍,李健.CLIQUE算法在信用卡審批模型中的應(yīng)用研究[J].安徽建筑工業(yè)學(xué)院學(xué)報(bào)（自然科學(xué)版）,2011,19(1):89-93.

〔6〕王志省,許曉兵.改進(jìn)的基于SOM的高維數(shù)據(jù)可視化算法[J].計(jì)算機(jī)工程與應(yīng)用,2013（17）: 112-115.

〔7〕翁芳菲,陳黎飛,姜青山.一種基于KNN的融合聚類算法[J].計(jì)算機(jī)研究與發(fā)展,2007（44）:187-191.

〔8〕廖禮.一種新的基于密度的聚類算法研究[D].蘭州大學(xué),2013.

〔9〕牛秦洲,陳艷.基于MCL與KNN的混合聚類算法[J].桂林理工大學(xué)學(xué)報(bào),2015,35(1):181-186.

〔10〕仰孝富,齊建東,吉鵬飛,等.一種CF樹(shù)結(jié)合KNN圖劃分的文本聚類算法[J].計(jì)算機(jī)工程與應(yīng)用,2015（07）:114-119.

收稿日期：2015-11-17

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1673-260X（2016）04-0014-04