基于數(shù)據(jù)場和單次劃分的聚類算法

張　霓，陳天天，何熊熊

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

?

基于數(shù)據(jù)場和單次劃分的聚類算法

張霓，陳天天，何熊熊

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

摘要：針對現(xiàn)有大部分聚類算法普遍存在聚類質(zhì)量不高、算法參數(shù)依賴性大、聚類類別個(gè)數(shù)和聚類中心無法準(zhǔn)確確定等問題，在此提出了基于數(shù)據(jù)場和單次劃分的聚類算法(DF_SPCA).該算法通過分析數(shù)據(jù)的分布特征，引入數(shù)據(jù)場理論，在分析每個(gè)數(shù)據(jù)對象的距離和勢值分布圖的基礎(chǔ)上確定聚類中心.等聚類中心確定后，其余數(shù)據(jù)點(diǎn)在比自身勢值更高的數(shù)據(jù)點(diǎn)中找到與其距離最小的數(shù)據(jù)點(diǎn)，將類標(biāo)與該數(shù)據(jù)點(diǎn)保持一致，從而實(shí)現(xiàn)單次劃分.最終算法在多個(gè)數(shù)據(jù)集上進(jìn)行性能測試，并與其他聚類算法進(jìn)行比較.實(shí)驗(yàn)結(jié)果證明：DF_SPCA具有較高的聚類質(zhì)量，能夠有效處理任意形狀的簇.

關(guān)鍵詞：數(shù)據(jù)場；數(shù)據(jù)聚類；勢值；聚類分析；勢值-距離分布

聚類的目的是根據(jù)物理對象或者抽象對象之間的相似性將數(shù)據(jù)集劃分成多個(gè)不同的類簇，使形成的同一個(gè)類簇中的對象具有較高的相似度，而不同簇中的對象相似度較低[1].聚類技術(shù)在文本分析[2]和模式識別[3]等諸多領(lǐng)域[4-7]都有廣泛的應(yīng)用前景，在現(xiàn)有的聚類算法中，基于劃分的方法是一種被廣泛使用的聚類算法，其基本思想是通過預(yù)設(shè)聚類數(shù)目，然后隨機(jī)選擇聚類中心，通過迭代不斷優(yōu)化目標(biāo)函數(shù)，直至獲得最優(yōu)目標(biāo)函數(shù)時(shí)完成聚類.代表算法有K-means[8]和FCM[9]等.這類算法的優(yōu)點(diǎn)在于簡單有效，易于操作，但由于算法需要預(yù)設(shè)聚類個(gè)數(shù)，對原始數(shù)據(jù)聚簇的分布形態(tài)有極大的影響，同時(shí)算法還存在聚類結(jié)果對初始簇類中心選擇敏感、對噪聲適應(yīng)性差、不能發(fā)現(xiàn)任意形狀的簇等缺點(diǎn).基于密度的方法主要是針對任意形狀的簇的發(fā)現(xiàn)而提出的，其基本思想是通過預(yù)設(shè)參數(shù)來發(fā)現(xiàn)數(shù)據(jù)密集區(qū)域，確定核心點(diǎn)，再利用核心點(diǎn)確定密度相連的對象實(shí)現(xiàn)聚類，獲得最終的聚類結(jié)果.代表算法有DBSCAN[10]和OPTIC[11]等等.這類算法的主要優(yōu)點(diǎn)是具有良好的可擴(kuò)展性，能夠處理任意形狀的簇，對于噪聲數(shù)據(jù)是健壯的，但是聚類結(jié)果的優(yōu)劣對參數(shù)的依賴性較強(qiáng)，通常需要經(jīng)驗(yàn)設(shè)定.

有些算法[12-17]將數(shù)據(jù)場理論與傳統(tǒng)聚類算法相結(jié)合來實(shí)現(xiàn)聚類；文獻(xiàn)[13，15]將數(shù)據(jù)場理論與劃分算法K-means,PAM等相結(jié)合，利用勢分布函數(shù)獲取初始的聚類中心，提高了聚類質(zhì)量和收斂速度，但保留了基于劃分算法需要預(yù)設(shè)聚類個(gè)數(shù)和對離群點(diǎn)敏感的缺點(diǎn)；文獻(xiàn)[18]提出了一種基于數(shù)據(jù)場的密度聚類算法DF_DBSCAN，結(jié)合勢函數(shù)分布改進(jìn)DBSCAN的聚類過程，提高了聚類準(zhǔn)確率，但同時(shí)增加了算法的復(fù)雜度，且保留了DBSCAN算法對參數(shù)敏感性強(qiáng)的缺陷.針對上述問題，在此提出了一種基于數(shù)據(jù)場和單次劃分的聚類算法(DF_SPCA).計(jì)算每個(gè)數(shù)據(jù)對象的勢值和距離值，作出勢值與距離的分布圖，根據(jù)聚類中心具有較高勢值，且被較低勢值的其他數(shù)據(jù)點(diǎn)包圍的特性確定聚類中心，無需預(yù)設(shè)聚簇的個(gè)數(shù)，同時(shí)能夠自動(dòng)聚類中心的位置.等聚類中心確定后，將其余點(diǎn)按到最近鄰的更高勢值對象的最小距離進(jìn)行劃分，該過程只需單次掃描，不需要迭代運(yùn)算.實(shí)驗(yàn)結(jié)果表明：DF_SPCA算法有較好的聚類性能，能夠?qū)崿F(xiàn)對任意形狀的簇聚類.

1數(shù)據(jù)場理論

場的概念是英國物理學(xué)家法拉第在1837年第一次提出，用于描述物質(zhì)粒子之間存在的非接觸相互作用.隨著場理論的發(fā)展，場的概念被抽象描述為一個(gè)數(shù)學(xué)概念，用來描述某個(gè)數(shù)學(xué)函數(shù)或物理量在空間中的分布規(guī)律.數(shù)據(jù)場理論[8]借鑒了物理學(xué)中場的思想，將其場的描述方法和物質(zhì)粒子間的相互作用引入到抽象的數(shù)據(jù)空間中.該理論用勢函數(shù)來描述數(shù)據(jù)對象之間多對一的相互關(guān)系，克服了傳統(tǒng)數(shù)據(jù)聚類算法中只考慮對象之間一對一作用關(guān)系的缺陷，認(rèn)為空間中任意點(diǎn)的狀態(tài)是其他所有對象共同作用的結(jié)果[18-20].

考慮到高斯分布的普適性以及短程場作用更有利于揭示數(shù)據(jù)分布的聚簇特性，將數(shù)據(jù)場勢函數(shù)[8]定義如下：

定義1已知數(shù)據(jù)空間Ω?Rd上的對象集合D={x1,x2,…,xi,…,xn}及其產(chǎn)生的數(shù)據(jù)場，則任意對象x∈D的勢函數(shù)描述為

(1)

為了分析單數(shù)據(jù)對象產(chǎn)生的數(shù)據(jù)場中場強(qiáng)與距離的分布關(guān)系，假設(shè)mi=1，可得到具體關(guān)系如圖1所示.

圖1　單數(shù)據(jù)對象數(shù)據(jù)場中場強(qiáng)與距離的分布關(guān)系Fig.1　The distribution of field intensity and distance in the data field of a single data object

當(dāng)距離數(shù)據(jù)對象0.705σ時(shí)，場強(qiáng)達(dá)到了最大值，即以場源對象為中心，半徑為0.705σ的球面上存在很強(qiáng)的作用力指向場源對象.而當(dāng)距場源對象的距離大于R≈2.121σ時(shí)，場強(qiáng)函數(shù)很快衰減為0，指示著短程場作用.因此，數(shù)據(jù)空間內(nèi)的任意對象主要受其R≈2.121σ鄰域空間內(nèi)的數(shù)據(jù)點(diǎn)影響作用，為了減小計(jì)算復(fù)雜度，將數(shù)據(jù)場勢函數(shù)定義進(jìn)行修改.

定義2已知數(shù)據(jù)空間Ω?Rd上的對象集合D={x1,x2,…,xi,…,xn}及其產(chǎn)生的數(shù)據(jù)場，則任意對象x∈D的勢函數(shù)描述為

(2)

式中p為數(shù)據(jù)空間內(nèi)對象x以半徑為R≈2.121σ所形成的鄰域空間內(nèi)數(shù)據(jù)對象的數(shù)目.

數(shù)據(jù)場理論具有較好的刻畫數(shù)據(jù)和反映數(shù)據(jù)間多對一作用關(guān)系的能力，能夠?qū)垲愃惴ǐ@得數(shù)據(jù)原始聚簇分布有較好的指導(dǎo)作用.

2基于數(shù)據(jù)場和單次劃分的聚類算法

2.1　主要思想

通過結(jié)合數(shù)據(jù)場理論對數(shù)據(jù)集中的數(shù)據(jù)對象分析，根據(jù)定義2計(jì)算每個(gè)數(shù)據(jù)對象的勢值，勢值越大的數(shù)據(jù)對象，說明其R≈2.121σ半徑內(nèi)的數(shù)據(jù)對象越多，且距離該數(shù)據(jù)對象的距離越近，因此該點(diǎn)很大程度上是該簇類集合的中心.而勢值很小的數(shù)據(jù)對象，說明其R≈2.121σ半徑內(nèi)的數(shù)據(jù)對象較少，說明該點(diǎn)很可能是游離在外的離群點(diǎn)對象.如圖2所示，x和y代表數(shù)據(jù)對象在二維空間的坐標(biāo)，而z代表其在空間內(nèi)的勢值強(qiáng)度，可以發(fā)現(xiàn)該數(shù)據(jù)存在4個(gè)簇類，且每個(gè)簇類的中心位置的勢值強(qiáng)度最大，越邊緣的數(shù)據(jù)對象的勢值強(qiáng)度越小.另外，簇中心與簇中心的距離較大，而簇內(nèi)的數(shù)據(jù)對象到簇中心的距離較小.

圖2　數(shù)據(jù)場示意圖Fig.2　Sketch map of data field

DF_SPCA算法主要基于以下兩點(diǎn)規(guī)律:

1) 簇類中心被具有較低勢值的鄰居點(diǎn)包圍，且與具有更高勢值的其它數(shù)據(jù)對象有相對較大的距離.

2) 噪聲點(diǎn)具有相對較小的勢值，且與勢值較高的數(shù)據(jù)對象有相對較大的距離.

對于任意一個(gè)數(shù)據(jù)對象xi，需要計(jì)算兩個(gè)量：數(shù)據(jù)對象的勢值φ(xi)和到具有更高勢值的其它點(diǎn)的最小距離δi.數(shù)據(jù)對象的勢值φ(xi)可以根據(jù)定義2計(jì)算得到.

定義3對于任意數(shù)據(jù)對象xi，其到具有更高勢值的其他數(shù)據(jù)對象xj的最小距離δi定義為

(3)

式中dij為兩個(gè)數(shù)據(jù)對象xi和xj之間的距離.

對于具有最高勢值的數(shù)據(jù)點(diǎn)xi，定義δi為該數(shù)據(jù)點(diǎn)到數(shù)據(jù)對象xj的距離的最大值，即δi=maxj(dij).

存在人造樣本數(shù)據(jù)集DataSet1，其數(shù)據(jù)對象由二維數(shù)值屬性x和y描述，其數(shù)值僅表示數(shù)據(jù)對象在二維空間中的位置分布，DataSet1數(shù)據(jù)集在二維空間內(nèi)的數(shù)據(jù)分布如圖3所示.

圖3　樣本DataSet1數(shù)據(jù)分布圖Fig.3　Data distribution map of sample DataSet1

計(jì)算樣本數(shù)據(jù)集中每個(gè)數(shù)據(jù)對象xi的勢值φ(xi)和到具有更高勢值的其他點(diǎn)的最小距離δi，作出φ(xi)和δi的分布圖如圖4所示.

圖4　數(shù)據(jù)對象勢值和距離分布圖Fig.4　Potential value and distance distribution map of data objects

圖3中B1，B2，B3是原始數(shù)據(jù)分布中的3個(gè)簇的簇類中心，其在圖4中具有較大的勢值φ(xi)和較大的距離δi；A1，A2，A3是遠(yuǎn)離簇的數(shù)據(jù)點(diǎn)，即離群點(diǎn)，其在圖4中具有較小的勢值φ(xi)和較大的距離δi；而其余點(diǎn)均屬于某個(gè)簇類，具有較小距離δi的性質(zhì).

通過分析圖4可以確定數(shù)據(jù)集的簇類中心，等簇類中心確定后，將其余點(diǎn)按到最近鄰的更高勢值對象的最小距離進(jìn)行劃分，使得當(dāng)前對象的類別標(biāo)簽與高于當(dāng)前對象勢值的最近鄰對象的標(biāo)簽一致，從而對所有對象的類別進(jìn)行標(biāo)定.該過程與傳統(tǒng)劃分算法不同，只需一步完成，不需要迭代計(jì)算.

對于噪聲點(diǎn)，算法無需用人為設(shè)定噪聲點(diǎn)閾值截?cái)嗟姆椒ㄈコ肼朁c(diǎn)，而是先算出類別之間的邊界，然后找出邊界中勢值最高的點(diǎn)的勢值作為閾值，將此勢值閾值記為φb，只保留此類別中大于或等于此勢值的點(diǎn).

算法在參數(shù)設(shè)定上只需要輸入影響因子σ的值，其作用在于控制對象間的相互作用力程，因此σ值的選擇也變得至關(guān)重要.淦文燕等[12,20]通過求解最小勢熵的方法確定最優(yōu)影響因子取值，由于勢熵越大，則表明此時(shí)產(chǎn)生的數(shù)據(jù)場越不穩(wěn)定；勢熵越小，則說明此時(shí)產(chǎn)生的數(shù)據(jù)場越穩(wěn)定.因此，淦文燕等將影響因子的優(yōu)化問題轉(zhuǎn)化求解最小勢熵的問題.DF_SPCA算法借鑒影響因子優(yōu)化算法來確定影響因子σ的值，進(jìn)而對σ值進(jìn)行整定，使得算法對于不同的數(shù)據(jù)集，能夠根據(jù)勢熵最小化原則確定相應(yīng)的σ值.

2.2　算法描述

輸入：數(shù)據(jù)集D={x1,x2,…,xi,…,xn}，影響因子σ的值.

輸出：聚類結(jié)果.

步驟1根據(jù)式(2，3)計(jì)算每個(gè)數(shù)據(jù)對象xi的勢值φ(xi)和相應(yīng)最小距離δi.

步驟2根據(jù)每個(gè)數(shù)據(jù)對象xi的勢值φ(xi)和相應(yīng)最小距離δi作出勢值和距離分布圖，分析勢值和距離分布圖確定聚類中心.

步驟3等聚類中心確定后，將所有數(shù)據(jù)對象按勢值從大到小排序.

步驟4將排序后的數(shù)據(jù)對象序列，按次序?qū)⑦@些點(diǎn)按到最近鄰的更高勢值對象的最小距離進(jìn)行劃分.

步驟5聚類完成，輸出聚類結(jié)果.

3實(shí)驗(yàn)與性能分析

實(shí)驗(yàn)操作系統(tǒng)為Windows 7，開發(fā)平臺(tái)為Microsoft Visual C++ 2010.硬件條件：CPU為Intel Core I5 2.6 GHz，內(nèi)存為4 GB.為了驗(yàn)證新算法DF_SPCA的性能，算法對5個(gè)數(shù)據(jù)集進(jìn)行測試.Aggregation，Spiral，F(xiàn)lam這3個(gè)數(shù)據(jù)集來自于東芬蘭大學(xué)(http://cs.joensuu.fi/sipu/datasets/),而其他2個(gè)數(shù)據(jù)集來自UCI數(shù)據(jù)庫，具體信息如表1所示.

表1　5個(gè)真實(shí)數(shù)據(jù)集信息

3.1　聚類結(jié)果評價(jià)

DF_SPCA采用由Huang和Ng[21]提出的聚類準(zhǔn)確率作為評價(jià)標(biāo)準(zhǔn)：聚類準(zhǔn)確率r的定義為

(4)

式中：ai為最終被正確分類的樣本數(shù)目；k為聚類數(shù)；n為數(shù)據(jù)集中的樣本個(gè)數(shù).聚類準(zhǔn)確率越高，說明算法的聚類質(zhì)量越高.當(dāng)聚類準(zhǔn)確率為1時(shí)，說明算法該數(shù)據(jù)集上獲得的聚類結(jié)果是完全正確的.

3.2　實(shí)驗(yàn)結(jié)果分析

數(shù)據(jù)集Aggregation、數(shù)據(jù)集Spiral、數(shù)據(jù)集Flame均為二維數(shù)據(jù)，其中包含各種形狀的簇.算法對這3個(gè)數(shù)據(jù)集進(jìn)行測試，其得到的勢值與距離分布圖和相應(yīng)聚類結(jié)果展示如圖5，6所示.

圖5　3個(gè)數(shù)據(jù)集的勢值和距離分布圖Fig.5　Potential value and distance distribution map of the three data sets

圖6　3個(gè)數(shù)據(jù)集的聚類結(jié)果分布圖Fig.6　Clustering result distribution map of the three data sets

對于數(shù)據(jù)集Aggregation、數(shù)據(jù)集Spiral、數(shù)據(jù)集Flame，算法均能夠得到聚類準(zhǔn)確率100%的聚類結(jié)果.實(shí)驗(yàn)結(jié)果表明：算法對任意形狀和變密度的簇進(jìn)行聚類，均能獲得較高的聚類質(zhì)量.

算法對UCI數(shù)據(jù)庫數(shù)據(jù)進(jìn)行測試，首先對Iris數(shù)據(jù)進(jìn)行實(shí)驗(yàn).Iris數(shù)據(jù)集包含150個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)對象由4個(gè)屬性值描述，數(shù)據(jù)集分為3個(gè)類：Iris-Setosa，Iris-Versicolour和Iris-Virginica.并在此說明，所有的數(shù)據(jù)集中，類屬性只用來評估算法的聚類結(jié)果，不參與聚類過程.圖7給出了算法在Iris數(shù)據(jù)上得到的勢值與距離分布圖，其對應(yīng)的σ為0.213.

圖7　Iris數(shù)據(jù)的勢值與距離分布圖Fig.7　Potential value and distance distribution map of Iris data set

DF_SPCA算法、K-means算法、DBSCAN算法、DF_DBSCAN算法[18]在Iris數(shù)據(jù)集上的聚類準(zhǔn)確率r如表2所示.

表2　4種算法在Iris數(shù)據(jù)集上的聚類準(zhǔn)確率r

表2中的聚類結(jié)果表明：DF_SPCA算法的聚類準(zhǔn)確率比K-means和DBSCAN分別高出了11.5%和26.67%，與DF_DBSCAN算法相當(dāng)，因此DF_SPCA算法和DF_DBSCAN算法在Iris數(shù)據(jù)集上均能夠獲得較好的聚類質(zhì)量.

Breast-Cancer(乳腺癌)數(shù)據(jù)集最早由Wisconsin州立醫(yī)院大學(xué)提供，含有699個(gè)數(shù)據(jù)對象，分為2個(gè)類：惡性腫瘤(Malignant)和良性腫瘤(Benign).每個(gè)數(shù)據(jù)對象由9個(gè)數(shù)值屬性描述.圖8給出了DF_SPCA算法在Breast數(shù)據(jù)上得到的勢值與距離分布圖，其對應(yīng)的σ為6.824.

圖8　Breast數(shù)據(jù)的勢值與距離分布圖Fig.8　Potential value and distance distribution map of Breast data set

DF_SPCA算法、K-means算法、DBSCAN算法、DF_DBSCAN算法在Breast數(shù)據(jù)集上的聚類準(zhǔn)確率r如表3所示.

表34種算法在Breast數(shù)據(jù)集上的聚類準(zhǔn)確率r

Table 3Clustering accuracy of four algorithms on Breast data set

算法K-meansDBSCANDF_DBSCANDF_SPCAr0.92800.65520.91560.9380

表3中的聚類結(jié)果表明：DF_SPCA算法的聚類準(zhǔn)確率比K-means、DBSCAN和DF_DBSCAN分別高出了1%，28.28%和2.24%.因此DF_SPCA算法的性能更好.

算法在不同數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明：DF_SPCA算法與其他算法相比，能夠取得更好的聚類準(zhǔn)確率，因此算法的性能更好.

3.3　算法復(fù)雜度分析

假設(shè)聚類對象數(shù)據(jù)集規(guī)模是n個(gè)數(shù)據(jù)(樣本)，則DF_SPCA算法的時(shí)間復(fù)雜性主要由計(jì)算每個(gè)數(shù)據(jù)對象的勢值與距離構(gòu)成的，該過程的計(jì)算復(fù)雜度分別為O(n2)，等聚類中心確定后，算法只需經(jīng)過一次劃分就能完成聚類，其計(jì)算復(fù)雜度為O(n-k)，其中k為確定的聚類中心數(shù)目.

一般基于劃分的聚類算法，如k-means算法，其時(shí)間復(fù)雜度是O(tkn)，通?；趯哟魏突诿芏染垲愃惴?，如DBSCAN算法，其時(shí)間復(fù)雜度為O(n2)，其中t為迭代次數(shù)，k為聚類個(gè)數(shù)，n為數(shù)據(jù)對象個(gè)數(shù).DF_DBSCAN算法的時(shí)間復(fù)雜度與DBSCAN算法相似.從以上理論分析可知：相比于基于劃分聚類算法，DF_SPCA算法復(fù)雜度要高，但與基于層次和基于密度的聚類算法相當(dāng)，主要消耗在計(jì)算每個(gè)數(shù)據(jù)對象的勢值和距離的過程中，但是其優(yōu)勢在于無需確定聚類個(gè)數(shù)，并能自動(dòng)確定聚類中心和對于任意形態(tài)分布的數(shù)據(jù)集均能得到較滿意的聚類結(jié)果，因此可以在一定程度上彌補(bǔ)其時(shí)間復(fù)雜度較高的缺陷.

4結(jié)論

筆者提出了一種基于數(shù)據(jù)場和單次劃分的聚類算法(DF_SPCA)，引入數(shù)據(jù)場理論，使其具有反映數(shù)據(jù)間多對一作用關(guān)系的優(yōu)勢，進(jìn)一步計(jì)算每個(gè)數(shù)據(jù)對象的勢值和相應(yīng)的距離.通過分析每個(gè)數(shù)據(jù)對象的勢值和距離分布確定簇類中心，得到的聚類結(jié)果更加符合數(shù)據(jù)的原始分布，使能獲得較好的聚類質(zhì)量，實(shí)驗(yàn)驗(yàn)證了本算法的可行性和有效性.DF_SPCA算法的惟一參數(shù)σ值采用勢熵最優(yōu)算法選取，使得算法具有一定的自適應(yīng)性，同時(shí)算法不需要預(yù)先設(shè)定聚類個(gè)數(shù)，能夠自動(dòng)確定聚類中心，并且能夠處理任意形狀的簇和離群點(diǎn).下一步的研究重點(diǎn)是使用DF_SPCA算法對混合屬性數(shù)據(jù)實(shí)現(xiàn)高質(zhì)量的聚類，進(jìn)一步探討如何對混合屬性數(shù)據(jù)進(jìn)行高效聚類.

參考文獻(xiàn)：

[1]HAN J, KAMBER M. Data mining concepts and techniques[M]. San Francisco: Morgan Kaufmann,2001.

[2]ZHANG W, YOSHIDA T, TANG X J, et al. Text clustering using frequent item sets[J]. Knowledge-based systems,2011,23(5):379-388.

[3]HAN J, KAMBER M, PEI J. Data mining concepts and techniques[M]. 3th ed. San Francisco: Elsevier,2011.

[4]IAMON N, BOONGOEN T, GARRETT S, et al. A link-based cluster ensemble approach for categorical data clustering[J]. IEEE knowledge and data engineering,2012,24(3):413-425.

[5]龍勝春，傅佳琪，堯麗君.改進(jìn)型K-Means算法在腸癌病理圖像分割中的應(yīng)用[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2014,42(5):581-585.

[6]高雪，謝儀，候紅衛(wèi).基于多指標(biāo)面板數(shù)據(jù)的改進(jìn)的聚類方法及應(yīng)用[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2014,42(4):468-472.

[7]肖剛，吳利群，張?jiān)Q，等.一種基于協(xié)作頻度聚類的Web服務(wù)信任評估方法[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2014,42(4):393-399.

[8]淦文燕,李德毅.基于核密度估計(jì)的層次聚類算法[J].系統(tǒng)仿真學(xué)報(bào),2004,16(2):302-306.

[9]余建橋,張帆.基于數(shù)據(jù)場改進(jìn)的PAM聚類算法[J].計(jì)算機(jī)科學(xué),2005,32(1):165-168.

[10]王海軍,鄧羽,王麗,等.基于數(shù)據(jù)場的C均值聚類方法研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2009,34(5):626-629.

[11]李學(xué),苗奪謙,馮琴榮.基于數(shù)據(jù)場的粗糙聚類算法[J].計(jì)算機(jī)科學(xué),2009,36(2):203-206.

[12]李春芳,劉連忠,陸震.基于數(shù)據(jù)場的概率神經(jīng)網(wǎng)絡(luò)算法[J].電子學(xué)報(bào),2011,39(8):1739-1745.

[13]JI Z X, SUN Q S, XIA D S. A modified possibilistic fuzzy c-means clustering algorithm for bias field estimation and segmentation of brain MR image[J]. Computerized medical imaging and graphics,2011,35(5):383-397.

[14]BERGET I, MEVIK H B, NAES T. New modifications and applications of fuzzy C-means methodology[J]. Computational statistics & data analysis,2008,52(5):2403-2418.

[15]ESTER M, KRIEGEL P H, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]// Proceedings of the National Conferences on Aritificial Intelligence. Stockholm: Stockholm University,1998:226-231.

[16]DAVE R N, BHASWAN K. Adaptive fuzzy c-shells clustering and detection of ellipses[J]. IEEE transactions on neural network,1992,3(5):643-662.

[17]ANKERST M, BREUNIG M, KRIEGEL H P, et al. OPTICS: ordering points to identify the clustering structure[J]. ACM sigmod record,1999,28(2):49-60.

[18]楊靜,高嘉偉,梁吉業(yè),等.基于數(shù)據(jù)場的改進(jìn)DBSCAN聚類[J].計(jì)算機(jī)科學(xué)與探索,2012,6(10):903-911.

[19]李德毅,杜鹢.不確定性人工智能[M].北京:國防工業(yè)出版社,2005.

[20]淦文燕,李德毅,王建民.一種基于數(shù)據(jù)場的層次聚類方法[J].電子學(xué)報(bào),2006,34(2):258-262.

[21]HUANG Z. Clustering large data sets with mixed numeric and categorical values[C]// In the first Pacific-Asia Conference on Knowledge Discovery and Data Mining. Singapore: World Scientific Publishing,1997:21-34.

(責(zé)任編輯：劉巖)

A single partition clustering algorithm based on data field

ZHANG Ni, CHEN Tiantian, HE Xiongxiong

(College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:Most existed clustering algorithms have problems such as low clustering quality, parameter sensitivity, and difficulty in determining cluster centers and number of clusters. In this paper, a single partition clustering algorithm based on data field (DF_SPCA) is proposed to solve the problems. Firstly, through analyzing the distribution of the data, the data field theory is introduced. Base on analysis of each data object distance and force distribution, the cluster center is determined Then the rest data point will find out the nearestt point from the data points with higher potential value and keep in same cluster with it. Finally, the proposed method is tested on a series of data sets and the results show that DF_SPCA algorithm has a better clustering quality and can deal with clusters of arbitrary shape.

Keywords:data field; data clustering; potential value; cluster analysis; potential value and distance distribution

中圖分類號：TP39

文獻(xiàn)標(biāo)志碼：A

文章編號：1006-4303(2016)01-0052-06

作者簡介：張霓(1970—)，女，浙江杭州人，副教授，碩士生導(dǎo)師，研究方向?yàn)獒t(yī)療信息系統(tǒng)和移動(dòng)機(jī)器人，E-mail:zn@zjut.edu.cn

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61473262)

收稿日期：2015-06-19