注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

淘尽网 官方博客

淘尽网http://www.tao3w.com做最好的比价网站

 
 
 

日志

 
 
关于我

淘尽网 http://www.tao3w.com 做最好的比价网站,做最好的数据抓取专家。

网易考拉推荐

聚类算法学习笔记(三)——顺序聚类  

2012-09-06 17:40:59|  分类: spider |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://www.blogjava.net/changedi/archive/2010/03/06/314698.html

1.    顺序聚类

事实上,将n个对象,聚类到k个聚类中这件事本身是一个NP难问题。熟悉组合数学应该知道这个问题的解事第二类Stirling数:。这样问题也就出现了,如果k值固定,那么计算还是可行的,如果k值不固定,就要对所有的可能k都进行计算,那运行时间可想而知了。然而并不是所有的可行聚类方案都是合理的,所谓的合理,我理解就是说接近你的聚类目标的,之所以我们要分类,必然有初始动机,那么可以根据这个动机制定可行的聚类方案,这样,复杂度的问题就回避了。

顺序算法(sequential algorithms)是一种非常简单的聚类算法,大多数都至少将所有特征向量使用一次或几次,最后的结果依赖于向量参与算法的顺序。这种聚类算法一般是不预先知道聚类数量k的,但有可能给出一个聚类数上界q。本文将主要介绍基本顺序算法(Basic Sequential Algorithmic Scheme,BSAS)和其几个变种,并给出代码实现。

首先看BSAS,这个算法方案需要用户定义参数:不相似性阈值θ和允许的最大聚类数q。算法的基本思想:由于要考虑每个新向量,根据向量到已有聚类的距离,将它分配到一个已有的聚类中,或者一个新生成的聚类中。算法的伪码描述如下:

1.       m=1   /*{聚类数量}*/

2.       Cm={x1}

3.       For i=2 to N

4.           Ck: d(xi,Ck)=min1?j?md(xi,Cj)

5.           If (d(xi,Ck)>ΘAND (m<q) then

6.               m=m+1

7.               Cm={xi}

8.           Else

9.               Ck=Ck?{xi}

10.           如果需要,更新向量表达

11.       End {if}

12.   End {for}

由上面的描述可以看出BSAS算法对向量顺序非常依赖,无论是聚类数量还是聚类本身,不同的向量顺序会导致完全不同的聚类结果。另一个影响聚类算法结果的重要因素是阈值θ的选择,这个值直接影响最终聚类的数量,如果θ太小,就会生成很多不必要的聚类,因为很多情况下向量与聚类的合并条件都受到θ的限制,而如果θ太大,则聚类数量又会不够。BSAS比较适合致密聚类,其对数据集进行一次扫描,每次迭代中计算当前向量与聚类间的距离,因为最后的聚类数m被认为远小于N,故BSAS的时间复杂度为O(N)

由于BSAS算法依赖于q,因此这里介绍一种自动估计聚类数q的简单方法,该方法也适用于其他的聚类算法,令BSAS(Θ)为具有给定不相似阈值θ的BSAS算法。

1.       For Θ=a to b step c

2.          算法BSAS(Θ)执行s,每一次都使用不同的顺序表示数据。

3.          估计聚类数,mΘ作为从sBSAS(Θ)算法得来的最常出现的聚类数。

4.       Next Θ

其中ab是数据集的所有向量对的最小和最大不相似级别,c的选择直接受d(x,C)的影响。

2. 算法实现

package util.clustering;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

/**
 * 
@author Jia Yu
 *
 
*/

public class BSAS <extends Clusterable<T>> {

    
/**
     * Basic Sequential Algorithmic Scheme
     * 适用于致密聚类
     
*/

    
    
public BSAS() {
    }

    
    
/**
     * Basic Sequential Algorithmic Scheme
     * 考虑样本空间中每个向量,根据向量到已有的聚类中心的距离,将它分配到一个已有聚类中,或者一个新生成的聚类中。
     * time complexity is O(N)
     * BSAS算法对整个数据集只进行一次扫描。
     * 
@param points 待聚类的向量
     * 
@param Phi 用户定义的不相似性阈值
     * 
@param q 用户定义的允许的最大聚类数
     * 
@return
     
*/

    
public List<Cluster<T>> cluster(final Collection<T> points,final double Phi,final int q){
        
int m = 0;
        
int n = points.size();
        
double disOfXandCj = 0;
        
double disOfXandCk;
        List
<T> ptList = new ArrayList<T>(points);
        Cluster
<T> C = new Cluster<T>(ptList.get(m));
        C.addPoint(ptList.get(m));
        Cluster
<T> Ck = C;
        List
<Cluster<T> > cList = new ArrayList<Cluster<T> >();
        cList.add(C);
        
for(int i=1;i<n;i++){
            disOfXandCk 
= Double.MAX_VALUE;
            Iterator
<Cluster<T> > cListIt = cList.iterator(); 
            
while(cListIt.hasNext()){
                Cluster
<T> Cj = cListIt.next();
                disOfXandCj 
= getDisOfPointAndCluster(ptList.get(i),Cj);
                
if(disOfXandCk > disOfXandCj){
                    disOfXandCk 
= disOfXandCj;
                    Ck 
= Cj;
                }

            }

            
if(disOfXandCk > Phi && m < q){            //不满足条件,则产生新的聚类
                m++;
                Cluster
<T> cm = new Cluster<T>(ptList.get(i));
                cm.addPoint(ptList.get(i));
                cList.add(cm);
            }

            
else{            //满足条件的将点加入已有聚类,并更新聚类中心
                if(cList.contains(Ck))
                    cList.remove(Ck);
                Ck.addPoint(ptList.get(i));
                
final T newCenter = Ck.getCenter().centroidOf(Ck.getPoints());
                Cluster
<T> tempCluster = new Cluster<T>(newCenter);
                
for(int j=0;j<Ck.getPoints().size();j++){
                    tempCluster.addPoint(Ck.getPoints().get(j));
                }

                cList.add(tempCluster);
            }

        }

        
return cList;
    }


    
/**
     * 选择不同的测度,有不同的算法。
     * 这里默认dis(x,C)为点到聚类中心的距离。
     
*/

    
private double getDisOfPointAndCluster(T t, Cluster<T> cj) {
        
return t.distanceFrom(cj.getCenter());
    }


}

3. 程序框架

       我的聚类程序主要扩展自Apache Commons Math开源框架,下面是其结构,我简单加入了Clusterer类作为抽象模板类,使用模板方法模式修改了框架,为后续加入的例如BSAS算法提供模板。

4. 小结

       顺序算法简单易实现,对于学习聚类来说是入门的最好选择,考虑到篇幅的限制,不能将代码全部发上来,如果有需要可以向我索要,Apache Commons Math框架可以到Apache的网站上下载。另外还有很多介绍不够详细,感兴趣的朋友可以继续深入研究BSAS的扩展。

5. 参考文献及推荐阅读

[1]Pattern Recognition Third Edition, Sergios Theodoridis, Konstantinos Koutroumbas

[2]模式识别第三版, Sergios Theodoridis, Konstantinos Koutroumbas李晶皎王爱侠张广源等译

  评论这张
 
阅读(500)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017