第9章 聚类分析进阶问题
9.1有哪些数据特性，会影响聚类算法结果？
面试官：有哪些数据特性，会影响聚类算法的结果？
程序员大树：数据特性影响着聚类分析的效果。
高维性。在高维数据集中，密度定义越来越局限（单位体积中点的个数），因为维数增加，体积会迅速增加，而点个数却没有太大改变，这样导致了密度趋向于0。解决方法是用维归约技术，摒弃不重要的特征；或者重新定义邻近度和密度的概念。
噪声和离群点。我们应尽可能剔除噪声和离群点。离群点会严重降低聚类算法性能，会误导合并两个本不该合并的簇。应当在聚类算法之前，先用算法删除或减少噪声和离群点的影响。这往往是聚类算法使用前首先要考虑的。比如在DBSCAN里，会将低密度点分类成噪声，并在聚类时把他们排除在外。
属性和数据集类型。数据集有不同的类型，比如结构化、图形的、有序或者无序；属性可以是离散的或者连续的、定量或者定性的等。甚至一些情况下，邻近性都很难下定义，要用特殊的数据结构来处理特定类型的数据。
尺度。不同的属性，用不同尺度度量，可能会影响两个对象间的距离和相似性，进而影响聚类分析结果。一般可以采用减去均值，再除以标准差，给每个属性都标准化，消除不因尺度不同而造成的影响。
规模。许多聚类算法对于中小规模的数据集运行良好，但不能处理大型数据集。因此数据规模也会影响聚类算法的结果。
9.2 如何使用基于原型的聚类？
面试官：什么是模糊聚类？
程序员大树：我们理想情况是能把对象明确分成不相交的簇，然而实际情况下，大部分都不能划分成明显分离的簇，而会有一定的随机性。我们可以把每个对象对每个簇给予一个权值，说明该对象属于簇的概率。
模糊聚类通常使用基于模糊c-means算法，简称为FCM算法，过程是：
1. 选择一个初始模糊伪划分，并对所有
2. 使用模糊伪划分，计算每个簇的质心。
3. 重新计算模糊伪划分，即
4. 重复过程2，3，直到质心不发生变化。（或者变化的绝对值低于一个阈值。或者误差的变化低于一个阈值。）
9.3 什么是基于网格的聚类？
面试官：网格的思想是什么？基于网格的聚类算法是怎样的？
程序员大树：网格是一种基于密度计算的有效方法。主要思想是，将每个属性值可能值尽可能分割成许多相邻区间，创建网络单元格，每个单元格可以看成是等大的。扫描数据时，可以把对象指派到网格单元中，并计算每个单元格的密度。
网格聚类算法步骤如下：
1. 定义一个网格单元集。
2. 将对象指派到合适的单元，并计算每个单元的密度。
3. 删除密度低于指定阈值r的单元。
4. 将邻近稠密单元组成簇。
9.4 什么是基于图的聚类？
面试官：图聚类的思想是什么？
程序员大树：我们可以使用图聚类算法，利用图的性质和特性，方便和简化计算。
稀疏化邻近度图。稀疏化图，思想是尽可能只保留对象与其最近邻之间的连接。通过稀疏化，数据量被大幅度压缩了。另外可以更好的聚类，降低噪声和离群点的影响。稀疏化临近矩阵图的过程如下图所示：
最小生成树分裂层次聚类算法：
1. 计算相异图的最小生成树。
2. 断开最大相异度的边，创建一个新的簇。
3. 重复第2步，直到只剩下单个簇（不可再拆分）。
这样可以使所有生成树的边总权值最小。
OPOSSUM聚类。它是一种专门为文档等稀疏、高维数据等聚类技术，基于邻近度图的稀疏化聚类。它所用的相似性度量，将图划分成k个分支（k为用户定义），以最小化分支之间边的权值。同时实现平衡约束，包括簇中对象个数或者簇内属性和的粗略值相等。
Chameleon聚类。它由三部分组成：稀疏化、图划分和层次聚类。首先是构建k-最邻近图，并用图划分算法划分数据集。然后二分当前最大的子图，不断重复此步，直到没有一个簇多余MAX_SIZE（用户指定）个点为止。
9.5 什么是可伸缩的聚类算法？
面试官：可伸缩是指一些数据是非线性的。那么对这样的数据，如何做聚类算法？
程序员大树： 可伸缩性聚类算法主要用于超大型数据集。
许多聚类算法的存储量是非线性的，比如层次聚类，其存储复杂度是O(m2)，m是对象的个数。所以应尽量减少计算量和存储量。对这样的数据做聚类算法有以下几种方法：
1. 多维或空间存取方法。在找出最近的质点、点最近邻点时，可以用多维或空间存取方法来执行任务，比如用k-d树，它可以用于分割多维空间的数据结构，其每一个节点是一个多维坐标。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。2. 邻近度界。使用邻近度界可以避免反复计算邻近度。比如在k-means计算中，需要评估点属于当前簇，还是移动到新簇。如果计算邻近度，算法是非常麻烦的。如果知道质心间距离，及点到所属质心距离，则可以采用三角不等式建立邻近度界，以避免计算到其他各个质心点距离。
3. 划分数据对象。我们可以用有效的技术，将数据划分成不相交的集合，再对这些集合结果合并。比如之前我们在k-means中找k个簇，每次迭代时候都要算每个点到每个簇质心点距离，如果k很大的话，开销会特别大。如果使用二分k-means法，先用二分法重分整个集合，之后每一步只需要计算点的一个子集到二分后两个被考虑的质心的距离，减少了计算量。
9.6 如何进行聚类算法的选择？
面试官：有这么多的聚类算法，在选择聚类算法时要考虑哪些条件？
程序员大树：需要考虑的条件：
（1）聚类的类型。比如对于需要划分层级结构的，用层次聚类是首选的。对于目的是汇总的聚类，应该选划分聚类。有些情况下，可以使用二者的结合，称作混合聚类。
（2）簇的类型。簇的类型包含基于原型、基于图和基于密度。基于原型的簇容易产生全局簇，其中每个对象与簇的原型足够近。基于图和密度的，易产生非全局簇，因为包含很多不相似的对象。
全局簇是指最终全局产生一个大簇；非全局簇指的是存在一些局部簇，不用合并成全局簇。
基于原型的簇可以用 k-means算法。基于图的簇可以用Chameleon聚类算法、OPOSSUM聚类等。基于密度的簇可以用DBSCAN算法。
（3）数据集和属性。数据集和属性类型可能决定算法类型。比如对k-means，数据集对质心计算很重要，然而对于凝聚层次聚类，只要建了邻近矩阵，数据集和属性就不那么重要了。（4）噪声和离群点。一方面，估计数据集中的噪声和离群点是非常困难的；另一方面，在某些场景下是噪声和离群点的，在其他场景下可能是有意义的。所以要根据实际情况进行选择。
（5）数据对象的个数。如果数据集特别大，有些聚类算法就会不适用，因为数据不能完全放入内存中，会遇到问题。但像BIRCH这样不要求数据都在内存的技术，就很有效。
百度主管面10人在聊