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

尚松蒲 趙中建

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

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

1 引言

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

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

2 問題描述

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

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

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

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

(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 基于無約束的聚類

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

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

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

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

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

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

4 總結(jié)

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

參考文獻

[1] 謝季堅, 劉承平. 模糊數(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]. 北京: 機械工業(yè)出版社, 2004.

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