三支聚類分析

于洪

?

三支聚類分析

于洪*

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

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

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

引言

聚類是一種無監督的學習方法被廣泛地應用到各個領域，如信息檢索、圖像分析、生物信息處理、網絡結構分析以及很多其它應用[1]。一般地，現實世界充滿了不確定性。例如，在網絡服務中，用戶的興趣是會改變的，興趣社區也是多變的。

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

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

圖1 數據集示意圖

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

圖2 聚類示意圖

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

圖3 二支聚類結果

圖4 三支聚類結果

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

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

1 相關工作

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

模糊聚類中假定一個類由一個模糊集合來表示，模擬了一個逐漸變化的邊界[2]。模糊聚類定量地描述類的邊界，而不是定性地描述類的邊界，不能很好地反映聚類結果的結構特征。為了解決這個問題Lingras和他的合作者研究了粗糙聚類和區間聚類[3,4]。Yao等人[5]用區間集而不是單一的集合來表示一個類。Chen和Miao[6]在Rough k-means中，通過合并區間集來表示聚類。基本思想是用一對上邊界和下邊界來表示一個類。采用一對集合來表示一個類，定性地描述一個類。

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

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

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

2 三支聚類分析框架

2.1 三支聚類表示

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

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

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

(2)

這些子集滿足如下性質：

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

三支聚類結果表示如下所示：

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

(6)

2.2 基于評價函數的三支聚類模型

本小節介紹一種基于評價函數的三支聚類模型，根據評價函數和評價函數上的一對決策閾值來產生三個域。

(8)

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

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

3.1 對象和多個類之間的劃分關系

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

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

3.2 對象和單個類的關系

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

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

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

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

3.3 算法描述

輸入：數據集、近鄰數。

Step1 初始化，指定距離數目；

Step5 如果聚類中心不發生變化，轉自Step6；否則轉至Step3；

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

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

Step8 算法結束，輸出結果：

3.4 實驗結果

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

圖8 數據集 D2上實驗結果

圖9 數據集 D3上實驗結果

圖10 數據集 D4上實驗結果

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

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

4 三支聚類研究

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

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

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

（3）針對動態數據或不完備數據，如何設計更高效合理的算法也是一個研究重點。

（4）三個域的應用。可以將三支決策聚類算法應用到實際問題中，比如社交網絡、網絡營銷、電子商務、推薦系統等。

[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智能、數據挖掘。

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