分类

KNN - K近邻算法

概念

一个样本与数据集中的k个样本最相似， 如果这k个样本中的大多数属于某一个类别， 则该样本也属于这个类别。也就是说，该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法在类别决策时，只与极少量的相邻样本有关。

KNN算法最简单粗暴的就是将预测点与所有点距离（这里未知实例与所有已知实例的距离使用欧氏距离进行计算）进行计算，然后保存并排序，选出前面K个值看看哪些类别比较多。

过拟合与欠拟合

K越小越容易过拟合，当K=1时，这时只根据单个近邻进行预测，如果离目标点最近的一个点是噪声，就会出错，此时模型复杂度高，稳健性低，决策边界崎岖。

但是如果K取的过大，这时与目标点较远的样本点也会对预测起作用，就会导致欠拟合，此时模型变得简单，决策边界变平滑。

如果K=N的时候，那么就是取全部的样本点，这样预测新点时，最终结果都是取所有样本点中某分类下最多的点，分类模型就完全失效了！

聚类

K-MEANS

KMEANS代价函数

• 能够帮助我们调试学习算法，确保k均值聚类算法是在正确运行中；
• 能够运用代价函数帮助k-均值找到更好的簇，并且避免局部最优解

聚类的过程为减小代价函数的过程，代价函数为：
$$\begin{gathered} J=\min （[c(1),c(2)...c(k)],[{\mu }_1,{\mu }_2...{\mu }_k]） \\ 其中，c(k)表示第k类聚类的索引。{\mu }_k表示第k类聚类的聚类中心 \\ 循环分为两次，第一次为减小J[c(1),c(2)...c(k)]，第二次为减小J[{\mu }_1,{\mu }_2...{\mu }_k] \end{gathered}$$
即第一次循环为固定聚类中心点不变，减小每个样本点到聚类中心的距离引起的代价，即给样本点分类

第二次循环为固定样本点的类别不变，减小聚类中心引起的代价，即重新确定聚类中心。

在迭代的过程中，每一次的代价函数应该都在减小或者保持不变，如果出现代价函数增大的情况，则说明实现的过程可能存在错误。

局部最小值问题

K-均值聚类会存在一个问题，也就是最终聚类的结果会停留在一个局部最小值处，这取决于初始化的情况。

解决方法

为了解决这个问题，我们通常采用多次运行k-均值聚类算法，每一次都重新进行随机初始化，最后比较多次运行k-均值的结果，选择代价函数最小的结果。但是上述这种方法，对于聚类中心数目K较小时（2-10）可行，但是当K较大时，这么做也可能不会有明显的改善。

聚类数如何选择？

没有最好的选择聚类数的方法，人们一般都是根据不同的问题进行手动选择。在进行选择的时候我们可以从k-均值聚类算法的动机是什么出发，选择出最好的适应于该动机的聚类数。
例如，我们搜集了一些人的身高和体重，想借助身高和体重两个特征进行衣服尺码的划分，例如厂家想生产三种类型的尺码（S、M、L），以此可以获得更好的收益，这是我们的聚类数目会选择K=3；例如厂家想生产五种类型的尺码（XS、S、M、L、XL），以此可以获得更好的收益，这是我们的聚类数目会选择K=5；所以这时候的聚类数目的选择是根据制造的衣服是否能较好的适应我们的客户。

目前采用的选择聚类数的方法：肘部法则

我们分别计算在各种K值情况下，聚类算法最终的损失函数，绘制出随着K值变化损失函数变化的曲线：

左图为存在肘部的情况，选择肘部点对应的K值作为模型的聚类数。
右图为不存在肘部的情况，根据业务需求确定K值

KMEANS存在的问题

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

于是就思考，样本密度大的成一类呗。这就是DBSCAN聚类算法。

DBSCAN

算法将具有足够高密度的区域划分为簇，并可以发现任何形状的聚类。

定义解释

概念

直接密度可达：
$$如果x_i是核心对象，且x_j位于x_i的\epsilon 邻域内，则x_j由x_i密度可达$$
密度可达：
$$x_i与x_j之间有一串序列p_1{p}_2...p_t，且p_{n+1}由p_n密度直达，则x_i与x_j密度相连$$
密度相连：
$$对于x_i与x_j如果他们两个点之间存在核心对象样本x_k，使得x_i与x_j均由x_k密度可达，则称x_i和x_j密度相连$$
三种关系中，只有密度相连是满足对称性的。

密度可达与密度相连的直观解释

从上图可以很容易看出理解上述定义，图中MinPts=5，红色的点都是核心对象，因为其ϵ-邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的ϵ-邻域内所有的样本相互都是密度相连的。

​ 由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。

DBSCAN发现簇的过程（即算法过程）

​ 初始，给定数据集D中所有对象都被标记为“unvisited”，DBSCAN随机选择一个未访问的对象p，标记p为“visited”，并检查p的**ϵ-领域是否至少包含MinPts个对象。如果不是，则p被标记为噪声点。否则为p创建一个新的簇C，并且把p的ϵ-领域中所有对象都放在候选集合N中。DBSCAN迭代地把N中不属于其他簇的对象添加到C中。在此过程中，对应N中标记为“unvisited”的对象 P’ ,DBSCAN把它标记为“visited”，并且检查它的ϵ-领域，如果 P’ 的ϵ-领域至少包含MinPts个对象，则P’ 的ϵ-**领域中的对象都被添加到N中。DBSCAN继续添加对象到C，直到C不能扩展，即直到N为空。此时簇C完成生成，输出。

为了找到下一个簇，DBSCAN从剩下的对象中随机选择一个未访问过的对象。聚类过程继续，直到所有对象都被访问。

DBSCAN的三个问题

• 噪音样本点

  一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。DBSCAN算法很容易检测异常点。

• 距离的度量（即如何计算某样本和核心对象样本的距离）

  在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。

• DBSCAN不稳定性

  某些样本可能到两个核心对象的距离都小于ϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说BDSCAN的算法不是完全稳定的算法。

优缺点

优点：

• 和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。

• 同时它在聚类的同时还可以找出异常点，对数据集中的异常点不敏感。一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。

缺点：

• 如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。

• 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPoints联合调参，不同的参数组合对最后的聚类效果有较大影响。一般这两个参数的确定靠经验值。如果觉得经验值聚类的结果不满意，可以适当调整ϵ和MinPoints的值，经过多次迭代计算对比，选择最合适的参数值。

  如果MinPoints不变，ϵ取得值过大，会导致大多数点都聚到同一个簇中，ϵ过小，会导致一个簇的分裂；如果ϵ不变，MinPoints的值取得过大，会导致同一个簇中点被标记为离群点，ϵ过小，会导致发现大量的核心点。

• 不适合高维数据，可以先进行降维操作

• Sklearn中效率很慢，可以先执行数据削减策略

参考：

• https://www.jianshu.com/p/d2eddc733c4d

• https://www.cnblogs.com/pinard/p/6208966.html