数据挖掘与数据分析：基于R语言- 课件 第8、9章 层次聚类、k均值聚类

DataMiningandDataAnalysiswithR数据挖掘与数据分析：基于R语言合作QQ：243001978第八章层次聚类合作QQ：243001978算法原理01算法示例02模型理解03R语言编程04章节内容8.1

算法原理图8-1层次聚类树状图和嵌套簇图聚类分析是一种典型的无监督学习，将未知类别的样本按照一定的规则划分成不同的类或簇，从而揭示样本之间的内在性质和相互之间的联系。聚类被广泛应用于医学、生物学、市场营销、心理学和数据挖掘等领域。层次聚类是最常用的聚类方法之一，它通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树，如图8-1所示。自下而上的凝聚法（Agglomerative）和自顶向下的分裂法（Divisive）是两种层次聚类的基本方法。凝聚层次聚类凝聚层次聚类是一种常见的聚类方法，从单个样本点作为类开始，不断合并最相似的两个类，直到所有类聚成一类为止。算法步骤如下：①定义每个观测值（样本点）为一类；②计算任意两类之间的距离，度量样本间的相似度；③合并距离最近（相似度最高）的两个类；④重复步骤②和③，直到所有类合并为一类。在上述过程中，最重要的环节是计算样本点间、类之间的距离，下面将介绍具体距离度量准则。凝聚层次聚类

凝聚层次聚类类之间距离度量：最小距离：将两个类中距离最近的样本间的距离定义为两个聚类间的距离。最大距离：将两个类中距离最远的样本间的距离定义为两个聚类间的距离。凝聚层次聚类

凝聚层次聚类

分裂层次聚类合作QQ：243001978分裂层次聚类先将所有样本作为一类，然后找出类中距离最远的两个簇并进行分裂，不断重复直到每个样本为一类。算法步骤如下：①定义所有观测值（样本点）为一类；②计算任意两样本点之间的距离；③找出同一类中距离最远的两个样本点a和b，分别作为两个簇的中心；④若类中剩余的样本点距离类中心a更近，将其分配到以a为中心的类中，否则分配到以b为中心的类中；⑤重复步骤③和④，直到每个观测值为一类。8.2

算法示例图8-65个二维点的集合例8-1：使用最小距离度量类之间的相似度，对如图8-2的样本数据进行凝聚层次聚类。点X坐标Y坐标p10.410.53p20.340.28p30.670.43p40.160.38p50.450.30表8-15个点的坐标p1p2p3p4p5p10.0000.2600.2790.2920.233p20.2600.0000.3620.2060.112p30.2790.3620.0000.5120.256p40.2920.2060.5120.0000.301p50.2330.1120.2560.3010.000表8-25个点的欧式距离矩阵8.2

算法示例p1p2p3p4p5p10.0000.2600.2790.2920.233p20.2600.0000.3620.2060.112p30.2790.3620.0000.5120.256p40.2920.2060.5120.0000.301p50.2330.1120.2560.3010.000

p1{p2,p5}p3p4p10.0000.2330.2790.292{p2,p5}0.2330.0000.2560.206p30.2790.2560.0000.512p40.2920.2060.5120.000更新2.继续找出距离最近的两个簇{p2,p5}和p4，合并为{p2,p4,p5}，并更新距离矩阵。p1{p2,p5}p3p4p10.0000.2330.2790.292{p2,p5}0.2330.0000.2560.206p30.2790.2560.0000.512p40.2920.2060.5120.000更新p1{p2,p4,p5}p3p10.0000.2330.279{p2,p4,p5}0.2330.0000.256p30.2790.2560.0008.2

算法示例3.接着继续找出距离最近的两个簇{p2,p4,p5}和p1，合并为{p1,p2,p4,p5}，更新距离矩阵。4.最后合并剩下的两个簇，即获得最终结果，如下图所示。在树状图中两个簇合并处的高度反映两个簇的距离，例如p2和p5间距离为0.112，即为树状图中两个簇合并时对应的高度。更新p1{p2,p4,p5}p3p10.0000.2330.279{p2,p4,p5}0.2330.0000.256p30.2790.2560.000{p1,p2,p4,p5}p3{p1,p2,p4,p5}0.0000.256p30.2560.000图8-7凝聚层次聚类结果8.2

算法示例例8-2：使用最小距离度量类之间的相似度，对如图8-2的样本数据（例8-1中的相同数据）进行分裂层次聚类，过程如下：将所有样本点聚为一类{p1,p2,p3,p4,p5}找出距离最远的两点p3、p4作为两个子类的中心，并根据距离最近原则将剩余点分配到这两个子类。此时，将原本类分裂为{p1,p3,p5}和{p2,p4}对每个子类，再执行分裂过程，直至所有样本点均属于一类，结束图8-65个二维点的集合p1p2p3p4p5p10.0000.2600.2790.2920.233p20.2600.0000.3620.2060.112p30.2790.3620.0000.5120.256p40.2920.2060.5120.0000.301p50.2330.1120.2560.3010.000表8-25个点的欧式距离矩阵8.2

算法示例例8-2：使用最小距离度量类之间的相似度，对如图8-2的样本数据（例8-1中的相同数据）进行分裂层次聚类，结果如下图所示：图8-8分裂层次聚类结果8.3

模型理解层次聚类的优点：层次聚类中距离和相似度容易定义，算法相对简单。适用于任意形状和任意属性的数据集。层次聚类不需要预先指定聚类数，能够得到不同粒度上的多层次聚类结构。可以使用树形图对聚类结果进行可视化，易于解释和理解。对样本的输入顺序不敏感。层次聚类的缺点：算法时间复杂度较大。过程具有不可逆性，一旦合并或分裂执行，就不能修正。如果某个合并或分裂决策在后来证明是不好的选择，该方法无法退回并更正。合并或分裂需要检查和估算大量的对象或簇，不具有很好的可伸缩性。距离度量的选择最小和最大距离代表簇间距离度量的两个极端，它们对离群点或噪声数据过分敏感。使用平均距离和质心距离是对最小和最大距离之间的一种折中方法，而且可以克服离群点敏感性问题。尽管质心距离计算简单，但平均距离既能处理数值数据又能处理分类数据，具有一定优势。8.4R语言编程game_df<-read.csv("./game.csv",header=TRUE,sep=",")str(game_df)输出:

数据简介：本案例采用北美和欧洲以及其他地区的游戏发行量情况数据集，其中包含游戏发行商（例如任天堂、索尼等），及不同类型游戏的销量和评分等级等详细信息。主要目的是分析2000年以来不同年份发售的游戏间的相似性及差异性。数据导入：使用read.csv()函数读取原始数据集game.csv，并通过str()函数查看详细信息，代码如下：数据导入属性名称属性解释属性示例Name游戏名称NewSuperMarioBros.platform所支持平台DSYear_of_Release发行年份2006Genre游戏类型PlatformPublisher游戏发行商NintendoNA_Sales北美销量11.28EU_Sales欧洲销量9.14JP_Sales日本销量6.5Other_Sales其他地区销量2.88Global_Sales全球总销量29.8Critic_Score测评师评分89Critic_Count评分测评师数量65User_Score用户评分8.5User_Count评分用户数量431Developer游戏开发者NintendoRating游戏分级E数据集属性的解释表格汇总：数据预处理将发布年份从字符串转换为数值删除缺失值过滤发布时间早于2000年的数据game_df$Year_of_Release<-suppressWarnings(as.numeric(as.character(game_df$Year_of_Release)))game_df<-na.omit(game_df)game_df<-subset(game_df,game_df$Year_of_Release>=2000)summary(game_df)输出:聚类分组层次聚类方法：hclust(d,method=…)参数method表示类之间相似性的度量方法，包括："single"、"complete"、"average"、"centroid"和"ward"距离计算方法：dist(x,method=…)参数method含义同上，可取值为"euclidean"、"maximum"、"manhattan"、"minkowski"、"canberra"和"binary"，且默认为欧式距离。聚类分组聚类代码和结果game<-game_df[,6:14]#抽取销量和评分数据set.seed(1234)game<-game[sample(nrow(game),20),]#随机抽取20个数据game<-matrix(unlist(game),nrow=20)#转换成matrixgame.scale<-scale(game)#数据标准化distance<-dist(game.scale)fit.average<-hclust(distance,method="average")plot(fit.average,hang=-1)输出:图8-11不同年份游戏发售数量的相似性及差异性结果分析选择聚类数为4，并对结果进行观察第一类有14个观测值：{9,18,12,5,16,2,14,11,13,6,20,19,1,8}第二类有4个观测值：{3,17,4,10}

第三类有1个观测值：{7}第四类有1个观测值：{15}clusters<-cutree(fit.average,4)#输出每一类内样本的数量table(clusters)输出:结果分析获取每类的中位数，包括原始数据和标准化数据两种度量形式aggregate(as.data.frame(game),by=list(cluster=clusters),FUN=median,na.rm=TRUE)aggregate(as.data.frame(game.scale),by=list(cluster=clusters),FUN=median,na.rm=TRUE)输出:结果分析使用rect.hclust()函数叠加四类，重新绘制树状图plot(fit.average,hang=-1)rect.hclust(fit.average,k=4)输出:图8-13不同年份游戏发售数量平均距离聚类结果分析聚类结果总结第一类游戏比较小众，但较受用户欢迎。其在各地销量较低，但用户和测评师对游戏的评分都比较高；第二类游戏销量和评分都比较低，不被大多数用户喜爱；第三类游戏比较受欢迎，游戏销售量和评分都比较高；第四类游戏销量一般，但用户评分比较高，也是受小众用户喜欢的游戏。本章小结首先详细介绍了层次聚类算法原理，包括凝聚法和分裂法；随后通过示例讲解两种算法的运行过程；接着，为了加深读者对层次聚类的理解，介绍了层次聚类的优缺点以及距离度量的选择；最后利用R语言对层次聚类过程进行实践。DataMiningandDataAnalysiswithR数据挖掘与数据分析：基于R语言合作QQ：243001978第九章K均值聚类合作QQ：243001978算法原理01算法示例02模型理解03R语言编程04章节内容9.1

算法原理K均值聚类是经典的划分聚类算法，是一种迭代的聚类分析算法，在迭代过程中不断移动聚类中心，直到聚类准则函数收敛为止，迭代步骤如下：①随机选择K个点作为质心；②将每个数据对象划分到距离最近的质心所在的类中；③计算每个类中数据对象的均值作为新的质心；④重复步骤②和③,直到质心不再发生变化或达到最大迭代次数。最优K值选取

最优K值选取手肘法SSE和K值关系示例图：

从上图目测,肘部对应的K值为4,即为最佳聚类数。当目测法难以识别肘部位置时，可以通过观测斜率、斜率变化量等指标进行定量判断。最优K值选取

最优K值选取

距离度量

K均值算法延伸K-Means++：对K均值算法随机初始化质心的过程进行优化，使初始质心的选择更合理，从而提升算法收敛速度。elkanK-Means：利用两边之和大于第三边，以及两边之差小于第三边的三角形性质，来减少距离的计算，相较于传统的K-Means迭代速度有很大的提高。MiniBatchK-Means：使用样本集中的部分样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快，但聚类的精确度也会有所降低。为了增加算法的准确性，一般会运行多次MiniBatchK-Mean算法，并选择其中最优的聚类簇。9.2

算法示例例9-1：对如下年龄数据进行聚类：[14,15,16,18,18,20,21,21,23,28,34,40,43,49,60,61]。K值设定为2，随机选择16和23作为两个质心，使用欧式距离。步骤如下：（1）计算距离，并进行第一次迭代将各样本点划分到距离最近的质心所在的类（Group）中，并更新各个聚类的质心（Mean），得到以下分类结果：141516181820212123283440434960611621022455712182427334445239875532205111720263738表9-1各样本点与质心的距离矩阵Group1(16)Group2(23)Mean1(16)Mean2(23)[14,15,16,18,18][20,21,21,23,28,34,40,43,49,60,61]16.236.36表9-2第一次迭代结果9.2

算法示例（2）将两个分组中样本数据的均值作为新的质心，并重复之前步骤Group1(16.2)Group2(36.36)Mean1(16.2)Mean2(36.36)[14,15,16,18,18,20,21,21,23][28,34,40,43,49,60,61]18.445表9-3第二次迭代结果Group1(18.4)Group2(45)Mean1(18.4)Mean2(45)[14,15,16,18,18,20,21,21,23,28][34,40,43,49,60,61]19.447.83表9-4第三次迭代结果Group1(19.4)Group2(47.83)Mean1(19.4)Mean2(47.83)[14,15,16,18,18,20,21,21,23,28][34,40,43,49,60,61]19.447.83表9-5第四次迭代结果9.2

算法示例（3）算法终止条件：新求得的质心和原质心相同，如表9-5所示。最终，得到以下两类：Group1(19.4)=[14,15,16,18,18,20,21,21,23,28]Group2(47.83)=[34,40,43,49,60,61]Group1(19.4)Group2(47.83)Mean1(19.4)Mean2(47.83)[14,15,16,18,18,20,21,21,23,28][34,40,43,49,60,61]19.447.83表9-5第四次迭代结果9.3

模型理解K均值聚类优点：聚类效果较优。原理比较简单，比较容易实现，收敛速度快。算法可解释性比较强。K均值聚类缺点：K值选取不当可能会导致较差的聚类结构。采用迭代方法，得到的结果只是局部最优，在大规模数据上收敛较慢。如果各隐含类别的数据不均衡，会导致聚类效果不佳。不适合发现非凸面形状的簇，或者大小差别很大的簇。对噪声点和异常点比较敏感。初始聚类中心的选择很大程度上会影响聚类效果。9.4R语言编程案例使用R语言内置的iris数据集，忽略种类变量Species，对150种鸢尾花植物样本进行K均值聚类分析，数据集情况如下：#R编程示例-iris数据集head(iris)输出:

属性名称属性解释属性示例Sepal.Length花瓣长度5.1Sepal.Width花瓣宽度3.5Petal.Length花萼长度1.4Petal.Width花萼宽度0.2Species所属物种setosa表9-6iris数据属性解释数据预处理对花瓣长度、花瓣宽度、花萼长度和花萼宽度四种属性进行z-score标准化处理df<-scale(iris[1:4])head(df)输出:

确定最佳K值R语言factoextra包中的fviz_nbclust()函数可对最佳K值进行选择

fviz_nbclust(x,FUNcluster=NULL,method=c(“silhouette”,“wss”,),diss=NULL,k.max=10,...)，参数含义如下：

FUNcluster：用于聚类的函数，可用的参数值为：kmeans,cluster::pam,cluster::clara,cluster::fanny,hcut等；method：用于评估最佳簇数的指标；diss：相异性矩阵，由dist()函数产生的对象，如果设置为NULL，那么表示使用dist(data,method="euclidean")计算data参数，得到相异性矩阵；k.max：最大的簇数量，至少是2。确定最佳K值