软件工程

本类阅读TOP10

·PHP4 + MYSQL + APACHE 在 WIN 系统下的安装、配置
·Linux 入门常用命令(1)
·Linux 入门常用命令(2)
·使用 DCPROMO/FORCEREMOVAL 命令强制将 Active Directory 域控制器降级
·DirectShow学习(八): CBaseRender类及相应Pin类的源代码分析
·基于ICE方式SIP信令穿透Symmetric NAT技术研究
·Windows 2003网络负载均衡的实现
·一网打尽Win十四种系统故障解决方法
·数百种 Windows 软件的免费替代品列表
·收藏---行百里半九十

分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
聚类算法的一个教程

作者:未知 来源:月光软件站 加入时间:2005-2-28 月光软件站

原文出自: http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/hierarchical.html
辅助资料: http://149.170.199.144/multivar/ca.htm

层次式聚类方法

How They Work

给定要聚类的N的对象以及N*N的距离矩阵(或者是相似性矩阵), 层次式聚类方法的基本步骤(参看S.C. Johnson in 1967)如下:

  1. 将每个对象归为一组, 共得到N组, 每组仅包含一个对象. 组与组之间的距离就是它们所包含的对象之间的距离.
  2. 将最近的两个组合并成一组, 于是总的组数少了一个.
  3. 重新计算新的组与所有旧组之间的距离.
  4. 重复第2步和第3步, 直到最后合并成一个组为止(此组包含了N个对象).

根据步骤3的不同, 可将层次式聚类方法分为几类: single-linkage, complete-linkage 以及 average-linkage 聚类方法等.
single-linkage 聚类法(也称 connectednessminimum 方法): 组间距离等于两组对象之间的最小距离.
complete-linkage 聚类法 (也称 diametermaximum 方法): 组间距离等于两组对象之间的最大距离.
average-linkage 聚类法: 组间距离等于两组对象之间的平均距离.
average-link 聚类的一个变种是R. D'Andrade (1978) 的UCLUS方法, 它使用的是median距离, 在受异常数据对象的影响方面, 它要比平均距离表现更佳一些.

Single-Linkage Clustering: The Algorithm
Let’s now take a deeper look at how Johnson’s algorithm works in the case of single-linkage clustering.
The algorithm is an agglomerative scheme that erases rows and columns in the proximity matrix as old clusters are merged into new ones.

The N*N proximity matrix is D = [d(i,j)]. The clusterings are assigned sequence numbers 0,1,......, (n-1) and L(k) is the level of the kth clustering. A cluster with sequence number m is denoted (m) and the proximity between clusters (r) and (s) is denoted d [(r),(s)].

The algorithm is composed of the following steps:

  1. Begin with the disjoint clustering having level L(0) = 0 and sequence number m = 0.
  2. Find the least dissimilar pair of clusters in the current clustering, say pair (r), (s), according to

    d[(r),(s)] = min d[(i),(j)]


    where the minimum is over all pairs of clusters in the current clustering.
  3. Increment the sequence number : m = m +1. Merge clusters (r) and (s) into a single cluster to form the next clustering m. Set the level of this clustering to

    L(m) = d[(r),(s)]
  4. Update the proximity matrix, D, by deleting the rows and columns corresponding to clusters (r) and (s) and adding a row and column corresponding to the newly formed cluster. The proximity between the new cluster, denoted (r,s) and old cluster (k) is defined in this way:

    d[(k), (r,s)] = min d[(k),(r)], d[(k),(s)]
  5. If all objects are in one cluster, stop. Else, go to step 2.



相关文章

相关软件