Algorithm 版 (精华区)
发信人: ssos (存在与虚无), 信区: Algorithm
标 题: (三)聚类
发信站: 哈工大紫丁香 (2001年06月14日16:06:02 星期四), 站内信件
聚类
聚类是把一组个体按照相似性归成若干类别,即“物以类聚”。它的目的是使得属于同
一类别的个体之间的距离尽可能的小而不同类别上的个体间的距离尽可能的大。聚类方
法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。
在统计方法中,聚类称聚类分析(clustering analysis),它是多元数据分析的三大方
法之一(其它两种是回归分析和判别分析)。它主要研究基于几何距离的聚类,如欧式
距离、明考斯基距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、
动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等[83]。这种聚类方法是一种基于
全局比较的聚类,它需要考察所有的个体才能决定类的划分;因此它要求所有的数据必
须预先给定,而不能动态增加新的数据对象。聚类分析方法不具有线性的计算复杂度,
难以适用于数据库非常大的情况。新的有名聚类方法是AutoClass,它使用了贝叶斯方法
来聚类。
在机器学习中聚类称作无监督归纳(unsupervised induction);因为和分类学习相比
,分类学习的例子或数据对象有类别标记,而要聚类的例子则没有标记,需要由聚类学
习算法来自动确定。很多人工智能文献中,聚类也称概念聚类(concept clustering)
;因为这里的距离不再是统计方法中的几何距离,而是根据概念的描述来确定的。当聚
类对象可以动态增加时,概念聚类则称是概念形成(concept formation)。典型的概念
聚类或形成方法有:COBWEB、OLOC和基于列联表的方法。
在神经网络中,有一类无监督学习方法:自组织神经网络方法。这类方法包括:Kohone
n自组织特征映射(self-organization feature mapping)网络、竞争学习网络、Hamm
ing网络、对传网络(Counter Propagation Network, 简称CPN)、神经认知机(Cogni
tion and Neocognition)和自适应谐振理论(Adaptive Resonance Theory,简称ART)
。在数据库知识发现领域里,见报道的神经网络聚类方法主要是自组织特征映射方法,
IBM在其发布的数据开采白皮书中就特别提到了使用此方法进行数据库聚类分割。
在KDD里,面临的常常是含有大量数据的数据库,因此要探讨面向数据库的聚类方法以适
应新问题带来的挑战,我们将在下节里对此进行介绍。
面向数据库的聚类方法
针对大数据库的聚类近来已在数据库研究界得到了相当的重视。研究人员提出了如下的
一些方法:基于随机搜索的聚类方法CLARANS、聚焦方法和聚类特征树法BIRCH。CLARAN
S方法仍然要求要聚类的对象必须预先都调入内存里,这对非常大的数据库显然是不合理
的;聚焦方法通过引入R树方法能够处理基于磁盘的大型数据,但是R树的构造并不容易
而要耗费相当的计算量。BIRCH方法(平衡迭代消减聚类法)则是一种较为灵活的递增式
(incremental)聚类方法,它能根据内存的配置大小而自动调整程序对内存的需要。下
面将着重讨论BIRCH算法。
BIRCH涉及两个概念:聚类特征(clustering feature)和聚类特征树(CF-tree)。聚
类特征是一个三元组,它总结了一簇个体的有关信息,从而使得一簇点的表示可以总结
为对应的一个聚类特征,而没必要再用具体的这一组点来表示。形式地描述,给定一组
有N个点、维数为d的一簇个体{Xi},在这簇个体的聚类特征可表示为:。 其中,N是点
的个数,是N个点的线性和,即,它反应了这簇点的重心;SS是N个点的平方和,即,它
反应了这簇点的直径大小,SS越小,这簇点聚得越紧。
聚类特征树是一个满足两个条件的平衡树。两个条件分别是:分枝因子和簇直径的限制
。分枝因子规定了树的每个节点的子女的最多个数;而簇直径体现了对一簇点的直径大
小的限制,即聚类特征的SS不能太大,否则不能聚为一类。非叶子节点上存储了它的子
女的聚类特征的和,因此该节点总结了其子女的信息。
聚类特征树可以动态构造,因此不要求所有数据一次读入内存,而可以从外存上逐个读
入数据项。新的的数据项总是插入到树中与该数据距离最近的叶子上。如果插入后使得
该叶子的直径大小超过了簇直径,则需要把该叶子或其它叶子分裂,直到叶子能够插入
到树中而同时满足簇直径的限制。新的数据项插入后,它的信息就可以从叶子一直传递
到树根,即重新计算该叶子的各个祖先的聚类特征值。
通过改变簇直径的限制大小,可以修改聚类特征树的大小。簇直径限制值越小(要求类
里的各个数据项相似度大),树会越大;反之,树越小。因此,当存储树的内存不够大
时,可以把簇直径限制值设置为较大的值,然后重新构造该树,重构时可以直接从原来
的树叶子计算,不需要重新读入数据。
BIRCH算法的CPU和I/O开销复杂度都是O(N),N为数据量大小。该方法具有如下优点:良
好的算法伸缩性(scalability)、数据输入顺序不敏感性、较好的聚类效果。除此之外
,聚类特征树方法显然还是一种通用技术,可用于各种聚类算法,包括前面所讲的CLAR
ANS聚类方法。
--
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间:5.054毫秒