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

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

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

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

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

信息時(shí)代中人們時(shí)刻都面臨著各種類(lèi)型的數(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ò)分析并處理特定類(lèi)型的數(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)分析、聚類(lèi)分析和特征選擇及提取[7-12]等.聚類(lèi)分析是指利用特定技術(shù)手段發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在規(guī)律，并按照規(guī)律將數(shù)據(jù)進(jìn)行科學(xué)分類(lèi).聚類(lèi)分析是數(shù)據(jù)挖掘的重要方法和關(guān)鍵過(guò)程，直接影響數(shù)據(jù)挖掘的最終結(jié)果，是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的重點(diǎn)研究?jī)?nèi)容之一.

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

1 算法模型

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

(1)

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

1) 計(jì)算聚類(lèi)中心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ù)聚類(lèi)中心和加權(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è)聚類(lèi)中心之間的距離D，并求出距離D的最小值Dmin.當(dāng)某個(gè)數(shù)據(jù)簇的勢(shì)Ni小于閾值MT時(shí)，就消去該數(shù)據(jù)簇.當(dāng)Dmin滿(mǎn)足式(12)時(shí)，合并距離為Dmin的兩個(gè)數(shù)據(jù)簇.MT公式和判別條件分別為

(11)

(12)

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

(13)

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

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

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

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

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

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

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

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

(14)

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

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

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

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

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

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

2.3 初始聚類(lèi)中心位置敏感性分析

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

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

3 結(jié) 論

本文結(jié)合軟子空間聚類(lèi)算法和基于競(jìng)爭(zhēng)合并機(jī)制的模糊聚類(lèi)算法，提出了一種軟子空間結(jié)合競(jìng)爭(zhēng)合并機(jī)制的模糊加權(quán)聚類(lèi)算法.該算法通過(guò)對(duì)軟子空間聚類(lèi)算法的目標(biāo)函數(shù)進(jìn)行修改，使其具備了軟子空間聚類(lèi)算法和競(jìng)爭(zhēng)合并機(jī)制模糊聚類(lèi)算法的優(yōu)點(diǎn).求解過(guò)程通過(guò)迭代的方式運(yùn)行，能夠根據(jù)實(shí)際需要控制運(yùn)算的速度和精度.結(jié)果表明，該算法能夠以較高的準(zhǔn)確度實(shí)現(xiàn)對(duì)數(shù)據(jù)樣本的聚類(lèi)分析，運(yùn)算結(jié)果與初始數(shù)據(jù)簇的個(gè)數(shù)和初始聚類(lèi)中心的位置無(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)的模糊聚類(lèi)有效性函數(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] 陳晉音，何輝豪.基于密度的聚類(lèi)中心自動(dòng)確定的混合屬性數(shù)據(jù)聚類(lèi)算法研究 [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ù)聚類(lèi)及故障診斷研究 [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ù)聚類(lèi)方法研究及應(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ù)聚類(lèi)方法研究 [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ù)聚類(lèi)方法 [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ù)聚類(lèi)分析方法 [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ù)聚類(lèi)算法 [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ù)聚類(lèi)算法 [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

鐘 媛 英文審校：尹淑英)