算法分析
近邻半监督聚类算法的MATLAB实现
向培素
(西南民族大学电气信息工程学院四川成都610041)
摘要：本文提出了一种用Matlab实现近邻半监督聚类算法的实例，补充进入MATLAB工具箱，并使用该算法对三个UCI数据集进行聚类，并通过F-measure指标验证了该算法的有效性，
关键词：聚类算法近邻传播半监督近邻传播Matlab
中图分类号：G254
文献标识码：A
文章编号：1007-9416(2012)08-0100-02
The MATLAB Program Designing of Semi-Supervised Clustering Based on Affinity
Propagation Algorithm
Xiang Peisu
School of Electrical and Information Engineering, Southwest University for Nationalities,Chengdu,Sichuan,610041, China
Abstract:The paper proposed a MATLAB programming of SemiSupervised Chustering Based on Affinity Propagation Algorithm and joined to the toolbox of MATLAB.The Fmeasure get from Simulating experiments on three UCI datasets show that the program is valid
Key words:Clustering algorithm AP SAP ; MATLAB
1、引言
聚类算法是数据挖掘，模式识别，机器学习等研究方向的重要分支之一。聚类算法是在没有任何数据的先验信息下对数据进行分类的方法。这类算法又称为无监督学习方法。
随着科技进步，在人类生活的各个领域都存在着海量的数据。在许多领域，有对大量数据分类的需求，如语音识别、字符识别，图像分割、机器视觉等领域都有数据聚类的需求。聚类分析在生物、地质地理、市场营销、考古等方面都有着重要作用。
在很多实际问题中，往往会有少部分数据具有先验知识，包括类标签和数据点的划分约束条件。但这此带先验知识的数据太少，不足以对大量数据进行监督聚类，于是人们提出了率监督聚类算法。半监督聚类是利用部分标记数据信息对未标记数据集进行聚类的过程。
率监督聚类算法分为两类。一类是基于约束的半监督聚类算法，这类算法是利用标签数据或者成对约束信息来改进聚类算法本身。另一类是基于距离的半监督聚类算法，这类算法是利用标签数据或者成对约束信息学习一种新的距离测度函数来满足约束条件，然后再使用基于距离测度的聚类算法进行聚类。除了这两类基本的率监督聚类方法以外，还有一些算法是结合这两种基本思想得到的率监督聚类算法。
文献[1腿出了近邻传播聚类算法，该算法提出一种新的两个数据点之间的相似性度量。数据点之间不断的交换实值信息，直到得到高质的聚类结果。
文献[2将率监督思想引人近邻传措聚类算法中，提出了一种近邻半率监督聚类算法。使用已知的标签数据或者成对点约束对数据形
成的相似度矩阵进行调整，进而达到提高AP算法的聚类性能的目的。
本文在Matlab环境下实现了基于近邻传播的半率监督聚类算法，并将其加人到Matlab的工具箱中。
2、近邻传播聚类AP算法和基于AP算法的半监督聚类算法
2.1AP算法
近邻传播聚类算法（AP算法）是由BrendanJ.Frey和Delbert Dueck在2007年发表于《Scinece》中的一篇文章中提出的。
AP算法将任意两点i，k之间的相似度设为欧几里得距离的负数；
s(i, k) = x, x
在得出最佳聚类结果的过程中，数据点之间交互的有两个信息量：,)，由点指间候选的类代表点人，反映了点所积累的点人作为点的类代表点的适宜度；a(,)由候选的类代表点指向点i，反映了点所积累的点选择点人作类代表点的适宜度，并考患了其它点对点&作为类代表点的支持度。
,)的初值为0，r(,)按下面的公式计算：
r(,k)=s(,k)max (a(t,k)+s(t,)
当i±k时，a(,)的计算：
a(i,k) = min (0, r(k, k)+
≥max(0, r(,k))H
当i=&时，a(t,t)是采用如下方式更新：
a(k,k)= max(0,r(i,k)
67
基金项目：本文是"2012年度西南民族大学中央高校基本科研业务费专项项日"(12NZYQN05)的研究成累之一
作者简介：向培素(1974一），女，西南民族大学电信学院，副教投，硕士，主要研究方向：计算机应用。 100