一種新的聚類有效性函數：模糊劃分的模糊熵

卿銘，孫曉梅

（1.西南交通大學 數學學院，四川 成都 600031; 2. 河南工程學院 數學與物理科學系,河南 鄭州 451191）

?

一種新的聚類有效性函數：模糊劃分的模糊熵

卿銘1，孫曉梅2

（1.西南交通大學 數學學院，四川 成都 600031; 2. 河南工程學院 數學與物理科學系,河南 鄭州 451191）

模糊聚類分析結果是否合理的問題屬于模糊聚類有效性判定課題，其核心是模糊聚類有效性函數的構造。文中基于序關系定義了模糊劃分模糊熵來描述模糊劃分的模糊程度。考慮到現有的一類有效的模糊聚類有效性函數就是基于數據集的模糊劃分的，因此文中也用模糊劃分的模糊熵作為聚類有效性函數。實驗表明，模糊劃分的模糊熵作為模糊聚類的有效性函數是合理的、可行的。

模糊C均值聚類；模糊劃分的模糊熵；聚類有效性；聚類分析；模糊劃分；模糊熵；熵函數；模糊集

聚類是一個在人類認識世界的過程中產生的古老問題。在面對紛繁的大千世界時，關注事物間的相似性并以此來區別不同的事物，對于人類來說是一種清晰而直觀的思路。而每個概念的最初形成無不借助于事物間的聚類分析。因此聚類分析的研究不僅具有重要的理論意義，而且具有重要的工程應用價值和人文價值。對于給定的數據集，首先要判斷有無聚類結構，這屬于聚類趨勢研究的課題；如果已經確認有聚類結構，則需要用算法來確定這些結構，這屬于聚類分析的研究課題；得到結構后，需要分析、判斷聚類的結果是否合理，這屬于聚類有效性研究的課題[1]。

傳統的聚類分析是一種硬劃分。它將每個待辨識的對象嚴格地劃分到某個類中，其聚類結果具有非此即彼的性質。而實際上大多數對象并沒有嚴格的屬性，它們在形態和類屬方面存在著中介性，往往具有亦此亦彼的性質，因此適合進行軟劃分。而模糊集理論的提出，對聚類分析軟劃分的發展起到了重要作用。用模糊的方法來處理聚類問題，稱之為模糊聚類分析，是當前聚類分析研究的主流。

關于聚類有效性問題的研究通常是基于硬C均值聚類算法和模糊C均值聚類算法進行的。在模糊聚類有效性函數中，基于數據集的模糊劃分的有效性函數是很重要的一類，其觀點是：好的分類聚類應對應于數據集較分明的劃分，劃分的分明性越好，分類的不確定性就越小。盡管以Dunn[4]的劃分系數為代表的聚類有效性函數取得一定的效果然而仍存在缺陷：劃分系數有隨類數增加而遞減的趨勢。為克服這一缺點，范九倫[2- 3]、Dave[5]和Robubens[6]作了很多的工作。但仍未較好解決這一難題——聚類有效性函數隨類數增加而遞減（增）的趨勢。其他一些學者也對模糊聚類的有效性做了深入的討論[7-20]，但都不完善，有繼續改進的余地。

文中借鑒好的聚類應對應于數據集較分明的劃分，劃分的分明性越好，分類的不確定性就越小的學術思想，基于序關系定義模糊劃分的模糊熵來反映模糊劃分的模糊程度，并以其作為聚類有效性函數，實驗證明模糊劃分的模糊熵作為模糊聚類的有效性函數是合理、有效的。

1 FCM算法

這里

Mfc={U∈Rnc|uij∈[0,1],?i,j

下面給出文中采用的從隨機初始化模糊劃分矩陣開始迭代FCM算法步驟[8-9]。

1）初始化: 給定聚類類別數c（2≤c≤n，n為樣本點個數）、模糊加權指數m，設定迭代停止閾值ε，隨機初始化劃分矩陣U（0），設置迭代計數器b=0。

2）計算或更新聚類原型模式矩陣P（b）:

3）更新模糊劃分矩陣U（b+1）;

4）若||U（b+1）-U（b）||<ε，輸出劃分矩陣U和聚類原型P等聚類信息，算法結束；否則，令b=b+1，轉向2）。其中||·||為合適的矩陣范數。

算法從隨機初始化模糊劃分矩陣開始迭代，這樣做的原因主要有3個：1）標準FCM算法本身并不能保證一定收斂到全局最優點，算法可能收斂于某個極值點或局部最優點，由于模糊劃分矩陣的隨機性選取，通過對FCM算法的多次調用，可能會發現全局最優點。2）若從初始化聚類原型模式矩陣開始迭代，初始聚類原型的選取有很多種方法，考慮到算法的通用性，很難抉擇一個優秀的選取方案，并且一旦選取方案（這里不包括隨機初始化聚類原型）確定了，迭代過程就隨之固定，算法可能始終收斂于某個極值點或局部最優點。3）隨機初始化聚類原型顯然沒有隨機初始化劃分矩陣方便，而且也沒有什么客觀的理由。

2 模糊劃分的模糊熵

記X上的所有模糊劃分為FP（X）。[a]∈FP（X）表示每個元素都是常數a的劃分矩陣。

2）硬劃分是其極小元，任何2個硬劃分都可比，且在同一個等價類中；

3）[1/c]是其最大元。

證明1）設U1=[uij]，U2=[vij]。

min{uij,1-uij}≤min{vij,1-vij}≤1/2。

2）證明略。

定義2一個實函數E:FP（X）→R+稱為有限論域X上模糊c劃分的模糊熵（簡稱模糊劃分模糊熵），如果E滿足：

1）E（U,c）=0當且僅當U是硬劃分；

若定義

式中：參數p>0。

顯然，下述的定理2、3是成立的。

定理2Ep（U;c） 是有限論域X上模糊劃分模糊熵。

定理3當1

2）Ep（U;c）=0 ?U是硬劃分；

則

性質2）、3）顯然成立。

若記熵函數h（u）=4u（1-u），則

為第j個類模糊集Aj的模糊熵，j=1,2,…,c，則

3）如果采用其他的熵函數，也可以得到類似的結果。

范九倫和吳成茂[3]基于模糊熵來定義聚類有效性函數：

顯然式（3）與式（4）有類似之處。式（3）中p=0即得式（4）。但強調2點：1）基于序關系得到公式（3）；2）參數p在聚類有效性分析中也起作用，給出參數p的初衷是克服劃分系數及其他類似的聚類有效性函數的缺陷。

3 模糊劃分模糊熵作為聚類有效性函數的實驗結果

文中采用3組不同的數據，對Ep（U;c）的聚類有效性進行實驗。實驗所用數據如表1所示。它們都是適合作為聚類有效性分析的典型數據集。

表1 3組典型實驗數據Table 1 Three types of classical experiment data

對數據集Ⅰ，調用FCM算法在不同分類數目c下的情況見圖1至圖8，其中m=2,ε=10-4。

圖1 c=2的聚類結果

圖2 c=3的聚類結果

圖3 c=4的聚類結果

圖4 c=5的聚類結果

圖5 c=6的聚類結果

圖6 c=7的聚類結果

圖7 c=8的聚類結果

圖8 c=9的聚類結果

對數據集Ⅱ與Ⅲ，取m=2,ε=10-4調用FCM算法在不同分類數目c下的聚類情況略去。

對數據集Ⅰ、Ⅱ與Ⅲ，取p=1/n，ε=10-4，且m分別取1.5, 1.6, 1.7，1.8, 1.9, 2.0, 2.1, 2.2, 2.3, 2.4, 2.5時調用FCM算法在不同分類數目c下Ep（U;c）的取值情況做了計算。部分情況見表2～4。表中黑體部分對應Ep（U;c）的最小值，相應的c值即聚類算法決定的“最優”分類數。

表2 數據集ⅠEp（U;c）的值Table 2 Values of Ep（U;c） for data Ⅰ

可以知道數據集Ⅰ真正的最優分類數是6，由此可見此時Ep（U;c）在m=1.5時有效，在m=2.0和m=2.5時未得到最優分類,得到的是次優分類。

表3 數據集ⅡEp（U;c）的值Table 3 Values of Ep（U;c） for data Ⅱ

可以知道數據集Ⅱ真正的最優分類數是5，由此可見,此時Ep（U;c）在m=1.7時有效，在m=2.0和m=2.3時未得到最優分類,得到的是次優分類。

表4 數據集Ⅲ Ep（U;c）的值Table 4 Values of Ep（U;c） for data Ⅲ

可以知道數據集Ⅲ真正的最優分類數是4，由此可見，此時Ep（U;c）在m=1.6時有效，在m=2.0和m=2.4時未得到最優分類,得到的是次優分類。

4 結束語

基于序關系定義了數據集模糊劃分的模糊熵并將其作為模糊聚類有效性函數。從3個實驗數據集的模糊聚類有效性驗證來看，Ep（U;c）中的參數取p=1/n，也總存在合適的參數m（對數據據集Ⅰ, m=1.5;對數據集Ⅱ, m=1.7;對數據集Ⅲ，m=1.6）使得模糊劃分的模糊熵Ep（U;c）作為聚類有效性函數是有效、可行的。下一步，將考慮參數p與m的最優組合問題。

[1]范九倫. 模糊聚類新算法與聚類有效性問題研究[D]. 西安：西安電子科技大學, 1998: 52-77. FAN Jiulun. The studies on some new algorithms of fuzzy clustering and clustering validity [D]. Xian: Xidian University, 1998: 1-165.

[2]范九倫，吳成茂．可能性劃分系數和模糊變差相結合的聚類有效性函數[J]．電子與信息學報， 2002， 24（8）： 1017-1021. FAN Jiulun, WU Chengmao. Clustering validity function based on possibilistic partition coefficient combined with fuzzy variation [J]. Journal of Electronics and Information Technology, 2002， 24（8）： 1017-1021.

[3]范九倫，吳成茂．基于模糊熵的聚類有效性函數[J]. 模式識別與人工智能，2001，14（4）: 390-394. FAN Jiulun, WU Chengmao. Clustering validity function based on fuzzy entropy [J]. Pattern Recongnition and Artificial Intelligence, 2001，14（4）: 390-394.

[4]DUN J C. Some recent investigations of a new fuzzy partitions algorithm and its application to classification problems [J]. J Cybernet, 1974（4）: 1-15.

[5]DAVE R N. Validating fuzzy partition obtained through c-shells clustering [J]. Pattern Recognition Letters, 1996（ 17）: 613-623.

[6]ROBUBENS M. Pattern classification problems and fuzzy sets [J]. Fuzzy Sets Systems, 1978, 1: 239-253.

[7]BEZDEK J C, HARRIS J. Fuzzy partitions and relations—an axiomatic basis for clustering[J]. Fuzzy Sets and Systems, 1978（1）: 111-126.

[8]BEZDEK J C. Pattern recognition with fuzzy objective function algorithms [M]. New York：Plenum Press, 1981: 105-133.

[9]PAL N R, BEZDEK J C. On cluster validity for fuzzy C-means model [J]. IEEE Trans Fuzzy Systems, 1995（3）: 370-379.

[10]ZHANG Huangxiang, LU Jin. Creating ensembles of classifiers via fuzzy clustering and deflection [J]. Fuzzy Sets and Systems, 2010（160）: 1790-1802.

[11]YU Jian, YANG Minshen, LEE E S. Sample-weighted clustering methods [J]. Computers and Mathematics with Applications, 2011（62）: 2200-2208.

[12]岳士弘，黃媞，王鵬龍. 基于矩陣特征值分析的模糊聚類有效性指標[J]. 天津大學學報，2014, 47（8）: 689-696. YUE Shihong, HUANG Ti, WANG Penglong. Matrix eigenvalue analysis-based clustering validity index [J]. Journal of Tianjin University, 2014, 47（8）: 689-696.

[13]張大慶，徐再花. 一種新的模糊聚類有效性指標[J]. 沈陽農業大學學報， 2012, 14（5）: 636-639. ZHANG Daqing, XU Zaihua. A new validity index for fuzzy clustering [J]. Journal of Shenyang Agricultural University, 2012, 14（5）: 636-639.

[14]朱文婕，吳楠，胡學鋼. 一個改進的模糊聚類有效性指標[J]. 計算機工程與應用， 2011, 45（5）: 206-209.

ZHU Wenjie, WU Nan, HU Xuegang. Improved cluster validity index for fuzzy clustering [J]. Computer Engineering and Applications, 2011, 45（5）: 206-209.

[15]胡春春，孟令奎，謝文君，等. 空間數據模糊聚類的有效性評價[J].武漢大學學報， 2007, 32（8）: 740-743. HU Chunchun, MENG Lingkui, XIE Wenjun, et al. Validity measure on fuzzy clustering for spatial data [J]. Journal of Wuhan University, 2007, 32（8）: 740-743.

[16]鄭弘亮，徐本強，趙曉慧，等. 新的模糊聚類有效性指標[J]. 計算機應用， 2014, 34（8）: 2166-2169. ZHENG Hongliang, XU Benqiang, ZHAO Xiaohui, et al. Novel validity index for fuzzy clustering [J]. Journal of Computer Applications, 2014, 34（8）: 2166-2169.

[17]王麗娜，馬曉曉. 一種改進的模糊聚類有效性指標[J]. 微電子學與計算機, 2014, 31（4）: 68-74. WANG Lina, MA Xiaoxiao. An improved validity index for clustering [J]. Microelectronics and Computer, 2014, 31（4）: 68-74.

[18]張宇獻，劉通，董曉，等. 基于改進劃分系數的模糊聚類有效性函數[J]. 沈陽工業大學學報，2014, 36（4）: 431-435. ZHANG Yuxian, LIU Tong, DONG Xiao, et al. Validity function for fuzzy clustering based on improved partition coefficient [J]. Journal of Shenyang University of Technology, 2014, 36（4）: 431-435.

[19]普運偉，金煒東，朱明，等. 核模糊C均值算法的聚類有效性研究[J]. 計算機科學，2007, 34（2）: 207-210. PU Yunwei, JIN Weidong, ZHU Ming, et al. On cluster validity for kernelized fuzzy C-means algorithm [J]. Computer Science, 2007, 34（2）: 207-210.

[20]姚曉紅，任珂珂，趙花妮，等. 一種新的模糊聚類有效性指標的驗證[J]. 洛陽理工學院學報， 2012, 22（3）: 76-79. YAO Xiaohong, REN Keke, ZHAO Huani, et al. The verification of a new fuzzy clustering validity index [J]. Journal of Luoyang Institute of Science and Technology, 2012, 22（3）: 76-79.

卿銘，男，1971年生，副教授，主要研究方向為智能信息處理、系統可信性分析，發表學術論文20余篇。

孫曉梅，女，1962年生，副教授，主要研究方向為組合最優化。

A new clustering effectiveness function: fuzzy entropy of fuzzy partition

QING Ming1， SUN Xiaomei2

（1.School of Mathematics, Southwest Jiaotong University, Chengdu 610031, China; 2. Department of Mathematical and Physical Science, Henan Institution of Engineering, Zhengzhou 451191, China）

In this paper, the determination that whether a fuzzy clustering analysis result is reasonable or not is decided by the effectiveness of fuzzy clustering and its core is the construction of fuzzy clustering effectiveness function. This paper proposed a new concept of fuzzy entropy for a fuzzy partition to describe fuzzy degree of a fuzzy partition based on an order relation. Fuzzy entropy for a fuzzy partition is also considered as a clustering effectiveness function because some existing fuzzy clustering effectiveness functions are based on fuzzy partition of data sets. The experiments demonstrated that it is reasonable and practicable to utilize fuzzy entropy for a fuzzy partition as the effectiveness function of a fuzzy clustering.

fuzzyC-means clustering; fuzzy entropy of fuzzy partition; clustering effectiveness; clustering analysis; fuzzy partition; fuzzy entropy; entropy function; fuzzy set

2014-10-08.

日期：2015-01-13.

中央高校基礎研究基金資助項目（2682014ZT28）.

卿銘. E-mail：qingming@swjtu.edu.cn.

10.3969/j.issn.1673-4785.201410004.

http://www.cnki.net/kcms/detail/23.1538.TP.20150113.1130.006.html

TP O235

A

1673-4785（2015）01-0075-06

卿銘，孫曉梅.一種新的聚類有效性函數：模糊劃分的模糊熵[J]. 智能系統學報， 2015, 10（1）: 75-80.

英文引用格式：QING Ming，SUN Xiaomei. A new clustering effectiveness function: fuzzy entropy of fuzzy partition[J]. CAAI Transactions on Intelligent Systems, 2015, 10（1）: 75-80.