紅河學院計算機科學與技術系 韋 相

基于模糊聚類的家庭成員識別算法

紅河學院計算機科學與技術系 韋 相

同一家庭的成員，相貌相似度高，不同家庭的成員，相貌相似度低。而聚類算法就是對數據進行分類，使同一類的數據對象相似度高，不同類的數據對象相似度低。本文構造相貌相似的模糊相似矩陣，計算出傳遞閉包，獲得準確的聚類結果。本文提供了模糊傳遞閉包的理論和具體的應用實例，有較好的參考價值。

模糊聚類；家庭成員；模糊相似矩陣

1.引言

客觀世界中，存在著大量的模糊現象和模糊概念，如“學習很優(yōu)秀”，“頭發(fā)很黑”，等，這里的“頭發(fā)很黑”等都是模糊概念[1]。而模糊數學正是研究和處理模糊性現象的數學方法。根據模糊數學提出的算法得到了廣泛的應用。文[2]實現了DNA序列的聚類，文[3]使用模糊聚類對網頁進行聚類優(yōu)化，文[4][5]通過模糊聚類，實現對用戶訪問網站興趣的挖掘。本文通過建立模糊相似矩陣，將客觀事物予以分類的方法。

2.定義

下面有關模糊集、及模糊相似矩陣的定理

見文[6][7][8]

定義1：X，Y是論域，R：X×Y->[0,1]，稱為從X到Y的模糊關系，把R(x,y)稱為x和y具有關系R的程度。如果是從X到X的模糊關系稱為X上的模糊關系。

定義2[6]：模糊等價關系：若模糊關系R是X上各元素之間的模糊關系，對于任意x,y?X，滿足：

(1)自反性：R(x,x)=1

(2)對稱性：R(x,y)=R(y,x)

(3)(x,y)∈R且(y,z)∈R→R(x,z)∈R

定理1[8]設R∈M(n×n)是模糊相似矩陣，則存在一個最小自然數k（k￡n），使得傳遞閉包t(R)=Rk，對于任何自然數b3k，都有Rb=Rk，此時，t(R)是模糊等價矩陣。

通過求傳遞閉包t(R)，將模糊相似矩陣變成模糊等價矩陣。

3.構建模糊等價矩陣

建立模糊相似矩陣：

對文獻中，日本學者Tamura給出的家庭成員相貌相似關系，在模糊數學中廣泛使用。案例如下：這里有三個家庭，總共16人。每個家庭為4-7人。每人提供一張照片，共計16張照片，由很多個不相識的中學生分別對照片兩兩進行比較，按相貌相似程度進行評分，相貌越相似，打的分就越靠近1，越不相似，分數越靠近0，分數都在在[0,1]之間。每對照片的相似程度由所有人對他們的評分的平均值確定，得到相貌相似矩陣，如表1所示。題目要求：把三個家庭區(qū)分開來（即對這16個人進行聚類）。

表1 相貌相似矩陣

表2 相貌相似矩陣傳遞閉包

本文的解決方法是，使用模糊傳遞閉包的聚類算法，因為得到的信息里，沒有聚類數（三個家庭的信息可以去掉），也沒有聚類中心等信息。

其中rij表示xi和xj的相似程度，rij接近1，說明兩個人相貌的相似度越高，也可能是一家人，rij接近0，說明兩個人相貌的相似度越低，越可能不是一家人。

從相似矩陣R出發(fā)，過程R→R2→R4→R8，最多經過log2N+1（N為樣本的數目，是20）后，必有R2k=(R2k)2，停止迭代，最終的R2k就是模糊等價矩陣。

表2是相貌相似矩陣傳遞閉包。

算法參數c=1，求出的模糊等價矩陣。當l=0.6時，得到的l-截集的分類結果：

{1 6 8 13 16}，{2 5 7 11 14}，{4 9 10 12 15}，{3}

3號這個人沒有歸入某一類，是錯誤的，準確度是15/16=93.75%。

4.模型評價及改進

本文根據相片中相貌的相似度，構建模糊相似聚類，利用模糊傳遞閉包的模糊聚類算法，較準確的實現那個家庭成員的聚類。

[1]王士同.神經模糊系統(tǒng)及其應用[M].北京:北京航空航天大學出版,1998.

[2]劉麗.DNA序列分類模型[J].安徽農業(yè)大學學報,2005,32(3):393-396.

[3]沈盈洪,豐翔龍,黃榮游.基于網頁聚類的搜索結果優(yōu)化算法研究[J].計算機應用,2010,30(1):51-54.

[4]陳冬玲,王大玲,于戈,于芳.基于PLSA方法的用戶興趣聚類[J].東北大學學報(自然科學版),2008,29(1):53-56.

[5]曾黃麟,劉小芳.模糊中心聚類學習方法的比較與改進[J].四川輕化工學院學報,2004,17(1):1-8.

[6]陳水利,李敬功,王向公.模糊集理論及其應用[M].北京:科學出版社,2005.

[7]何清.模糊聚類分析理論與應用研究進展[J].模糊系統(tǒng)與數學,1998(2):89-94.

[8]賀仲雄.模糊數學及其應用[M].天津:天津科技出版社,1983.

云南省教育廳科研基金項目（2011C122）。

韋相（1980—），男，紅河學院計算機科學與技術系講師，研究方向：數據挖掘，圖象處理。