發(fā)布時(shí)間：2021-03-21 16:00

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

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

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

【部分圖文】：

TIOC-TWD算法流程TIOC-TWD算法能同時(shí)解決增量聚類(lèi)和重疊聚類(lèi)問(wèn)

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

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

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



本文編號(hào)：3093147