下载

3下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 聚类算法综述

聚类算法综述.PDF

聚类算法综述

破晓
2009-11-06 0人阅读 举报 0 0 暂无简介

简介:本文档为《聚类算法综述pdf》,可适用于IT/计算机领域

聚类算法综述SunstoneZhang分层次聚类法(最短距离法)最简单的聚类方法最大距离样本K平均聚类法(距离平方和最小聚类法)叠代自组织(ISODATA)聚类法ISODATA法的改进基于“核”的评估聚类方法聚类(Cluster):相似文档的分组表达方式。在向量空间模型中用户可以通过比较查询向量和聚类的中心进行检索并在聚类中进一步检索以找到最相似的文档。向量空间模型(VectorSpaceModel):文档和查询的一种表达方式将它们转换为向量。向量的特征一般是对应文档或查询中处理过的单词(取过词根并且删除了stopword)。这些向量被赋予权重以强调那些与语义相关的词目这在检索中很有用。在检索中比较查询向量和文档向量并将最接近的文档作为相关文档返回给用户。SMART是使用向量空间模型的最有名的例子。分层次聚类法(最短距离法)思路:寻找“距离”最近的两个样本结合有N个样本的集合Zs={Z,Z,,ZN}若想要聚成K个类(事先给定K)k=N,Ci={Zi},i=,,,Nifk=KthenEND找到Ci与Cj之间的距离d(Ci,Cj)最小的一对Ci和Cj合成一个类Ci,并计算新的Ci的中心去除Cj,k=kgoto类间距离d(Ci,Cj)类中心间距:d=||Mi–Mj||其中∑∈=iCZiiZnMni是属于Ci的样本数。靠得最近的样本:||||,minjijjiiZZCZCZd−∈∈=离得最远的样本:||||,maxjijjiiZZCZCZd−∈∈=类间平均距离:∑∑∈∈−=iijjCZCZjijiZZnnd||||距离计算的次数:)(−=NNCN。组合−NC−NC最简单的聚类方法相似性尺度(距离)阈值不需要事先给定K。有N个样本Zs={Z,Z,,ZN}给定一个阈值T。任取一个样本例如Z把Z作为第一个类的中心Z=Z然后依次取Zi(i=,,,N)计算Z与Zi的距离Di若Di≤T则判定Zi属于Z为中心的那个类若Di>T则把Zi作为新的类中心Z。然后对剩下的样本Zi分别计算与ZZ的距离DiDi若其中较小者≤T则判定Zi属于较小的那一类否则就把Zi作为新的一个类的中心Z如此继续直至对全体样本做完处理。特点:不需要事先决定类数。适用于类内距离小类间距离大的情况。否则结果与取样本的顺序有关亦与T相关。CCCCCC相似性尺度()>T>T>T最大距离样本思路:取尽可能离得远的样本做中心。有N个样本Zs={Z,Z,,ZN}任取一个样本例如Z把Z作为第一个类的中心Z=Z从集合Zs中找出到Z距离最大的样本作为Z对Zs中剩余样本Zi分别计算到ZZ的距离。令其中较小的那个为izD计算}{maxiZsDZ。若其值大于某一计算值或给定阈值则取此Zi为新的类中心。计算值可取:大于等于Z和Z间距离的nm倍(<≤mn)。重复同样的处理直到再也找不到符合条件的新的类中心。把剩余样本分配到离它最近的那个中心所属的类缺点:与首先选取哪个样本有关。K平均聚类法(距离平方和最小聚类法)假设要聚成K个类。由人为决定K个类中心Z(),Z(),,Zk()。在第k次叠代中样本集{Z}用如下方法分类:对所有i=,,,Ki≠j若||)(||||)(||kZZkZZij−<−则)(kSZj∈令由得到的Sj(k)的新的类中心为Zj(k)令∑∈−=)(||)(||kSZjjjkZZJ最小。j=,,,K则∑∈=)()(kSZjjjZNkZNj:Sj(k)中的样本数。对于所有的j=,,,K若Zj(k)=Zj(k)则终止。否则goto。开始时K的选择:最初选择哪些样本作为中心将对叠代产生影响。多次叠代多次修正。叠代自组织(ISODATA)聚类法IterativeSelfOrganizingDataAnalysisTechnologyAlgorithm思路:给定一些大致参数(根据目的)。原则:①样本数太少的类取消②类内离散太大的类分裂③距离近的类合并。)给一些参数K:期望分类个数的大致范围Kθ:一个类内的最少样本数Sθ:关于类内分散程度的参数Cθ:关于类间距离(最小)的参数L:每次叠代允许合并的类数I:允许叠代的最大次数)适当选取类中心{Z,Z,,ZNc}Nc:类数)’分配样本。如果有{i=,,,Nc}||||||||ijZZZZ−≤−则cjNjSZ,,,,=∈)如果Sj类样本数kjNθ<则取消Sj类。Nc=Nc,goto)’)重新计算各类中心cSZjjNjZNZj,,,,==∑∈)计算类Sj内平均距离∑∈=−=jSZcjjjNjZZND,,,||,||)对全体样本求类内距离平均值∑∑===⋅=ccNjjNjjjNNDNND,)a如果叠代次数≥I则转向)(合并)b若KNc≤则转向)(分裂)c若偶数次叠代或KNc≥则转向)(合并))计算各类中各分量的标准差∑∈−=jSZijikjijzxN)(σi=,,,nj=,,,Nck=,,,Njxik为jSZ∈的第i个分量zij为Zj的第i个分量。ijσ为第j类第i个分量标准差)找到各类的标准差最大的分量cnjjjjNj,,},,,,max{max==σσσσ)分裂:条件Sjθσ>max且DDj>且)(>kjNθ条件Sjθσ>max且KNc≤若满足两条件之一则分裂Sj(a)建立jZ和−jZ个新的类中心Nc=Nc其中jZ和−jZ是沿着maxjσ轴在原来的Zj位置上分别加上和减去一个数)(max≤<kkjσ。k是经验值。(b)goto)’(分配样本)。)计算所有各类中心的相互距离ccjiijNijNiZZD,,,,,,||,||==−=−)对于比cθ小的Dij从小到大排队。假定为LLjijijiDDD≤≤≤)按l=,,,L的顺序把lljiD对应的liZ和ljZ合并,*−==ccjjiijilNNZNZNNNZllllll计算lljiD时的ZiZj若至少其中一个是在本次叠代中合并取得类中心则越过此项。)若叠代次数≥I或参数无改变则终止。否则goto)’需要时可返回)修改参数。ISODATA法的改进聚类好:满足客观需要客观标准客观性:类内近可能相似(类内距小)类间相似性尽可能小(类间距大)定义一个类间相似性:定义:Dii是类i的类内离散程度例如||||⎥⎦⎤⎢⎣⎡−=∑=iNjijiiiZZND其中Ni为i类中样本数Zi为i类的中心。类间距:)(⎥⎦⎤⎢⎣⎡−=∑=nkkjkiijzzD其中kiz为Zi中的第k个分量。情况⑴若Djj=Dkk且Dij<Dik则),,(),,(kkikiiikjjijiiijDDDRDDDR>其中Rij,Rik为相似度。情况⑵若Dij=Dik且Djj<Dkk则),,(),,(kkikiiikjjijiiijDDDRDDDR>。定义:类间相似性(测度)ijjjiiijDDDR=其中Dii,Djj,Dij有各种定义。在ISODATA每次分配样本后评估某一类i与其它所有各类的相似性计算i=,,,NcNc为当前类数。当ji≠令{}ijiRijjR≠=,max计算∑==cNiicRNR:各类相似性最大值的平均。当R最小时可以认为聚类最优。本方法作为一种评估标准用于调整聚类情况。而ISODATA法是一种手段一种过程手段和评估可以分离即该评估标准不一定要用ISODATA法。例:某个样本一般每类我们用一个点作为中心例如Zi,Mi等(平均值)。如果分布对于中心非完美对称则结果有时不能令人满意。基于“核”的评估聚类方法例:RNcmin类内距离(离散程度)属于该类样本SZ∈Z到Sj类“核”的距离*假定全部样本已聚成Nc类{}NcSSSS,,,=当ji≠时φ=∩jiSS每个类都有自己的“核”},,,{NcEEEE=每个核内样本数M,M,,MNc每个类内样本数N,N,,NNc定义:样本Z到核内一点Z距离为d(X,Z)例如欧氏距离样本Z到i类“核”的距离∑∈=iEZiZXdEZD),(),(定义每一个类内距离和:∑∑∈∈=iiSXEZiiZXdSED),(),(X分配到各类的原则:若),(),(jiEXDEXD≤则判定iSX∈。如何确定Ei?目前为计算方便各类核的点数一般相同。对属于Si类的Ni个样本每次取M个样本计算类内距离iiMNC哪一组Ei类内距离小但计算量大。每类中心(核)可有多个点分层次聚类法(最短距离法)最简单的聚类方法最大距离样本K平均聚类法(距离平方和最小聚类法)叠代自组织(ISODATA)聚类法ISODATA法的改进

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/7

聚类算法综述

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利