第3章〓分布式表示学习和聚类算法 3.1分布式表示学习的概念 分布式表示学习是表示学习中的一个重要分支，其主要思想是将样本对象的特征表示为多个维度的编码单元(统称表征向量)，每个编码单元都能独立地表示对象的不同局部特征。早期广泛使用的表示方法是非分布式表示，其中常用的是稀疏高维的onehot编码表示（又称符号表示）。onehot编码的表征向量中只有一个值为1，其他值均为0，对象的特征由唯一激活的编码单元来体现，所以其每一个表征向量对应一个类别。但是，这样的表征之间是离散的，表征向量除类别信息之外不会包含其他有用的信息，这会造成两个十分相似的样本表征却显得毫不相关。分布式表示学习则采用一个维度为n的k值特征来表示对象的kn种属性，每个维度都对应一个分布式区域，可以表示对象的局部特点，这样就可以使得相似的样本部分区域的属性相同，从而缓解onehot编码所存在的问题。 具体来说，假设有4个样本对象，分别为“水平放置的长方体”“垂直放置的长方体”“水平放置的圆柱体”“垂直放置的圆柱体”，onehot编码表示方法可以如图31所示。其中，每一维度都代表了唯一的类别，黑色圆圈表示1，白色圆圈表示0。onehot编码使用维度为4的二值向量来表示各个对象，这种表示方法很好地区分4个对象的类别，适合用在类别数少或者类别稀疏的分类任务中，如手写数字识别。然而，这种方法在多类别的分类任务中会由于编码长度过长进而影响后续模型的学习。 图31onehot编码表示方法 在一些大型任务，特别是深度学习任务中，onehot编码容易因为高维度从而受到维度灾难的影响。而且，每个编码都代表一个类别，这会使得大型数据集编码变得异常困难。此外，onehot编码的维度之间是相互独立的，没有明确的所属关系，这在很多有交叉类别的任务上，会导致无法有效地挖掘实例对象间的关系。相比较而言，分布式表示方法则可以更好地表示出对象之间的相似性和差异性。如图32所示，分布式表示方法会对前面提及的4个对象进行分割，得到“水平放置”“垂直放置”“长方体”“圆柱体”来表示对象，其中，相同的局部属性会有相同的编码来表示。显然，同样都是用四维向量表示，该方法会比onehot编码更能表示出样本间的相似性。例如，前两个对象分别可以用1010和0110表示，第3位可以看出它们都属于长方体类别，而且它们的第3、4位编码是相同的，可以推断出它们之间存在一定的相似性。由此可见，分布式表示方法确实可以更好地挖掘样本对象之间的关系。 图32分布式表示方法 除了可以在编码表示中包含样本的信息，分布式表示方法也可以缓解维度灾难的问题。假设已获得onehot编码表示或者分布式表示的情况下，现在额外引入一个新的样本对象“正方体”。传统的onehot编码会在原有的维度上进行增加，如图33上半部分所示。由于onehot编码表示是由一组互相排斥的二元向量组成的(有且只有一个值为1的激活单元)，因此，这会导致之前的4个样本对象的表示编码必须发生相应的改变。而分布式表示方法可以依据对象的局部特点进行划分，如“正方体”既可以看成水平放置的长方体也可以看成垂直放置的长方体，所以其可以表示成1110的编码方式。在这种方法下，编码不仅长度可以保持不变，而且可以使得拥有相同的局部特征的样本对象在特征空间中更加靠近。 图33额外引入新对象时的onehot编码表示（上）和分布式表示（下） 由于分布式表示可以让不同样本之间有共享属性，因此其具有丰富的空间相似性，可以使得语义相似的样本在表示空间上更加靠近，而这是单纯的onehot编码表示所无法达到的。从样本空间的角度来看，分布式表示方法可以如图34所示。其中，3个决策边界h1、h2、h3将样本空间切分成多个区域。每个决策边界的h+i即hi=1表示在该边界的正区域，h-i即hi=0表示在该边界的负区域，每个决策边界分别为图34中的一条直线。划分的每个区域可以得到由3个边界所指向的正负区域得到的唯一表示，例如，(1,1,1)T表示h+1∩h+2∩h+3区域的表示。在输入维度是d的情况下，分布式表示会交叉分割半空间(而不是半平面)Rd。具有n个特征的分布式表示给O(nd)个不同区域分配唯一的编码，而非分布式表示只能给n个不同区域分配唯一的编码，如具有n个样本的K近邻算法。因此，分布式表示能够比非分布式表示多分配指数级的区域。 不同非分布式方法的样本空间可以具有不同的几何形状，但它们通常将输入的样本空间划分为若干互斥区域，每个区域具有不同的参数。例如，如图35所示，非分布式表示中的K近邻算法采取直接为每个区域独立地设置不同的参数，因此它可以在给定足够的参数下拟合一个训练集，而不需要复杂的优化算法。然而，这类非分布式表示的模型只能通过平滑先验来局部地泛化，因此在学习波峰波谷多于样本的复杂函数时，该方法是不可行的。 图34基于分布式表示划分样本空间 图35K近邻算法划分的样本空间 相反，在一个具有复杂结构的问题上，分布式表示方法可以用更少量参数去学习更加密集的表示，该方法会更加具有统计学上的优势。因为传统的非分布式表示方法需要在真实模型平滑的假设下才可以得到泛化的效果，例如，在u≈v的情况下，默认得到的学习函数f也会符合f(u)≈f(v)。这个假设对大部分问题是非常有用的，但也很容易受到维度灾难的影响。onehot编码表示将每个区域都视为一个类别或者一个符号，并赋予每个类别或者符号独立的自由度，这虽然可以基于学习到的目标函数去泛化到已有的数据上，但这种映射关系不适合推广到新区域或者新类别上。 从几何角度来解释，onehot编码表示中的每个二元特征将Rd分成一对半空间，n个相应半空间的指数级数量的交集确定了该分布式表示学习器能够区分多少区域。通过应用关于超平面交集的一般结果，这个二元特征表示能够区分的空间数量是 ∑dj=0nj=O(nd)(31) 因此，输入大小会呈指数级增长，隐含单元的数量呈多项式级增长。 而对于分布式表示，在交叉空间Rd中，n个线性阈值划分的O(nd)个参数能够确定出样本空间中的O(nd)个区域。如果对每个区域都使用唯一的符号来指代，每个符号又都使用单独的参数去识别交叉空间Rd的对应区域，那么O(nd)个区域就会对应这O(nd)个样本。除了线性划分交叉空间的情况外，还存在更一般的非线性划分。如果有k个参数的变换可以学习到空间中的r个区域，那么这种方式会比非分布式方式泛化得更好，因为分布式表示在使用较少参数的情况下，就可以满足用O(r)个样本来获得相同的特征并将样本空间分割成r个区域的相同需求。 换句话说，虽然非分布式表示可以明确地划分多个不同区域的编码，但是它们的容量仍是有限的。例如，线性阈值单元神经网络的VC维仅为O(ωlogω)，其中ω是权重的数目。这是由于我们为样本空间分配了很多独立且离散的唯一编码，不能完全使用所有的编码空间。例如，onehot编码有且只有一个值为1的激活值，这就使得编码空间中编码包含2个及以上激活值的编码全被舍弃。除此之外，也不可能使用线性分类器去学习从样本空间h到输出y的任意函数映射。因此，从这个角度出发，就可以看出分布式表示可以传达一种先验知识： 待预测的类在h代表的潜在因子的函数下是线性可分的。一般需要学习的样本类别都会拥有明显的表征区别，而不是需要隐含的非线性逻辑类别。这也很贴切实际情况。例如，我们会将一堆猫、狗数据集的图片按照物种种类划分或者按照物种颜色划分，而不会将“白色的猫”和“黑色的狗”划分为一个集合，将“黑色的猫”和“白色的狗”划分为另一个集合。 得益于上述优点，分布式表示学习逐渐成为主流的表示方法。但其实非分布式表示仍然有很多优秀的学习算法，其思想非常值得借鉴。如上述提到的K近邻算法是非常典型的一种算法。此外还有最常见的聚类算法。聚类算法，即模式的无监督分类，是探索性数据分析中最重要的任务之一。聚类的主要目标包括深入了解数据(检测异常情况、识别显著特征等)、对数据进行分类和压缩数据。聚类在包括人类学、生物学、医学、心理学、统计学、数学、工程学和计算机科学在内的各种学科中有着悠久而丰富的历史。因此，自20世纪50年代初以来，人们已经提出了许多聚类算法，而从解决聚类问题的角度不同，可大致分为Kmeans算法、原型聚类算法、基于密度的聚类算法和层次聚类。这些都将在本节后续继续介绍。 3.2Kmeans算法和K近邻算法 3.2.1Kmeans算法 Kmeans算法是一种常用的高维数据聚类算法，其目标是将样本分成K个簇，使得每个簇内的样本相似度较高，而不同簇之间的样本相似度较低。Kmeans算法的核心思想是基于点与点之间距离的相似度来计算最佳类别归属，它通过迭代的方式调整簇中心，最小化每个簇内样本与其簇中心的距离之和，从而使得簇内样本的方差最小。该算法要求指定集群的数量，它可以很好地扩展到大量的样本，并且已经在许多不同领域中广泛使用。由于被分在同一个簇中的数据具有相似性，而不同簇中的数据是不同的，因此，当聚类结束之后，我们可以分别研究每个簇中的样本都有什么样的性质，从而根据业务需求制定不同的商业或者科技策略。Kmeans算法常用于客户分群、用户画像、精确营销和基于聚类的推荐系统等。 Kmeans算法是一种局部搜索算法。具体来说，假设由K个任意的聚类中心启动，它会将每个数据点分配到其最近的中心，然后重新计算、调整这些中心，接着重新分配这些数据点直到中心稳定下来。Kmeans算法的实际性能和普及程度与理论性能形成了鲜明的对比。在理论上，Kmeans算法终止于某个局部最优，这就可能出现比全局最优要差得多。然而在实践中，它的效果非常好，也因为其简单性和速度而特别受欢迎。Kmeans算法的运行时间的唯一上界是基于在Kmeans算法运行中没有集群出现两次的观察，值得注意的是，当存在n个数据点时，这些点可以仅以Kn的方式分布在K个集群中。 形式上，假设给定由n个点组成的点集X∈Rd。Kmeans算法的目标是通过最小化整体平方和 ∑Ki=1∑x∈Ci‖x-ci‖2(32) 从而找到X的K个聚类分区C1,C2,…,Ck，其中，c1,c2,…,cK是其对应的集群中心。 给定集群中心，Kmeans算法要求每个数据点都应该分配给集群中心与它接近的集群。其中，给定的集群中心c1,c2,…,cK应该被选择为质心，即ci=1|Ci|∑x∈Cix。 具体来说，Kmeans算法的步骤如下： (1) 初始化选择集群中心c1,c2,…,cK； (2) 计算每个样本数据点x∈X到K个聚类中心的距离，并将x分配给最接近的集群中心ci所属的集群Ci； (3) 对每个类别重新设置集群中心ci=1|Ci|∑x∈Cix(即该类所有样本的质心公式)。 如果集群或集群中心发生改变，跳转到(2)，根据终止条件(如迭代次数、最小整体平方和变化等)来结束算法。由于每一步的整体平方和都在降低，因此不会发生两次一模一样的聚类，所以最小整体平方和可以使算法可以达到终止。 Kmeans算法在进行类别划分及调整过程中，始终追求“簇内差异小，簇间差异大”，其中差异是由样本点到其所在簇的质心的距离来衡量的。整体平方和越小，代表着每个簇内样本越相似，聚类的效果就越好。因此，Kmeans算法要求最终解是能够让簇内平方和最小化的质心。Kmeans算法的时间复杂度是O(tKnm)，其中t为迭代次数，K为集群的数量，n为样本个数，m为样本点维度。Kmeans算法的空间复杂度是O(m(n+K))，其中的K,m,n意义同上。 值得注意的是，Kmeans算法是没有误差函数的。误差函数通常用于衡量模型的拟合效果和泛化能力，通过调整参数以最小化误差，从而提高模型的预测性能。而Kmeans算法不需要求解参数，它的本质不在于拟合数据而在于探索数据。虽然Kmeans算法也可以视为一种优化问题，但其目标是通过不断调整簇中心位置，最小化簇内距离平方和，而非最小化预测误差，因此该算法不涉及传统意义上的误差函数。 一般来说，在常用的sklearn代码库中只能被动地选择欧氏距离来度量样本和集群中心二者之间的差异。然而，其他的距离度量方式也可以用来衡量集群内外的差异。总的来说，只要正确地选择质心(簇中心)和合适的距离度量方法，Kmeans算法就可以达到不错的聚类效果。 Kmeans算法是解决聚类问题的一种经典算法，其优点是算法简单、计算速度快。由于该算法的目标是尝试找出使得簇内平方和值最小的若干划分集群，因此当样本数据集群是密集的、球状或团状的，且不同集群之间的区别明显时，聚类效果较好。然而，Kmeans算法也有局限性。对于非凸形状的簇、不同大小的簇，或者数据中存在噪声的情况，Kmeans算法可能表现不佳。而且，它在集群的平均值被定义的情况下才能使用，对有些分类属性的数据（无法进行算术运算）也不适用。此外，Kmeans算法必须事先给出要生成的簇的数目，对于初始簇中心的选择也比较敏感，不同的初始值可能导致不同的聚类结果。Kmeans算法本质上是一种基于欧氏距离度量的数据划分方法，均值和方差大的维度对数据的聚类结果将会产生决定性的影响。因此，一般会在聚类前对数据(具体来说是每个维度的特征)做归一化和单位统一化处理。此外，异常值会对均值计算产生较大影响，导致中心偏移，因此对于噪声和孤立点数据一般也需要提前过滤。 3.2.2Kmeans的改进 Kmeans算法虽然效果不错，但是每一次迭代都需要遍历全部数据，一旦数据量过大、迭代的次数过多，计算复杂度就会过大，容易导致收敛速度非常慢。 由前面内容可知，Kmeans算法在聚类之前首先需要初始化个K个集群中心。显然，K的取值会直接影响聚类的效果，如果K的值不适合该数据集，就可能造成较大的误差。但由于初始化是一个随机过程，因此很有可能所选的簇中心实际上都属于同一个簇，在这种情况下，Kmeans算法很大程度上都不会收敛到全局最小。想要优化Kmeans算法的效率，可以从样本数量和迭代次数两方面改进。此外，为了克服Kmeans算法的一些缺点，可以考虑融合数据预处理(去除异常点)、合理选择K值和高维映射等技术手段，以进一步提升算法的健壮性和性能。 数据预处理： 正如上述所说，在Kmeans算法中，未做归一化处理和统一单位的数据是无法直接参与运算和比较的，因此数据预处理是至关重要的。常见的数据预处理方式有数据归一化和数据标准化。此外，离群点或者噪声数据会对均值产生较大的影响，导致中心偏移，因此还需要对数据进行异常点检测。 合理选择K值： K值的选择对Kmeans算法影响很大，常见的选择K值的方法有手肘法、间隙统计量（gap statistic）方法。 手肘法首先需要根据数据得到类似图36的关系图，其中X轴代表簇数K，Y轴表示K簇下使用Kmeans算法后每个点到其簇中心的距离平方和。然后对关系图进行分析。如图36所示，当K<3时，曲线快速下降； 而当K≥3时，曲线趋于平稳。因此，通过手肘法可以认为拐点3为K的最佳值。然而手肘法也有一定的不足，它不能自动得到最佳值，需要通过人工进行判定。于是，间隙统计量方法应运而生。该方法具有一个衡量公式： 图36K值的大小对距离之和的影响 Gap(K)=E(logD*K)-logDK(33) 其中DK为原始样本的损失函数，E(logDK)指的是logDK的期望。这个数值通常通过蒙特卡洛模拟产生，一般会在样本所在的区域中按照均匀分布随机产生与原始样本数目一样多的随机样本，并对这些随机样本进行Kmeans算法处理，从而得到随机样本的D*K。通常重复20次就可以得到20个logD*K，然后对这些数值求平均值就可以得到E(logD*K)的近似值。最终就可以按照上述衡量公式计算Gap(K)。如果Gap(K)较大，说明原始数据的聚类效果在所选的簇数K下明显优于随机样本。因此，Gap(K)取得最大值所对应的K就是最佳簇数。图37展示了不同的K值计算得到的Gap值，由此可见，当K=3时，Gap(K)取值最大，所以最佳的集群数是K=3。 图37K值的大小对Gap值的影响 采用核函数： 基于欧氏距离的Kmeans算法假设各个集群的数据具有一样的先验概率并呈球形分布，但这种分布在实际生活中并不常见。不过，面对非凸的数据分布形状时，可以引入核函数来优化，这时算法又称为核Kmeans算法，这也是核聚类方法的一种。核聚类方法是一种用于处理复杂数据结构的聚类方法，其核心思想是通过一个非线性映射，将输入空间中的数据点映射到高维的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，因此当经典的聚类算法失效时，通过引入核函数，也能够获得准确的聚类结果。 Kmeans++算法： 该改进算法专注于更好地初始化聚类中心，以避免不良的初始选择导致的局部最优不佳的问题。其主要步骤如下： 首先随机选取一个中心点c1，然后计算每个数据点x到当前选中的聚类中心的距离，取最远的距离记为D(x)，并以概率P(xi)=D(xi)2∑x∈XD(x)2选择新的中心点ci，最后不断重复迭代该过程，直到算法停止。总的来说，Kmeans++算法是选择离已选择的集群中心点最远的点，该方法符合真实情况，因为不同集群中心之间一般是离得越远越好。然而，这个算法难以并行化，但是可以通过改变取样策略来避免该问题。例如，每次遍历不要只选取一个样本作为新中心点，而是可以取样K个，然后重复该取样过程log(n)次，这样就能够得到Klog(n)个样本点组成的集合，然后从这些点中再选取K个。 ISODATA： 正如前面所说，K的值需要预先人为确定。但当遇到高维度、海量的数据集时，人们往往很难准确地估计出K的大小。ISODATA就针对这个问题进行了改进。ISODATA的全称是迭代自组织数据分析法，其思想很直观： 当属于某个类别的样本数过少时，将该类别去除； 而当属于某个类别的样本数过多、分散程度较大时，则将这个类别分为两个子类别。通过这种方式，ISODATA能够动态地调整聚类的数量，更灵活地适应数据的分布情况，从而提高聚类效果。 K+means算法： 除上述几种方法之外，K+means算法也是一个不错的选择，它也能很好解决Kmeans算法的不足。 K+means算法的步骤： (1) 使用原始的Kmeans算法找到K个集群。 (2) 计算每个集群的最小值、最大值和平均集群内相似度。 (3) 期望每个集群内的平均距离相对较小，甚至几乎相似。 (4) 如果某个集群的平均距离大于其他任何集群，则检查其最大值和最小值。如果最大值较高，则检测离群值对象，因为它与其集群的代表的距离最大。 (5) 将这个离群值作为另一个新的代表，重复该算法，将对象分配给K+1个集群。 (6) 重复整个算法，直到没有新的代表形成，并且现有的代表不再改变。 K+means算法的优势是操作简单，易于理解和实现。该算法的时间复杂度是O(tK2n)，其中，n为数据点的数量，K为集群数，t为迭代次数。该改进算法只需要用户指定初始K值，就可以根据数据获得实际的集群数量。它还有一个优点是对异常值不敏感。因为如果出现离群值，它将定义一个新的集群。 现在我们已经了解了K+means算法的基本概念，为了更深入地理解其实际计算过程，将通过一个具体的例子来演示该算法是如何在实践中运作的。表31给出一个示例数据集。 表31示例数据集 数据p1p2p3p4p5p6p7p8p9p10 x1127895678 y4322326767 根据表31，可以在二维空间中绘制对象，如图38所示。 图38示例数据的二维坐标表示 现假设设置K=2为集群数的初始值，并且选择p1和p5作为初始质心。首先通过运行Kmeans算法，我们可以得到含有{p1,p2,p3}的集群1和含有{p4,p5,p6,p7,p8,p9,p10}的集群2，如图39所示。 图39运行Kmeans算法后的集群 接着计算新的质心，如图310所示。 图310新的集群质心 然后基于新的质心计算c1和c2的集群内距离。 c1： Min=0.33,Max=1.20,Avg=0.86 c2： Min=1.30,Max=3.29,Avg=2.39 在这里，可以发现c2的平均值和最大值都相对较大。因此可以检测p6为离群值对象，因其与所在集群的质心的距离最远，即d(c2,p6)=3.29。接着使p6(9,2)为新的聚类质心c3，然后就可以重新分配c1、c2和c3中的对象，如图311所示。 图311初始质心c1、c2、c3 现在重新计算质心，如图312所示。 图312调整质心c1、c2、c3 接着计算各个集群内的最小、最大和平均距离。 c1： Min=0.33,Max=1.20,Avg=0.86 c2： Min=0.71,Max=1.58,Avg=1.14 c3： Min=0.67,Max=1.05,Avg=0.92 可以看到，3个簇的平均簇内距离都是相似的，因此可以认为算法在这里停止。最后得到了3个集群： 集群c1={p1,p2,p3}，集群c2={p7,p8,p9,p10}和集群c3={p4,p5,p6}，如图312所示。 K+means算法的复杂度略高于Kmeans算法。但是，总体而言，K+means算法比Kmeans算法具有更好的聚类性能。为了让读者有更深的了解，下面具体展示两种算法对离群值对象的处理方式。图313显示了当运行取K=2的算法时，Kmeans算法如何对对象进行分组。而图314则显示了当运行使用K=2的算法时，K+means算法如何对对象进行分组。显然，通过两张图的对比可以发现，改进后的算法在处理离群点方面展现出更为优越的性能。 图313通过Kmeans算法进行聚类 图314通过K+means算法进行聚类 综上所述，对Kmeans算法进行改进后而提出的K+means算法不仅保留了Kmeans算法的所有优点，还成功克服了Kmeans算法的缺点。 3.2.3K近邻算法 Kmeans算法常常与K近邻(KNearest Neighbor，KNN)算法进行比较，因此本节将对KNN算法进行介绍。 KNN算法是最简单、最常见的机器学习算法之一，它是一种监督学习方法，主要用于分类和回归。给定一个新样本，KNN算法的工作原理是根据某种基于距离的度量方法来找出在训练集中与其最接近的K个相邻样本，然后基于这K个相邻样本的特征来对该新样本进行预测。在分类任务上，这通常可以理解为“投票法”，即根据这最相邻的K个样本出现次数最多的类别作为该样本的预测类别； 而在回归任务上则可以视为“平均法”，即基于这K个相邻的样本计算它们属性的平均值来作为该样本的预测值。此外，也可以按照这K个样本距离的远近来进行加权投票或者加权平均进行分类或者回归，其中距离越近的样本拥有越大的权重，表示对预测该样本越有话语权。 图315KNN分类实例 接下来通过一个实例来演示KNN算法在分类问题中的应用。如图315所示，图中的正方形和三角形是已经分好类别的数据，分别代表不同的标签，而中间的圆形样本是待分类的数据。在样本空间中，不同类别的样本是以离散的形式分布在整个空间中，为了找到该待测样本的K个相邻样本，同时为了可以得到更好的可视化效果，我们以它为中心画圆作为边界度量方式，如图中实线圆和虚线圆。 以待测样本为中心，如果选择K=3，可以看到在实线圆所包围中离该样本点最近的K个点中有2个三角形和1个正方形。以这3个点进行投票，其中三角形的比例为2/3，因此KNN算法会认为该待分类点属于三角形类别。如果K=5，则可以看到在虚线圆所包围中离待测点最近K个点中有2个三角形和3个正方形。同样根据这5个相邻点进行投票，可以发现正方形的比例为3/5，在这种情况下，KNN算法则会将这个待分类点划分到正方形类别中。 从上述例子可以看到，KNN算法本质上是一种基于数据统计的方法，事实上，许多机器学习算法也都具备这种基于数据统计的特性。此外，KNN算法还是一种基于距离的学习方法，是懒惰学习(lazy learning)的典型代表。与其他算法不同，KNN算法无须明显的前期训练过程，只要把数据集导入就可以直接开始进行分类计算。通常情况下，K的选取取决于数据集的特性，一般不会选择大于20的整数。 进一步讨论，在给定测试样本x的情况下，若其相邻样本为z，近邻分类器出错的概率就是x与z所属不同类别的概率，即 P(err)=1-∑c∈YP(c|x)P(c|z)(34) 假设样本独立同分布，且对任意x和任意小正数δ，在x附近δ距离范围内总能找到一个训练样本； 换言之，对任意测试样本，总能在任意近的范围内找到上述公式的训练样本z。令c*=argmaxc∈YP(c|x)表示贝叶斯最优分类器的结果，可以得到 P(err)=1-∑c∈YP(c|x)P(c|z)(35) P(err)≈1-∑c∈YP2(c|x)(36) P(err)≤1-P2(c*|x)(37) P(err)=(1+P(c*|x))(1-P(c*|x))(38) P(err)≤2×(1-P(c*|x))(39) 根据上述公式的推导，可以得出结论： KNN分类器虽然简单，但是它的泛化错误率不会超过贝叶斯最优分类器的错误率的2倍。 具体来说，用于分类的KNN算法的计算步骤如下。 (1) 计算待分类点与所有已知类别的样本点之间的距离。 (2) 按照距离递增次序排序。 (3) 选取与待分类点距离最小的前K个点。 (4) 确定前K个点所在类别的出现次数。 (5) 返回前K个点出现次数最高的类别作为待分类点的预测分类。 图316K=3的KNN算法回归实例 如果将KNN算法用在回归任务中，那么要预测的点的值是通过求与它距离最近的K个点的值的平均值得到的，这里的“距离最近”可以是欧氏距离，也可以是其他距离，具体的度量标准一般依数据而定。如图316所示的例子，x轴表示特征，y是该特征所对应的值，圆形点是已知点，K设为3。要预测第一个点的位置，则需计算离它最近的三个点(虚线框中的三个圆形点)的平均值，得出第一个三角形点，以此类推，就可以得到图中三角形点构成的线。可以看出，这样的预测明显比直线准。 通过上述例子，可以清晰地看到，KNN算法在分类和回归任务中都涉及如下关键点。 (1) 算法超参数K的选取。 (2) 距离度量方法，特征空间中样本点的距离是样本点间相似程度的反映。 (3) 分类决策规则，少数服从多数。 其中，K值的选择和距离度量的设定相对而言更为重要。 K值是KNN算法中唯一的超参数，该值的选择对算法的最终预测结果会产生直观的影响。如果选择较小的K值，就相当于用较小邻域中的训练实例进行预测，“学习”的近似误差会减小，因为此时只有与输入实例较近的训练实例才会对预测结果起作用。然而选择较小的K值的缺点是“学习”的估计误差会增大，因为预测结果会对邻近的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，K值的减小就意味着整体模型非常复杂，容易发生过拟合。如果选择较大的K值，相当于使用较大邻域中的训练实例进行预测，虽然这能减少“学习”的估计误差，但同时也会增大“学习”的近似误差。因为此时与输入实例较远的训练实例也会对预测产生作用，从而增加预测错误的可能性。也就是说，K值的增大表示整体模型变得简单，但也容易导致欠拟合。例如，当假定极端条件K=N，那么无论输入实例是什么，都将简单地预测出它属于训练实例中最多的类。这时，模型过于简单，完全忽略训练中的大量有用信息，很显然这是不可取的。 在实际应用中，通常采用交叉验证法来选择最优的K值。从上述分析也可知，一般K值取得相对较小。因此，我们会在较小的范围内尝试不同的K值，并选择在验证集上准确率最高的那个值作为最终的算法超参数K。 距离度量的选择也是影响算法效果的一个关键因素。在样本空间中，两个点之间的距离度量代表两个样本点之间的相似程度，距离越小，则表示相似程度越高； 相反，距离越大，相似程度越低。接下来，我们将详细描述KNN算法中常用的距离度量，如欧氏距离、曼哈顿距离、切比雪夫距离和闵可夫斯基距离等。为了更好地解释，假设有数据点x和y，它们都包含了n维特征。其数学描述如下： x=(x1,x2,…,xn),y=(y1,y2,…,yn)(310) 欧氏距离： 该距离度量方法是最常见的两点之间或多点之间的距离表示法，又称为欧几里得度量。它定义于欧几里得空间中，其距离公式如下： d(x,y)=(x1-y1)2+(x2-y2)2+…+(xn-yn)2=∑ni=1(xi-yi)2(311) 基于式（311），可以计算欧几里得空间中任意点之间的距离。例如，三维空间中的两个点a(x1,y1,z1)和b(x2,y2,z2)之间的欧氏距离为 d(a,b)=(x1-x2)2+(y1-y2)2+(z1-z2)2(312) 其也可以表示成向量运算的形式： d(x,y)=(x-y)(x-y)T(313) 曼哈顿距离： 曼哈顿距离的严格定义是L1距离或城市区块距离，即在欧几里得空间的固定直角坐标系上，两点形成的线段对坐标轴产生的投影的距离总和，其距离公式为： d(x,y)=∑ni=1|xi-yi|，i=1,2,…,n。例如在平面上，坐标为(x1,y1)的点P1和坐标为(x2,y2)的点P2之间的曼哈顿距离为|x1-x2|+|y1-y2|。在三维空间中，两个点a(x1,y1,z1)和b(x2,y2,z2)之间的曼哈顿距离则为 d(a,b)=|x1-x2|+|y1-y2|+|z1-z2|(314) 值得注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。 切比雪夫距离： 该距离描述了在任何坐标轴方向上两个点之间最远距离，其定义如下： d(x,y)=max(|xi-yi|),i=1,2,…,n(315) 这也等同于Lp度量的极值，即limp→∞∑ni=1|xi-yi|p1/p，因此切比雪夫距离也被称为L∞度量。以数学的观点来看，切比雪夫距离是由一致范数(或称为上确界范数)所衍生的度量，也是超凸度量的一种。根据上述定义，在平面几何中，若两点p及q的直角坐标系坐标为(x1,y1)和(x2,y2)，那么就可以得出其切比雪夫距离为 d(p,q)=max(|x2-x1|,|y2-y1|)(316) 闵可夫斯基距离： 闵可夫斯基距离(Minkowski distance)不是一种距离，而是Lp度量的泛化。其数学定义如下: dp(x,y)=∑ni=1|xi-yi|p1/p(317) 当p=1时，表示为曼哈顿距离； p=2时，表示欧氏距离； p=∞,则为切比雪夫距离。 标准化欧氏距离： 标准化欧氏距离是对简单欧氏距离的一种改进方案，其考虑了数据的尺度，旨在更好地处理数据各维分量的分布不同的问题。标准化欧氏距离的思路是将各个分量都“标准化”到均值、方差相等，以适应数据各维分布的差异性，消除量纲的影响。具体来说，假设样本集X的数学期望或均值为m，标准差为s，样本集的标准化过程为 X*=X-ms(318) 这里的X*就是X的“标准化变量”，且其数学期望为0，方差为1。如果将方差的倒数看成一个权重，那么上述公式可以看成一种加权欧氏距离。经过简单地推导就可以得到两个n维向量x与y之间的标准化欧氏距离，即 d(x,y)=∑ni=1xi-yisi2(319) 其中，si是第i个维度上的标准差。标准化欧氏距离在处理各维度差异较大的数据时，具有明显的优势。 马氏距离： 假设有M个样本向量X1,X2,…,XM，其协方差矩阵记为S，均值记为向量μ，则样本向量X到u之间的马氏距离(Mahalanobis distance)定义为 D(X)=(X-μ)TS-1(X-μ)(320) 其中，协方差矩阵中每个元素是各个矢量元素之间的协方差Cov(X,Y)，一般表示为Cov(X,Y)=E{［X-E(X)］［Y-E(Y)］}，这里的E为数学期望。因此，向量Xi与Xj之间的马氏距离则定义为 D(Xi,Xj)=(Xi-Xj)TS-1(Xi-Xj)(321) 值得注意的是，若协方差矩阵是单位矩阵，则表示各个样本向量之间独立同分布，此时公式会演变成欧氏距离。若协方差矩阵为对角矩阵，则公式会变为标准化欧氏距离。 巴氏距离： 在统计中，巴氏距离(Bhattacharyya distance)用于衡量两个离散或连续概率分布的相似度。该距离与巴氏系数密切相关，后者常用于衡量两个统计样本或种群之间的重叠程度。同时，巴氏系数可用于确定两个样本相对接近的程度，因此其被广泛应用于测量类别间的可分离性。对于在同一域X上的离散概率分布p和q，其巴氏距离被定义为 D(p,q)=-ln(BC(p,q))(322) 其中BC(p,q)=∑x∈Xp(x)q(x)是巴氏系数。而对于连续概率分布，巴氏系数被定义为： BC(p,q)=∫p(x)q(x)dx。计算巴氏系数涉及将两个样本的基本形式的重叠时间间隔值进行积分，这两个样本会被分隔成一个选定的分区数，并且在每个分区中，每个样本的成员数量使用∑ni=1∑ai·∑bi进行计算。 汉明距离： 该距离用于衡量两个向量之间不同元素的个数，即dH(x,y)=∑ni=1δ(xi,yi)。其中，δ(xi,yi)是一个指示函数，当xi≠yi时为1，否则为0。 两个等长字符串s1与s2之间的汉明距离(Hamming distance)被定义为将其中一个字符串转换为另一个所需的最小替换次数。例如，字符串"1111"与"1001"之间的汉明距离为2。其主要应用在信息编码领域中，为了增强容错性，通常希望编码间的最小汉明距离尽可能大。 夹角余弦： 夹角余弦(cosine)是一种用于衡量几何中两个向量方向差异的方法。在机器学习中，常借用这一概念来衡量样本向量之间的差异。在二维空间中，向量A(x1,y1)与向量B(x2,y2)的夹角余弦表示为 cos(θ)=x1x2+y1y2x12+y12x22+y22(323) 而在高维空间中，两个n维样本点a(x1,x2,…,xn)和b(y1,y2,…,yn)的夹角余弦则定义为 cos(θ)=a·b‖a‖‖b‖(324) 其中，a·b是向量点积运算，‖a‖和‖b‖分别是向量a和b的模。 在介绍了上述多种距离度量方式后，我们可以发现距离度量就是为了定义哪些样本可以被认定为邻居，而K的选取就是决定一次需要选取多少邻居。因此，距离度量至关重要，在实际应用中，可以多尝试不同的方法，以选取最适合当下任务的距离度量方式。 3.2.4KNN的改进 上述小节介绍了KNN算法，然而该算法也存在一些局限性。为了解决这些问题，涌现出了多种改进算法。其中，有些算法是通过权重来改进KNN算法，即通过训练点到样本数据点的距离来分配权重，以解决KNN对异常值敏感的问题。然而，这些算法仍然面临计算复杂性和内存需求仍然的问题。另外一些算法为了克服内存限制，选择减少数据集的大小，即消除训练样本中没有额外信息的重复模式。为了进一步提升性能，一些算法还从训练数据集中剔除对结果没有影响的数据点。除了时间和内存的限制外，KNN算法还有一个需要注意的因素是K值的选择，有些算法会使用基于模型的算法，使得所提出的模型能够自动选择K值。在提高经典KNN速度方面，一些算法利用排序、假邻居信息和聚类的概念对其进行改进。此外，KNN算法也可以使用球树(ball tree)、KD树(KD tree)、最近特征线(NFL)、可调度量、主轴搜索树和正交搜索树来实现。树形结构化使得训练数据被划分为节点，而NFL和可调度量等技术则根据平面来划分训练数据集,这些技术也都能提高基本KNN算法的速度。 常见的改进算法有很多。例如，加权KNN(WKNN,Weighted KNearest Neighbor)算法，它根据K值计算样本数据点之间的距离，并为每个计算值赋权值，然后确定最近邻，最终为样本数据点分配类别。压缩近邻(Condensed Nearest Neighbor，CNN)算法则采用逐个存储模式，通过消除重复模式的方式减小数据集。它删除了不添加更多信息的数据点，使得与其他训练数据集的相似点更能呈现。简化近邻(Reduced Nearest Neighbor，RNN)算法是对CNN算法的进一步改进，它多包括一个步骤，即消除不影响训练数据集结果的模式。基于模型的KNN算法是另一种算法，它选择相似度度量，并从给定的训练集中创建一个“相似度矩阵”。接着，在同一类别中，找到覆盖大量邻域的最大局部邻域，将数据元组放置在最大的全局邻域中。这些步骤将重复进行，直到所有数据元组都被分组为止。注意，一旦使用模型形成数据，就会执行KNN算法来指定未知样本的类别。 一些研究通过引入等级的概念来改进KNN算法，具体来说，该算法是将属于不同类别的所有观察结果汇集起来，并按升序为每个类别的数据分配排名。然后对观测结果进行计数，接着根据等级将其分配给未知样本。该算法在多变量数据中非常有用。在修正KNN算法中，它会对训练数据集中所有数据样本的WKNN有效性进行修正，并计算相应的权重赋值，然后将效度与权重结合起来，对样本数据点进行类别分类。另一些研究则定义了样本数据点分类的新概念。该算法引入了伪邻居，顾名思义，它并非实际的最近邻，而是根据每个类中未分类模式的KNN距离的加权和值选择一个新的最近邻。然后对未知样本进行欧氏距离计算，找到权重较大的伪邻域，借此对未知样本进行分类。在新提出的技术中，还有采用聚类的方法来计算最近邻。这些步骤包括首先从训练集中移除位于边界附近的样本，然后通过K值聚类对每个训练集进行聚类，所有聚类中心形成新的训练集。最后，根据每个聚类所拥有的训练样本的数量，为每个聚类分配权重。 此外，还有一类基于球树、KD树、主轴树(PAT)、正交结构树(OST)、最近特征线、中心线(CL)等数据结构的近邻技术，这种技术使得KNN算法在速度方面有了很大改进。其中，球树是一种二叉树，其使用自顶向下的方法进行构造。树的叶子包含相关信息，而内部节点用于指导有效搜索。KD树将训练数据分为右节点和左节点两部分，根据查询记录搜索树的左侧或右侧。到达终端节点后，检查其中的记录，找到距离查询记录最近的数据节点。有研究者提出最近特征线邻居（NFL）算法，其将训练数据划分为平面并引入特征线来寻找最近邻。为此，他们为每个类计算了查询点和每对特征线之间的FL距离，计算后可以得到一组距离。这些距离按升序排列，产生了NFL距离，其划分为等级1。对NFL的一个改进是局部最近邻，该方法仅针对点进行评估。有研究还引入了一种新的评估NFL距离的度量方式，称为可调度量，进而提出可调最近邻算法（TNN）。它遵循与NFL相同的程序，但在第一阶段中，它使用可调度量来计算距离，再实现NFL的步骤。而基于中心的最近邻是对NFL和可调性最近邻的改进。它采用中心基线来连接样本点与已知的标记点。具体来说，该算法首先计算CL，即通过训练样本和类中心的直线，然后计算从查询点到CL的距离，最后进行最近邻的计算。还有一种近邻算法称作PAT。它允许将训练数据以有效的速度划分，以进行最近邻评估。PAT包括两个阶段，即PAT结构和PAT搜索。PAT使用主成分分析，并将数据集划分为包含相同数量的点的区域。一旦树形成，KNN就被用于搜索PAT中的最近邻，搜索时可以使用二进制搜索来确定给定点的区域。OST是对PAT改进的另一种近邻算法。它使用正交向量，采用了“长度(范数)”的概念，然后在第一阶段进行评估。接着通过创建一个根节点，并将所有数据点分配给该节点来形成正交搜索树，然后使用pop操作形成左右节点。 为了更为直观地理解和比较，表32展示了多种近邻算法，主要介绍其关键思想、优缺点和所适合的数据集。 表32多种近邻算法的比较 序号方法名称关键思想优点缺点目标数据 1K近邻算法使用近邻规则1. 训练速度快 2. 简单易学 3. 对有噪声的训练数据具有健壮性 4. 训练数据数量越大越有效1. 受K值的影响 2. 计算复杂性 3. 内存限制 4. 作为一个监督学习的惰性算法，运行缓慢 5. 很容易被不相关的属性所愚弄大数据样本 2加权K近邻算法根据计算出的距离为邻居分配权重1. 克服了KNN隐式分配K个邻居的局限性 2. 使用所有的训练样本，而不仅仅是K个 3. 使该算法成为全局算法1. 在计算权重时，计算复杂度增加 2. 算法运行缓慢大样本数据 3压缩近邻算法消除显示相似性的数据集，且不添加额外的信息1. 减少训练数据的大小 2. 提高查询时间和内存需求 3. 降低识别率1. CNN是依赖于顺序的； 它不太可能在边界上找到一些点 2. 计算复杂性度大主要关注内存需求的数据集 4简化近邻算法删除不影响训练数据集结果的模式1. 减少训练数据的大小，消除模板 2. 提高查询时间和内存需求 3. 降低识别率1. 计算复杂度大 2. 成本高 3. 耗时长大型数据集 5基于模型的K近邻算法利用数据构建模型，并利用模型对新数据进行分类1. 更多的分类精度 2. K的值可以被自动选择 3. 高效化，减少了数据点的数量不考虑该区域以外的边际数针对大型存储库的动态Web挖掘 6排序K近邻算法为每个类别的训练数据分配等级1. 当特性之间有太多变化时表现更好 2. 这是基于自己的排名 3. 与KNN算法相比，计算复杂度更低多变量KRNN依赖于数据的分布高斯性质的类分布 7修正K近邻算法利用数据点的权重和有效性对近邻进行分类1. 部分克服了WKNN的低精度 2. 稳定、稳健计算复杂度大面向出口的方法 8伪/广义近邻 (Pseudo/Generalized Nearest Neighbor， GNN)算法利用n-1个邻居的信息，而不是只有最近的邻居使用n-1个类来考虑整个训练数据集1. 并不适用于小数据 2. 计算复杂度大大数据集 9聚类K近邻 (Clustered K Nearest Neighbor,CKNN) 算法形成集群来选择最近的邻居1. 克服了训练样本不均匀分布的缺陷 2. 稳定、可靠1. 在运行算法之前，阈值参数的选择比较困难 2. 对聚类的K值有偏差文本分类 10球树K近邻(Ball Tree K Nearest Neighbor,KNS1) 算法使用球树结构来提高KNN算法的速度1. 好调整所表示数据的结构 2. 好处理高维实体 3. 易于实现1. 昂贵的插入算法 2. 随着距离的增加，KNS1算法会降解几何学习任务，如机器人、视觉、语音、图形 11KD树近邻(KD Tree Nearest Neighbor，KDNN) 算法将训练数据精确地分成半平面1. 产生完全平衡的树 2. 快速、简单1. 更多的计算 2. 需要密集的搜索 3. 盲目地将切片点分割成一半，容易忽略数据内部结构多维点的组织结构 12最近特征线邻居 (Nearest Feature Line Neighbor， NFL)算法利用每个类的多个模板1. 提高分类精度 2. 对小尺寸非常高效 3. 利用近邻中忽略的信息，即每个类的模板1. 当NFL中的原型远离查询点时失败 2. 计算复杂度大 3. 用直线来描述特征点是一项艰巨的任务人脸识别问题 13局部近邻(Local Nearest Neighbor， LNN)算法重点关注查询点的近邻原型NFL的覆盖限制计算次数多人脸识别问题 14可调近邻(Tunable Nearest Neighbor， TNN)算法使用了可调度量对小的数据集有效大量的计算判别问题 15基于中心的近邻 (Centerbased Nearest Neighbor) 算法计算中心线高效的小数据集大量的计算模式识别 16主轴树的近邻 (Principal Axis Tree Nearest Neighbor， PAT)算法使用PAT算法1. 性能良好 2. 搜索快速计算时间长模式识别 17正交搜索树中的近邻(Orthogonal Search Tree Nearest Neighbor，OSTNN)算法使用正交树算法1. 减少了计算时间 2. 对大型数据集有效查询时间多模式识别 由于具有一定相似性，所以KNN算法和Kmeans算法经常被用来比较。总的来说，这两种算法最大的区别在于，KNN算法是为了解决分类问题的有监督学习算法，而Kmeans算法是为了解决聚类问题的无监督学习算法。其次是两种算法的K所指代的内容也有差异，KNN算法中的K是为选取待分类样本点的某种度量距离最近的K个点，而Kmeans算法的K是在聚类前就提前指定的集群数K。而这两种算法的共同点是它们都采用相同的可供选择的距离度量方法。 3.3原型聚类算法 原型聚类即“基于原型的聚类”(prototypebased clustering)，其假设在聚类过程中能通过参考一个原型来完成算法。原型聚类算法在实际聚类情况中是非常常见的。通常情况下，算法首先对原型进行初始化，然后通过迭代对原型更新求解。采用不同的原型表示和求解方式，将产生不同的算法。例如，常见的Kmeans算法是基于簇中心来实现聚类的，学习向量量化（Learning Vector Quantization，LVQ）算法则采用样本的真实类标签来辅助聚类，而高斯混合聚类算法则是基于簇分布来实现聚类。 3.3.1学习向量量化算法 LVQ算法是一种基于原型的聚类算法。与Kmeans算法不同，LVQ借助样本的真实类标签来描述原型。具体来说，LVQ算法会首先根据样本的类标签，从各类中分别随机选取一个样本作为该类簇的原型，从而组成一个原型向量组。接着，从样本集中随机挑选一个样本，计算其与原型向量组中每个向量的距离，并选取距离最小的原型向量所在的类簇作为其划分结果。最后将结果与真实类标签进行比较。若划分结果正确，则对应原型向量向这个样本靠近一些； 若划分结果不正确，则对应原型向量向这个样本远离一些。 具体来说，LVQ算法的流程如下所示。 输入： 样本集D={(x1,y1),(x2,y2),…,(xm,ym)}； 原型向量个数q，各原型向量预设的类别标记{t1,t2,…,tq}； 学习率η∈(0,1)。 输出： 聚类原型向量{p1,p2,…,pi}。 (1) 初始化一组原型向量{p1,p2,…,pq}。 (2) 从样本集D中随机选取样本(xi,yi)。 (3) 计算样本xj和pi(1≤i≤q)的距离： dji=‖xj-pi‖2。 (4) 找出与xj距离最近的原型向量pi*,i*=argmini∈{1,2,…,q}dji。 (5) 如果yi=ti*，那么p′=pi*+η·(xj-pi*)即类中心向x靠近，否则p′=pi*-η·(xj-pi*)即类中心向x远离。 (6) 将原型向量pi*更新为p′，继续循环直到满足停止条件。 为了更直观地理解，我们将通过一个具体的例子来进一步说明LVQ算法的过程。首先，构造一个如下的数据集，其中xi为特征数据，对应的yi为该样本的真实标签。 x1： (3,4),y1： (1) x2： (3,3),y1： (1) x3： (1,2),y1： (0) x4： (1,1),y1： (0) x5： (2,1),y1： (0) 假设任务是要将上述的点集划分为两个集群，我们随机挑选x1和x3作为初始原型向量p1和p2，学习率η=0.1。在第一轮迭代时随机选取出样本x2，然后就分别计算x2和p1、p2之间的距离（这里采用欧氏距离），得到1和5。可以看出x2和p1的距离会小于x2和p2的距离，所以，x2和p1会具有相同的标签值。然后通过以下公式 p′1=p1+η·(x1-p1)=(3,4)+0.1×((3,3)-(3,4))=(3,3.9)(325) 将p1更新为p′1，之后不断重复上述过程，直到满足终止条件。这就是LVQ算法的具体计算过程。 LVQ算法简单、易于理解，但也要注意一些细节问题。例如，基于上述例子，若挑选x1和x2或x3和x4作为初始簇，那么最后得到的两个原型向量的标签值其实都是相同的，如都为0。这样就会导致无论输入的样本与哪个原型向量更接近，其标签值最终都为0，这显然不是我们希望得到的结果。因此，在挑选初始原型向量时需要将当前样本集的所有标签值都囊括在初始原型向量组中。 3.3.2高斯混合聚类算法 高斯混合聚类算法与Kmeans算法、LVQ算法不同，它是采用概率模型来刻画原型。 在深入介绍高斯混合聚类之前，我们先来回顾一下多元高斯分布的定义。在n维的样本空间X中的随机向量x，若x是服从多元高斯分布的，那么x的概率密度函数为 p(x)=1(2π)n2|Σ|12e-(x-μ)TΣ-1(x-μ)2(326) 其中，μ是n维均值向量，Σ是n×n的协方差矩阵。由式(326)可以看出，高斯分布只取决于均值向量μ和协方差矩阵Σ这两个参数。这两个参数对应的高斯分布概率密度函数记作p(x|μ,Σ)，因此，高斯混合分布可以表示为 pM(x)=∑ki=1αi·p(x|μi,Σi)(327) 混合的高斯分布由k个高斯分布混合组成，其中μi和 Σi对应第i个高斯分布的参数，而αi是对应高斯分布的“混合系数”，αi符合如下条件： ∑ki=1αi=1(328) 根据给定的各个高斯分布的参数以及其对应的概率αi，通过选定的混合概率密度函数进行采样，便可生成所需样本。 假设从给定的多元高斯分布中采样出的训练集为D={x1,x2,x3,…,xm}，令随机变量zj∈{1,2,…,k}，其表示xj的高斯混合成分。可以看出，zj的先验概率p(zj=i)恰好对应αi，所以根据贝叶斯定理可以得到zj的后验概率为 pM(zj=i|xj)=P(zj=i)·pM(xj|zj=i)pM(xj)(329) pM(zj=i|xj)=αi·p(xj|μi,Σi)∑kl=1αl·p(xj|μl,Σl)(330) 其中，pM(zj=i|xj)是给定样本xj由第i个高斯混合分布生成的后验概率，记为γji。 在多元高斯混合分布已知的情况下，高斯混合聚类算法的目标是将样本集D划分为k个集群C={C1,C2,…,Ck}，其中，样本集中的每个样本xj的集群标记为λj，则 λj=argmaxi∈{1,2,…,k}γji(331) 因此，从原型聚类的角度来看，高斯混合模型采用概率模型对原型进行刻画，而集群划分则由原型对应的后验概率确定。 高斯混合聚类算法具有显著的优点，即在投影后，样本点不是得到一个确定的分类标记，而是得到每个类的概率。与确定的类别相比，这种概率算法更加贴近实际生活，提供了高价值的信息。此外，高斯混合模型不仅可以用在聚类上，还可以用于概率密度估计，具有广泛的应用，同时提供了从另一个角度来解释确定性模型。然而，高斯混合模型也存在一些缺点。首先，当每个混合模型样本点不足时，协方差的估算就会变得困难，这很容易导致算法发散，并且找到具有无穷大似然函数值的解，除非能够对协方差进行正则化。其次，高斯混合模型每一步迭代的计算量较大，超过了Kmeans算法。此外，由于高斯混合模型的求解算法是基于EM算法，因此有可能陷入局部极值的风险，所以初始化值的选取对模型的最终求解影响较大。 3.4基于密度的聚类算法 聚类算法对于空间数据库中的类别识别十分重要。然而，应用于大型空间数据库的聚类算法需要满足以下要求： 减少输入参数的领域知识要求，能够发现任意形状的集群(簇)，并能在大型数据库上保持高效性。众所周知的聚类算法并未提供这些需求的组合解决方案，不过，基于密度的聚类算法能满足上述需求之一，它通过依赖密度的概念就能够实现对任意形状簇的发现。 基于密度的聚类算法的核心思想是： 对于任意数据点，只有当邻近区域的密度(即对象或数据点的数目)超过某个阈值时，才将其加入与之相近的聚类中。换句话说，对于给定类中的每个数据点，在一个给定范围的区域中必须至少包含一定数目的点，这样才能被认为该点属于某一个簇。在基于密度的聚类算法中，集群的形成必须满足： 在每个集群内都有一个典型的点密度，其远高于集群外的密度。此外，噪声区域内的密度低于任何一个集群内的密度。基于密度的聚类算法中，代表算法有DBSCAN算法、OPTICS算法和DENCLUE算法。 3.4.1DBSCAN算法 DBSCAN(DensityBased Spatial Clustering of Application with Noise，基于密度的噪声应用空间聚类)算法常用于二维或三维欧几里得空间，也适用于一些高维特征空间。其关键思想是，对于簇内的每个点，给定半径Eps的邻域必须至少包含一个最小数量的点，即邻域的密度必须超过某个阈值MinPts。一个邻域的形状是由衡量两个点p和q的距离函数来决定的，一般用dist(p,q)表示。例如，当在二维空间中使用曼哈顿距离时，邻域的形状是矩形的。事实上，任何距离函数都适用于DBSCAN算法，因此可以根据给定的应用程序来选择合适的函数。在这里，一个点的密度是以一个关于Eps和MinPts的值来表示的。为了确保每个簇中的边缘点，在虽然不满足最小密度要求但是在核心点的邻域范围内的情况下仍被考虑，DBSCAN算法引入了密度直达(directly densityreachable)、密度可达(densityreachable)和密度相连(densityconnected)的概念。在这种情况下，所有在给定参数Eps和MinPts密度相连的数据点组成一个簇，而未包含在任何簇内的点才被视为噪声。其实在具体实现时，无须过于关注密度相连的概念，只需要迭代地将核心点邻域中的所有点(即密度直达的点)包含进来，这样最终形成的簇其内的所有点必定是密度相连的。相关概念的具体定义如下。 定义31(Eps邻域)给定一个对象p，p的Eps邻域NEps(p)定义为以p为核心、以Eps为半径的d维超球体区域，即 NEps(p)={q∈D|dist(p,q)≤Eps}(332) 其中，D为d维实空间上的数据集，dist(p,q)表示D中的两个对象p和q之间的距离。 定义32(核心点与边界点)对于对象p∈D，给定一个整数MinPts，如果p的Eps邻域内的对象数满足|NEps(p)|≥MinPts，则称p为(Eps,MinPts)条件下的核心点； 不是核心点但落在某个核心点的Eps邻域内的对象称为边界点。 定义33(直接密度可达)给定(Eps,MinPts)，如果对象p和q同时满足如下条件： p∈NEps(p)和|NEps(q)|≥MinPts(即q是核心点)，则称对象p是从对象q出发直接密度可达的。 定义34(密度可达)给定数据集D，当存在一个对象链p1,p2,…,pn，其中p1=q,pn=p，对于pi∈D，如果在(Eps,MinPts)条件下pi+1从pi直接密度可达，则称对象p从对象q在条件(Eps,MinPts)下密度可达。密度可达是非对称的，即p从q密度可达不能推出q也从p密度可达。 定义35(密度相连)如果数据集D中存在一个对象o，使得对象p和q是从o在(Eps,MinPts)条件下密度可达的，那么称对象p和q在(Eps,MinPts)条件下密度相连。密度相连是对称的。 图317DBSCAN算法基本概念示意 如图317所示，在MinPts=3的情况下，虚线表示Eps邻域，x1是核心对象，x2由x1密度直达，x3由x1密度可达，x3和x4密度相连。 DBSCAN算法的步骤如下。 (1) 任意选取一个没有加簇标签的点p。 (2) 得到所有p关于Eps和MinPts密度可达的点。 (3) 如果p是一个核心点，形成一个新的簇，给簇内所有对象点加簇标签。 (4) 如果p是一个边界点，没有从p密度可达的点，DBSCAN将访问数据库中的下一个点。 (5) 继续上述这一过程，直到数据库中所有的点都被处理。 DBSCAN算法具有诸多优点。首先，它可以克服基于距离的算法只能发现“类圆形”聚类的限制，能够发现任意形状的聚类。其次，DBSCAN算法能有效地处理数据集中的噪声数据，并对数据输入顺序不敏感。然而，它也存在一些缺点。首先，DBSCAN算法对输入参数较为敏感，确定参数值Eps和MinPts困难，不当的参数选择可能导致聚类质量下降。其次，由于在DBSCAN算法中变量Eps和MinPts是全局唯一的，因此当空间聚类的密度不均匀、聚类间距离相差很大时，聚类质量可能较差。而且，计算密度单元的计算复杂度较大，需要建立空间索引来降低计算量，并且其对于数据维数的伸缩性较差。此外，这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此在处理大规模数据时会导致频繁的I/O操作。 3.4.2OPTICS算法 OPTICS(Ordering Points To Identify the Clustering Structure，通过排序点来识别聚类结构)算法也是一种基于密度的聚类算法，是DBSCAN算法的改进版本。正如上文所述，DBSCAN算法对于输入参数过于敏感，即在DBSCAN算法中需要输入两个参数： Eps和MinPts，而选择不同的参数将会导致最终聚类的结果千差万别。OPTICS算法的提出就是旨在降低DBSCAN算法对输入参数的敏感度，并改进其性能。准确来说，OPTICS算法主要是针对输入参数Eps过敏感做的改进。OPTICS算法和DBSCNA算法的输入参数一样，也是Eps和MinPts，但该算法对Eps输入不敏感(一般将Eps固定为无穷大)，从而降低了参数选择的影响。同时，该算法中并不显式地生成数据聚类，只是对数据集合中的对象进行排序，然后得到一个有序的对象列表。通过该有序列表，可以得到一个决策图。通过决策图，OPTICS算法可以检测不同Eps参数下的数据集中的聚类，即先通过固定的MinPts和无穷大的Eps得到有序列表，然后创建决策图，通过决策图便可知当Eps取特定值(如Eps=3)时数据的聚类情况。这一过程使得OPTICS算法更具灵活性。 在DBSCAN算法定义的基础上，OPTICS算法新引入了两个概念。 第一个概念是核心距离(coredistance)： 样本x∈X，对于给定的Eps和MinPts，使得x成为核心点的最小邻域半径称为x的核心距离。其数学表达如下： cd(x)=未定义，|NEps(x)|