例3.欧洲语言例子similarity=read.table("http://staff.ustc.edu.cn/~ynyang/vector/data/Euro-language1.txt"similarity=as.matrix(similarity)Cluster Dendrogramd=10-similarity#相似性转为距离#或 dij = /si + sjj - 2sijd=as.dist(d) #myclust=hclust(d,method="complete")plot(myclust）#画树图（右图）#树图的其它画法：library(ape)co=c(rep("blue",5),ep("red",4),rep("darkgreen",2)plot(as.phylo(myclust),type="unrooted")plot(as.phylo(myclust),type="fan",tip.color=co)GermaDutchHungarianFinnishPolishPolishSpaienahian11
11 例3.欧洲语言例子 similarity=read.table("http://staff.ustc.edu.cn/~ynyang/vector/data/Euro-language1.txt") similarity=as.matrix(similarity) d=10-similarity # 相似性转为距离 #或 𝑑𝑖𝑗 = 𝑠𝑖𝑖 + 𝑠𝑗𝑗 − 2𝑠𝑖𝑗 d=as.dist(d) # myclust= hclust(d, method=“complete") plot(myclust) #画树图（右图） #树图的其它画法： library(ape) co=c(rep("blue",5), ep("red",4),rep("darkgreen",2)) plot(as.phylo(myclust), type = “unrooted”) plot(as.phylo(myclust), type = “fan“,tip.color=co)
install.packages("BiocManager")BiocManager::install("ggtree")# Updateall/some/none?[a/s/nl:nlibrary(ggtree)hc=hclust(d)ggtree(hc,layout="circular")+Hungxlim(0,7)+geom_tiplab2(offset=0.1,乌拉尔size=5)+Finnish#geom_text(aes(label=node)+Danishgeom_highlight(node = 13,fill="red")+geom_highlight(node=15,fill="steelblue")+geom_highlight(node=16,fill="forestgreen")+m日其号geom_cladelabel(node=13,label="拉丁"offset=1.2,barsize=2,vjust=-0.5,color="red")+geom_cladelabel(node=15,label="日耳曼"offset=1.2,barsize = 2,hjust=1.2,vjust=1.5,color="steelblue")+geom_cladelabel(node=16,label="乌拉尔"offset=1.2,barsize=2,hjust=1.2,color="forestgreen")12
12 install.packages("BiocManager") BiocManager::install("ggtree") # Update all/some/none? [a/s/n]: n library(ggtree ) hc =hclust(d) ggtree (hc,layout="circular")+ xlim(0,7)+ geom_tiplab2(offset=0.1, size=5)+ # geom_text (aes(label=node))+ geom_highlight(node = 13,fill="red")+ geom_highlight(node=15,fill="steelblue")+ geom_highlight(node=16,fill="forestgreen")+ geom_cladelabel(node=13,label="拉丁", offset=1.2,barsize = 2, vjust = -0.5,color="red")+ geom_cladelabel(node=15,label="日耳曼", offset=1.2,barsize = 2, hjust=1.2,vjust=1.5,color="steelblue")+ geom_cladelabel(node=16,label="乌拉尔", offset=1.2,barsize = 2, hjust=1.2,color="forestgreen")
各种连结的比较Complete方法以两个类的最远的点之间的距离来决定两个类是否应该聚合或拆分，因而适合类内较为紧密，类之间分离的较好的情形。·Single方法容易形成长链式的聚集效果，因而对非线性的聚族数据聚类效果可能较好（右图）。.Variahle!●Average方法介于single、complete之间。(a) Single linkage conf used by inear overla●层次聚类计算复杂度0（nlog（n））Centroid，median较为稳健，但可能会产生逆序(inversion)现象（右图）。BAC·Ward合并使得组间平方和变化最小的两类。13
13 各种连结的比较 Complete方法以两个类的最远的点之间的距离来决定两个类是 否应该聚合或拆分，因而适合类内较为紧密，类之间分离的较好 的情形。 Single方法容易形成长链式的聚集效果，因而对非线性的聚簇数 据聚类效果可能较好（右图）。 Average方法介于single、complete之间。 层次聚类计算复杂度 𝑂(𝑛log(𝑛)) Centroid, median 较为稳健，但可能会产生逆序(inversion)现象 （右图）。 Ward合并使得组间平方和变化最小的两类
K-medoid聚类K-medoid聚类算法使用距离矩阵进行聚类，各类的中心限定为某个个体，称为medoid。尤其适用于只有主观距离而没有原始向量数据的情形。定义(medoid)：假设n个个体的距离矩阵为D=(d,）nn,与其它中心点Medoid点的距离之和最小的点定义为n个个体的中心(medoid)：7medoid = arg minaje(I,...,n)i=l假设n个个体的距离为D=(d,)nn,d,=dist(i,j),K-medoid方法K-medoid聚类问题求解{12....n的K划分C.Ck及其中心medoidsm..mk)C(1,2...n)使得组内距离之和极小2Zdist(i, m)=min!k=l ieCk14
14 medoid arg min . (medoid) (medoid): ( ) , 1 {1,., } n i ij j n ij n n d n n D d 点的距离之和最小的点定义为 个个体的中心 ： 定义 假设 个个体的距离矩阵为 与其它 ！ 使得组内距离之和极小： 求解 的 划分 及其中心 假设 个个体的距离为 方法 dist( , ) min {1,2,., }, {1,2,., } - ,., { ,., } ( ) , dist( , ), -medoid 1 1 1 K k i C k K K ij n n ij k i m n n K C C medoids m m n D d d i j K 𝐾-medoid聚类 中心点 Medoid K-medoid 聚类问题 K-medoid聚类算法使用距离矩阵进行聚类，各类的中心限 定为某个个体，称为medoid。 尤其适用于只有主观距离 而没有原始向量数据的情形
·当划分已知时，根据定义，容易确定各类的中心：K-medoid当各类中心已知时，我们只需把每个个体划分到离其最近算法的中心所在的类；给定划分或中心的初始值，上述两步递归迭代。K-medoid clustering算法：1给定1,2..n的一个划分C...Ck,对每一个类<k≤K,类内与其它个体总距离最小的点m,EC,作为中心：m = arg min Zjec dy2．给定当前的中心mk,k=1.,K},将每个个体划分到离它最近的中心所属的类中，即对所有1≤i≤n,求k, =argmindim,1<k,≤K,并将个体i划归到第k类。由此得到更新的划分Ci,Ck3.送代1-215
15 K-medoid 算法 3. 1- 2 ,., . arg min 1 , 1 , 2. { , 1,., }, argmin 1. {1,2,., } ,., , 1 , -medoid clustering 1 1 1 迭代 并将个体 划归到第 类。由此得到更新的划分 ， 的中心所属的类中，即对所有 求 给定当前的中心 将每个个体划分到离它最近 与其它个体总距离最小的点 作为中心： 给定 的一个划分 对每一个类 类内 算法： i K im i k K i k j C ij i C k k k K i k C C k d k K i n m k K m d m C n C C k K K k k k • 当划分已知时，根据定义，容易确定各类的中心； • 当各类中心已知时，我们只需把每个个体划分到离其最近 的中心所在的类；给定划分或中心的初始值， 上述两步递归迭代