基于模糊聚类的家庭成员识别算法

红河学院计算机科学与技术系 韦 相

基于模糊聚类的家庭成员识别算法

红河学院计算机科学与技术系 韦 相

同一家庭的成员，相貌相似度高，不同家庭的成员，相貌相似度低。而聚类算法就是对数据进行分类，使同一类的数据对象相似度高，不同类的数据对象相似度低。本文构造相貌相似的模糊相似矩阵，计算出传递闭包，获得准确的聚类结果。本文提供了模糊传递闭包的理论和具体的应用实例，有较好的参考价值。

模糊聚类；家庭成员；模糊相似矩阵

1.引言

客观世界中，存在着大量的模糊现象和模糊概念，如“学习很优秀”，“头发很黑”，等，这里的“头发很黑”等都是模糊概念[1]。而模糊数学正是研究和处理模糊性现象的数学方法。根据模糊数学提出的算法得到了广泛的应用。文[2]实现了DNA序列的聚类，文[3]使用模糊聚类对网页进行聚类优化，文[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，对于任何自然数b³k，都有Rb=Rk，此时，t(R)是模糊等价矩阵。

通过求传递闭包t(R)，将模糊相似矩阵变成模糊等价矩阵。

3.构建模糊等价矩阵

建立模糊相似矩阵：

对文献中，日本学者Tamura给出的家庭成员相貌相似关系，在模糊数学中广泛使用。案例如下：这里有三个家庭，总共16人。每个家庭为4-7人。每人提供一张照片，共计16张照片，由很多个不相识的中学生分别对照片两两进行比较，按相貌相似程度进行评分，相貌越相似，打的分就越靠近1，越不相似，分数越靠近0，分数都在在[0,1]之间。每对照片的相似程度由所有人对他们的评分的平均值确定，得到相貌相似矩阵，如表1所示。题目要求：把三个家庭区分开来（即对这16个人进行聚类）。

表1 相貌相似矩阵

表2 相貌相似矩阵传递闭包

本文的解决方法是，使用模糊传递闭包的聚类算法，因为得到的信息里，没有聚类数（三个家庭的信息可以去掉），也没有聚类中心等信息。

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

从相似矩阵R出发，过程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]王士同.神经模糊系统及其应用[M].北京:北京航空航天大学出版,1998.

[2]刘丽.DNA序列分类模型[J].安徽农业大学学报,2005,32(3):393-396.

[3]沈盈洪,丰翔龙,黄荣游.基于网页聚类的搜索结果优化算法研究[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].模糊系统与数学,1998(2):89-94.

[8]贺仲雄.模糊数学及其应用[M].天津:天津科技出版社,1983.

云南省教育厅科研基金项目（2011C122）。

韦相（1980—），男，红河学院计算机科学与技术系讲师，研究方向：数据挖掘，图象处理。