基于模糊聚類的家庭成員識(shí)別算法

紅河學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 韋 相

基于模糊聚類的家庭成員識(shí)別算法

紅河學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 韋 相

同一家庭的成員，相貌相似度高，不同家庭的成員，相貌相似度低。而聚類算法就是對(duì)數(shù)據(jù)進(jìn)行分類，使同一類的數(shù)據(jù)對(duì)象相似度高，不同類的數(shù)據(jù)對(duì)象相似度低。本文構(gòu)造相貌相似的模糊相似矩陣，計(jì)算出傳遞閉包，獲得準(zhǔn)確的聚類結(jié)果。本文提供了模糊傳遞閉包的理論和具體的應(yīng)用實(shí)例，有較好的參考價(jià)值。

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

1.引言

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

2.定義

下面有關(guān)模糊集、及模糊相似矩陣的定理

見(jiàn)文[6][7][8]

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

定義2[6]：模糊等價(jià)關(guān)系：若模糊關(guān)系R是X上各元素之間的模糊關(guān)系，對(duì)于任意x,y?X，滿足：

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

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

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

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

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

3.構(gòu)建模糊等價(jià)矩陣

建立模糊相似矩陣：

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

表1 相貌相似矩陣

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

本文的解決方法是，使用模糊傳遞閉包的聚類算法，因?yàn)榈玫降男畔⒗铮瑳](méi)有聚類數(shù)（三個(gè)家庭的信息可以去掉），也沒(méi)有聚類中心等信息。

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

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

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

算法參數(shù)c=1，求出的模糊等價(jià)矩陣。當(dāng)l=0.6時(shí)，得到的l-截集的分類結(jié)果：

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

3號(hào)這個(gè)人沒(méi)有歸入某一類，是錯(cuò)誤的，準(zhǔn)確度是15/16=93.75%。

4.模型評(píng)價(jià)及改進(jìn)

本文根據(jù)相片中相貌的相似度，構(gòu)建模糊相似聚類，利用模糊傳遞閉包的模糊聚類算法，較準(zhǔn)確的實(shí)現(xiàn)那個(gè)家庭成員的聚類。

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

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

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

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

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

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

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

[8]賀仲雄.模糊數(shù)學(xué)及其應(yīng)用[M].天津:天津科技出版社,1983.

云南省教育廳科研基金項(xiàng)目（2011C122）。

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