基于粗糙集理論的模糊C-means高維數(shù)據(jù)聚類算法

朱付保， 徐顯景， 白慶春， 朱顥東

(鄭州輕工業(yè)學(xué)院 計算機(jī)與通信工程學(xué)院， 鄭州 450002)

?

基于粗糙集理論的模糊C-means高維數(shù)據(jù)聚類算法

朱付保， 徐顯景， 白慶春， 朱顥東*

(鄭州輕工業(yè)學(xué)院 計算機(jī)與通信工程學(xué)院， 鄭州 450002)

模糊C-means算法是一種重要的聚類分析算法，但是在數(shù)據(jù)維數(shù)較高的情況下，該算法計算量急劇上升從而導(dǎo)致其效率較低.針對這一問題，提出了一種基于粗糙集理論的模糊C-means高維數(shù)據(jù)聚類算法，該算法在傳統(tǒng)模糊C-means算法的基礎(chǔ)上引入了粗糙集屬性約簡的理念，通過對數(shù)據(jù)集屬性的約簡，提取出對分類影響較大的屬性集而摒棄與分類無關(guān)的屬性，進(jìn)而在聚類過程中只計算屬性約簡結(jié)果集中的屬性，從而減少聚類過程的工作量、提高聚類效率.理論分析和實驗結(jié)果表明，該算法在處理高維數(shù)據(jù)時較高效.

粗糙集； 模糊C均值； 高維數(shù)據(jù)； 聚類

聚類分析是當(dāng)前數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的一個重要手段，聚類分析的目的是將數(shù)據(jù)庫中的實體對象劃分為由類似對象組成的多個類，使得同一類中的對象具有最大的相似度，不同類中的對象具有最大的相異度.模糊C-means算法是一種常用的聚類分析方法，它被應(yīng)用于諸多領(lǐng)域并被廣泛關(guān)注[1-4].模糊C-means算法雖然在處理低維數(shù)據(jù)方面是有效的，但是由于在每次迭代的過程中都要對整個數(shù)據(jù)集進(jìn)行操作，因此對于復(fù)雜的高維數(shù)據(jù)其執(zhí)行起來效率較低[5].在高度信息化的今天，我們所面對和掌握的數(shù)據(jù)越來越復(fù)雜，數(shù)據(jù)的維度也越來越高[6]，因此對高維數(shù)據(jù)聚類執(zhí)行效率不理想的問題亟待解決.在高維數(shù)據(jù)諸多的屬性中，各個屬性對于知識發(fā)掘的重要程度是不相同的，其中一部分屬性起到了決定性作用，但對于另外一部分屬性而言，他們對于分類能力是多余的.粗糙集理論[7]提出了有關(guān)屬性約簡[8-11]的概念，其目的是在保留基本屬性及其對各對象分類能力不變的前提下，將那些重復(fù)的、多余的屬性以及屬性值予以刪除，從而實現(xiàn)對屬性的精簡和提煉.對于高維數(shù)據(jù)而言，屬性約簡是一項很有意義且有必要的工作，通過對數(shù)據(jù)庫的屬性約簡可以為數(shù)據(jù)挖掘和知識發(fā)現(xiàn)減少工作量[12-13].同時還能夠?qū)⒛切δ繕?biāo)知識發(fā)掘而言無關(guān)緊要的屬性排除在外，避免這些無關(guān)的屬性擾亂挖掘的結(jié)果.

本文針對模糊C-means算法在處理高維數(shù)據(jù)時執(zhí)行效率較低的問題，提出了基于粗糙集理論的模糊C-means高維數(shù)據(jù)聚類算法.實驗表明，在處理高維數(shù)據(jù)時，該算法在保證聚類效果的基礎(chǔ)上，還能夠有效提高聚類效率.

1 模糊C-means算法(FCM)基本原理

設(shè)樣本集合X={x1，x2，…，xn}?RD，通過最小化目標(biāo)函數(shù)：

(1)

其中，C表示該樣本集合要劃分的類別個數(shù)，dik=‖vi-xk‖表示樣本集合中第k個樣本數(shù)據(jù)到第i個聚類中心的歐幾里得距離，m∈[1，+∞)是表示模糊程度的一個加權(quán)指數(shù)，μik表示第k個樣本對象對第i個類的隸屬度函數(shù)，其滿足：

(2)

具體算法如下：

1)確定聚類數(shù)目C，同時初始化聚類中心Vi和加權(quán)指數(shù)m.

2)對第t次迭代，根據(jù)當(dāng)前的聚類中心，用公式

計算出新的隸屬度函數(shù)；用公式

計算出新的聚類中心.

2 粗糙集理論

粗糙集理論是一種分析、研究不確定及數(shù)據(jù)不完整或不精確的知識分析方法[14].對于不精確概念，粗糙集用上近似和下近似這一對精確的概念來予以表示.粗糙集理論的主要思想是在保持分類能力不變的情況下，通過對屬性的約簡導(dǎo)出問題的決策或分類規(guī)則[15-17].

2.1 知識表達(dá)系統(tǒng)

知識表達(dá)系統(tǒng)S可以表示為一個有序的四元組S={U，A，V，F(xiàn)}，其中U={x1，x2，…，xn}是論域，是全體樣本的一個非空有限集合.A=C∪D是屬性的非空有限集合，且C∩D=φ，C→D，C為條件屬性集合，D為決策屬性集合.V為屬性值的集合，Va表示屬性a的取值范圍，a∈A.f是一個信息函數(shù)，f:U×A→V，用于確定每一個樣本對象屬性值，即?a∈A，x∈U，fa(x) ∈Va.

2.2 不可分辨關(guān)系

兩個對象的不可分辨關(guān)系也被稱作等價關(guān)系，指的是兩個對象能夠被完全相同的屬性所描述.對任意屬性子集B?A，如果對象xi，xj∈U，?a∈B當(dāng)且僅當(dāng)f(xi，a)=f(xj，a)時，xi與xj是不可分辨關(guān)系，記作Ind(B).Ind(B)是樣本集合U上的等價關(guān)系，它是屬性子集B對樣本集合U的一個劃分.

2.3 知識庫和上、下近似集

1)在粗糙集理論中，由不可分辨的對象所組成的樣本子集X(X?U)表示的是U中的一個概念，同時概念的族集表示的是U中的知識，則樣本集合U上的知識庫表現(xiàn)為U上的分類族.假設(shè)U為非空有限集合，A是U上的等價關(guān)系集合，則知識庫可定義為K={U，A}.

2)上、下近似集

設(shè)特征集R，樣本子集X?U，滿足：

R-(X)={x∈U，[x]R∩X≠φ}，

R-(X)={x∈U，[x]R?X}，

其中，[x]R表示的是關(guān)于所有知識R的基本集合中，包含x樣本對象的集合.分別稱R-(X)和R-(X)為樣本子集X的R上近似集和R下近似集.R-(X)判斷的是基于特征集R論域U中可能屬于集合X的元素所組成的集合，R-(X)判斷的是基于特征集R論域U中肯定屬于集合X的元素所組成的集合.

2.4 屬性約簡

屬性約簡其主要目的是確保知識在分類能力基本不變的前提下，去除掉冗余的或不重要的條件屬性.假定A是一個等價關(guān)系族，a∈A，當(dāng)Ind(A)=Ind(A-{a})，那么條件屬性a被認(rèn)為是可以省略的，否則a不可被省略.當(dāng)?a∈A都不能被省略時，A可被稱作是獨立的.假設(shè)B?A，若B是獨立的并且Ind(B)=Ind(A)，那么可以稱B為A的一個約簡.

2.5 區(qū)分矩陣

區(qū)分矩陣的定義：設(shè)U={x1，x2，…，xn}為論域，fa(xi)為對象xi在屬性a上的取值，C為條件屬性集，D為決策屬性集，屬性集合A=C∪D.則區(qū)分矩陣[Mij]n×n的定義如下：

(3)

由上式可知，Mij表示的是能夠區(qū)分樣本對象xi和xj的所有屬性的集合，當(dāng)xi與xj同屬于一個決策類時Mij的取值為空.同時區(qū)分矩陣是一個card(U)×card(U)的對稱方陣，因此在進(jìn)行運(yùn)算時只需考慮區(qū)分矩陣的上三角或下三角即可.

核屬性就是區(qū)分矩陣中所有單個屬性元素組成的集合，是進(jìn)行決策或劃分時不可或缺的屬性，核屬性記作：

(4)

3 高維數(shù)據(jù)屬性約簡模型

初始化決策表記作T={U，R，C，D}，C={c1，c2，…，cm}是條件屬性集，D=g0gggggg是決策屬性集，R=C∪D，屬性集C的約簡結(jié)果集記作Reduce.

模型輸入數(shù)據(jù)：決策表T；

模型輸出數(shù)據(jù)：約簡結(jié)果集Reduce.

定義1Q和R為樣本集合U上的等價關(guān)系，Q的R正域記作：PosR(Q)=∪R_(Q)，PosR(Q)是論域U中所有根據(jù)分類Ind(R)所表達(dá)的知識可以準(zhǔn)確劃分到分類Ind(Q)中的對象的集合.設(shè)?r∈R，若PosR(Q)=PosR-{r}(Q)，則認(rèn)為屬性r是可去除的.

定義2屬性的區(qū)分度指的是屬性對于對象分類的影響程度，區(qū)分度越大說明對于對象的影響力越大，反之說明影響力較小，屬性的區(qū)分度用屬性在區(qū)分矩陣各元素中的出現(xiàn)頻率來標(biāo)識.設(shè)屬性a∈A，則屬性a的區(qū)分度可定義為：

(5)

根據(jù)模糊集理論的相關(guān)概念，首先生成有關(guān)決策表T的區(qū)分矩陣[Mij]m×n，進(jìn)而從區(qū)分矩陣中選擇元素值為單一屬性的元素組成核屬性集Core(A)，如果

(6)

則令屬性約簡結(jié)果集Reduce=Core(A)；如果不等，根據(jù)屬性區(qū)分度的定義，求出A-Core(A)中區(qū)分度最大的屬性加入到Core(A)中，直到兩者相等為止；令屬性約簡結(jié)果集Reduce=Core(A)，輸出Reduce.

4 基于粗糙集理論的模糊C-means高維數(shù)據(jù)聚類算法

4.1 算法核心思想

4.2 算法描述

通過對高維數(shù)據(jù)屬性約簡模型和算法核心思想的定義說明，基于粗糙集理論的FCM聚類算法具體描述如下：

初始化數(shù)據(jù)集X={x1，x2，…，xn}，?xi∈RD，設(shè)置聚類中心數(shù)目C和閾值ε，初始化各樣本到C個聚類中心的隸屬度矩陣U(0)；O(|n|*|D|+|n2|+|n|*|C|.

1)依據(jù)數(shù)據(jù)集X生成區(qū)分矩陣[Mij]m×n；

2)求屬性約簡結(jié)果集Reduce；

3)依據(jù)屬性約簡結(jié)果集Reduce和當(dāng)前聚類中心V計算新的隸屬度矩陣U(t)，t++；

4)依據(jù)當(dāng)前隸屬度矩陣更新各聚類中心，t++；

4.3 時空復(fù)雜度分析

時間復(fù)雜度分析：步驟1.中計算區(qū)分矩陣[Mij]的時間復(fù)雜度為O(D*n2)；步驟2求屬性約簡結(jié)果集Reduce的時間復(fù)雜度是O(n2/2)；步驟3計算隸屬度矩陣U(t)的時間復(fù)雜度是O(|Reduce|·|n|·|C|)；步驟4更新各聚類中心的時間復(fù)雜度是O(|n2|·|C|+|n|·|C|)；步驟5的時間復(fù)雜度是O(|t|·(|Reduce|·|n|·|C|))+O(|t|·(|n2|·|C|+|n|·|C|))；因此本文算法的時間復(fù)雜度為O(|t|·|n2|·|C|).空間復(fù)雜度分析：用于存儲初始化數(shù)據(jù)集合X的空間復(fù)雜度為O(|n|·|D|)；求取區(qū)分矩陣[Mij]的空間復(fù)雜度為O(|n2|)；求取隸屬度矩陣U(t)的空間復(fù)雜度為O(|C|·|n|)；因此本文算法的空間復(fù)雜度為O(|n2|).

5 實驗與分析

為了驗證本文算法的有效性，算法使用Matlab實現(xiàn)，實驗的運(yùn)行環(huán)境：2 GB內(nèi)存；250 GB硬盤；Microsoft Windows XP操作系統(tǒng).測試數(shù)據(jù)是從加州大學(xué)提供的機(jī)器學(xué)習(xí)數(shù)據(jù)庫UCI上下載的5個數(shù)據(jù)集，這5個數(shù)據(jù)集分別是：Musk(Version 2)數(shù)據(jù)集、ISOLET數(shù)據(jù)集、Ionosphere數(shù)據(jù)集、Dresses_Attribute_Sales數(shù)據(jù)集和Tic_Tac_Toe數(shù)據(jù)集，各數(shù)據(jù)集的詳細(xì)信息如表1所示.

表1 實驗數(shù)據(jù)Tab.1 Experimental data

本次實驗中設(shè)計了一個對比實驗，將本文所提出的算法與傳統(tǒng)的模糊C-means算法進(jìn)行對比，性能評估主要從算法的執(zhí)行效率和聚類分析結(jié)果的精度兩方面進(jìn)行衡量，其中執(zhí)行效率主要考慮兩種算法對同一數(shù)據(jù)集在同一實驗環(huán)境下的執(zhí)行時間，聚類分析結(jié)果的精度則主要考慮聚類結(jié)果的準(zhǔn)確率.兩種算法的實驗對比結(jié)果如表2所示.

表2 實驗結(jié)果Tab.2 Experimental results

本文算法與傳統(tǒng)的模糊C-means(FCM)算法相比，其主要差異在于本文所提出的算法融入了粗糙集相關(guān)理論，在對高維數(shù)據(jù)集聚類的過程中對屬性進(jìn)行了約簡，在保證聚類能力的前提下刪除無關(guān)屬性，進(jìn)而減少聚類過程中算法的計算量，從而提高算法執(zhí)行效率.

從表2中的實驗對比結(jié)果來看，對于五個實驗數(shù)據(jù)集，本文所提出的算法在執(zhí)行效率方面大都優(yōu)于傳統(tǒng)的FCM算法，平均可以節(jié)省大約20%～40%的執(zhí)行時間，同時聚類結(jié)果的準(zhǔn)確率也都基本與傳統(tǒng)算法持平.對于數(shù)據(jù)集Ionosphere，本文算法的執(zhí)行時間略高于傳統(tǒng)算法，主要是由于本文算法在執(zhí)行過程中屬性約簡也需要耗費一部分時間，對于小量的數(shù)據(jù)集而言，本文算法雖然能夠減少在聚類過程中計算的工作量，但是由于數(shù)據(jù)集較小，這種工作量的減少在整個時間消耗上體現(xiàn)不明顯；對于數(shù)據(jù)集ISOLET，本文算法不僅在執(zhí)行時間上優(yōu)于傳統(tǒng)算法，而且在聚類能力方面也略高于FCM算法，由此也說明通過屬性約簡不僅能夠找到對聚類結(jié)果起決定性作用的屬性，而且還能夠剔除掉那些對聚類結(jié)果造成干擾的屬性.因此，對于高維數(shù)據(jù)聚類而言，通過引入粗糙集屬性約簡來對模糊C-means算法所做的改進(jìn)是行之有效的.

6 結(jié)束語

針對模糊C-means算法在處理高維度數(shù)據(jù)集時聚類效率不高的問題，本文將粗糙集屬性約簡理念融入到模糊C-means算法之中，以保證在聚類能力不變的情況下，減少算法執(zhí)行過程中的計算量，進(jìn)而提高聚類執(zhí)行效率.通過對不同數(shù)據(jù)集的測試表明，本文所提出的算法在對高維數(shù)據(jù)聚類的過程中對于保證聚類結(jié)果和降低時間消耗是行之有效的.

[1] 唐德玉， 齊德昱， 蔡先發(fā)， 等. 改進(jìn)的FCM算法在網(wǎng)絡(luò)入侵檢測中的應(yīng)用[J]. 計算機(jī)工程與應(yīng)用， 2012， 48(6): 5-8．

[2] 范 明， 田 錚， 趙 偉. FCM型聚類算法的統(tǒng)一框架及其核推廣[J]. 電子設(shè)計工程， 2013， 21(4): 134-136．

[3] 張思發(fā)， 劉汭祥. 一種應(yīng)用分治策略改進(jìn)的FCM聚類算法[J]. 計算機(jī)工程與應(yīng)用， 2013， 49(22): 194-196．

[4] 柳佳雯， 梁光明， 劉任任， 等. 融合加窗色調(diào)直方圖的彩色圖像FCM分割算法[J]. 計算機(jī)工程與應(yīng)用， 2013， 49(3): 230-232．

[5] 虞倩倩， 戴月明. 基于MapReduce的并行模糊C均值算法[J]. 計算機(jī)工程與應(yīng)用， 2013， 49(14): 133-151．

[6] 賀 玲， 蔡益朝， 楊 征. 高維數(shù)據(jù)聚類方法綜述[J]. 計算機(jī)應(yīng)用研究， 2010， 27(1): 23-26．

[7] Pawalk Z. Rough sets[J]. International Journal of Computer and Information Science， 1982， 11(5): 341-356．

[8] She Y， He X. On the structure of the multigranulation rough set model[J]. Knowledge-Based Systems， 2012， 36(12): 81-92．

[9] He Q， Wu C， Chen D， et al. Fuzzy rough set based attribute reduction for information systems with fuzzy decisions[J]. Knowledge-Based Systems， 2011， 24(5): 689-696．

[10] Qian Y， Liang J， Pedrycz W， et al. Positive approximation: an accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence， 2010， 174(10): 597-618．

[11] 王國胤， 姚一豫， 于 洪. 粗糙集理論與應(yīng)用研究綜述[J]. 計算機(jī)學(xué)報， 2009， 32(7): 1230-1245．

[12] 陳 源， 曾德勝， 謝 沖. 基于聚類的屬性約簡方法[J]. 計算機(jī)系統(tǒng)應(yīng)用， 2009， 18(5): 173-176．

[13] Li B， Tommy W， Chow S， et al. Analyzing rough set based attribute reductions by extension rule[J]. Neurocomputing， 2014， 123(10): 185-196．

[14] 林 山， 項 菲. 模糊決策表的一種改進(jìn)的屬性約簡算法[J]. 計算機(jī)工程與應(yīng)用， 2011， 47(26): 167-169．

[15] 黃治國， 王 端. 基于粗糙集的數(shù)據(jù)約簡方法研究[J]. 計算機(jī)工程與設(shè)計， 2009， 30(18): 4284-4286．

[16] 徐 山， 杜衛(wèi)鋒， 閔 嘯. 一種新的模糊決策表屬性約簡方法[J]. 計算機(jī)工程與應(yīng)用， 2013， 49(18): 105-107．

[17] 王培吉， 趙玉琳， 呂劍峰. 粗糙集屬性約簡的方法[J]. 計算機(jī)工程與應(yīng)用， 2012， 48(2): 113-115．

FuzzyC-means clustering algorithm of high-dimensional data based on rough set

ZHU Fubao， XU Xianjing， BAI Qingchun, ZHU Haodong

(School of Computer and Communication Engineering， Zhengzhou University of Light Industry， Zhengzhou 450002)

FuzzyC-means algorithm is an important clustering analysis algorithm， however， larger amount of its calculation result in its lower efficiency in the case of high dimension data. In order to overcome this problem， a fuzzyC-means clustering algorithm of high-dimensional data based on rough set was proposed. This algorithm introduces attribute reduction of rough set into traditional fuzzyC-means algorithm. It firstly extracts a dataset of important attributes and abandons some unrelated attributes， and then only calculates the important attributes to reduce the workload of the clustering process and improve the efficiency of clustering. Theoretic analysis and experimental results show that this method is more efficient on solving high-dimensional data．

rough set; fuzzyC-means; high-dimensional data; clustering

2015-01-11.

國家自然科學(xué)基金項目(61201447); 河南省科技攻關(guān)項目(122102210492); 河南省教育廳科學(xué)技術(shù)研究重點項目(13A520368、13A520367)；河南省高等學(xué)校青年骨干教師資助計劃項目(2014GGJS-084);鄭州輕工業(yè)學(xué)院校級青年骨干教師培養(yǎng)對象資助計劃項目(XGGJS02)．

1000-1190(2015)04-0511-04

TP311.131< class="emphasis_bold">文獻(xiàn)標(biāo)識碼： A

A

*通訊聯(lián)系人. E-mail: zhuhaodong80@163.com．