聚类算法哪个场景有用到

❶ 聚类分析（cluster analysis)

我们这里来看看聚类分析。

比较流行的有聚类方法有k均值聚类,属于分割式聚类的方法。

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。目的是最小化E=sum(x-\miu_i), 其中\miu_i是每个簇的均值。

直接求上式的最小值并不容易，这是一个NP难的问题，因此采用启发式的迭代方法K-Means。

K-Means很简单，用下面一组图就可以形象的描述。上图a表达了初始的数据集，假设k=3。在图b中，我们随机选择了三个k类所对应的类别质心，即图中的红绿和草绿色质心，然后分别求样本中所有点到这三个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红绿和草绿色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红绿和草绿色点分别求袭埋其新的质心，重复了这个过程，将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的三个类别如图。

首先我们看看K-Means算法的一些要点。

1 对于K-Means算法，首先要注意的是k值的选择，一般来说，我们会根据对数据的先验经验选择一个合适的k值，如果没有什么先验知识，则可以通过交叉验证选择一个合适的k值。

2 在确定了k的个数后，我们需要选择k个初始化的质心，就像上图b中的随机质心。由于我们是启发式方法，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心，最好这些质心不能太近。

传统的K-Means算法流程。

输入样本集合，然后划分成k 人为分类，凭经验将样品进行初步的分类

选择凝聚点后，求均值，求距离，归类

更新质心

重新求均值和距离，再重新归类

  大样本优化Mini Batch K-Means

在统的K-Means算法中，要计算所有的样本点到所有的质心的距离。如果样本量非常大，比如达到10万以上，特征有100以上，此时用传统的K-Means算法非常的耗时，就算加上elkan K-Means优化也依旧。在大数据时代，这样的场景越来越多。此时Mini Batch K-Means应运而生。

顾名思义，Mini Batch，也就是用样本集中的一部分的样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会洞伏有一些降低。一般来说这个降低的幅度在可以接受的范围之内。

在Mini Batch K-Means中，我们会选择一个合适的批样本大小batch size，我们仅仅用batch size个样本来做K-Means聚类。那么这batch size个样本怎么来的？一般是通过无放回的随机采样得到的。

为了增加算法的准确性，我们一般会多跑几次Mini Batch K-Means算法，用得到不同的随机采样集来得到聚类簇，选择其中最优的聚类簇。

K-Means与KNN

K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。

两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。

KNN(K-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻近值来代表。近邻算法就是将数据集合中每一个记录进行分类的方法。

总体来说，KNN分类算法包括以下4个步骤： 

1准备数据，对数据进行预处理 

2计算测试样本点（也就是待分类点）到其他每个样本点的距离 

3对每个距离进行排序，然后选择出距离最小的K个点 

4对K个点所属的类别进行比较，根据少数服从多数的原则，将测试样本点归入在K个点中占比最高的那一类

该算法在分类时有个主要纳禅携的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数 , 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点 。

K-Means小结

K-Means的主要优点有：

1）原理比较简单，实现也是很容易，收敛速度快。

2）聚类效果较优。

3）算法的可解释度比较强。

4）主要需要调参的参数仅仅是簇数k。

K-Means的主要缺点有：

1）K值的选取不好把握

2）对于不是凸的数据集比较难收敛

3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。

4） 采用迭代方法，得到的结果只是局部最优。

5） 对噪音和异常点比较的敏感。

PAM算法。 PAM法和K-means法很相似，但是它保证跑出来你的数据是最优的，和k-means不一样的是，虽然它也随机选择群中心，但是群中心的选择并非虚拟的，而是选取真正的数据点作为群中心。比如一开始选择3和20两个点作为群中心，并得到SS值。然后用不同的点去替换3或者20，选择最小SS值的点作为新的群中心，依次类推，直到SS值不能进一步优化。然后根据最后的群中心去聚类。PAM算法能够处理非数值类型的字段，但是其效率很慢，难以处理大数据量的情况。

除了分割聚类的方法,还有阶层式聚类的方法。我们看看ward方法。

华德法（ Ward’s Method ）:  华德法是阶层式聚类分析法中效果最好的，但是其运算速度较慢。理论差平方是判断聚类效果好不好的一个指标（每个资料点同群中心距离的平方和），其计算方式如下，SS值最小则说明聚类效果最好。华德法采用了一个取巧的方法，保证效果最好，仍然以上述例子示范。第一次聚类（聚成4类）有十种可能性，选择AB使得SS值最小，第二次（聚成3类）选择DE使得SS最小，第三次（聚成2类）选择CDE使得SS最小，直到聚成一类。

聚类分析是非常有用的,比如在公司可以给客户分类,或者说客户画像。如何了解用户的需求，把握用户的期望，对迅速对用户作出精准的投放这些手段已经成为企业能否的关键了。

某移动运营商在5月发展了19999个新用户，在新用户入网后一个月后，1、希望通过提供一些优惠提高用户的忠诚度  2、希望通过推荐一些产品提升客单价。

为达到这一目的，我们需要对新用户进行洞察，弄清楚以下的问题: a、应该给客户提供什么优惠？ 我们的优惠能否给客户带来惊喜？不同的客户是否该根据他们的喜好提供不同的优惠？b、客户对我们的什么产品感兴趣？不同的客户是否应该推荐不同的产品？

这个时候就可以使用聚类分析。

❷ 八：聚类算法K-means（20191223-29)

学习内容：无监督聚类算法K-Means

k-means：模型原理、收敛过程、超参数的选择

聚类分析是在数据中发现数据对象之间的关系，将数据进行分组，组内的相似性越大，组间的差别越大，则聚类效果越好。

不同的簇类型： 聚类旨在发现有用的对象簇，在现实中我们用到很多的簇的类型，使用不同的簇类型划分数据的结果是不同的。

基于原型的： 簇是对象的集合，其中每个对象到定义该簇的 原型 的距离比其他簇的原型距离更近，如(b)所示的原型即为中心点，在一个簇中的数据到其中心点比到另一个簇的中心点更近。这是一种常见的 基于中心的簇 ，最常用的K-Means就是这样的一种簇类型。 这样的簇趋向于球形。

基于密度的 ：簇是对象的密度区域，(d)所示的是基于密度的簇，当簇不规则或相互盘绕，并且有早上和离群点事，常常使用基于密度的簇定义。

关于更多的簇介绍参考《数据挖掘导论》。

基本的聚类分析算法

     1. K均值： 基于原型的、划分的距离技术，它试图发现用户指定个数(K)的簇。

     2. 凝聚的层次距离： 思想是开始时，每个点都作为一个单点簇，然后，重复的合并两个最靠近的簇，直到尝试单个、包含所有点的簇。

     3. DBSCAN: 一种基于密度的划分距离的算法，簇的个数有算法自动的确定，低密度中的点被视为噪声而忽略，因此其不产生完全聚类。

不同的距离量度会对距离的结果产生影响，常见的距离量度如下所示：

优点：易于实现 

缺点：可能收敛于局部最小值，在大规模数据收敛慢

算法思想：

选择K个点作为初始质心 

repeat

    将每个点指派到最近的质心，形成K个簇 

    重新计算每个簇的质心  

until 簇不发生变化或达到最大迭代次数

这里的“重新计算每个簇的质心”，是根据目标函数来计算的，因此在开始时要考虑 距离度量和目标函数。

考虑欧几里得距离的数据，使用 误差平方和（Sum of the Squared Error,SSE） 作为聚类的目标函数，两次运行K均值产生的两个不同的簇集，使用SSE最小的那个。

k表示k个聚类中心，ci表示第几个中心，dist表示的是欧几里得距离。 

这里有一个问题就是为什么，我们更新质心是让所有的点的平均值，这里就是SSE所决定的。

k均值算法非常简单且使用广泛，但是其有主要的两个缺陷：

1. K值需要预先给定 ，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确精确的K值的场景，可以进行迭代运算，然后找出Cost Function最小时所对应的K值，这个值往往能较好的描述有多少个簇类。

2. K-Means算法对初始选取的聚类中心点是敏感的 ，不同的随机种子点得到的聚类结果完全不同

3. K均值算法并不是很所有的数据类型。 它不能处理非球形簇、不同尺寸和不同密度的簇，银冠指定足够大的簇的个数是他通常可以发现纯子簇。

4. 对离群点的数据进行聚类时，K均值也有问题 ，这种情况下，离群点检测和删除有很大的帮助。

下面对初始质心的选择进行讨论：

当初始质心是随机的进行初始化的时候，K均值的每次运行将会产生不同的SSE,而且随机的选择初始质心结果可能很糟糕，可能只能得到局部的最优解，而无法得到全局的最优解。

多次运行，每次使用一组不同的随机初始质心，然后选择一个具有最小的SSE的簇集。该策略非常的简单，但是效果可能不是很好，这取决于数据集合寻找的簇的个数。

关于更多，参考《数据挖掘导论》

为了克服K-Means算法收敛于局部最小值的问题，提出了一种 二分K-均值(bisecting K-means)

将所有的点看成是一个簇

当簇小于数目k时

    对于每一个簇

        计算总误差

        在给定的簇上进行K-均值聚类,k值为2        计算将该簇划分成两个簇后总误差

    选择是的误差最小的那个簇进行划分

在原始的K-means算法中，每一次的划分所有的样本都要参与运算，如果数据量非常大的话，这个时间是非常高的，因此有了一种分批处理的改进算法。

使用Mini Batch（分批处理）的方法对数据点之间的距离进行计算。

Mini Batch的好处：不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。n 由于计算样本量少，所以会相应的减少运行时间n 但另一方面抽样也必然会带来准确度的下降。

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集成为一个“簇”。通过这样的划分，每个簇可能对应于一些潜在的概念（也就是类别）；需说明的是，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇对应的概念语义由使用者来把握和命名。

聚类是无监督的学习算法，分类是有监督的学习算法。所谓有监督就是有已知标签的训练集（也就是说提前知道训练集里的数据属于哪个类别），机器学习算法在训练集上学习到相应的参数，构建模型，然后应用到测试集上。而聚类算法是没有标签的，聚类的时候，需要实现的目标只是把相似的东西聚到一起。

聚类的目的是把相似的样本聚到一起，而将不相似的样本分开，类似于“物以类聚”，很直观的想法是同一个簇中的相似度要尽可能高，而簇与簇之间的相似度要尽可能的低。

性能度量大概可分为两类： 一是外部指标， 二是内部指标 。

外部指标：将聚类结果和某个“参考模型”进行比较。

内部指标：不利用任何参考模型，直接考察聚类结果。

对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大

初学者会很容易就把K-Means和KNN搞混，其实两者的差别还是很大的。

K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。

当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。

优点：

简单， 易于理解和实现 ；收敛快，一般仅需5-10次迭代即可，高效

缺点：

    1，对K值得选取把握不同对结果有很大的不同

    2，对于初始点的选取敏感，不同的随机初始点得到的聚类结果可能完全不同

    3，对于不是凸的数据集比较难收敛

    4，对噪点过于敏感，因为算法是根据基于均值的

    5，结果不一定是全局最优，只能保证局部最优

    6，对球形簇的分组效果较好，对非球型簇、不同尺寸、不同密度的簇分组效果不好。

K-means算法简单理解，易于实现（局部最优），却会有对初始点、噪声点敏感等问题；还容易和监督学习的分类算法KNN混淆。

参考阅读：

1.《 深入理解K-Means聚类算法 》

2.《 K-Means 》

❸ 声纹识别 | 快速概览 + 了解N：N聚类算法是如何应用的

关于声纹识别的N：N聚类算法

本文将从如下方面为你一一解读：

声纹(Voiceprint)，是用电声学仪器显示的携带言语信息的声波频谱，是由波长、频率以及强度等百余种特征维度组成的生物特征，具有稳定性、可测量性、唯一性等特点。

人类语言的产生是人体语言中枢与发音器官之间一个复杂的生理物理过程，发声器官--舌、牙齿、喉头、肺、鼻腔在尺寸和形态方面每个人的差异很大，所以任何两个人的声纹图谱都有差异。每个人的语音声学特征既有相对稳定性，又有变异性，不是一成不变的。这种变异可来自生理、病理、心理、模拟、伪装，也与环境干扰有关。尽管如此，由于每个人的发音器官都不尽相同，因此在一般情况下，人们仍能区别不同的人的声音或判断是否是同一人的声音。

1.  1:1 说话人确认

1:1 说话人确认是确认说话人身份的方法，针对“对于同样的文本内容，有两段录音，这两段录音到底是不是出自一人之口”这样的问题，也就是“两句话到底是不是一个人说“的问题；该类场景相对简单，主要应用于用户的注册和验证，以及APP内的声纹核身；

2.  1:N 说话人确认

1:N说话人辨认是辨认说话人身份的方法，针对“对于一段语音，需要迅速在样本库中进行搜寻比对，以确认这段语音与样本库中哪段语音相似度最高”，也就是说“给定的一段语音属于样本库中谁说的”的问题；该类场景比较常见，主要应用于黑名单用户进线检测，提高安防能力等。

3.  N：N说话人聚类 

对于千亿级别的无标签录音文件，如何做有效的处理？举个例子，假如说你有很多的语音片段（语音的文本内容是相同的），这些语音片段分别归属于甲乙丙丁等人，仅凭人耳辨识是无法分辨出哪些语音片段属于甲，哪些语音片段属于乙，通过N：N聚类的算法，进行声纹的相似度检测，将属于同一个人说话的语音片段不断进行合并归类，最后属于甲说话的语音片段全部被归为一类，属于乙说话的语音片段全部被归为一类，以此类推，类内语音的相似度极高，类间语音的相似度较低，达到将这些语音片段分人整理的目的；

简单介绍一下聚类分析：聚类分析是根据在数据中发现的描述对象及其关系的信息，将数据对象分组。目的是，组内的对象相互之间是相似的（相关的），而不同组中的对象是不同的（不相关的）。组内相似性越大，组间差距越大，说明聚类效果越好。聚类效果的好坏依赖于两个因素：1.衡量距离的方法（distance measurement） 2.聚类算法（algorithm）

目前主流的说话人聚类算法是在说话人分割的基础上，基于贝叶斯信息判据，采用凝聚分层聚类算法，直接对说话人分割后的语音段进行判决，将属于同一个说话人的语音段合并为一类。其基本思想是从每个语片段中提取特征参数，例如梅尔倒谱参数，计算每两个语音段之间特征参数的相似度，并利用BIC判断相似度最高的两个语音段是否合并为同一类。对任意两段语音都进行上述判决，直到所有的语音段不再合并。 ---摘自“说话人聚类的初始类生成方法”

聚类&声纹识别的主要场景 ：在跨渠道，跨场景收集语音同时建立声纹库的时候，由于各场景应用的客户账号或许不同，说话人在不同场景中分别注册过声纹，难以筛除重复注册语音，建立统一声纹库；我们如何快速的去筛除属于某一个人在不同情况下录制的多条录音文件？也就是如何保证最终留下的录音文件（声纹库）是唯一的？每一个人只对应一条音频，这就要用到聚类的算法；利用声纹识别N：N说话人聚类，对所有收集到的语音进行语音相似度检测，将同一说话人在不同场景中的多次录制的语音筛选出来，并只保留其中一条，从而保证了声纹库的独特性，节省了大量的人力成本，资源成本。

对于目前的场景，我们选择 凝聚层次聚类算法 ，在这种场景下，我们是要筛除重复人说话，那么我们可以将每一个录音文件都当作一个独立的数据点，看最后有凝聚出多少个独立的数据簇，此时可以理解为类内都是同一个人在说话；

1. 我们首先将每个数据点（每一条录音文件）视为一个单一的类，即如果我们的数据集中有 X 个数据点，那么我们就有 X 个类。然后，我们选择一个测量两个类之间距离的距离度量标准。作为例子，我们将用 average linkage，它将两个类之间的距离定义为第一个类中的数据点与第二个类中的数据点之间的平均距离。 （这个距离度量标准可以选择其他的）

2. 在每次迭代中，我们将两个类合并成一个。这两个要合并的类应具有最小的 average linkage。即根据我们选择的距离度量标准，这两个类之间的距离最小，因此是最相似的，应该合并在一起。 

3. 重复步骤 2 直到我们到达树根，即我们只有一个包含所有数据点的类。这样我们只需要选择何时停止合并类，即何时停止构建树，来选择最终需要多少个类--- 摘自知乎

按照实际的场景，如果我们最终要得到1000个不重复的录音文件，为了防止过度合并，定义的退出条件是最后想要得到的录音文件数目；

1. 录音重放攻击 ： 攻击者录制目标说话人的语音进行播放，以目标人身份试图通过声纹识别系统的认证。

策略：基于随机内容声纹的检测技术：利用随机数字的不确定性，用户在规定的时间内（5-10S）需要念出指定的随机内容，如果超时，则随机内容更新； 因为对于录音重放的内容是固定的，很不灵活，所以比较容易做限制

2. 波形拼接攻击

攻击者将目标说话人的语音录制下来，通过波形编辑工具，拼接出指定内容的语音数据，以放音的方式假冒目标说话人，试图以目标人身份通过声纹识别系统的认证。

策略：同录音重放

3.语音合成攻击

攻击者用语音合成技术生成目标说话人的语音，以放音的方式假冒目标说话人，试图以目标人的身份通过声纹识别系统的认证。

策略：1. 同录音重放 

           2. 利用活体检测技术，加强算法的识别度

❹ 聚类算法的算法用途

聚类的用途是很广泛的。
在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯。它作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；并且，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。
聚类分析的算法可以分为划分法（Partitioning Methods）、层次法（Hierarchical Methods）、基于密度的方法（density-based methods）、基于网格的方法（grid-based methods）、基于模型的方法（Model-Based Methods）。