下午我在实验室挥汗如雨的工作,某君拿着一份东南大学的学报找到我,问我能不能在Matlab里实现资料中的那个聚类算法,我看了一下,觉得这个算法不适合使用Matlab实现,或者说我不太会在Matlab中实现这样的算法,但是这段时间一直在使用Matlab,其它语言相对生疏了,且Matlab这种解释执行的环境比较适合调试,开发速度肯定比C快多了,所以还是试着做了一下。 简略地看了一下学报中的这篇文章,算法叫做广度优先邻居搜索的聚类算法。里面有几个定义: 一、数据矩阵。这是一个m行2列的矩阵,行数 m=待分类的元素个数,第一列代表元素横坐标,第二列代表元素纵坐标; 二、相似度矩阵 simiR。这是一个归一化了的矩阵,simiR(a,b)代表元素a和 b的相似度,相似度越大越相似。该矩阵是一个对称,且对角线元素为 1的矩阵; 三、邻居门限 r。如果有两个元素 a,b,且simiR(a,b)>r,则这两个元素是邻居; 四、类门限 lambda。类A中有n个元素,有一个待分类的元素 k,若类A中有超过(lambda*100)%个元素是k的邻居,则 k属于类A; 五、广度优先邻居搜索。即搜索某个元素的所有邻居,然后分别搜索每个邻居的所有邻居,依此; 使用广度优先,正好我前几天看了一个广度优先抓取网页的Python程序,马上就能想起(参见《用Python写一个小小的爬虫程序》)。 广度优先的典型算法就是使用队列:找出队首的元素的所有邻居,把它们从队尾压入,然后将队首弹出,非常方便。 如果把互为邻居的元素用无向线段相连,则所有的元素构成一个非连通图,需要多次调用广度优先搜索才能完成所有元素的分类。 下面给出代码(Matlab7.0.1): createSimiR.m 这个函数不是我写的,是某君给我的生成测试数据的代码中的函数,如果哪位看客知道这段代码的出处,请及时通知我,我会在文章中注明出处。 生成归一化相似度矩阵的函数,参数为待分类数据,返回值为归一化相似度矩阵。 function simiR=createSimiR(INPUTDATA) Xk=mean(INPUTDATA); %列均值 Sk=var(INPUTDATA); %列方差 numrows=size(INPUTDATA,1); %INPUTDATA行数 for i=1:numrows INPUTDATA(i,:)=(INPUTDATA(i,:)-Xk)./Sk; %标准差标准化 end for i=1:numrows for j=1:2 DATAFORCLUS(i,j)=(INPUTDATA(i,j)-min(INPUTDATA(:,j)))... /(max(INPUTDATA(:,j))-min(INPUTDATA(:,j))); %极值标准化 end end %--------相似矩阵----------% for i=1:numrows for j=1:numrows simiR(i,j)...