基于特征加權(quán)理論的數(shù)據(jù)聚類算法*

費(fèi)賢舉，李 虹，田國(guó)忠

(1.常州工學(xué)院 計(jì)算機(jī)信息工程學(xué)院，江蘇 常州 213032；2.吉林省質(zhì)檢檢測(cè)基地 吉林省纖維檢驗(yàn)處，長(zhǎng)春 130103)

基于特征加權(quán)理論的數(shù)據(jù)聚類算法*

費(fèi)賢舉1，李 虹2，田國(guó)忠1

(1.常州工學(xué)院 計(jì)算機(jī)信息工程學(xué)院，江蘇 常州 213032；2.吉林省質(zhì)檢檢測(cè)基地 吉林省纖維檢驗(yàn)處，長(zhǎng)春 130103)

針對(duì)數(shù)據(jù)挖掘過(guò)程中數(shù)據(jù)聚類操作的初始聚類數(shù)目和初始聚類中心確定困難的問(wèn)題，提出了一種軟子空間結(jié)合競(jìng)爭(zhēng)合并機(jī)制的模糊加權(quán)聚類算法.通過(guò)對(duì)軟子空間聚類算法的目標(biāo)函數(shù)進(jìn)行改寫，并結(jié)合數(shù)據(jù)簇勢(shì)的大小對(duì)各數(shù)據(jù)簇進(jìn)行競(jìng)爭(zhēng)與合并操作，實(shí)現(xiàn)了對(duì)數(shù)據(jù)的聚類處理.結(jié)果表明，該算法能夠準(zhǔn)確地對(duì)數(shù)據(jù)樣本進(jìn)行聚類，并且聚類結(jié)果與初始數(shù)據(jù)簇?cái)?shù)目和初始聚類中心無(wú)關(guān)，能夠滿足對(duì)高維數(shù)據(jù)聚類處理的需要，具有較好的實(shí)際應(yīng)用價(jià)值.

數(shù)據(jù)挖掘；數(shù)據(jù)聚類；特征加權(quán)；軟子空間聚類；競(jìng)爭(zhēng)合并機(jī)制；模糊聚類算法；聚類中心；聚類數(shù)目

信息時(shí)代中人們時(shí)刻都面臨著各種類型的數(shù)據(jù)，這些數(shù)據(jù)對(duì)生產(chǎn)生活具有重要影響.隨著技術(shù)的發(fā)展，數(shù)據(jù)信息成指數(shù)級(jí)快速增長(zhǎng).如何利用這些數(shù)據(jù)，如何在數(shù)據(jù)中發(fā)現(xiàn)所需信息成為當(dāng)前的研究熱點(diǎn).數(shù)據(jù)挖掘技術(shù)[1-6]作為海量數(shù)據(jù)處理的有效手段，越來(lái)越受到人們的重視.數(shù)據(jù)挖掘通過(guò)分析并處理特定類型的數(shù)據(jù)，發(fā)現(xiàn)其中包含的潛在規(guī)律，輔助人們做出正確的決策.數(shù)據(jù)挖掘分為數(shù)據(jù)準(zhǔn)備、信息挖掘和結(jié)果解釋三個(gè)步驟.信息挖掘通過(guò)處理數(shù)據(jù)來(lái)發(fā)現(xiàn)其內(nèi)部包含的規(guī)律信息或潛在價(jià)值，是數(shù)據(jù)挖掘的重點(diǎn).信息挖掘的方法包括監(jiān)督學(xué)習(xí)、關(guān)聯(lián)分析、聚類分析和特征選擇及提取[7-12]等.聚類分析是指利用特定技術(shù)手段發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在規(guī)律，并按照規(guī)律將數(shù)據(jù)進(jìn)行科學(xué)分類.聚類分析是數(shù)據(jù)挖掘的重要方法和關(guān)鍵過(guò)程，直接影響數(shù)據(jù)挖掘的最終結(jié)果，是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的重點(diǎn)研究?jī)?nèi)容之一.

軟子空間聚類算法是聚類分析算法的重要組成部分.軟子空間聚類算法通過(guò)給數(shù)據(jù)的不同特征賦予加權(quán)系數(shù)來(lái)區(qū)分特征之間的重要性，實(shí)現(xiàn)對(duì)聚類結(jié)果的靈活控制.影響軟子空間聚類算法效果的關(guān)鍵因素包括數(shù)據(jù)簇?cái)?shù)目和初始聚類中心兩個(gè)方面.優(yōu)秀的聚類算法要能夠收斂到合理的聚類數(shù)目并且聚類中心的初始選擇對(duì)聚類結(jié)果影響較小.目前流行的聚類方法包括數(shù)據(jù)簇評(píng)估準(zhǔn)則法、聚類可視化法和模糊聚類法等.這些方法雖然能夠得到合理的聚類數(shù)目，但是對(duì)數(shù)據(jù)各方面特征的考慮還不全面.本文在軟子空間聚類算法的基礎(chǔ)上引入競(jìng)爭(zhēng)合并機(jī)制，提出了一種軟子空間結(jié)合競(jìng)爭(zhēng)合并機(jī)制的模糊加權(quán)聚類算法，結(jié)合了軟子空間算法和競(jìng)爭(zhēng)合并機(jī)制的優(yōu)點(diǎn)，實(shí)現(xiàn)了可靠聚類到合理數(shù)目和初始化聚類中心不影響聚類結(jié)果的目標(biāo).

1 算法模型

軟子空間聚類算法也稱為特征加權(quán)聚類算法，是指在數(shù)據(jù)的處理過(guò)程中為每個(gè)數(shù)據(jù)簇的特征賦予加權(quán)系數(shù)來(lái)標(biāo)記特征的重要性.基于競(jìng)爭(zhēng)合并機(jī)制的模糊聚類算法利用正則化項(xiàng)來(lái)使各個(gè)聚類中心競(jìng)爭(zhēng)合并，最后得到滿足要求的聚類數(shù)目.將軟子空間聚類算法與競(jìng)爭(zhēng)合并的模糊聚類算法相結(jié)合，可以得到軟子空間結(jié)合競(jìng)爭(zhēng)合并機(jī)制的模糊加權(quán)聚類算法的目標(biāo)函數(shù)，即

(1)

式(1)中前半部分用于計(jì)算各數(shù)據(jù)點(diǎn)到聚類中心的模糊加權(quán)距離和，后半部分計(jì)算各數(shù)據(jù)簇的勢(shì)平方和.當(dāng)聚類中心數(shù)為n時(shí)，前半部分最?。划?dāng)聚類中心數(shù)為1時(shí)，后半部分最小.合理選擇α并使J最小可得到滿足條件的數(shù)據(jù)簇?cái)?shù)和聚類中心位置.利用拉格朗日乘子法原理并采用迭代求解的方法求滿足J最小時(shí)的vik.根據(jù)要求設(shè)置初始聚類中心數(shù)目c、聚類中心vik、模糊加權(quán)指數(shù)m和模糊隸屬度uij，迭代過(guò)程如下所示.

1) 計(jì)算聚類中心vik、特征加權(quán)系數(shù)wik和第i個(gè)數(shù)據(jù)簇的勢(shì)Ni，其計(jì)算公式分別為

(2)

(3)

(4)

2) 計(jì)算正則項(xiàng)系數(shù)α.正則項(xiàng)系數(shù)用于調(diào)節(jié)目標(biāo)函數(shù)中前后兩部分的比重，需要根據(jù)聚類中心和加權(quán)系數(shù)等參數(shù)動(dòng)態(tài)計(jì)算，其計(jì)算公式為

(5)

式中：t為迭代次數(shù)；τ(t)為每次迭代中的學(xué)習(xí)因子，其計(jì)算公式為

τ(t)=τ0exp(-|t-t0|/ζ)

(6)

其中：τ0為學(xué)習(xí)因子初始值；t0和ζ為根據(jù)實(shí)際情況選擇的常量.

3) 計(jì)算模糊隸屬度uij，其計(jì)算公式為

(7)

(8)

(9)

(10)

4) 計(jì)算數(shù)據(jù)簇勢(shì)的閾值MT和各個(gè)聚類中心之間的距離D，并求出距離D的最小值Dmin.當(dāng)某個(gè)數(shù)據(jù)簇的勢(shì)Ni小于閾值MT時(shí)，就消去該數(shù)據(jù)簇.當(dāng)Dmin滿足式(12)時(shí)，合并距離為Dmin的兩個(gè)數(shù)據(jù)簇.MT公式和判別條件分別為

(11)

(12)

式中：η為合并閾值參數(shù)；c(t)為t次迭代時(shí)的聚類中心數(shù)；d(r)為兩個(gè)聚類中心之間的距離數(shù)值；R為各個(gè)聚類中心之間的距離數(shù)據(jù)總數(shù)，其表達(dá)式為

(13)

5) 根據(jù)削減和合并結(jié)果調(diào)整聚類中心數(shù)目c，當(dāng)聚類中心數(shù)目保持穩(wěn)定或滿足迭代結(jié)束條件時(shí)停止計(jì)算，所得的vik即為所需的聚類中心結(jié)果，否則返回步驟1)繼續(xù)執(zhí)行.

2 試驗(yàn)及結(jié)果分析

假設(shè)初始聚類中心數(shù)為15，學(xué)習(xí)因子初始值τ0為0.7，時(shí)間常量t0和ζ分別為10和15，合并閾值參數(shù)η為0.75，模糊加權(quán)指數(shù)m為3.數(shù)據(jù)點(diǎn)、真實(shí)聚類中心和初始聚類中心如圖1所示.

圖1 數(shù)據(jù)點(diǎn)及聚類中心分布Fig.1 Data points and distribution of clustering center

2.1 聚類準(zhǔn)確性分析

迭代運(yùn)算多次后，聚類結(jié)果如圖2所示.其中，圖2a表示2次迭代后，15個(gè)初始聚類中心還剩下10個(gè)；圖2b表示5次迭代后，聚類中心還剩下6個(gè)；圖2c表示9次迭代后，聚類中心還剩下5個(gè)；圖2d表示12次迭代后，聚類中心還剩下3個(gè)，在之后的迭代運(yùn)算中聚類中心數(shù)目不再改變.由圖2可知，在迭代過(guò)程中，聚類中心的數(shù)目不斷減少，并且各個(gè)聚類中心的位置也在不斷變化.最后剩下的3個(gè)聚類中心的坐標(biāo)已經(jīng)非常接近各自的真實(shí)聚類中心，因此，該算法有比較好的聚類效果和聚類準(zhǔn)確性.

圖2 聚類結(jié)果Fig.2 Clustering results

分別設(shè)置5組不同的真實(shí)聚類中心進(jìn)行試驗(yàn).每組數(shù)據(jù)的產(chǎn)生方法與前述試驗(yàn)相同，即指定相應(yīng)的聚類中心，根據(jù)不同的協(xié)方差矩陣產(chǎn)生隨機(jī)的數(shù)據(jù)樣本.采用互信息指標(biāo)作為評(píng)價(jià)聚類準(zhǔn)確性的指標(biāo).互信息指標(biāo)通過(guò)計(jì)算聚類結(jié)果與實(shí)際分類進(jìn)行匹配后的平均互信息大小來(lái)標(biāo)記正確分類的準(zhǔn)確度，其計(jì)算公式為

(14)

式中：npq為真實(shí)類為p而被分為聚類結(jié)果q的數(shù)據(jù)個(gè)數(shù)；np為聚類結(jié)果為p的數(shù)據(jù)個(gè)數(shù)；nq為真實(shí)類為q的數(shù)據(jù)個(gè)數(shù)；N為總的數(shù)據(jù)個(gè)數(shù).不同真實(shí)聚類中心NMI如表1所示.

表1 聚類處理互信息指標(biāo)數(shù)據(jù)表Tab.1 Mutual information index data table in cluster operation

由表1可知，聚類算法對(duì)數(shù)據(jù)聚類的準(zhǔn)確度較高，且聚類結(jié)果不受真實(shí)聚類中心影響，因此，該算法能夠在各種情況下實(shí)現(xiàn)對(duì)數(shù)據(jù)樣本的可靠聚類.

2.2 初始聚類中心數(shù)目敏感性分析

分別選擇不同的初始聚類中心數(shù)進(jìn)行運(yùn)算，迭代過(guò)程中聚類中心數(shù)的變化情況如圖3所示.由圖3可知，雖然選擇的初始聚類中心數(shù)不同，迭代過(guò)程中聚類中心數(shù)目在不斷下降.經(jīng)過(guò)若干次迭代后，聚類中心數(shù)目都穩(wěn)定于3.因此，聚類算法對(duì)初始聚類中心數(shù)目變化不敏感，能夠可靠地收斂到合理的聚類中心數(shù).

圖3 運(yùn)算過(guò)程中聚類中心數(shù)Fig.3 Number of clustering center in operation process

2.3 初始聚類中心位置敏感性分析

隨機(jī)選擇15個(gè)初始聚類中心位置進(jìn)行6次聚類處理，每次迭代過(guò)程中聚類中心數(shù)的減少情況如圖4所示.由圖4可知，在初始聚類中心不同時(shí)，經(jīng)過(guò)若干次運(yùn)算后聚類中心數(shù)目都穩(wěn)定于3.因此，聚類算法對(duì)初始聚類中心位置的選擇不敏感，任意選擇初始聚類中心位置都能夠保證可靠地收斂于真實(shí)聚類中心.

圖4 聚類處理過(guò)程中聚類中心數(shù)Fig.4 Number of clustering center in operation process

3 結(jié) 論

本文結(jié)合軟子空間聚類算法和基于競(jìng)爭(zhēng)合并機(jī)制的模糊聚類算法，提出了一種軟子空間結(jié)合競(jìng)爭(zhēng)合并機(jī)制的模糊加權(quán)聚類算法.該算法通過(guò)對(duì)軟子空間聚類算法的目標(biāo)函數(shù)進(jìn)行修改，使其具備了軟子空間聚類算法和競(jìng)爭(zhēng)合并機(jī)制模糊聚類算法的優(yōu)點(diǎn).求解過(guò)程通過(guò)迭代的方式運(yùn)行，能夠根據(jù)實(shí)際需要控制運(yùn)算的速度和精度.結(jié)果表明，該算法能夠以較高的準(zhǔn)確度實(shí)現(xiàn)對(duì)數(shù)據(jù)樣本的聚類分析，運(yùn)算結(jié)果與初始數(shù)據(jù)簇的個(gè)數(shù)和初始聚類中心的位置無(wú)關(guān)，具有比較廣泛的適用性.

[1] 任艷.微信息大數(shù)據(jù)粗糙集的近似約簡(jiǎn) [J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2016，38(3)：309-313.

(REN Yan.Approximate reduction of micro-message big data rough set [J].Journal of Shenyang University of Technology，2016，38(3)：309-313.)

[2] 劉城霞.基于MS關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘模型的應(yīng)用與探討 [J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，23(1)：25-28.

(LIU Cheng-xia.Application and discussion of data mining model based on microsoft association rules algorithm [J].Computer Technology and Development，2013，23(1)：25-28.)

[3] 張宇獻(xiàn)，劉通，董曉，等.基于改進(jìn)劃分系統(tǒng)的模糊聚類有效性函數(shù) [J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2014，36(4)：431-435.

(ZHANG Yu-xian，LIU Tong，DONG Xiao，et al.Validity function for fuzzy clustering based on improved partition coeffcient [J].Journal of Shenyang University of Technology，2014，36(4)：431-435.)

[4] 陳晉音，何輝豪.基于密度的聚類中心自動(dòng)確定的混合屬性數(shù)據(jù)聚類算法研究 [J].自動(dòng)化學(xué)報(bào)，2015，41(10)：1798-1813.

(CHEN Jin-yin，HE Hui-hao.Research on density-based clustering algorithm for mixed data with determine cluster centers automatically [J].Acta Automa-tica Sinica，2015，41(10)：1798-1813.)

[5] 高志春，陳冠瑋，胡光波，等.傾斜因子K均值優(yōu)化數(shù)據(jù)聚類及故障診斷研究 [J].計(jì)算機(jī)與數(shù)字工程，2014，42(1)：14-18.

(GAO Zhi-chun，CHEN Guan-wei，HU Guang-bo，et al.Fault diagnosis and optimal data clustering based on K-means with slope factor [J].Computer & Digital Engineering，2014，42(1)：14-18.)

[6] 劉云霞.基于動(dòng)態(tài)時(shí)間規(guī)整的面板數(shù)據(jù)聚類方法研究及應(yīng)用 [J].統(tǒng)計(jì)研究，2016，33(11)：93-101.

(LIU Yun-xia.Research and application of panel data clustering method based on dynamic time warping [J].Statistical Research，2016，33(11)：93-101.)

[7] 王德青，朱建平，王潔丹.基于自適應(yīng)權(quán)重的函數(shù)型數(shù)據(jù)聚類方法研究 [J].數(shù)據(jù)統(tǒng)計(jì)與管理，2015，34(1)：84-92.

(WANG De-qing，ZHU Jian-ping，WANG Jie-dan.Research of clustering analysis for functional data based on adaptive weighting [J].Journal of Applied Statistic and Management，2015，34(1)：84-92.)

[8] 李因果，何曉群，李新春.基于Tucker3分解的三路數(shù)據(jù)聚類方法 [J].數(shù)理統(tǒng)計(jì)與管理，2016，35(1)：71-80.

(LI Yin-guo，HE Xiao-qun，LI Xin-chun.Three-way data clustering method based on tucker3 decomposition [J].Journal of Applied Statistic and Management，2016，35(1)：71-80.)

[9] 唐東明.基于Hadoop的仿射傳播大數(shù)據(jù)聚類分析方法 [J].計(jì)算機(jī)工程與應(yīng)用，2015，51(4)：29-34.

(TANG Dong-ming.Affinity propagation clustering for big data based on Hadoop [J].Computer Engineering and Applications，2015，51(4)：29-34.)

[10]孫浩軍，閃光輝，高玉龍，等.一種高維混合屬性數(shù)據(jù)聚類算法 [J].計(jì)算機(jī)工程與應(yīng)用，2015，51(8)：128-133.

(SUN Hao-jun，SHAN Guang-hui，GAO Yu-long，et al.Algorithm for clustering of high-dimensional data mixed with numeric and categorical attributes [J].Computer Engineering and Applications，2015，51(8)：128-133.)

[11]馬雯雯，鄧一貴.新的短文本特征權(quán)重計(jì)算方法 [J].計(jì)算機(jī)應(yīng)用，2013，33(8)：2280-2282.

(MA Wen-wen，DENG Yi-gui.New feature weight calculation method for short text [J].Journal of Computer Applications，2013，33(8)：2280-2282.)

[12]胡先兵，趙國(guó)慶.引入時(shí)頻聚集交叉項(xiàng)干擾抑制的大數(shù)據(jù)聚類算法 [J].計(jì)算機(jī)科學(xué)，2016，43(4)：197-201.

(HU Xian-bing，ZHAO Guo-qing.Large data clustering algorithm introducing time and frequency clustering interference suppression [J].Computer Science，2016，43(4)：197-201.)

Dataclusteringalgorithmbasedonfeatureweightingtheory

FEI Xian-ju1, LI Hong2, TIAN Guo-zhong1

(1.School of Computer Information & Engineering, Changzhou Institute of Technology, Changzhou 213032, China; 2.Office of Fiber Inspection of Jilin Province, Quality Supervision and Inspection Base of Jilin Province, Changchun 130103, China)

Aiming at the problem that the initial clustering number and center are difficult to be determined in the data clustering opertion of data mining process, a fuzzy weighting clustering algorithm based on the soft subspace as well as the competition and combination mechanism was proposed.Through rewriting the objective function of soft subspace clustering algorithm and combining the size of data clusters, the competition and combination operation was carried out for the data clusters, and the clustering treatment of data was achieved.The results show that the proposed algorithm can accurately perform the clustering of data samples, and the clustering results are independent on the initial clustering number and center.The algorithm can meet the need in high dimensional data clustering processing and has the great practical value.

data mining; data clustering; feature weighting; soft subspace clustering; combination and competition mechanism; fuzzy clustering algorithm; clustering center; clustering number

2016-12-16.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61363004).

費(fèi)賢舉(1975-)，男，安徽合肥人，講師，碩士，主要從事數(shù)據(jù)挖掘、智能信息處理和數(shù)據(jù)可視化等方面的研究.

* 本文已于2017-12-22 15∶21在中國(guó)知網(wǎng)優(yōu)先數(shù)字出版.網(wǎng)絡(luò)出版地址：http：//kns.cnki.net/kcms/detail/21.1189.T.20171222.0920.002.html

10.7688/j.issn.1000-1646.2018.01.14

TP 311

A

1000-1646(2018)01-0077-05

鐘 媛 英文審校：尹淑英)