首页 理论教育 八种系统聚类法

八种系统聚类法

时间:2022-02-12 理论教育 版权反馈
【摘要】:类与类之间距离定义法不同,产生了不同的系统聚类法:最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法及离差平方和法.dij表示样品Xi与Xj的距离,Dij表示类Gi与Gj的距离.●最短距离法:Dij=mindij,Xj∈Gj,Xi∈Gi,即类Gi与Gj之间的距离为两类最近样品之间的距离,当i=j时,规定Dij=0.设Gp与Gp合并为新类Gr,则任一类Gk与Gr的距离为:Dk

类与类之间距离定义法不同,产生了不同的系统聚类法:最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法及离差平方和法.dij表示样品Xi与Xj的距离,Dij表示类Gi与Gj的距离.

●最短距离法:Dij=mindij,Xj∈Gj,Xi∈Gi,即类Gi与Gj之间的距离为两类最近样品之间的距离,当i=j时,规定Dij=0.设Gp与Gp合并为新类Gr,则任一类Gk与Gr的距离为:Dkr=min dij=min Dkp,Dkq,聚类步骤如下:

(1)定义样品之间距离,计算样品的两两距离,得距离阵D(0)=(dijn×n,开始时每个样品自成一类,Dij=dij.

(2)找出D(0)中非对角线最小元素,设为Dpq,将Gp和Gp合为一类Gr,即Gr=[Gp,Gq].如非对角线最小的元素不止一个,则对应类可以同时合并.

(3)给出计算新类与其他类的计算公式:Dkr=min Dkq,Dkp,将D(0)中第p,q行及p,q合并为一个新行,新列,对应Gr,矩阵记为D(1).

(4)对D(1)重复(2)、(3)步骤得D(2),如此下去,直到所有的元素并成一类.实际问题中有时给出一个阈值T,要求类与类之间距离小于T,这样可能会有些样品归不了类.也可用于指标(变量)分类,可以用距离也可用相似系数,用相似系相时,此时公式Dik=min Dip,Diq改为Dik=max Dip,Diq.

●最长距离法:Dpq=max dij,Xi∈Gp,Xj∈Gq,即定义类Gi与Gj之间距离为两类最远样本之间的距离.聚类步骤与最短距离法同.

●中间距离法:如果类与类之间的距离既不采用两者之间的最短也不采用两者之间的最长距离,而是用来两者之间的中间距离,称为中间距离法.

若某一步将Gp和Gq合并为Gr,任一类Gk与Gr的距离公式为:

不失一般性,设Dkp>Dkq.按最短:Dkr=Dkq,按最长:Dkr=Dkp,介于Dkp和Dkq之间的线,直观上以Dpq边的中线为好.计算步骤:开始每个样品自成一类,Dij=dij,得表D(0).然后D(0)中元素平方得D2(0),其并类步骤与最短距离法同,只不过D(l)D(l)的元素改为平方,相应的矩阵记为D2(l),l=0,1,….

●重心法:从物理观点看,类与类之间的距离可以用重心(该类样品的均值)之间的距离来代表.设Gp和Gq的重心为,则Gp和Gq之间的距离,这种定义两类之间距离方法称为重心法.

●类平均法:类重心法未能充分利用各样品的信息,为此可将两类之间距离平方定义为这两类元素两两/元间的距离平方平均,即.

设聚类到某步将Gp和Gq合并为Gr.则任一新类,Gk与Gr的距离为:

●可变类平均法:类平均法公式中没有反映Gp和Gq之间距离Gpq的影响,可以将公式改进为:.

●可变法:定义两类之间的距离同上,而新类Gr与Gk的距离公式为:

●离差平方和法:思想来自于方差分析,如果分类正确,同类样品的离差平方和较小,类与类之间较大.类Gp与Gq的定义为 D2pq=Sr-Sp-Sq,Sr=GpUGq.合并类的公式为:.

先将n个样品自成一类,然后每次减少一类,每次减少一类离差、平方和增大,选择S增大最小的类合并,直到所有样品归为一类为止.采用欧氏距离时,八种聚类公式给一形式为:D2kr=apD2kpqD2kq+βD2pq+γ|D2kp-D2kq|.

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈