人在江湖

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  82 Posts :: 10 Stories :: 169 Comments :: 0 Trackbacks

聚类分析被称之为unsupervised分析,一个跟它相似的概念是分类(classification)模型,不同的是,分类模型预先知道一共有几个类别,每个类别的定义是什么,所以叫做supervised。聚类分析预先不知道目标分成哪几类。往往在实际中,先用cluster分成一些类,然后有了这些类之后,可以再可以做classification分析,就是所谓的two steps analytisis.

聚类分析的算法主要基于“距离”的计算。聚类之后的结果要尽量保证每个segment内部的对象之间距离要短, segment之间的距离要长。这篇博客的内容总结自Han Jiawei的书,这本书可以在这篇博客里找到: 分享读书笔记Data Mining Concepts and Techniques 

关于距离:

如果有n个对象,每个对象有p个属性,那么可以得到这样一个矩阵:

image

距离通常是用另一个变形后的矩阵来做的:

image

其中d(2,1)表示第二个对象和第一个对象之间的距离。

对于连续型变量(interval)的,通常要对数据预先做标准化“standardiz”,方式如下:

1. 算mean absolute deviation.

Image(9)

2. 得出标准度量(不知道怎么翻译,standardized measurement)

Image(10)

3.最后结果:

Image(11)

 

对于二值型(binary)的, 有两种,一种是均衡型的(symmetric),另一种是非均衡型的(asymmetric),均衡指的是yes or no两种状态权重一样。比如如果你没有性别歧视的话,性别是均衡的二值变量。如果通过一系列症状诊断一个人是否生病了,yes比no的权重要大的多。

两种形式都通过下面这个2x2的表来算距离:

image

对于均衡型的,

image

对于非均衡型的

image

 

对于类别型(categorical)的变量,比较简单

image

where m is the number of matches (i.e., the number of variables for which i and  j are
in the same state), and p is the total number of variables.

 

对于顺序型(ordinal)的变量,要先把顺序map成[0.0,1.0]之间的数,然后按interval的方式来算。直接上截图,因为太多数学符号了

image

书上对每种计算基本都有例子。

 

 

 

 

 

 

 

 

 

关于聚类方法:

有partitioning, hierarchical, density-based, grid-based, model-based, clustering High-Dimensional, Constraint-Based.

Partitioning方法:

代表方法是K-means:

它的大致算法是,选定K值(最后要分成多少组)后,任选K个object作为cluster的中心,然后对每个其他的对象计算离哪个中心最近,就归到哪个cluster里,最后从每个cluster中找到新的中心,然后这样重复计算,直到聚类没有变化为止。

image

 

Hierarchical方法:

分agglomerative和Divisive两种,前者是自底向上的,就是一个一个object merge出一个segment,后者相反,自顶向下的。 上面说的K-means方法有时候和hierarchical联在一起用,因为K-means需要k作为参数,这个参数还挺重要的,极大影响了聚类的结果,可以先用hierarchical看看大致分几类合理,然后再用K-means。

 

Density-based方法:

基于距离的算法segment都是类球形的,density-based克服了这个问题。他的理念基本上是,一个对象为中心画个圆,看看圈近来的对象过没过threshold.

 

Grid-Based:

它是从上往下分层,底层grid粒度更细。它的特点是是scalability比较好。没细看理论,但是看图能感觉个大概。

image

 

 

Constraint-Based:

有的时候用户清楚应用的需求,想要指引聚类的过程,比如每个cluster size的range, 不同对象不用的权重等等。这就用到constraint-based聚类分析。这个也没细看,还有另外的clustering high-dimensional data, model based clustering都没怎么看,也许以后再写一篇“再访聚类分析”。下一篇会关于决策树。

posted on 2011-09-16 12:55 人在江湖 阅读(2998) 评论(1)  编辑  收藏 所属分类: BI

Feedback

# re: cluster聚类分析 2011-09-17 08:59 tbw
很不错啊   回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: