申彥博 袁潔 紀淑娟 張純金

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

關鍵詞：聚類分析;增量聚類;離群點;三支決策理論;屬性重要度

DOI：10. 11907/rjdk. 191251 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2019）008-0042-07

A Weighted Three-way Decision Incremental Clustering Algorithm

and Performance Analysis

SHEN Yan-bo1，YUAN Jie1，JI Shu-juan1，2，ZHANG Chun-jin3

（1. College of Computer Science and Engineering， Shandong University of Science and Technology;

2. Key Laboratory for Wisdom Mine Information Technology of Shandong Province， Shandong University of Science and Technology;

3. Network Information Center， Shandong University of Science and Technology， Qingdao 266590，China）

Abstract：Though the existing incremental clustering algorithms can solve the problem of data increment and class overlap， those algorithms do not consider the difference of attribute importance in distance measurement and generally have a higher time complexity. To solve the above problems， this paper proposes the W-TIOC-TWD algorithm. Taking attribute importance into the calculation of distance measure， this algorithm can cover the shortage that equally regard the importance of all attributes in the process of clustering. Moreover， the definition of outlier point is proposed， which improves the time efficiency of this algorithm. To verify the effectiveness and accuracy of this algorithm， experiments on artificial datasets and UCI datasets are implemented. Experimental results show that the W-TIOC-TWD algorithm outperform the comparison algorithms.

Key Words：clustering analysis; incremental clustering; outlier point; three-way decision theory; attribute importance

基金項目：國家自然科學基金項目（71772107，71403151，61502281，61433012）;青島社會科學規(guī)劃研究項目（QDSKL1801138）;山東省重點研發(fā)計劃項目（2018GGX101045）;山東省自然科學基金項目（ZR2018BF013，ZR2013FM023，ZR2014FP011）;山東省研究生質量提升計劃項目（2016）;山東科技大學領軍人才計劃項目（2014）;泰山學者攀登計劃項目（2014）

作者簡介：申彥博（1994-），男，山東科技大學計算機科學與工程學院碩士研究生，研究方向為人工智能與智能商務信息處理;袁潔（1992-），女，山東科技大學計算機科學與工程學院碩士研究生，研究方向為人工智能與智能商務信息處理;紀淑娟（1977-），女，博士，山東科技大學計算機科學與工程學院、山東省智慧礦山信息技術重點實驗室副教授、博士生導師，研究方向為人工智能與智能商務信息處理;張純金（1977-），男，碩士，山東科技大學網(wǎng)絡信息中心工程師，研究方向為智能信息處理和網(wǎng)絡安全。

0 引言

聚類分析[1]作為一種常用的數(shù)據(jù)挖掘技術，廣泛應用在推薦系統(tǒng)、話題追蹤與檢測等領域。傳統(tǒng)的聚類算法大多是靜態(tài)硬聚類算法，無法處理動態(tài)變化的數(shù)據(jù)，并且數(shù)據(jù)對象經(jīng)過聚類后只能劃分到唯一的類簇中，聚類準確率低。為此，人們提出了基于增量的聚類算法。這類算法基本特點是：增量數(shù)據(jù)到來后，只需在原聚類結果基礎上對增量數(shù)據(jù)進行聚類，無需重新聚類整個數(shù)據(jù)集，從而避免了大量的重復計算。然而，增量聚類算法依然屬于硬聚類算法，存在著數(shù)據(jù)對象只能劃分到唯一類簇的局限性。軟聚類算法則有效解決了這一問題，使得一個數(shù)據(jù)對象可以屬于多個類簇。

基于樹結構的三支決策增量聚類算法[2]（TIOC-TWD算法）同時解決了數(shù)據(jù)增量和類簇重疊問題，但該算法在聚類時沒有將屬性重要程度考慮到距離計算公式中;此外，該算法將密度為1的點也標記為代表點，使構建搜索樹以及增量更新時浪費大量時間。針對以上問題，本文提出一種基于屬性重要度的加權三支決策增量軟聚類算法（W-TIOC-TWD算法），將屬性重要度考慮到距離度量中，彌補了TIOC-TWD算法在聚類過程中將所有屬性的重要程度視為相等的不足，提高了聚類結果準確率;同時，本文對密度為1的點進行隔離，降低了算法的時間復雜度。

1 相關工作

為降低時間成本，提高聚類準確率，提高聚類算法動態(tài)處理變化數(shù)據(jù)集能力，解決數(shù)據(jù)對象重疊問題，研究人員提出了很多增量聚類算法和軟聚類算法。

1.1 基于增量的聚類算法

Charkraborth等[3]將K-means算法應用到增量聚類中，對離增量數(shù)據(jù)最近的簇進行聚類操作;Pham等[4]提出一種基于目標優(yōu)化的增量K-means聚類算法，能對大數(shù)據(jù)集快速進行增量聚類。但這兩種算法都是基于K-means思想實現(xiàn)的，需要人為設定聚類個數(shù)并且算法只能發(fā)現(xiàn)球狀類簇。

ALM等[5]對DBSCAN算法進行了擴展，提出了新的增量DBSCAN聚類算法，并使用有效性評測指標GDI和DB對聚類結果進行評價。實驗結果表明增量DBSCAN聚類算法較傳統(tǒng)的DBSCAN算法更有效率，但該算法仍未解決算法參數(shù)敏感問題。為解決DBSCAN算法受參數(shù)影響較大問題，劉青寶等[6]提出了一種基于相對密度的增量式聚類算法，但算法聚類形成的類簇都必須由全部數(shù)據(jù)組成，在進行增量更新時內存占用問題很難解決。

在基于網(wǎng)格的增量聚類研究中，LEI等[7]提出了新的增量聚類算法IGrid算法，算法基于網(wǎng)格對空間多維數(shù)據(jù)進行統(tǒng)計分析，利用網(wǎng)格聚類思想處理增量聚類問題，該算法可以發(fā)現(xiàn)任意形狀的類簇;劉卓等[8]將網(wǎng)格聚類與數(shù)據(jù)流聚類相結合，使得網(wǎng)格聚類在數(shù)據(jù)流中得到進一步發(fā)展，但是基于網(wǎng)格的聚類算法仍無法解決參數(shù)敏感問題。

1.2 軟聚類算法

二支決策硬聚類算法都存在不能發(fā)現(xiàn)重疊類簇的缺點。為滿足應用領域對聚類的需求，人們提出了軟聚類算法。Labroche等[9]提出了在線模糊中心聚類算法，該算法可以檢測奇異數(shù)據(jù)對象和重疊的類簇，但需要人工指定數(shù)據(jù)集中最終的類簇個數(shù);Peters等[10]提出了一種動態(tài)粗糙聚類算法，該算法主要使用粗糙集理論檢測數(shù)據(jù)集結構的改變，且算法還定義了一些標準度量新增數(shù)據(jù)與已有數(shù)據(jù)對象間的結構一致性，并對增量數(shù)據(jù)進行聚類。但在實際數(shù)據(jù)處理過程中，這些判斷標準很難確定;Perez-Suarea等[11]提出了一種基于圖理論的動態(tài)重疊聚類算法DClustR，算法根據(jù)數(shù)據(jù)的密度相關性尋找一組節(jié)點完成圖的覆蓋，且只對受增量數(shù)據(jù)影響的圖進行更新，但該算法的缺點是發(fā)現(xiàn)的類簇都比較小。

近幾年提出的三支決策思想為解決重疊聚類問題提供了新思路。三支決策[12]是對傳統(tǒng)二支決策的擴展，其在二支決策基礎上增加了不承諾決策，即三支決策由接受、拒絕、不承諾3種決策組成，分別對應于粗糙集模型的正域、邊界域和負域。于洪等[13]將三支決策思想與K-means算法相結合，提出了一種基于K-means的自動三支決策聚類方法，該算法能夠發(fā)現(xiàn)重疊類簇，并能自動確定類簇個數(shù)。然而，該算法對聚類個數(shù)的確定依賴于近鄰選取。

1.3 三支決策增量聚類算法（TIOC-TWD）

為解決上述問題，于洪等提出了基于樹結構的三支決策增量聚類算法（TIOC-TWD算法）。圖1展示了TIOC-TWD算法流程。TIOC-TWD算法由4部分組成，算法1、算法2采用離線計算方法，算法3、算法4采用在線計算方法。算法1為三支決策重疊聚類算法，采用歐式距離尋找數(shù)據(jù)集的代表點，對數(shù)據(jù)集進行初始聚類;算法2的主要任務是創(chuàng)建代表點搜索樹;算法3的基本思想是在增量數(shù)據(jù)到來后尋找增量數(shù)據(jù)的鄰居代表點;算法4是更新增量算法，更新代表點搜索樹和代表點關系，得到增量后的聚類結果。

圖1 TIOC-TWD算法流程

TIOC-TWD算法能同時解決增量聚類和重疊聚類問題，實驗結果證明該算法的聚類準確率要高于其它增量重疊聚類算法。但TIOC-TWD算法在初始聚類時，將密度為1的點記為代表點，使算法在創(chuàng)建代表點搜索樹及增量更新時浪費了大量時間。此外，算法在距離度量時并未考慮數(shù)據(jù)各屬性重要度不同的問題，無法增強重要屬性或消除冗余屬性對聚類結果的影響，不能體現(xiàn)數(shù)據(jù)各屬性之間的差異性，大大降低了聚類結果的準確率。

2 W-TIOC-TWD算法

針對TIOC-TWD算法不足，本文提出一種基于屬性重要度的加權三支決策增量軟聚類算法（W-TIOC-TWD算法），下面闡述算法定義及執(zhí)行步驟。

2.1 基本概念及定義

定義1：代表點。如果條件|Neighbor（r）|≥ζ成立，ζ是密度閾值，就稱 r為代表點，其代表了以r為中心、以δ為半徑數(shù)據(jù)區(qū)域內所有數(shù)據(jù)對象。

定義2：代表區(qū)域。每個代表點 r 代表了以r為中心，以δ為半徑的球形數(shù)據(jù)空間區(qū)域，將該球形區(qū)域作為代表點r的代表區(qū)域。

定義3：代表區(qū)域相似度。設D維數(shù)據(jù)空間中任意2個代表點分別為[ri]、[rj]，則按照如下方式定義它們代表區(qū)域之間的相似性值大小。

[SimilarR（ri，rj）=Cover（ri）？Cover（rj）min（Cover（ri），Cover（ri））]? （1）

式中，[Cover（ri）]，[Cover（rj）]各自表示[ri]、[rj]代表區(qū)域數(shù)據(jù)對象的個數(shù)，[Cover（ri）？Cover（rj）]表示代表點[ri]、[rj]代表區(qū)域重疊部分中數(shù)據(jù)對象的個數(shù)。

定義4：數(shù)據(jù)元素相似性。算法中兩個數(shù)據(jù)元素的相似性采用歐氏距離計算，計算公式如下：

[d（xi，xj）=k=1m（xi，k-xj，k）2]? ? ? ?（2）

定義5：樹節(jié)點。設代表點搜索樹第i層第j個樹節(jié)點為[Nodeij]，[Nodeij]所包含的代表點集合為[{r1，r2，？，][rNodeij}]。[Nodeij]的值范圍采用一個區(qū)間表示為[Nodeij=][[Nodeij.left，Nodeij.right]]，其中，[Nodeij]左值和右值分別計算，即[Nodeij.left=min{ri1.left，？，riNodeij.left}]，[Nodeij.right=][max{ri1.right，？，riNodeij.right}]。一個樹節(jié)點由多個代表點組成，并且在第i維屬性上組成樹節(jié)點的代表點的數(shù)學值范圍區(qū)間在樹節(jié)點的值范圍區(qū)間內。

定義6：數(shù)值范圍相似性。設兩個數(shù)值的范圍代表區(qū)間分別為R1、R2，其代表區(qū)間的數(shù)據(jù)元素個數(shù)分別為[R1]、[R2]，其中R1=[R1.left，R1.right]，R2=[R2.left，R2.right]，則當R1[？]R2[≠φ]時，稱R1與R2這兩個數(shù)值范圍代表區(qū)間元素相似，即當R1[？]R2[≠φ]時認為兩個數(shù)值范圍是相似的。

定義7：數(shù)據(jù)非負標準化。在對數(shù)據(jù)集進行熵權重計算前，先對數(shù)據(jù)集進行非負標準化，將數(shù)據(jù)元素映射成[0，1]范圍內的數(shù)據(jù)。

[rij=xij-min（xij）max（xij）-min（xij）]? ? ? ? ? （3）

定義8：信息熵。屬性j的信息熵[14]計算公式如下：

[Ej=-1lnni=1nbijlnbij]? ? （4）

其中，[bij=riji=1nrij]。

定義9：熵權值。屬性j的熵權值計算公式為：

[wj=1-Ejk=1m（1-Ek）]? ? ? ? ? （5）

由公式（5）可知，信息熵越大，對應的屬性熵權值越小，屬性重要程度越低。

定義10：基于熵權值的加權距離?；陟貦嘀档募訖嗑嚯x計算公式如下：

[d（xi，xj）=k=1nwi2（xi，k-xj，k）2]? ? ? ? ? ? （7）

其中[wi=1-Eik=1m（1-Ek）]，m為屬性個數(shù)。

定義11：離群點。假設數(shù)據(jù)集U在聚類之后，若聚類結果中存在不屬于任何一個類簇且密度為1的代表點組成的類簇，則將此類簇定義為離群點并進行隔離。

2.2 W-TIOC-TWD算法

W-TIOC-TWD算法基本思想是：①通過對具有不同權重的各屬性進行加權求和改進距離度量;②提出離群點這一概念，通過隔離離群點方法降低算法的時間復雜度。

W-TIOC-TWD算法由3部分組成：算法1為加權靜態(tài)重疊聚類算法，算法2為創(chuàng)建代表點搜索樹算法，算法3為增量更新算法。算法1的基本思想：首先對標準化處理的數(shù)據(jù)集進行屬性權重計算，然后利用改進的距離計算公式尋找數(shù)據(jù)集的代表點，對數(shù)據(jù)集進行初始聚類，最后對初始聚類結果中的離群點進行隔離;算法2的主要任務是根據(jù)屬性重要度創(chuàng)建代表點搜索樹;算法3的基本思想是將增量數(shù)據(jù)與離群點結合，通過搜索樹尋找增量數(shù)據(jù)集的鄰居代表點，得到增量后的聚類結果。

圖2簡要展示了算法流程，其中紅色虛線框內部分為W-TIOC-TWD算法與TIOC-TWD算法（圖1所示）的改進之處。下面介紹W-TIOC-TWD算法中每個子算法實現(xiàn)。

2.2.1 加權靜態(tài)重疊聚類算法（算法1）

針對TIOC-TWD中忽略屬性重要度這一不足，提出一種加權靜態(tài)重疊聚類算法（詳見算法1）。首先，對標準化處理的數(shù)據(jù)集進行屬性權重計算，為數(shù)據(jù)各屬性分配權重。屬性重要度分配能夠起到強化重要屬性消除冗余屬性作用[13];然后，利用改進的距離計算公式尋找數(shù)據(jù)集代表點，對數(shù)據(jù)集進行初始聚類;最后，對初始聚類結果中的離群點進行隔離。

圖2 W-TIOC-TWD算法流程

2.2.2 創(chuàng)建代表點搜索樹算法（算法2）

樹結構具有簡單、快速、易查找和更新的特點，適合處理動態(tài)增量問題。搜索樹的創(chuàng)建由屬性重要度大小確定，采用自上向下的方式構建。本算法樹結構節(jié)點由若干個代表點組成，每個樹節(jié)點代表了這些代表點所處的數(shù)據(jù)空間區(qū)域。本文在建立搜索樹時根據(jù)信息熵（公式4）確定屬性優(yōu)先程度，信息熵值越大其所對應屬性的模糊程度越高，需要根據(jù)更多信息確定。

2.2.3 增量更新算法（算法3）

針對新到來的增量數(shù)據(jù)提出增量更新算法。該算法由3部分組成：①根據(jù)算法1中代表點的尋找方法尋找增量數(shù)據(jù)代表點;②利用算法2創(chuàng)建的代表點搜索樹，尋找增量數(shù)據(jù)代表點的鄰居代表點;③對發(fā)生變化的代表點及代表區(qū)域進行更新，即更新代表點搜索樹和代表點關系圖。

增量更新算法與原算法不同之處是，增量數(shù)據(jù)各屬性的權重由初始數(shù)據(jù)集和增量數(shù)據(jù)集共同組成的數(shù)據(jù)集整體確定。

2.2.4 算法性能分析

為降低算法的時間復雜度，提高算法效率，本文提出離群點這一概念，下面介紹隔離離群點方法對算法性能的影響。

算法1是加權靜態(tài)重疊聚類算法，設數(shù)據(jù)塊大小為h，數(shù)據(jù)屬性個數(shù)為m，代表點總數(shù)為|R|，則計算距離矩陣及尋找數(shù)據(jù)對象鄰居所需時間為[O（n2）]，根據(jù)鄰居個數(shù)數(shù)據(jù)對象的排序時間為[O（nlog（n））]。假設代表點代表區(qū)域中的數(shù)據(jù)對象個數(shù)為p，則尋找代表點所需時間為[O（R*p*m+][nlog（n））]，創(chuàng)建代表點關系圖所需時間為[O（2*R2）]。通過計算發(fā)現(xiàn)，尋找代表點及創(chuàng)建代表點關系圖的時間復雜度均與|R|的大小直接相關。由此可知，通過隔離離群點的方法可使|R|變小，從而降低尋找代表點及創(chuàng)建代表點關系圖的時間復雜度。

Algorithm1：加權靜態(tài)重疊聚類算法

Input：初始數(shù)據(jù)集[U]，閾值[α，β，δ];權重[wi];

Output： 聚類結果集，R，Neighbor（[ri]）;

過程：

初始化R=[φ]、代表點鄰居集合Neighbor（[ri]）=[φ]、類簇集合C=[φ] ;

根據(jù)式（5）計算數(shù)據(jù)集的屬性權重值[wi];

利用公式（7）生成距離矩陣[Distance（x，y）];

計算每個數(shù)據(jù)元素的鄰居數(shù)據(jù)Neighbor（[xi]）;

按照[Neigbor（xi）]值大小排序距離矩陣[Distance（x，y）]中[xi]所在的行;

將[Distance（x，y）]中第一行的數(shù)據(jù)對象（設為[x1]）作為[rnew]的幾何中心;

[cover（rnew）]中的每個元素[xi]，刪除距離矩陣[Distance（x，y）]中[xi]所在的行;

將新生成的代表點[rnew]添加到代表點集合R中，并從代表點集合中根據(jù)定義11進行離群點的隔離;

for（對于任意兩個代表點[ri]）;

根據(jù)公式（1）計算相似度并添加強弱連通邊構建代表點無向關系圖;

寬度優(yōu)先搜索算法尋找代表點無向關系圖中的強連通子圖;

for （任意強連通子圖[G]）;

for （強聯(lián)通子圖中的每一個代表點[ri]）;

[Pos（Cnew）=Pos（Cnew）∪Cover（ri）];

for （與強聯(lián)通子圖有弱邊相連的每一個代表點[rj]）;

[Bnd（Cnew）=Bnd（Cnew）∪Cover（rj）];

[Cnew= Pos（Cnew）∪Bnd（Cnew）];

最終的聚類結果C=C[？][Cnew];

算法2 為創(chuàng)建代表點搜索樹算法，最壞情況下代表點搜索樹一共有m層，每層需要對|R|個代表點進行排序，則需要進行[（R*（R-1））]次計算，從而分裂節(jié)點，所以算法2的時間復雜度為[O（m*（RlogR+R*（R-1））），]也與|R|的大小直接相關。

算法3是增量更新算法。假設離群點的個數(shù)為|r|，增量數(shù)據(jù)塊有[R]個代表點，樹節(jié)點共有L個子節(jié)點，查找新增代表點鄰居代表點的時間復雜度為[O（m*（L*log（L）+][L+（R-|r|））]。假設每個代表點的代表區(qū)域有k1個數(shù)據(jù)對象，鄰居代表點集合大小為k2，則算法3的時間復雜度為[O（|R|*（m*（L*log（L）+L）+R-|r|））]。通過計算可知，隨著離群點個數(shù)|r|的增加，算法3的時間復雜度降低。

由于W-TIOC-TWD算法的3個子算法串行執(zhí)行，所以該算法的時間復雜度為[O（sum（算法1，算法2，算法3））]。通過對3個子算法時間復雜度的分析可知，本文通過隔離離群點方法，分別降低了3個子算法的時間復雜度。所以，隔離離群點方法可以降低W-TIOC-TWD算法的總體時間復雜度，提高算法時間效率。

Algorithm2：創(chuàng)建代表點搜索樹算法

Input：初始數(shù)據(jù)集U，代表點集合R

Output：代表點搜索樹

過程：

根據(jù)公式（4）計算初始數(shù)據(jù)集U各屬性的[Ej]值;

按照[Ej]由大到小的順序對數(shù)據(jù)各屬性進行排序;

對每個代表點的各維屬性的屬性值范圍進行排序，按照代表點在第j維屬性的左值由小到大對代表點排序，并依次計算代表點的值范圍相似度。

采用降序排序后的數(shù)據(jù)集屬性集合創(chuàng)建搜索樹的每一層樹節(jié)點，即屬性重要度越高的屬性越先用于構造樹的節(jié)點。

3 實驗結果分析

為了定性和定量評估W-TIOC-TWD算法性能，設計兩組實驗：第一組實驗在人工數(shù)據(jù)集上對算法進行定性分析，驗證W-TIOC-TWD算法是否具有在增量數(shù)據(jù)下的類簇合并、增長以及發(fā)現(xiàn)新類簇等能力;第二組實驗基于UCI[15]真實數(shù)據(jù)集進行定量分析，以準確率（Accuracy）作為評價指標，以最新、效果最好的增量軟聚類算法TIOC-TWD算法和增量聚類算法OFCMD算法[16]作為比較算法。

Algorithm3：增量更新算法

Input：①增量數(shù)據(jù)集代表點集合R;②代表點無向關系圖G;③參數(shù)[α、β、δ];

Output：聚類結果C={[C1]，…[Ci]，…[Cn]}

過程：

for （對任意增量數(shù)據(jù)代表點[rwait] ）

FindNeighbor（[rwait]）;//尋找代表點[rwait]的鄰居代表點

//Mapping each [xi] in [rwait] to neighbor representative points in[Rneighbor]

for （[rwait]代表區(qū)域中的任意一個[xi]）

for （[rwait]中的任意代表點[ri]）

根據(jù)公式（7）計算[xi]與[ri]之間的距離;

if （distance（[xi]，centriod [ri]）[≤][δ]）

Cover（[ri]）=Cover（[ri]）[？][xi];

if（there exists [xi] which cant map to any[? Rneighbor]）

for（[Rneighbor]中的任意代表點[ri]）

for （代表點 [ri] 中的任意 [xj] ）

if distance（[xj]，centriod[ rwait]）[≤][δ]

Cover（[rwait]）=Cover（[rwait]）[？][xj];

add [rwait] to [ Rneighbor]

else

for（對于每一個樹節(jié)點 [nodeij] in Path）

從樹節(jié)點 [nodeij] 中尋找代表點[rwait]，并將其從[nodeij] 中刪除掉;

更新發(fā)生變化的代表點無向關系圖G

for （each representative point [ri] in[ Rneighbor]）

for（each representative point [ri] in neighbor（[ri]））

根據(jù)公式（1）計算[ri]、[rj]代表區(qū)域的相似性，構建無向連通圖;

new=0

for（ each changed sub-graph [G'] in G）

new=+1;

for （each representative point [ri] in [G']）

POS（[Cnew]）=POS（[Cnew]）[？]Cover（[ri]）;

for（each [rj] which is linked to [G] with weak edge）

BND（[Cnew]）=BND（[Cnew]）[？]Cover（[rj]）;

C=C[？][Cnew];

3.1 數(shù)據(jù)與預處理

本文實驗數(shù)據(jù)集為3個人工數(shù)據(jù)集和6個UCI真實數(shù)據(jù)集，數(shù)據(jù)集規(guī)模如表1所示。

第一組實驗所用到的人工數(shù)據(jù)集D1、D2、D3是在二維坐標下隨機生成的，維度即屬性個數(shù)，且每組數(shù)據(jù)都屬于一個類，其余6個數(shù)據(jù)集為第二組實驗所用的真實數(shù)據(jù)集。letterABC和LetterAGI均為數(shù)據(jù)集Letter的一部分，letter ABC包括字母類A、B和C三個類標簽，letter AGI包括字母A、G和I三個類標簽;pendigits1234和pendigits1469均來自數(shù)據(jù)集 pendigits，pendigits1234包括1、2、3和4四個類標簽，pendigits1469包括數(shù)字類1、4、6和9四個類標簽。實驗參數(shù)有3個，其中δ為距離閾值、α和β為連通邊強弱閾值。

表1 數(shù)據(jù)集

3.2 實驗設置

第一組實驗，隨機選擇D2數(shù)據(jù)集80%的數(shù)據(jù)以及D1全部數(shù)據(jù)作為初始數(shù)據(jù)集，D2剩余20%數(shù)據(jù)作為增量數(shù)據(jù)，驗證本文算法的類簇增長功能;隨機選取D1數(shù)據(jù)集80%作為初始數(shù)據(jù)集，20%作為增量數(shù)據(jù)集，驗證本文算法具有類簇合并功能;選取D3作為初始數(shù)據(jù)集，D1作為增量數(shù)據(jù)集驗證本文算法具有發(fā)現(xiàn)新類簇功能。

第一組實驗參數(shù)以0.1的間隔對參數(shù)進行插值調整，參數(shù)取值范圍為[0，1]，實驗參數(shù)δ、α、β分別設置為0.35、0.25、0.01。

第二組實驗將每個真實數(shù)據(jù)集劃分為初始訓練數(shù)據(jù)集和增量數(shù)據(jù)集兩個部分。隨機選取真實數(shù)據(jù)集60%數(shù)據(jù)作為初始訓練數(shù)據(jù)集，剩余40%的數(shù)據(jù)分別均分為4組和2組，模擬連續(xù)4次每次10%的數(shù)據(jù)增量實驗，以及連續(xù)2次每次20%的數(shù)據(jù)增量實驗，具體增量數(shù)據(jù)流如圖3和圖4所示。

圖3 連續(xù)4次10%增量數(shù)據(jù)流

圖4 連續(xù)兩次20%增量數(shù)據(jù)流

第二組實驗參數(shù)采用0.1為間隔的插值分析方法進行調整，參數(shù)的取值范圍[0，1]，W-TIOC-TWD算法采用δ、α、β 三個參數(shù)最優(yōu)值，見表2。

3.3 評價指標

在第二組定量實驗中，用準確率作為評價指標對比本文算法與比較算法的性能。

定義12 準確率（Accuracy）：設樣本集X包括k個類，準確率計算公式如下：

[Accuracy=i=1kaiX]? ? ? （8）

其中，[ai]表示被正確聚類到類[Ci]中的對象數(shù)，[X]表示集合中包含的元素數(shù)。

表2 參數(shù)最優(yōu)值

3.4 實驗結果及分析

3.4.1 人工數(shù)據(jù)集實驗結果及分析

增量數(shù)據(jù)到來時，本文算法對類簇增長、合并、發(fā)現(xiàn)新類簇等處理能力實驗結果如圖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。

結論1：通過在人工數(shù)據(jù)集的實驗可知，當增量數(shù)據(jù)集到來時，W-TIOC-TWD算法具有使類簇增長、類簇合并和發(fā)現(xiàn)新類簇的能力。

圖5 初始聚類結果一? ? ? ? ? ? ? ? ? ? ? ?圖6 增量聚類結果一

圖7 初始聚類結果二? ? ? ? ? ? ? ? ? ? ? 圖8 增量聚類結果二

圖9 初始聚類結果三? ? ? ? ? ? ? ? ? 圖10 增量聚類結果三

3.4.2 UCI數(shù)據(jù)集實驗結果及分析

基于UCI[15]真實數(shù)據(jù)集上的橫向定量比較實驗結果如表3、表4所示。

表3 增量數(shù)據(jù)為10%時對比試驗結果

表4 增量數(shù)據(jù)為20%時對比試驗結果

由表3可知，在增量數(shù)據(jù)為10%時，W-TIOC-TWD算法在LetterABC、LetterAGI、 Pendigists1469數(shù)據(jù)集上的聚類準確率比TIOC-TWD算法和OFCMD算法有明顯提高，其余3個數(shù)據(jù)集上的準確率也和最高值相差無幾。

由表4可知，在增量數(shù)據(jù)為20%時，W-TIOC-TWD算法在數(shù)據(jù)集LetterABC、LetterAGI、Banknote、Pendigists1469上的聚類準確率比其余算法要高，而在數(shù)據(jù)集Waveform、Pendigists1234上，本文算法準確率也與最高值相差無幾。

通過增量占比為40%，模擬連續(xù)4次10%以及兩次20%的增量聚類實驗結果可知，將各屬性的重要程度以加權方式體現(xiàn)在距離度量計算中，可以有效加強重要屬性對聚類結果的積極影響，消除冗余屬性對聚類結果的消極影響，從而提高聚類準確率，由此驗證了本文算法的有效性。

結論2：通過在UCI真實數(shù)據(jù)集的實驗可知，在增量數(shù)據(jù)為10%和20%時，本文W-TIOC-TWD算法在聚類準確率上要優(yōu)于其余兩種算法。通過本文算法與其余兩種算法實驗對比，證明了本文提出的加權距離公式有效解決了數(shù)據(jù)各屬性重要程度不同的問題，驗證了本文所提出的距離加權公式的有效性。

4 結語

在分析增量聚類以及軟聚類算法研究現(xiàn)狀基礎上，為降低現(xiàn)有算法的時間復雜度，解決現(xiàn)有算法未考慮數(shù)據(jù)各屬性重要度這一問題，提出一種加權三支決策增量軟聚類算法（W-TIOC-TWD）。該算法將屬性重要度考慮到距離度量公式中，給出一種基于屬性重要度的加權距離度量方法。將各屬性重要度的不同體現(xiàn)在算法中，并提出離群點這一概念。利用隔離離群點的方法降低算法的時間復雜度，并從算法的角度分析這一行為的有效性。通過在人工數(shù)據(jù)集實驗可知，W-TIOC-TWD算法具有使類簇增長、合并以及發(fā)現(xiàn)新類簇的功能。通過UCI真實數(shù)據(jù)集上實驗，證明本文算法在聚類準確率上優(yōu)于其余兩種算法，證明W-TIOC-TWD算法的有效性。

雖然本文在一定程度上提高了聚類性能，但仍有很多方面值得進一步研究：①本文所提算法中涉及到的參數(shù)，均是通過插值法選取最優(yōu)參數(shù)，在接下來的工作中，可以考慮采用貝葉斯理論、層次分析法、優(yōu)化算法、博弈論、統(tǒng)計學等方法解決最優(yōu)參數(shù)選擇問題;②考慮到當下數(shù)據(jù)具有格式多樣、結構復雜、數(shù)量龐大、實時更新等特點，進一步提高本文算法的普適性尤為重要;③本文算法利用三支決策的思想對數(shù)據(jù)進行聚類，但未將算法應用到實際推薦系統(tǒng)中，下一步研究可考慮將W-TIOC-TWD算法應用到包含增量和重疊數(shù)據(jù)的推薦系統(tǒng)中。

參考文獻：

[1] 海沫. 大數(shù)據(jù)聚類算法綜述[J]. 計算機科學，2016，43（S1）：380-383.

[2] YU H， ZHANG C， WANG G. A Tree-based incremental overlapping clustering method using the three-way decision theory[J]. Knowledge-Based Systems，2016， 91（C） ：189-203.

[3] SANJAY CHARKRABORTH，NAGWANI N K. Analysis and study of incremental k-means clustering algorithm[J]. High Performance Architecture and Grid Computing， 2011（169）： 338-341.

[4] PHAM D T，DIMOV S S，NGUYEN C D. An incremental k-means algorithm[J]. ARCHIVE Proceedings of the Institution of Mechanical Engineers Part C Journal of Mechanical Engineering Science 1989-1996 （vols 203-210）， 2004， 218（7）：783-795.

[5] ALM S，KUMAR K R S. A density based dynamic data clustering algorithm based on incremental dataset[J].? Journal of Computer Science，2012，（5）：656-664.

[6] 劉青寶，侯東風，鄧蘇，等. 基于相對密度的增量式聚類算法[J]. 國防科技大學學報， 2006，28（5）：73-79.

[7] LEI G，YU X，YANG X，et al. An incremental clustering algorithm based on grid[C]. Fuzzy Systems and Knowledge Discovery （FSKD），2011 Eighth International Conference on，2011：1099-1103.

[8] 劉卓，楊悅，張健沛，等. 不確定度模型下數(shù)據(jù)流自適應網(wǎng)格密度聚類算法[J]. 計算機研究與發(fā)展，2014， 51（11）：218-221.

[9] LABROCHE N. Online fuzzy medoid based clustering algorithms[J].? Neurocomputing，2014（126）： 141-150.

[10] PETERS G，WEBER R，NOWATZKE R. Dynamic rough clustering and its applications[J]. Applied Soft Computing，2012，12（10）： 3193-3207.

[11] PéREZ-SUáREZ A，MARTíNEZ-TRINIDAD J F，CARRASCO- OCHOA J A，et al. An algorithm based on density and compactness for dynamic overlapping clustering[J].? Pattern Recognition， 2013，46（11）： 3040-3055.

[12] YAO Y Y. The? superiority of three-way decisions in probabilistic? rough set models[J]. Information Sciences，2011，181（6）：1080-1096.

[13] 于洪，毛傳凱. 基于k-means的自動三支決策聚類方法[J].? 計算機應用，2016，36（8）： 2061-2065.

[14] BARBARá D，LI Y，COUTO J. Coolcat： an entropy-based algorithm for categorical clustering[J]. Giteseerx， 2002，1（4）：582-589.

[15] LABROCHE N. Online fuzzy medoid based clustering algorithms[J].? Neurocomputing，2014（126）：141-155.

[16] 周漩，張鳳鳴，惠曉濱，等. 基于信息熵的專家聚類賦權方法[J].? 控制與決策，2011，26（1）：153-156.

[17] KOHAVI？R，？BECKER B.Machine learning repository[EB/OL].? [2014-11-16]. http：// archive.ics.uci. edu/ ml/.

（責任編輯：杜能鋼）