一類帶最小約束的模糊聚類問題

尚松蒲 趙中建

摘要: 考慮到模糊聚類中引入傳遞性可能使問題失真, 提出了一類帶最小約束的模糊聚類問題. 給出了解決這類問題的兩類方法: 直接聚類法與基于無約束聚類的方法. 并將這些方法與一般模糊聚類的方法進(jìn)行了比較.

關(guān)鍵詞: 模糊聚類;約束聚類;失真;算法

1 引言

模糊聚類分析是根據(jù)模糊相似矩陣對各個(gè)對象進(jìn)行分類[1]. 模糊聚類分析是模糊數(shù)學(xué)中應(yīng)用最多、最活躍的一個(gè)分支,在科學(xué)研究、工程技術(shù)、經(jīng)濟(jì)管理方面都有著廣泛的應(yīng)用. 模糊聚類分析的常用方法包括傳遞閉包法、直接聚類法以及作為直接聚類法圖形化的最大樹法. 這些方法都是等價(jià)的,結(jié)果也完全一樣,在聚類時(shí)都假設(shè)了傳遞性.由模糊相似矩陣求傳遞閉包得到模糊等價(jià)矩陣,這種對傳遞性的引入使兩個(gè)相似度很小的元素可以通過其它的元素而歸為一類,而這在有些實(shí)際問題中是不可接受的[2,3]. 因此我們提出了一類帶最小約束的模糊聚類問題,它比一般的模糊聚類問題多了一個(gè)約束條件: 相似度小于某個(gè)閾值的兩個(gè)元素不能在同一類中。

在接下來的第二部分我們給出問題的數(shù)學(xué)描述,第三部分給出直接聚類的解法,第四部分給出基于無約束的解法,最后第五部分做出總結(jié),并比較以上的方法與無約束模糊聚類方法的聯(lián)系與區(qū)別。

2 問題描述

假定有要對集合{x1,x2,…,xn}里的n個(gè)元素(對象)進(jìn)行聚類, 給定的條件包括:

(1)模糊相似矩陣R, 矩陣中的元素rij表示元素i與元素j的相似系數(shù), R滿足自反性(rii=1)與對稱性(rij=rji);

2.1約束閾值?姿0:帶最小約束條件的模糊聚類問題即是在聚類閾值?姿水平上,限制同一類的元素間的相似系數(shù)大于等于約束閾值?姿0的模糊聚類問題. 下面給出這個(gè)問題的一些解法.

2.2直接聚類法:直接聚類法最開始將n個(gè)對象各自作為一類,然后在滿足約束條件的情形下,逐步將某些類合并,直到不能合并為止.算法如下:

(1)初始有n類: {x1},{x2},…,{xn},令

,

(2)若S=?覫,算法終止;否則轉(zhuǎn)(3).

(3)取S中最大元素,令,若i0所在類中的元素與j0所在類中的元素的相似系數(shù)的最小值大于等于?姿0,則將i0所在類與j0所在類合并為一類,轉(zhuǎn)(2);否則直接轉(zhuǎn)(2).該算法與無約束模糊聚類中的直接聚類法類似,只是考慮到約束條件而更加復(fù)雜。算法的結(jié)果是滿足約束條件的聚類.

3 基于無約束的聚類

按照不考慮約束條件給出在?姿水平上的模糊聚類,然后在每一類中進(jìn)行必要的再分類以滿足約束條件。

方法一: 我們以n個(gè)對象為頂點(diǎn)構(gòu)造一個(gè)圖,頂點(diǎn)i與頂點(diǎn)j連邊當(dāng)且僅當(dāng)對象i與對象j滿足rij姿0,我們稱這個(gè)圖為約束圖。顯然,對象i與對象j不能歸為一類當(dāng)且僅當(dāng)頂點(diǎn)i與頂點(diǎn)j之間有連邊。將這些點(diǎn)k分類, 等價(jià)于將約束圖構(gòu)造為一個(gè)k-部圖. 確定最小的k是NP-困難的[4]。我們可以先構(gòu)造約束圖的點(diǎn)覆蓋, 假設(shè)C={i1,i2,…,im}是約束圖的點(diǎn)覆蓋,D是約束圖中不包含C中的點(diǎn)的非零度的點(diǎn)的集合,以點(diǎn)覆蓋C中的點(diǎn)與D為基礎(chǔ),構(gòu)造m+1類,將其余點(diǎn)按照相似系數(shù)的大小,分別歸入這m+1類。得到一個(gè)滿足約束條件的分類。

(1)將某類中所有相似系數(shù)小于?姿0的集合記為T.

(2)若T=?覫,算法終止;否則轉(zhuǎn)(3).

(3)取T中的最小元素,則將i0與j0分屬于不同的兩類,其余元素按照相似系數(shù)大小歸為其中某一類,對這兩個(gè)類,分別轉(zhuǎn)(1)。

方法一是應(yīng)用圖論中有限覆蓋理論來構(gòu)造滿足約束條件的分類,方法二采用逐步分解法得到滿足約束條件的分類。

4 總結(jié)

以上提出了一類帶最小約束的模糊聚類問題, 這個(gè)問題對解決無約束模糊聚類中因傳遞性而產(chǎn)生的失真問題是一個(gè)有益的嘗試. 并給出了兩類解法:直接聚類法法與基于無約束聚類的聚類,后者分為點(diǎn)覆蓋法與逐步聚類法. 與無約束的模糊聚類問題相比, 這個(gè)問題更復(fù)雜, 解法的難度也更大, 聚類的結(jié)果也更具有不確定性. 對上述問題可以提出更具體的聚類目標(biāo)而得到更數(shù)學(xué)化的模型。

參考文獻(xiàn)

[1] 謝季堅(jiān), 劉承平. 模糊數(shù)學(xué)方法及其應(yīng)用[M]. 武漢: 華中科技大學(xué)出版社,2000.

[2] 鮑正益. 模糊聚類算法及其有效性研究 [D]. 廈門: 廈門大學(xué), 2006.

[3] 于劍,程乾生.模糊聚類方法中的最佳聚類數(shù)的搜索范圍[J].中國科學(xué)(E輯),2002,32(2): 274-280.

[4] W.T.Tutte. Graph theory [M]. 北京: 機(jī)械工業(yè)出版社, 2004.

作者簡介:尚松蒲(1974 -),男,河南葉縣人,講師,博士,主要從事組合優(yōu)化問題研究。