聚类是一种将数据点按一定规则分群（分组）的机器学习技术。其主要研究数据间逻辑上或物理上的相互关系。聚类分析本身不是一个特定的算法，而是要解决的一般任务。它可以通过各种算法来实现，这些算法在理解群集的构成以及如何有效地找到它们方面存在显着差异。由聚类所组成的簇是一组数据对象的集合，这些对象与同一簇中的对象彼此类似，与其他簇中的对象相异。其分析结果不仅可以揭示数据间的内在联系与区别，还可以为进一步的数据分析与知识发现提供重要依据。

监督学习：当我们根据一组给定的预测因子变量或自变量去预测一个目标变量时，这些问题被称为监督学习问题。

无监督学习：没有任何固定目标变量的这些问题被称为无监督学习问题。在这些问题中，我们只有自变量而没有目标/因变量。

 

1、K-Means 聚类算法原理详解：

简单来说K-Means 聚类算法接受一个未标记的数据集，然后将数据聚类成不同的组，同时，k-means算法也是一种无监督学习。

簇的两个属性：聚类的主要目的不仅仅是创建簇，而是创建好的和有意义的簇。

1）组中的所有数据点应该彼此相似；

2）来自不同组的数据点应尽可能不同；

簇第一个属性：Inertia评估。Inertia实际上计算簇内所有点到该簇的质心的距离的总和。我们为所有簇计算这个总和，最终Inertia值是所有这些距离的总和。簇内的这个距离称为簇内距离(intracluster distance.)。因此，Inertia为我们提供了簇内距离的总和：

现在，你认为一个好的簇的Inertia值应该是什么？小的Inertia好还是大的Inertia好？我们希望同一簇中的点彼此相似，因此它们之间的距离应尽可能小。记住这一点，Inertia越小，聚类越好。

簇第二个属性：Dunn Index，我们现在知道Inertia试图最小化簇内距离，它正试图划分更紧凑的簇。换句话说如果一个簇的质心与该簇中的点之间的距离很小，则意味着这些点彼此更接近。因此，Inertia可确保满足簇的第一个属性。但它并不关心第二个属性，不同的簇应尽可能彼此不同，这就是Dunn Index可以用来评估的地方。

除了质心和点之间的距离，Dunn Index还考虑了两个簇之间的距离，两个不同簇的质心之间的距离称为簇间距离(inter-cluster distance)。Dunn Index指数的公式：

Dunn Index是簇间距离的最小值与簇内距离的最大值之比。我们希望最大化Dunn Index，Dunn Index的值越大，簇就越好。为了最大化Dunn Index的值，分子应该是最大的。在这里，我们采用最小的簇间距离。因此，即使是最近的簇之间的距离也应该更大，这最终将确保簇彼此远离。此外，分母应该是最小的，以最大化Dunn Index。在这里，我们采取最大的簇内距离。同样，这里的直觉也是一样的。簇质心和点之间的最大距离总和应该最小，这最终将确保划分的簇紧凑。

 

什么是K-means聚类：

回想一下簇的第一个属性，它表明簇中的点应该彼此相似。因此，我们的目标是最小化簇内点之间的距离。有一种算法试图通过它们的质心最小化簇中点的距离,那就是K-means聚类技术。K-means是一种基于质心的算法，或基于距离的算法，我们计算将点分配给一个簇的距离。在K-means中，每个聚类都与一个质心相关联。K-means算法的主要目的是最小化点与它们各自的簇质心之间的距离之和。

“求点群中心的算法”：欧氏距离（Euclidean Distance）：（差的平方和的平方根）

 

举个例子来了解K-means实际上是如何工作的：

 我们有这8个点，我们想要应用K-means来为这些点划分簇。下面将演示我们是怎样做到的。

第一步：选择簇的数目k

K-means的第一步是选择簇的数目k。

第二步：从数据中选择k个随机点作为质心

接下来，我们为每个簇随机选择质心。假设我们想要有2个簇，所以k在这里等于2。然后我们随机选择质心：这里，红色和绿色圆圈代表这些簇的质心。

 

第三步：将所有点分配给到某个质心距离最近的簇

一旦我们初始化了质心，我们就将每个点分配给到某个质心距离最近的簇：在这里，你可以看到更接近红点的点被分配给红色簇，而更接近绿点的点被分配给绿色簇。

 

第四步：重新计算新形成的簇的质心

现在，一旦我们将所有点分配到任一簇中，下一步就是计算新形成的簇的质心：在这里，红色和绿色叉号是新的质心。

第五步：重复第三步和第四步

然后我们重复第三步和第四步：计算质心并基于它们与质心的距离将所有点分配给簇的步骤是单次迭代。但我们什么时候应该停止这个过程？它不能永远运行下去对吧？

 停止K-means聚类的标准，基本上有三种停止标准可用于停止K-means算法：新形成的簇的质心不会改变数据点保留在同一个簇中达到最大迭代次数如果新形成的簇的质心没有变化，我们就可以停止算法。即使在多次迭代之后，所有簇都还是相同的质心，我们可以说该算法没有学习任何新模式，并且它是停止训练的标志。另一个明显的迹象表明，在多次迭代训练的之后，如果数据点仍然都在同一簇中，我们应该停止训练过程。最后，如果达到最大迭代次数，我们可以停止训练。假设我们将迭代次数设置为100。在停止之前，该过程将重复100次迭代。

 

算法实现步骤（总结）：

1. 确定要聚类的数量，并随机初始化它们各自的中心点（质心）；

2. 计算每个点分别到k个聚类中心的聚类，然后将该点分到最近的聚类中心，这样就行成了k个簇；

3. 再重新计算每个簇的质心（均值，即向量各维取平均）；

4. 重复以上2~3步，直到质心的位置不再发生变化或者达到设定的迭代次数。

 

K-means聚类算法面临的挑战

1）使用K-means时我们面临的普遍挑战之一是簇的大小不同。假设我们有以下几点：

 与中心簇相比，左侧和最右侧的簇的点的数量比较少。现在，如果我们在这些点上应用K-means聚类，结果将是这样的：

2）K-means的另一个挑战是当原始点的密度不同时。比如下面这些原始点：

这里，红色簇中的点比较松散，而其余簇中的点紧密地堆积在一起。现在，如果我们在这些点上应用K-means，我们将得到这样的簇：

 

我们可以看到紧凑的点已分配给同一个簇。而实际松散分布但在同一簇中的点却分配给不同的簇。效果并不理想，我们能做些什么呢？

解决方案一：是使用更多的簇进行划分。因此，在所有上述场景中，我们可以拥有更多的簇，而不是使用3个簇。也许设置k = 10可能会产生更有意义的簇。

解决方案二：K-means ++为K-means聚类选择初始簇质心。还记得我们如何在K-means聚类中随机初始化质心吗？这也可能有问题，因为我们每次都可能得到不同的簇。因此，为了解决随机初始化的这个问题，有一种称为K-means ++的算法可用于为K-means选择初始值或初始簇质心。

 

K-means++算法介绍：

在某些情况下，如果簇的初始化不合适，K-means可能导致产生坏的簇。这就是K-means ++产生作用的地方。它指定了在使用标准K-means聚类算法向前推进之前初始化簇质心的过程。使用K-means ++算法，我们优化了随机选择簇质心的步骤。在使用K-means ++初始化时，即(init='K-means++')，我们更有可能找到与最佳K-means解决方案竞争的解决方案。

使用K-means ++初始化质心的步骤是：

1）从我们想要聚类的数据点随机均匀地选择第一个簇；这类似于我们在K-means中所做的，但不是随机挑选所有质心，而是在这里选择一个质心；

2）接下来，我们计算每个数据点到已经选择的簇的质心的距离(D(x))；

3）然后，从数据点中选择新的簇质心；

4）重复步骤2和3，直到选择了k个簇。

举个例子来更清楚地理解这一点。假设我们有以下几点，我们想在这里划分3个簇：

现在，第一步是随机选择一个数据点作为簇质心：

 

假设我们选择绿点作为初始质心。现在，我们将使用此质心计算每个数据点与质心的距离(D(x))：

下一个质心将是其平方距离(D(x)2)离当前质心最远的那个点：

在这种情况下，红点将被选为下一个质心。现在，为了选择最后一个质心，我们将计算所有点到其最近的质心的距离，其中具有最大平方距离的点作为下一个质心：

我们将选择最后一个质心为：

接下来，我们将从一个小的簇值开始，比如说2使用2个簇训练模型，计算该模型的Inertia，最后将其绘制在上图中。假设我们得到Inertia大约为1000：

 现在，我们将增加簇的数量，再次训练模型，并绘制Inertia。这是我们得到的图：

当我们将簇值从2更改为4时，Inertia急剧下降。随着我们进一步增加簇的数量，Inertia的下降变得缓慢并最终变得稳定。Inertia的减小幅度变为常数时对应的簇的个数可以选择作为我们数据的正确簇的个数。

 在这里，我们可以选择6到10之间的任意数量的簇的个数。我们可以有7个，8个甚至9个簇。你还必须在确定簇的个数时查看计算成本。如果我们增加簇的数量，计算成本也会增加。因此，如果你没有高计算资源，我的建议是选择较少数量的簇。K值的选择主要还是根据经验以及利用k-means聚类的目的来决定。

 

k-means 算法的优点：

1）法简单快捷，容易理解，速度快，真正在做的是计算点和组中心之间的距离：非常少的计算！因此它具有线性复杂度 O(n)；

2）对所有的数据样本都进行聚类；

3）对满足高斯分布、均匀分布的数据类型聚类效果表较好，适合常规数据集。

k-means算法的缺点：

1）需要事先确定聚类个数；

2）对初始聚类中心敏感，而K-means 也是从随机选择的聚类中心开始，所以可能在不同的算法中产生不同的聚类结果(结果可能不可重复并缺乏一致性，其他聚类方法更加一致)；

3）对孤立点和噪声点相对敏感。

4）很难发现任意形状的簇

 

2、DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）：

是一种基于密度的空间聚类算法，与KMeans算法不同，它不需要确定聚类的数量，而是基于数据推测聚类的数目，它能够针对任意形状产生聚类。 该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

基本概念：

1.epsoiln-neighborhood(简称e-nbhd）密度空间：表示半径为e且含有若干个点的nbhd，密度等于包含点的个数/空间大小。图中中心点是（3,2），半径epsilon是0.5。根据式子密度=点的个数/面积，可以计算得到上图中密度=31/2pi(0.5)*(0.5)=62/pi，这个数字本身意义不大，但通过计算某一小区域的密度，横向对比可以得知整个区域的密度分布，由此相近的点可聚类到同一区域内。

 2. DBSCAN算法需要首先确定两个参数：

1）epsilon：在一个点周围邻近区域的半径
2）minPts：邻近区域内至少包含点的个数

3. 根据以上两个参数，结合epsilon-neighborhood的特征，可以把样本中的点分成三类：

核点（core point）：满足NBHD(p,epsilon)>=minPts，则为核样本点
边缘点（border point）：NBHD(p,epsilon)<minPts，但是该点可由一些核点获得（density-reachable或者directly-reachable）
离群点（Outlier）：既不是核点也不是边缘点，则是不属于这一类的点

上图中A表示核心对象；B,C表示边界点；N表示离群点。我们可以认为A是系统在众多样本点中随机选中一个，围绕这个被选中的样本点画一个圆，规定这个圆的半径以及圆内最少包含的样本点，如果在指定半径内有足够多的样本点在内，那么这个圆圈的圆心就转移到这个内部样本点，继续去圈附近其它的样本点，类似传销一样，继续去发展下线。等到这个滚来滚去的圈发现所圈住的样本点数量少于预先指定的值，就停止了。那么我们称最开始那个点为核心点，如A，停下来的那个点为边界点，如B、C，没得滚的那个点为离群点，如N。

基于密度这点有什么好处呢，我们知道kmeans聚类算法只能处理球形的簇，也就是一个聚成实心的团（这是因为算法本身计算平均距离的局限）。但往往现实中还会有各种形状，比如下面两张图，环形和不规则形，这个时候，那些传统的聚类算法显然就悲剧了。于是就思考，样本密度大的成一类呗。呐这就是DBSCAN聚类算法。
  

 

如果是传统的Kmeans聚类，我们也来看一下效果：可以看出DBSCAN算法基于密度聚类的优势就明显了。

      

 

DBSCAN算法迭代可视化展示：https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/

 

DBSCAN的实现步骤：（在已知epsilon和minPts的前提下）

1）任意选择一个点（既没有指定到一个类也没有特定为外围点），计算它的NBHD(p,epsilon)判断是否为核点。如果是，在该点周围建立一个类，否则，设定为外围点。
2）遍历其他点，直到建立一个类。把directly-reachable的点加入到类中，接着把density-reachable的点也加进来。如果标记为外围的点被加进来，修改状态为边缘点。
3）重复步骤1和2，直到所有的点满足在类中（核点或边缘点）或者为外围点

 

参数选择：

epsilon：半径，是最难指定的 ，大了，圈住的就多了，簇的个数就少了；反之，簇的个数就多了，这对我们最后的结果是有影响的。我们这个时候K距离可以帮助我们来设定半径r，也就是要找到突变点，比如有一组数据：首先选中一个点，计算它和所有其他的点的距离，从小到大排序，d1，d2，d3，d4，......，可以发现d3和d4之间的差异很大，于是认为前面的距离是比较合适的，那么就可以指定出r半径的大小为0.12。

data = 【0.1，0.11，0.12，0.3，0.31，0.32，......】

                d1      d2      d3     d4      d5      d6  

以上虽然是一个可取的方式，但是有时候比较麻烦 ，大部分还是都试一试进行观察，用k距离需要做大量实验来观察，很难一次性把这些值都选准。 

MinPts:这个参数就是圈住的点的个数，也相当于是一个密度，一般这个值都是偏小一些，然后进行多次尝试

 

总结:

（1）epsilon不变的情况下，调整minPts的大小，则minPts越大，NBHD越密集，产生离群点越多。

（2）在minPts不变的情况下，epsilon越小，聚类越密集，产生离群点越多。

（3）epsilon越小，minPts越多，则密度越高，产生聚类越密集。

DBSCAN最大的特点是事先不必确定聚类的种类，通过基于密度的方法，聚类并找出离群点；不仅需要对大部分在类中的点分析，也需要对离群点分析.

 

DBSCAN 算法的优点：

1）不需要指定簇个数，即不需事先知道要形成的簇类数量；

2）可以发现任意形状的簇类（非线性聚类）；

3）能够识别出噪声点，擅长找到离群点（检测任务）。

DBSCAN 算法的缺点：

1）算法聚类时采用全局性的表征密度参数，当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差；

2）算法须指定两个参数：半径和最小密度阈值。所以对用户定义的参数敏感，细微的不同都可能导致差别很大的结果，而参数的选择无规律可循，难以选择，只能靠经验确定；

3）算法对稀疏的高维数据性能差，因对高维数据，欧几里得密度定义不能很好理解（可以做降维）；

4）对不满足给定条件的样本点会作为噪声点剔除；

5）因算法直接对数据库进行操作，当数据量增大时，要求较大的内存支持且I/O消耗也很大；

6）算法的计算复杂度较高。