聚类算法教材.docx

 TOC \o 1-3 \h \z \u  HYPERLINK \l _Toc438043363 聚类算法实践（一）——层次聚类、K-means聚类  PAGEREF _Toc438043363 \h 1  HYPERLINK \l _Toc438043364 聚类算法实践（2）——谱聚类、Chameleon聚类  PAGEREF _Toc438043364 \h 7  HYPERLINK \l _Toc438043365 聚类算法实践（3）——PCCA、SOM、Affinity Propagat  PAGEREF _Toc438043365 \h 14  聚类算法实践（一）——层次聚类、K-means聚类 所谓聚类，就是将相似的事物聚集在一起，而将不相似的事物划分到不同的类别的过程，是数据分析之中十分重要的一种手段。比如古典生物学之中，人们通过物种的形貌特征将其分门别类，可以说就是一种朴素的人工聚类。如此，我们就可以将世界上纷繁复杂的信息，简化为少数方便人们理解的类别，可以说是人类认知这个世界的最基本方式之一。 在数据分析的术语之中，聚类和分类是两种技术。分类是指我们已经知道了事物的类别，需要从样品中学习分类的规则，是一种有指导学习；而聚类则是由我们来给定简单的规则，从而得到分类，是一种无指导学习。两者可以说是相反的过程。 网上关于聚类算法的资料很多，但是其实大都是几种最基本的方法，如K-means、层次聚类、SOM等，以及它们的许许多多的改进变种。这里，我就来讨论一下这些聚类算法，对它们的表现做一个简单的评估。因为内容有点多（其实主要是图占位置……），所以准备分几次来完成。 基本测试 0、测试数据集 ??????在介绍这些算法之前，这里先给出两个简单的测试样品组，下面每介绍完一个算法，可以直接看看它对这两个样品组的聚类结果，从而得到最直观的认识。 下图就是两个简单的二维样品组： 1）第一组样品属于最基本的聚类测试，界线还是比较分明的，不过三个cluster的大小有较明显差异，可以测试一下算法对cluster?size的敏感度。样品总共有2000个数据点。 2）第二组是典型的甜甜圈形。使用这样的测试组主要是为了考察算法对cluster形状敏感度。共有1500个数据点。 对于这样的两个样品组，人类凭肉眼可以很容易地判断它们应该分为三个cluster（特别是我还用颜色做了区分……），但对于计算机就不一定了，所以就需要有足够优秀的聚类算法。 1、相似性度量 ??????对于聚类，关键的一步是要告诉计算机怎样计算两个数据点的“相似性”，不同的算法需要的“相似性”是不一样的。 ??????比如像以上两组样品，给出了每个数据点的空间坐标，我们就可以用数据点之间的欧式距离来判断，距离越近，数据点可以认为越“相似”。当然，也可以用 HYPERLINK /heaad/archive/2011/03/08/1977733.html \t _blank 其它的度量方式，这跟所涉及的具体问题有关。 ?2、层次聚类 ?????层次聚类，是一种很直观的算法。顾名思义就是要一层一层地进行聚类，可以从下而上地把小的cluster合并聚集，也可以从上而下地将大的cluster进行分割。似乎一般用得比较多的是从下而上地聚集，因此这里我就只介绍这一种。 ??????所谓从下而上地合并cluster，具体而言，就是每次找到距离最短的两个cluster，然后进行合并成一个大的cluster，直到全部合并为一个cluster。整个过程就是建立一个树结构，类似于下图。 ??????那么，如何判断两个cluster之间的距离呢？一开始每个数据点独自作为一个类，它们的距离就是这两个点之间的距离。而对于包含不止一个数据点的 cluster，就可以选择多种方法了。最常用的，就是average-linkage，即计算两个cluster各自数据点的两两距离的平均值。类似的 还有single-linkage/complete-linkage，选择两个cluster中距离最短/最长的一对数据点的距离作为类的距离。个人经验complete-linkage基本没用，single-linkage通过关注局域连接，可以得到一些形状奇特的cluster，但是因为太过极端，所以效果也不是太好。 ??????层次聚类最大的优点，就是它一次性地得到了整个聚类的过程，只要得到了上面那样的聚类树，想要分多少个cluster都可以直接根据树结构来得到结果，改变cluster数目不需要再次计算数据点的归属。层次聚类的缺点是计算量比较大，因为要每次都要计算多个cluster内所有数据点的两两距离。另外，由于层次聚类使用的是贪心算法，得到的显然只是局域最优，不一定就