韋 相,李志勇,朱永繽

(紅河學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系,云南蒙自 661100)

0 引 言

聚類分析在模式識別、圖像處理、機(jī)器學(xué)習(xí)等領(lǐng)域有著廣泛的應(yīng)用,其也是數(shù)據(jù)挖掘的重要研究領(lǐng)域之一[1].目前,用于數(shù)據(jù)挖掘的聚類算法主要有4類:以 k-means算法為代表的分割聚類法,以BIRCH為代表的分層聚類法,以DBSCAN算法為代表的密度聚類法和STING為代表的網(wǎng)格聚類法[2-5].其中, BIRCH算法能夠通過一遍掃描進(jìn)行有效聚類,特別適合大規(guī)模的數(shù)據(jù)集,但該算法采用直徑來控制聚類的邊界,如果子簇非球形,則得不到較好的聚類效果;DBSCAN算法利用類的密度連通特性,可以快速地發(fā)現(xiàn)任意形狀的簇,但它效率較低,無法進(jìn)行動(dòng)態(tài)聚類.本文在 k-means算法基礎(chǔ)上提出了基于質(zhì)心的樣本加權(quán)的分割聚類算法,實(shí)驗(yàn)表明,該算法提高了聚類的精確度.

1 算法的具體描述

1.1 算法的基本思想

本文提出的聚類算法的基本思想是基于物質(zhì)的質(zhì)心及物質(zhì)質(zhì)心的運(yùn)動(dòng)定理.與 k-means聚類算法一樣,本算法聚類的過程就是給每個(gè)樣本尋找最近的質(zhì)心(聚類中心),但與 k-means聚類算法不同,本算法中,質(zhì)心不僅有位置信息,它還有質(zhì)量,它的質(zhì)量就是歸入該聚類中心的樣本的質(zhì)量總和,當(dāng)然,每個(gè)樣本也有它自己的質(zhì)量.聚類過程是給每個(gè)樣本尋找最近的質(zhì)心,當(dāng)某個(gè)樣本將歸入某個(gè)質(zhì)心時(shí),該質(zhì)心的質(zhì)量就它原有的質(zhì)量和新歸入樣本質(zhì)量之和,同時(shí)該質(zhì)心的位置也要根據(jù)物質(zhì)質(zhì)心的運(yùn)動(dòng)定理發(fā)生改變.某個(gè)樣本原來屬于某個(gè)質(zhì)心,當(dāng)它要離開該質(zhì)心歸入新質(zhì)心時(shí),原質(zhì)心的質(zhì)量及位置也發(fā)生相應(yīng)的改變.

1.2 算法的定義

定義1 樣本的特征:數(shù)據(jù)集的 n個(gè)d維樣本(xi),i=1,2,…,n,樣本的聚類特征CF有2個(gè),CF =(mi,si),mi表示xi的質(zhì)量,它是由xi的非空間屬性決定,si表示xi的位置,由 xi的空間屬性來表示.

定義2 聚類中心的特征:給定具有 n個(gè)樣本的數(shù)據(jù)集(xi),i=1,2,…,n,子簇聚類中心的特征定義為2維CF=(M,S),M表示子簇的質(zhì)量,它是屬于這個(gè)子簇所有樣本的質(zhì)量總和;S表示子簇聚類中心的位置,它由屬于這個(gè)子簇所有樣本的質(zhì)量和位置決定.

定義3 聚類中心的運(yùn)動(dòng):給定具有 n個(gè)樣本的數(shù)據(jù)集(xi),i=1,2,…,n,一個(gè)子簇含有n1個(gè)數(shù)據(jù)點(diǎn),它的聚類中心特征是 CF=(M,S).

假定有一個(gè)新的數(shù)據(jù)點(diǎn) y歸入該子簇,那么該子簇的特征向量變化如下:

假定某個(gè)數(shù)據(jù)點(diǎn)原先屬于這個(gè)子簇,現(xiàn)在要?dú)w入別的子簇,那這個(gè)子簇特征的變化如下:

1.3 算法的實(shí)現(xiàn)

本文提出的聚類算法其實(shí)現(xiàn)的基本步驟如下:

本算法和 k-means聚類算法的不同之處在于: k-means聚類算法在掃描完所有樣本之后,才調(diào)整聚類中心,而本算法是掃描一個(gè)樣本,就調(diào)整相關(guān)的聚類中心.本算法的具體描述如下:

1.4 樣本的權(quán)重確定

1.4.1 使用非空間屬性確定.

當(dāng)對數(shù)據(jù)集中的樣本沒有任何先驗(yàn)知識時(shí),可以直接定義每個(gè)樣本的權(quán)重為1,這時(shí),本算法的聚類效果 k-mean算法相似.本文提出確定樣本權(quán)重的方法可根據(jù)一些先驗(yàn)知識,即2個(gè)樣本的相異性的計(jì)算并不一定要依賴所有的屬性,有些屬性可以用來計(jì)算相似度,而有些屬性則可從其他角度對聚類中心產(chǎn)生影響.

對給定具有 n個(gè)樣本的d維數(shù)據(jù)集,(xi),i= 1,2,…,n,(包含d1個(gè)空間屬性,可以用來計(jì)算相似度,d2個(gè)非空間屬性,可以用來計(jì)算樣本的權(quán)重),可以從相關(guān)領(lǐng)域?qū)＜夷抢铽@得每個(gè)非空間屬性的權(quán)重wi,然后再按下式計(jì)算樣本的權(quán)重,

1.4.2 使用樣本密度確定權(quán)重.

在一些數(shù)據(jù)集中,當(dāng)樣本只有空間屬性,而沒有用于計(jì)算權(quán)重的非空間屬性時(shí),則可以用別的方法計(jì)算樣本的權(quán)重.對那些處于稠密區(qū)域中的樣本(即周圍被更多樣本包圍),其必將對聚類中心產(chǎn)生更大的影響.對此,可采用點(diǎn)密碼的思想:樣本 p的Eps鄰域密度,用N(p)表示,它表示在樣本 p的Eps鄰域的樣本數(shù)目,用它作為樣本 p的權(quán)重.

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

在實(shí)驗(yàn)中,我們將本文的算法和 k-means算法的聚類結(jié)果進(jìn)行了比較.測試數(shù)據(jù)為 IRIS和Soybean-small數(shù)據(jù)(這2組測試數(shù)據(jù)都來自網(wǎng)站:http:// archive.ics.uci.edu,它們是用來進(jìn)行聚類分析的標(biāo)準(zhǔn)數(shù)據(jù)集).IRIS有150個(gè)樣本,分為3個(gè)子類,每類有50個(gè)樣本,其中2個(gè)子類具有交叉的樣本,很難對這些交叉樣本進(jìn)行準(zhǔn)確的分類.

2.1 對IRIS數(shù)據(jù)的聚類結(jié)果

采用本文提出算法對IRIS數(shù)據(jù)的聚類結(jié)果見表1.采用 k-means算法對IRIS數(shù)據(jù)的聚類結(jié)果見表2.

表1 本文算法對IRIS的聚類結(jié)果

表2 k-means算法對IRIS的聚類結(jié)果

從表1、2可見,k-means算法把第2類的3個(gè)樣本,錯(cuò)誤的歸入第3類,而把第3類14個(gè)樣本錯(cuò)誤的歸入第2類,共有17個(gè)錯(cuò)分的樣本,準(zhǔn)確度是88.7%;而本文提出的算法總共有14個(gè)錯(cuò)分的樣本,算法的準(zhǔn)確度為90.7%.顯然,本文的算法有效且具有更高的精確度.

2.2 對Soybean-small數(shù)據(jù)的聚類結(jié)果

Soybean-small數(shù)據(jù)具有47個(gè)樣本,每個(gè)樣本有35個(gè)屬性,共分為4個(gè)子類,其中一個(gè)類包含17個(gè)樣本,另外3個(gè)類各有10個(gè)樣本.因?yàn)檫@些屬性中有14個(gè)屬性值是完全相同的,所以我們只使用另外21個(gè)屬性進(jìn)行聚類分析.本文算法的聚類結(jié)果見表3,用 k-means算法的聚類結(jié)果見表4.

表3 本文算法對Soybean-small數(shù)據(jù)的聚類結(jié)果

表4 k-means算法對Soybean-small數(shù)據(jù)的聚類結(jié)果

從表3、4可見,使用k-means算法,它錯(cuò)分了15個(gè)樣本,準(zhǔn)確度是66%;而本文的算法僅錯(cuò)分了12個(gè)樣本,準(zhǔn)確度是74.5%.同樣,本文算法的聚類結(jié)果精度更優(yōu).

3 結(jié) 論

依據(jù)不同樣本對聚類中心產(chǎn)生不同影響,我們提出了基于樣本加權(quán)的聚類算法,并針對具體數(shù)據(jù)集,把樣本屬性分為空間屬性和非空間屬性,這樣可以提高聚類算法的應(yīng)用領(lǐng)域.實(shí)驗(yàn)表明,該算法比k-means聚類算法具有更高的精確度.下一步的研究方向?yàn)?一是引入模糊數(shù)學(xué),實(shí)現(xiàn)模糊聚類,提高邊界處理能力;二是把該算法應(yīng)用于圖像分割等領(lǐng)域.

[1]Han J,Kamber M,Tung A K H.Spatial Clustering Methods in Data Mining:A Survey[M].New Y ork:John Wiley,2001.

[2]Jain A K,Murty M N,Flynn1 P J.Data clustering:A review [J].ACM Computing Surveys,1999,31(3):1145-1149.

[3]Zhang T,Ramakrishnan R,Linvy M.Birch:an Efficient Data Clustering Method for very Large Databases[C]//Proceeding of ACM SIGMOD International Conference.New Y ork:ACM Press, 1996.

[4]Ester M,Kriegel H,Sander J,et al.A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise [C]//Proceeding of2nd International Conference on Knowledge Discovery and Data Mining.Portland,Oregon:ACM Press,1996.

[5]Wang W,YangJ,Myntz R.Sting:a Statistical Information Grid Approach to Spatial Data Mining[C]//Proceedings of the23International Conference on Very Large Databases Athens.New Y ork:ACM Press,1997.