三支聚類分析

于洪

?

三支聚類分析

于洪*

(重慶郵電大學(xué)計算智能重慶市重點實驗室，重慶 400065)

受三支決策理論的啟發(fā)，該文介紹了一種新的聚類策略，即三支決策聚類，簡稱三支聚類。在三支聚類分析中，類簇不再用一個集合表示，而是用兩個集合來表示。這兩個集合分別叫做這個類的核心域和邊緣域。位于核心域的對象是類中的典型對象；位于邊緣域中的對象是類中的邊緣對象，他們可能屬于這個類，也可能不屬于這個類。這種三支表示既能夠處理傳統(tǒng)的硬聚類也能處理軟聚類任務(wù)。隨后，該文介紹了基于評價函數(shù)的三支決策聚類模型，并給出一種基于k-means的三支決策聚類方法作為實例分析。最后，該文綜述了近年來三支聚類方面的研究成果以及發(fā)展方向。

聚類；三支決策；不確定性；硬聚類；軟聚類

引言

聚類是一種無監(jiān)督的學(xué)習(xí)方法被廣泛地應(yīng)用到各個領(lǐng)域，如信息檢索、圖像分析、生物信息處理、網(wǎng)絡(luò)結(jié)構(gòu)分析以及很多其它應(yīng)用[1]。一般地，現(xiàn)實世界充滿了不確定性。例如，在網(wǎng)絡(luò)服務(wù)中，用戶的興趣是會改變的，興趣社區(qū)也是多變的。

人工智能和認(rèn)知科學(xué)的研究揭示了人類智能的特征，即在認(rèn)識和處理現(xiàn)實世界問題時，人類經(jīng)常從不同的層面或者粒度來觀察和分析同一問題。聚類的過程反映了在不同層面做決策的過程。也就是說，聚類是一個在一定粒度層面確定對象屬于或者不屬于一類的過程。

設(shè)由若干對象組成一個論域，如圖1 所示。對應(yīng)于最細(xì)粒度的聚類結(jié)果是每個對象單獨成為一個類；對應(yīng)于更粗粒度的聚類結(jié)果是這里有兩個類；對應(yīng)于最粗粒度的聚類結(jié)果是所有的對象組成一個類。聚類過程中如果信息足夠充分，可以得到某一粒度下確定的聚類結(jié)果；如果信息不過充分就無法判定對象是否確定屬于某個類，需要更多的信息來做最終的決策。

圖1 數(shù)據(jù)集示意圖

觀察圖1在一定的粒度層面下，論域中存在兩個明顯的類。如圖2 所示黃色部分為一個類，紅色部分為一個類。觀察對象x1和x2，它們可能屬于黃色的類也可能屬于紅色的類。一個解決方法是把這些對象確切地劃分到不同的類中，如軟聚類、重疊聚類或者模糊聚類。換而言之，一個對象可以屬于不同的類。

圖2 聚類示意圖

觀察對象x3和x4它們應(yīng)該屬于黃色的類，x5和x6應(yīng)該屬于紅色的類，如圖3所示。這是一種典型的二支決策聚類結(jié)果，即對象確定屬于一個類或則確定不屬于一個類。然而，二支決策聚類結(jié)果不能直觀地反映對象x3和x4是黃色類的邊緣對象這一事實。同理，對象x5和x6是紅色類的邊緣對象。圖4展示了三支聚類結(jié)果，x1、 x2、x3和x4被劃分到黃色類的邊緣區(qū)域。x1、 x2、x5和x6被劃分到紅色類的邊緣區(qū)域。

圖3 二支聚類結(jié)果

圖4 三支聚類結(jié)果

人們通常根據(jù)已有的信息和證據(jù)做決策。然而，信息的獲取通常是一個動態(tài)的過程。由于當(dāng)前信息不充分，不能確切地知道對象的類別歸屬，提供了另外一種方案來處理這種帶有不確定性現(xiàn)象的聚類任務(wù)。對于那些當(dāng)前很難做出決策的對象，根據(jù)當(dāng)前知識系統(tǒng)的規(guī)則，可以提供一種二支決策結(jié)果。也可以提供一種三支決策結(jié)果，對于信息充分的對象做出確切的決策；對于信息不夠充分的對象待獲取信息后作進(jìn)一步?jīng)Q策。這是一種典型的三支決策思想。

三支決策方法用三個域而不是兩個域來表示概念。盡管在其它領(lǐng)域中得到研究，三支決策方案并沒有明確的機器學(xué)習(xí)和規(guī)則歸納原理。在基于三支決策的聚類分析中，對象和類存在三種關(guān)系：1)對象確定屬于一個類；2)對象確定不屬于一個類；3)對象可能屬于也可能不屬于一個類。這是一種典型的三支決策過程來確定對象和類之間關(guān)系。這些關(guān)系促使在本文中引入三支決策思想來處理聚類分析問題。

1 相關(guān)工作

聚類分析的一個廣泛潛在假設(shè)是一個類可以用一個單一的集合來表示，或者說類的邊界是確定的、清晰的。類的邊界是確定的可能更便于聚類結(jié)果的分析與應(yīng)用，但是在一些具體應(yīng)用中也顯得不是那么合理。比如，在興趣網(wǎng)絡(luò)中，一方面一個成員很可能有多個興趣愛好，另外一方面，一個成員對這些不同的興趣的愛好程度是不同的。

模糊聚類中假定一個類由一個模糊集合來表示，模擬了一個逐漸變化的邊界[2]。模糊聚類定量地描述類的邊界，而不是定性地描述類的邊界，不能很好地反映聚類結(jié)果的結(jié)構(gòu)特征。為了解決這個問題Lingras和他的合作者研究了粗糙聚類和區(qū)間聚類[3,4]。Yao等人[5]用區(qū)間集而不是單一的集合來表示一個類。Chen和Miao[6]在Rough k-means中，通過合并區(qū)間集來表示聚類?；舅枷胧怯靡粚ι线吔绾拖逻吔鐏肀硎疽粋€類。采用一對集合來表示一個類，定性地描述一個類。

本文的一個目的就是采用兩個集合來表示一個類，從而來擴展聚類分析。這促使引入三支聚類分析。位于核心域的對象是類中的典型對象；位于邊緣域的對象是類中的邊緣對象。換而言之，一個類用一個核心對象集合和一個邊緣對象集合來表示。

三支決策思想被廣泛地應(yīng)用到許多領(lǐng)域和學(xué)科，包括醫(yī)療決策、社會判斷原理、統(tǒng)計學(xué)中的假設(shè)測試、管理科學(xué)以及論文評審過程。因此，姚一豫教授[7][8]介紹并研究了三支決策的概念，包括正規(guī)則、邊界規(guī)則和負(fù)規(guī)則。三支決策由三個域組成，對不同的域采用不同處理方式和決策方式。

最近，三支決策方法在一些領(lǐng)域中取得了一定成果，如決策、來及郵件過濾、聚類分析等等[9-13] [14-16]。也做了一些基于三支決策的研究工作[16,17- 19] [20-21]。本文首先對三支聚類進(jìn)行形式化描述，然后給出一個基于k-means的三支決策聚類實例。

2 三支聚類分析框架

2.1 三支聚類表示

Vladimir Estivill-Castro指出類不能夠被精確定義，這也是為什么有如此多的聚類算法的原因之一[4]。類的廣泛命名是：一組數(shù)據(jù)對象。聚類就是把對象進(jìn)行分組，相較于不同組中的對象同一組中的對象更相似。

在現(xiàn)有的研究工作中，聚類結(jié)果中的類被表示為一個單一的集合，即。從決策的觀點來看，單一的集合表示集合中的對象確定屬于這個類，不在該集合中的對象確定不屬于這個類。這是一種典型的二支決策結(jié)果。硬聚類中一個對象只能屬于一個類；軟聚類中對象可以屬于多個類。然而，這種表示并沒有表明那些對象可能屬于這個類，不能夠反映對象對類形成的影響程度。如前文所述，用三個域來表示一個類比用一個集合來表示一個類更合適。這直接產(chǎn)生了基于聚類解釋的三支決策。

相對于一般的二支決策的類的表示形式，提出類的三支表示形式：

(2)

這些子集滿足如下性質(zhì)：

另一方面，定義一個類，滿足如下性質(zhì)：

三支聚類結(jié)果表示如下所示：

顯然，一個二支聚類結(jié)果可以表示如下：

(6)

2.2 基于評價函數(shù)的三支聚類模型

本小節(jié)介紹一種基于評價函數(shù)的三支聚類模型，根據(jù)評價函數(shù)和評價函數(shù)上的一對決策閾值來產(chǎn)生三個域。

(8)

基于前文的表述，可以用如下公式來表示軟聚類和硬聚類：

3 一種基于k-means的三支聚類方法

3.1 對象和多個類之間的劃分關(guān)系

這一小節(jié)提出一種基于k-means的三支決策聚類算法。在聚類分析中可以從以下兩個方面來考慮一個類的組成：一方面考慮類和類之間的關(guān)系，如果類中對象只和一個類關(guān)系緊密，那么該對象確定屬于這個類，屬于類的域；如果對象和多個類的關(guān)系都在一定程度上緊密，那么這個對象可能同時屬于這幾個類，是類中的非典型對象，應(yīng)該同時屬于這幾個類的域。另一方面，考慮類中對象之間的關(guān)系，類中有大部分對象相互之間聯(lián)系很緊密，構(gòu)成類的核心部分，屬于類的域，少部分對象和類中大部分對象之間的聯(lián)系相對較弱，是類的關(guān)鍵部分，屬于該類的域。

傳統(tǒng)的硬聚類方法要求對象只能劃分到唯一確定的類中，但是存在對象和多個類簇都有著密切聯(lián)系的情況，這種情況下對象可能同時屬于這幾個類簇。這些對象可能是類間的重疊部分，這時把這些對象劃分到這些類的域中更為合理，如圖5所示。

3.2 對象和單個類的關(guān)系

圖6 同一類中不同對象之間的差異性

同一類中的對象之間的關(guān)系也會存在強弱不同的情況，對類的形成起著不同的作用。一個類域中的對象為類中的核心部分，域中的對象是類中的重要部分，如圖6所示。

直觀上，類中的對象可以分為兩個部分，即圖中呈三角形的那部分對象是一個部分，呈圓形的那部分對象是另一個部分。圖中少數(shù)呈三角形的對象明顯遠(yuǎn)離呈圓形的對象，呈三角形的那部分對象可能屬于類,也可能不屬于類。對類中的對象進(jìn)一步區(qū)分，可以把呈三角形的對象劃分到類的域中，呈圓形的對象劃分到類的域中。

基于以上考慮，文中采用類中對象到類中心的距離的差值對類中對象作進(jìn)一步區(qū)分?？疾閷ο蠛皖?，依次計算對象到類中心的距離，并按值從小到大排列，得到呈升序排列的序列、、、…、、。然后，依次計算這些距離的差值、、…、，找到第一個距離差值最大的對象對，和，那么把對象劃分到類的域,把及其后的對象劃分到類的域中。

3.3 算法描述

輸入：數(shù)據(jù)集、近鄰數(shù)。

Step1 初始化，指定距離數(shù)目；

Step5 如果聚類中心不發(fā)生變化，轉(zhuǎn)自Step6；否則轉(zhuǎn)至Step3；

Step6 考查對象和類、、。如果，那么。

Step7 對于類中剩余非域中對象，根據(jù)差值排序法，找到第一個距離差值最大的對象對，和，把及其后的對象劃分到；

Step8 算法結(jié)束，輸出結(jié)果：

3.4 實驗結(jié)果

為了直觀展示文中提出三支決策聚類和傳統(tǒng)二支聚類算法的不同之處，在4個二維人工數(shù)據(jù)集D1 、D2 、D3和 D4上進(jìn)行行實驗，實驗結(jié)果如圖7-10所示。

圖8 數(shù)據(jù)集 D2上實驗結(jié)果

圖9 數(shù)據(jù)集 D3上實驗結(jié)果

圖10 數(shù)據(jù)集 D4上實驗結(jié)果

從圖7-10可知：在D1 數(shù)據(jù)集上，文中算法找到了3個類之間的重疊部分，把重疊部分對象分別劃分到相應(yīng)類的邊緣域中。數(shù)據(jù)集D2中的3個類彼此分離沒有重疊部分。文中的三支決策聚類方法并沒有強制找出類之間的重疊部分，即不存對象同時屬于多個類的現(xiàn)象，而是把每個類中離該類中大部分對象較遠(yuǎn)的對象，劃分到類的邊緣域中。數(shù)據(jù)集D3中的4個類彼此分離沒有重疊部分。同樣，文中的三支決策聚類方法并沒有強制找出類之間的重疊部分，即不存對象同時屬于多個類的現(xiàn)象，而是把每個類中離該類中大部分對象較遠(yuǎn)的對象劃分到類的邊緣域中。在D4 數(shù)據(jù)集上，文中算法找到了2個類之間的重疊部分，把重疊部分對象分別劃分到相應(yīng)類的邊緣域中。同時，兩個類中存在少部分對象遠(yuǎn)離類中的其它對象，文中算法把這些對象也劃分到相應(yīng)類的邊緣域中。

通過實驗可以驗證文中提出的三支決策聚類方法是有效的。文中提出算法不僅能夠找出類間的重疊部分，同時還能根據(jù)類中對象之間的緊密程度對類中對象做進(jìn)一步區(qū)分，得到更加豐富的信息，便于對聚類結(jié)果的進(jìn)一步分析。

4 三支聚類研究

本文主要闡述并解釋了三支決策聚類問題。傳統(tǒng)的聚類分析中通常將一個類簇用一個集合來表示，通過兩個域來描述一個類簇，是一個典型的二支決策問題，即對象確定屬于某個類簇或確定不屬于某個類簇。但實際應(yīng)用中，存在著很多情況是難以給出明確二支決策結(jié)果的。受三支決策理論的啟發(fā)，本文提出用兩個集合即三個域來描述一個類簇：核心域中數(shù)據(jù)對象確定屬于該類簇，瑣碎域中數(shù)據(jù)對象確定不屬于該類簇，邊緣域中數(shù)據(jù)對象可能屬于也可能不屬于該類簇。這種表示方法可以更加直觀地展示數(shù)據(jù)對象確定屬于或可能屬于某個類簇。通過對邊界域中數(shù)據(jù)對象進(jìn)一步處理，可以更加清晰地了解到其對所屬類簇的影響程度。認(rèn)為關(guān)于三支聚類還有以下幾方面的關(guān)鍵問題：

（1）三支聚類的表示。通過區(qū)間集、決策粗糙集來對三支決策聚類進(jìn)行表示的相關(guān)工作已經(jīng)取得了一定的進(jìn)展。接下來，可以考慮通過模糊集、陰影集以及其他的模型來對三支聚類進(jìn)行表示。針對不同聚類問題，不同的表示方法會得到不同的結(jié)果。

（2）三支聚類方法的研究。通過二支決策擴展得到三支決策的方法是非常合理的。但是閾值的設(shè)定以及類簇個數(shù)的確定對三支決策聚類算法的效率會產(chǎn)生很大的影響。

（3）針對動態(tài)數(shù)據(jù)或不完備數(shù)據(jù)，如何設(shè)計更高效合理的算法也是一個研究重點。

（4）三個域的應(yīng)用?？梢詫⑷Q策聚類算法應(yīng)用到實際問題中，比如社交網(wǎng)絡(luò)、網(wǎng)絡(luò)營銷、電子商務(wù)、推薦系統(tǒng)等。

[1] XU R. Survey of clustering algorithms [J]. Neural Networks IEEE Transactions on, 2005, 16(3):645 - 678.

[2] Hoppner F, Klawonn F, Kruse R, et al. Fuzzy cluster analysis: methods for classification, Data Analysis and Image Recognition [J]. Journal of the Operational Research Society, 2000, 51(6):769-770.

[3] LINGRAS P, YAN R. Interval clustering using fuzzy and rough set theory[C]// In Proc.2004 IEEE Annual Meeting. Fuzzy Information, Ban, Alberta, 2004: 780-784.

[4] LINGRAS P, WEST C. Interval set clustering of web users with rough k-Means [J]. Journal of Intelligent Information Systems, 2004, 23(1):5-16.

[5] YAO Y Y, Lingras P, Wang R, et al. Interval set cluster analysis: a re-formulation[C]// Rough Sets, Fuzzy Sets, Data Mining and Granular Computing, International Conference, India: Delhi, 2009: 15-18.

[6] CHEN M, MIAO D Q. Interval set clustering [J]. Expert Systems with Applications, 2011, 38(4): 2923-2932.

[7] YAO, Y Y. An outline of a theory of three-way decisions[C]// Rough Sets and Current Trends in Computing,8th International Conference, RSCTC2012 . Berlin Heidelberg : Springer Press , 2012: 1-17.

[8] YAO Y Y. Three-way decisions and cognitive computing [J]. Cognitive Computation, 2016:1-12.

[9] Azam N, Yao J T. Analyzing uncertainties of probabilistic rough set regions with game-theoretic rough sets[J]. International Journal of Approximate Reasoning, 2013, 55(1):142-155.

[10] LIANG D, LIU D. A novel risk decision making based on decision-theoretic rough sets under hesitant fuzzy information [J]. IEEE Transactions on Fuzzy Systems, 2015, 23(2):237-247.

[11] ZHOU B, YAO, LUO J. Cost-sensitive three-way email spam filtering [J]. Journal of Intelligent Information Systems, 2014, 42(1):19-45.

[12] CHEN H, LI T, LUO C, et al. A decision-theoretic rough set approach for dynamic data mining [J]. IEEE Transactions on Fuzzy Systems, 2015, 23(6):1958-1970.

[13] LI Y, ZHANG Z H, CHEN W B, et al. TDUP: an approach to incremental mining of frequent item sets with three-way-decision pattern updating [J]. International Journal of Machine Learning & Cybernetics, 2015:1-13.

[14] ZHANG , ZOU H, CHEN X, et al. Cost-sensitive three-way decisions model based on CCA[M]// Rough Sets and Current Trends in Computing. Springer International Publishing, 2014:172-180.

[15] LI H X, ZHOU X Z. Risk decision making based on decision-theoretic Rough Set: A three-way view decision model [J]. International Journal of Computational Intelligence Systems, 2013, 4(1):1-11.

[16] YU H, LIU Z G, WANG G Y. An automatic method to determine the number of clusters using decision-theoretic rough set [J]. International Journal of Approximate Reasoning, 2014, 55(1):101-115.

[17] YU H, WANG Y. Three-way decisions method for overlapping clustering[M]// Rough Sets and Current Trends in Computing. Springer Berlin Heidelberg, 2012:277-286.

[18] YU H, ZHANG C, HU F. An incremental clustering approach based on three-way decisions [M]// Rough Sets and Current Trends in Computing. 2014:152-159.

[19] YU H, SU T, ZENG X H. A three-way decisions clustering algorithm for incomplete data [M]// Rough Sets and Knowledge Technology. Springer International Publishing, 2014:765-776.

[20] YU H, JIAO P, WANG G Y, et al. Categorizing overlapping regions in clustering analysis using three-way decisions[C]//IEEE/WIC/ACM International Joint Conferences on Web Intelligence. 2014:350-357.

[21] YU H, ZHANG C, WANG G Y. A tree-based incremental overlapping clustering method using the three-way decision theory [J]. Knowledge-Based Systems, 2016, 91:189-20

Three-way Cluster Analysis

YU Hong*

(Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

This paper proposes a new clustering strategy, named three-way decision clustering, or simply "three-way cluster" for short, which is inspired by the theory of three-way decisions. In the three-way cluster analysis, a cluster is represented by two sets instead of a single set, and the two sets called the core region and fringe region. Objects in the core region are typical elements of the cluster. Objects in the fringe region are fringe elements of the cluster, and they might or might not belong to the cluster. The new strategy has the ability to deal with the conventional hard or soft clustering. Besides, this paper proposes an evaluation-based three-way decision clustering model and illustrates an approach of three-way clustering based on k-means as an instance. The paper also reviews recent three-way clustering studies and points out the future research directions.

clustering; three-way decision; uncertainty; hard clustering; soft clustering

1672-9129(2016)01-00032-06

TP391

A

2016-07-05；

2016-07-21。

三支決策聚類理論模型與方法研究（61379114）。

于洪(1972-)，女，重慶，教授，博士，主要研究方向：粗糙集、三支決策、智能信息處理、Web智能、數(shù)據(jù)挖掘。

(*通信作者電子郵箱：yuhongcq@aliyun.com)