2.15 降维和聚类
降维和聚类是两种无监督学习任务中的算法，聚类（Clustering）是将数据按相似度聚成不同的分组，降维（Reducing Dimensionality）是在保留数据结构和有用性的同时对数据进行压缩。本节主要针对降维和聚类一些常见的问题点进行总结。
2.15.1 图解为什么会产生维数灾难
假如数据集包含10张照片，照片中包含三角形和圆形两种形状。现在来设计一个分类器进行训练，让这个分类器对其他的照片进行正确分类（假设三角形和圆形的总数无限大），我们简单用一个特征进行分类，示意图如图2-24所示。
图2-24 一个特征进行分类示意图
从上图可看到，如果只有一个特征进行分类，那么三角形和圆形几乎均匀分布在这条线段上，很难将10张照片线性分类。那么，增加一个特征后的情况会怎么样？其示意图如图2-25所示。
图2-25 两个特征分类示意图
增加一个特征后，我们发现仍然无法找到一条直线将三角形和圆形分开。所以，考虑需要再增加一个特征，其分类效果如图2-26所示。
图2-26 三个特征分类示意图1
此时，可以找到一个平面将三角形和圆形分开，如图2-27所示。
图2-27 三个特征分类示意图2
现在计算一下不同特征数量时的样本密度。
• 当有一个特征时，假设特征空间是长度为5的线段，则样本密度为10÷5=2。
• 当有两个特征时，特征空间大小为5×5=25，样本密度为10÷25=0.4。
• 当有三个特征时，特征空间大小为5×5×5=125，样本密度为10÷125=0.08。
以此类推，如果继续增加特征数量，样本密度就会越来越稀疏，此时，更容易找到一个超平面将训练样本分开。当特征数量增至无限大时，样本密度就变得非常稀疏。
下面看一下将高维空间的分类结果映射到低维空间时，会出现什么情况？图2-28是将三维特征空间映射到二维特征空间后的结果。
图2-28 三维特征空间映射到二维特征空间示意图
虽然在高维特征空间时训练样本线性可分，但是映射到低维空间后，结果正好相反。事实上，增加特征数量使得高维空间线性可分，相当于在低维空间内训练一个复杂的非线性分类器。不过，这个非线性分类器太过“聪明”，仅仅学到了一些特例。如果将其用来辨别那些未曾出现在训练样本中的测试样本，那么通常结果不太理想，会造成过拟合问题。图2-29所示的是采用2个特征的线性分类器分错了一些训练样本示意图。
图2-29 采用2个特征的线性分类器错分样本示意图
图2-29中的分类准确率似乎没有图2-28中的高，但是采用2个特征的线性分类器的泛化能力比采用3个特征的线性分类器要强。因为采用2个特征的线性分类器学习到的不只是特例，而是一个整体趋势，对于那些未曾出现过的样本也可以比较好地辨别开来。换句话说，通过减少特征数量，可以避免出现过拟合问题，从而避免“维数灾难”。
图2-30从另一个角度诠释了维数灾难。
图2-30 维数灾难产生示意图
假设只有一个特征，特征的值域是0到1，那么每一个三角形和圆形的特征值都是唯一的。如果我们希望训练样本覆盖特征值值域的20%，那么就需要三角形和圆形总数的20%。我们增加一个特征后，为了继续覆盖特征值值域的20%，就需要三角形和圆形总数的45%（0.4522≈0.2）。继续增加一个特征后，需要三角形和圆形总数的58%（0.5833≈0.2）。随着特征数量的增加，为了覆盖特征值值域的20%，就需要更多的训练样本。如果没有足够的训练样本，就可能会出现过拟合问题。
通过上述例子，可以看到特征数量越多，训练样本就会越稀疏，分类器的参数估计就会越不准确，更加容易出现过拟合问题。维数灾难的另一个影响是训练样本的稀疏性并不是均匀分布的，处于中心位置的训练样本比四周的训练样本更加稀疏。
假设有一个二维特征空间，如图2-31所示的矩形，在矩形内部有一个内切的圆形。
图2-31 矩形内部包含一个内切圆形的二维特征空间示意图
从图2-31中可看出，越接近圆心的样本越稀疏，因此，相比于圆形内的样本，那些位于矩形四角的样本更加难以分类。当维数变大时，特征超空间的容量不变，但单位圆的容量会趋于0，在高维空间中，大多数训练数据驻留在特征超空间的角落。散落在角落的数据要比处于中心的数据难分类。
2.15.2 怎样避免维数灾难
理论上，如果训练样本的数量无限大，那么就不会存在维数灾难，我们可以采用任意多的特征来训练分类器。但实际上，训练样本的数量是有限的，所以不应该采用过多的特征。
避免维数灾难的一种思路是降维处理。许多高维空间中的数据集可削减至低维空间数据，而不必丢失重要信息。降维的常用方法有投影、流形学习、主成分分析、核主成分分析、局部线性嵌入、小波分析法等。
此外，自动编码利用神经网络产生的低维来代表高维输入，克服了传统降维方法（比如主成分分析）对提取特征维度有限制的缺点。
2.15.3 聚类和降维
聚类和降维都可以作为分类等问题的预处理步骤。
下面是聚类和降维的区别。
聚类用于找寻数据内在的分布结构，既可以作为一个单独的过程，比如异常检测等，也可作为分类等其他学习任务的前驱过程。聚类是标准的无监督学习。在一些推荐系统中需确定新用户的类型，但定义用户类型可能不太容易，此时往往可先对原有的用户数据进行聚类，根据聚类结果将每个簇定义为一个类，然后再基于这些类训练分类模型，用于判别新用户的类型。聚类的示意图如图2-32所示。
图2-32 聚类示意图
降维则是为了缓解维数灾难的一个重要方法，就是通过某种数学变换将原始高维属性空间转变为一个低维“子空间”。其基于的假设就是，虽然人们平时观测到的数据样本是高维的，但是实际上真正与学习任务相关的是低维度的分布。从而通过最主要的几个特征维度就可以实现对数据的描述，对于后续的分类很有帮助。比如，对于Kaggle上的泰坦尼克号生还问题。通过给定一个乘客的许多特征如年龄、姓名、性别、票价等，来判断其是否能在海难中生还。这就需要首先进行特征筛选，从而能够找出主要的特征，让学习到的模型有更好的泛化性。
虽然都能实现对数据的约减，但是二者适用的对象不同，聚类针对的是数据点，而降维针对的是数据的特征。另外它们有着很多种实现方法，聚类中常用的方法有k-means、层次聚类、基于密度的聚类等；降维中常用的方法则有PCA、Isomap、LLE等。
2.15.4 聚类算法优劣的衡量标准
不同聚类算法的优劣可从以下方面进行衡量判断。
（1）算法的处理能力：处理大的数据集的能力，即算法复杂度；处理数据噪声的能力；处理任意形状，包括有间隙的嵌套的数据的能力。
（2）算法是否需要预设条件：是否需要预先知道聚类个数，是否需要用户给出领域知识。
（3）算法的数据输入属性：算法处理的结果与数据输入的顺序是否相关，也就是说算法是否独立于数据输入顺序；算法处理有很多属性数据的能力，也就是对数据维数是否敏感，对数据的类型有无要求。
2.15.5 聚类和分类
聚类：简单地说就是把相似的东西分到一组，聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起。一个聚类算法通常只需要知道如何计算相似度就可以开始工作了，因此聚类通常并不需要使用训练数据进行学习，在机器学习中属于无监督学习。
分类：对于一个分类器，通常需要你告诉它“这个东西被分为某某类”。在一般情况下，一个分类器会从它得到的训练集中进行学习，从而具备对未知数据进行分类的能力，在机器学习中属于监督学习。
2.15.6 聚类算法的性能比较
不同聚类算法的性能比较如表2-23所示。
表2-23 不同聚类算法的性能比较
2.15.7 4种常用聚类方法比较
主要的聚类算法可以划分为如下几类：划分方法、层次方法、基于密度的方法、基于网格的方法，以及基于模型的方法。下面主要介绍k-means聚类算法、层次聚类算法、神经网络自组织映射（Self-Organizing Maps，SOM）聚类算法，以及模糊C均值（Fuzzy C-means，FCM）聚类算法，并通过通用测试数据集进行聚类效果的比较和分析。
k-means聚类算法
k-means是划分方法中较经典的聚类算法之一。该算法效率高，在对大规模数据进行聚类时被广泛应用。
k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。
k-means算法的处理过程如下：首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心；其次，对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；然后重新计算每个簇的平均值。
这个过程不断重复，直到准则函数收敛。通常，采用平方误差准则，其定义如下：
这里的E是数据中所有对象的平方误差的总和，p是空间中的点，mi是簇ci的平均值。该目标函数使生成的簇尽可能紧凑独立，使用的距离度量是欧几里得距离，当然也可以用其他距离度量。
算法流程：
输入：包含n个对象的数据和簇的数目k。
输出：n个对象到k个簇，使平方误差准则最小。
步骤：
（1）任意选择k个对象作为初始的簇中心。
（2）根据簇中对象的平均值，将每个对象（重新）赋予最类似的簇。
（3）更新簇的平均值，即计算每个簇中对象的平均值。
（4）重复步骤（2）、（3）直到簇中心不再变化。
层次聚类算法
根据层次分解的顺序是自底向上的还是自上向下的，层次聚类算法分为凝聚型层次聚类算法和分裂型层次聚类算法。凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。
以采用最小距离的凝聚型层次聚类算法为例。
算法流程：
（1）将每个对象看作一类，计算两两之间的最小距离。
（2）将距离最小的两个类合并成一个新类。
（3）重新计算新类与所有类之间的距离。
（4）重复（2）、（3），直到所有类最后合并成一类。
SOM聚类算法
SOM神经网络假设在输入对象中存在一些拓扑结构或顺序，可以实现从输入空间（n维）到输出平面（二维）的降维映射，其映射具有拓扑特征保持性质，与实际的大脑处理有很强的理论联系。
SOM神经网络包含输入层和输出层。输入层对应一个高维的输入向量，输出层由一系列组织在二维网格上的有序节点构成，输入节点与输出节点通过权重向量连接。在学习过程中，找到与之距离最短的输出层单元，即获胜单元，对其更新。同时，将邻近区域的权值更新，使输出节点保持输入向量的拓扑特征。
算法流程：
（1）网络初始化，对输出层每个节点权重赋初值。
（2）从输入样本中随机选取输入向量并且归一化，找到与输入向量距离最小的权重向量。
（3）定义获胜单元，在获胜单元的邻近区域调整权重使其向输入向量靠拢。
（4）提供新样本、进行训练。
（5）收缩邻域半径，减小学习率，并不断重复，直到输出节点值小于允许值，输出聚类结果。
FCM聚类算法
用模糊数学的方法进行聚类分析，就是模糊聚类分析。FCM算法是一种以隶属度来确定每个数据点属于某个聚类程度的算法。该聚类算法是传统硬聚类算法的一种改进。
设数据集
，它的模糊c划分可用模糊矩阵U=[uij]表示，矩阵U的元素uij表示第j（j=1,2，…，n）个数据点属于第i（i=1,2，…，c）类的隶属度，uij满足如下条件：
目前被广泛使用的聚类准则是取类内加权误差平方和的极小值。即：
其中V为聚类中心，m为加权指数，
。
算法流程：
（1）标准化数据矩阵。
（2）建立模糊相似矩阵，初始化隶属矩阵。
（3）算法开始迭代，直到目标函数收敛到极小值。
（4）根据迭代结果，由最后的隶属矩阵确定数据所属的类，显示最后的聚类结果。
4种聚类算法试验
选取专门用于测试分类、聚类算法的国际通用的UCI数据库中的IRIS数据集，在数据集上执行不同的聚类算法，可以得到不同精度的聚类结果。基于前面描述的各算法原理及流程，可初步得如表2-24所示的聚类结果。
表2-24 4种聚类算法比较
注：
• 聚错样本数：总的聚错的样本数，即各类中聚错的样本数的和。
• 运行时间：即聚类整个过程所耗费的时间，单位为s。
• 平均准确度：设原数据集有K个类，用ci表示第i类，ni为ci中样本的个数，mi为聚类正确的个数，则mi/ni为第i类中的精度，则平均精度为：
。