現(xiàn)有的增量聚類算法雖然解決了數(shù)據(jù)增量和類簇重疊問題,但在距離度量時沒有考慮屬性重要度不同,且普遍擁有較高的時間復(fù)雜度。針對以上問題,提出一種基于屬性重要度的加權(quán)三支決策增量軟聚類算法（W-TIOC-TWD算法）,將屬性重要度考慮到距離度量中,彌補了現(xiàn)有算法在聚類過程中將所有屬性的重要程度視為相等的不足。該算法還引入離群點概念,降低了算法的時間復(fù)雜度�；谌斯�(shù)據(jù)集和UCI數(shù)據(jù)集的實驗結(jié)果表明,W-TIOC-TWD算法的聚類準(zhǔn)確率優(yōu)于比較算法。 

【文章來源】：軟件導(dǎo)刊. 2019,18(08)

【文章頁數(shù)】：8 頁

【部分圖文】：

TIOC-TWD算法流程TIOC-TWD算法能同時解決增量聚類和重疊聚類問

第8期圖2W-TIOC-TWD算法流程2.2.2創(chuàng)建代表點搜索樹算法（算法2）樹結(jié)構(gòu)具有簡單、快速、易查找和更新的特點，適合處理動態(tài)增量問題。搜索樹的創(chuàng)建由屬性重要度大小確定，采用自上向下的方式構(gòu)建。本算法樹結(jié)構(gòu)節(jié)點由若干個代表點組成，每個樹節(jié)點代表了這些代表點所處的數(shù)據(jù)空間區(qū)域。本文在建立搜索樹時根據(jù)信息熵（公式4）確定屬性優(yōu)先程度，信息熵值越大其所對應(yīng)屬性的模糊程度越高，需要根據(jù)更多信息確定。2.2.3增量更新算法（算法3）針對新到來的增量數(shù)據(jù)提出增量更新算法。該算法由3部分組成：①根據(jù)算法1中代表點的尋找方法尋找增量數(shù)據(jù)代表點；②利用算法2創(chuàng)建的代表點搜索樹，尋找增量數(shù)據(jù)代表點的鄰居代表點；③對發(fā)生變化的代表點及代表區(qū)域進行更新，即更新代表點搜索樹和代表點關(guān)系圖。增量更新算法與原算法不同之處是，增量數(shù)據(jù)各屬性的權(quán)重由初始數(shù)據(jù)集和增量數(shù)據(jù)集共同組成的數(shù)據(jù)集整體確定。2.2.4算法性能分析為降低算法的時間復(fù)雜度，提高算法效率，本文提出離群點這一概念，下面介紹隔離離群點方法對算法性能的影響。算法1是加權(quán)靜態(tài)重疊聚類算法，設(shè)數(shù)據(jù)塊大小為h，數(shù)據(jù)屬性個數(shù)為m，代表點總數(shù)為|R|，則計算距離矩陣及尋找數(shù)據(jù)對象鄰居所需時間為O(n2)，根據(jù)鄰居個數(shù)數(shù)據(jù)對象的排序時間為O(nlog(n))。假設(shè)代表點代表區(qū)域中的數(shù)據(jù)對象個數(shù)為p，則尋找代表點所需時間為O(||R*p*m+nlog(n))，創(chuàng)建代表點關(guān)系圖所需時間為O(2*||R2)。通過計算發(fā)現(xiàn)，尋找代表點及創(chuàng)建代表點關(guān)系圖的時間復(fù)雜度均與|R|的大小直接相關(guān)。由此可知，通過隔離離群點的方法可使|R|變小，從而降低尋找代表點及創(chuàng)建代表點關(guān)

第8期集和增量數(shù)據(jù)集兩個部分。隨機選取真實數(shù)據(jù)集60%數(shù)據(jù)作為初始訓(xùn)練數(shù)據(jù)集，剩余40%的數(shù)據(jù)分別均分為4組和2組，模擬連續(xù)4次每次10%的數(shù)據(jù)增量實驗，以及連續(xù)2次每次20%的數(shù)據(jù)增量實驗，具體增量數(shù)據(jù)流如圖3和圖4所示。UU1U2U3U4圖3連續(xù)4次10%增量數(shù)據(jù)流UU1U2圖4連續(xù)兩次20%增量數(shù)據(jù)流第二組實驗參數(shù)采用0.1為間隔的插值分析方法進行調(diào)整，參數(shù)的取值范圍［0，1］，W-TIOC-TWD算法采用δ、α、β三個參數(shù)最優(yōu)值，見表2。3.3評價指標(biāo)在第二組定量實驗中，用準(zhǔn)確率作為評價指標(biāo)對比本文算法與比較算法的性能。定義12準(zhǔn)確率（Accuracy）：設(shè)樣本集X包括k個類，準(zhǔn)確率計算公式如下：Accuracy=i=1kai||X（8）其中，ai表示被正確聚類到類Ci中的對象數(shù)，||X表示集合中包含的元素數(shù)。表2參數(shù)最優(yōu)值數(shù)據(jù)集LetterABCLetterAGIBanknotePendigists1234Pendigists1469Waveformδ0.250.200.230.180.190.26α0.230.250.380.340.260.35β0.050.050.040.10.10.043.4實驗結(jié)果及分析3.4.1人工數(shù)據(jù)集實驗結(jié)果及分析增量數(shù)據(jù)到來時，本文算法對類簇增長、合并、發(fā)現(xiàn)新類簇等處理能力實驗結(jié)果如圖5-圖7所示。由圖5和圖6可知，類2的數(shù)據(jù)個數(shù)隨著增量數(shù)據(jù)的到來而增長。由圖7和圖8可知，隨著增量數(shù)據(jù)的到來，類1和類2的邊界域數(shù)據(jù)個數(shù)超過一定量時，兩個類合并成一個類。由圖9和圖10可知，增量數(shù)據(jù)到來時，算法能夠識別出新產(chǎn)生的類2。結(jié)論1：通過在人工數(shù)據(jù)集的實驗可?

【參考文獻】：
期刊論文
[1]基于k-means的自動三支決策聚類方法[J]. 于洪,毛傳凱.  計算機應(yīng)用. 2016(08)
[2]大數(shù)據(jù)聚類算法綜述[J]. 海沫.  計算機科學(xué). 2016(S1)
[3]不確定度模型下數(shù)據(jù)流自適應(yīng)網(wǎng)格密度聚類算法[J]. 劉卓,楊悅,張健沛,楊靜,初妍,張澤寶.  計算機研究與發(fā)展. 2014(11)
[4]基于信息熵的專家聚類賦權(quán)方法[J]. 周漩,張鳳鳴,惠曉濱,李克武.  控制與決策. 2011(01)
[5]基于相對密度的增量式聚類算法[J]. 劉青寶,侯東風(fēng),鄧蘇,張維明.  國防科技大學(xué)學(xué)報. 2006(05)



本文編號：3093147