大数据-212 数据挖掘 机器学习理论 - 无监督学习算法 KMeans 基本原理 簇内误差平方和

点一下关注吧！！！非常感谢！！持续更新！！！

目前已经更新到了：

• Hadoop（已更完）
• HDFS（已更完）
• MapReduce（已更完）
• Hive（已更完）
• Flume（已更完）
• Sqoop（已更完）
• Zookeeper（已更完）
• HBase（已更完）
• Redis （已更完）
• Kafka（已更完）
• Spark（已更完）
• Flink（已更完）
• ClickHouse（已更完）
• Kudu（已更完）
• Druid（已更完）
• Kylin（已更完）
• Elasticsearch（已更完）
• DataX（已更完）
• Tez（已更完）
• 数据挖掘（正在更新…）

章节内容

上节我们完成了如下的内容：

• 逻辑回归 scikit-learn 实现 剩余部分
• max_iter 分类方式选参数

基本概念

决策树、线性和逻辑回归都比较常用的机器学习算法，他们虽然有着不同的功能，但却属于有监督学习的一部分，模型在训练的时候，需要特征矩阵 X，也需要真实标签 Y。机器学习当中，还有相当一部分属于无监督学习，无监督的算法在训练的时候只需要特征矩阵 X，不需要标签。无监督学习的代表算法有聚类算法、降维算法。
聚类算法又叫做：“无监督分类”，其目的是将数据划分成有意义或有用的组（或簇）。这种划分可以基于我们的业务需求或建模需求来完成，也可以单纯的帮助我们探索数据的自然结构和分布。
比如商业中，如果我们手头上大量的当前和潜在客户的信息，我们可以使用聚类将客户划分为若干组，以便于进一步分析和开展营销活动，最有名的客户价值判断模型 RFM（Recency frequency monetary），就常常和聚类分析共同使用。再比如，聚类可以用于降维和矢量量化（vector quantization），可以将高维特征压缩到一列当中，常常用于图像、声音、视频等非结构化数据，可以大幅度压缩数据量。

对比他们的特征

聚类算法是无监督类机器学习算法中最常用的一类，其目的是将数据划分成有意义或有用的组（也被称为簇）。这种划分可以基于我们的业务需求或建模需求来完成，也可以单纯的帮助我们探索数据的自然结构和分布。如果目标是划分成有意义的组，则簇应该捕获数据的自然结构。然而，在某种意义下，聚类分析知识解决其他问题（如数据汇总）的起点。无论是皆在理解还是应用，聚类分析都在广泛的领域扮演着重要角色。这些领域包括：心理学和其他社会科学、生物学、统计学、模式识别、信息检索、机器学习、数据挖掘。
聚类分析在许多实际问题上都有应用，下面是一些具体的例子，按聚类目的是为了理解数据自然结构还用于数据处理来组织。

K-Means

基本原理

关键概念：簇和质心
K-Means是一种经典的无监督学习聚类算法，主要用于将一组数据划分为K个簇（Clusters），其中K是用户预先定义的聚类数量。它的目标是使得同一簇内的数据点之间的距离尽可能接近，而不同簇的数据点之间的距离尽可能远。
KMeans 算法将一组 N 个样本特征矩阵 X 划分为 K 个无交集的簇，直观上来看簇是一组一组聚集在一起的数据，在一个簇中的数据就认为是同一类，簇就是聚类的结果表现。
簇中所有数据的均值通常被称为这个簇的质心（centroids）。在一个二维平面中，一簇数据带你的质心的横坐标就是这一簇数据点的横坐标的均值，质心的纵坐标就是这一簇数据的纵坐标的均值。同理可推导到高维空间。
在 KMeans 算法中，簇的个数 K 是一个超参数，需要我们人为输入来确定。KMeans的核心任务就是根据我们设定好的 K，找出 K 个最优的质心，并将离这些质心最近的数据分别分配到这些质心代表的簇中去。

工作过程

K-Means 的执行步骤如下：

• 初始化簇中心（质心）：随机选择K个数据点作为初始簇中心，称为质心（Centroid）。
• 分配数据点到簇：对于每一个数据点，计算它到每个质心的欧式距离，并将该数据点分配到距离最近的簇。这样就可以得到K个初始簇。
• 更新质心：对于每一个簇，计算该簇内所有数据点的平均位置，将该平均位置作为新的质心。
• 迭代更新：重复步骤2和步骤3，直到质心位置不再发生明显变化（即达到收敛）或达到最大迭代次数。

具体过程

具体过程可总结如下：

• 创建 K 个点作为初始质心（通常随机选择）
• 当任意一个点的簇分配结果发生改变时：计算质心与数据点之间的距离、将数据点分配到离其最近的簇
• 对每个簇，计算簇中所有点的均值并将均值作为新的质心
• 直到簇不再发生变化或者达到最大的迭代次数

那么什么情况下，我们的质心位置不再发生变化呢？
当我们找到一个质心，在每次迭代中被分配到这个质心上的样本都是一致的，即每次新生成的簇是一致的，所有的样本点都不会再从一个簇转移到另一个簇，质心就不会变化了。
这个过程可以由下图来显示，我们规定，将数据分为 4（K=4），其中白色 X 代表质心位置：

在数据的多次迭代下（iteration），就会：

第六次迭代之后，基本上质心的位置就不会再改变了，生成的簇也变得稳定，此时我们的聚类就完成了，我们可以明显看出，K-Means 按照数据的分布，将数据聚集成了我们规定的 4 类，接下来我们就可以按照我们的业务求或者算法需求，对四类数据进行不同的处理。

簇内误差平方和

聚类算法出的类有什么含义呢？这些类有什么样的性质？我们认为，被分在同一个簇中的数据是有相似的，而不同的簇中的数据是不同的，当聚类完毕之后，我们就要分别去研究每个簇中的样本都有什么样的性质，从而根据业务需求定制不同的商业或者科技策略。
聚类算法的目的就是追求“簇内差异小，簇外差异大”。而这个差异，由样本到其所在簇的质心的距离来衡量。
对于一个簇来说，所有样本点质心的距离之和越小，我们就认为这个簇中的样本越相似，簇内差距离来衡量。
对于一个簇来说，所有样本点到执行距离之和越小，我们就认为这个簇中的样本越来越相似，簇内差异就越小，而距离的衡量方法由多种。

假设：

• x 表示簇中的一个样本点
• u 表示该簇中的质心
• n 表示每个样本点中的特征数目
• i 表示组成点 x 的每个特征编号

则该样本到质心距离可以由以下距离来衡量：

如果我们采用欧几里得距离，则一个簇中所有样本点的质心距离的平方和为：

• 其中，m 为一个簇中样本的个数
• j 是每个样本的编号

这个公式被称为簇内平方和（cluster sum of square），又叫做 Inertia。
而将一个数据集中的所有簇的簇内平方和相加，就得到了整体的平方和（Total Cluster Sum Of Square），又叫做 Total Inertia。

Total Intertia 越小，代表着每个簇内样本越相似，聚类的效果就越好。
因此 KMeans 追求的是，求解能够让 Inertia 最小化的质心。

实际上，在质心不断变化不断迭代的过程中，总体平方和是越来越小的，当整体平方和最小的时候，质心就不再发生变化了。
大家可以发现，我们的 Intertia 是基于欧几里得距离的计算公式得来的。实际上，我们也可以使用其他距离，每个距离都有自己对应的 Inertia。在过去的经验中，我们总结出距离所对应的质心选择方法和 Inertia，在 KMeans 中，只要使用了正确的质心和距离组合，无论使用什么样的距离，都可以达到不错的聚类效果：

而这些组合，都可以由严格的数学证明来推导，在实际中我们往往都使用欧式距离，因此我们无需去担忧这些距离所搭配的质心选择是如何得来的。