机器学习

K-means聚类分析

K-Means是一种常见的无监督机器学习算法，用于数据的聚类分析。它通过迭代的方式将数据划分为k个互不重叠的簇，目的是使每个簇内的样本相似度最大化，而簇间的相似度最小化。

概念：

• 簇：K-Means算法将数据划分为k个簇，每个簇包含一组相似的数据点。
• 质心：每个簇的中心点，代表簇内所有数据点的平均值。
• 距离度量：通常使用欧氏距离来度量数据点之间的距离。

算法步骤：

1. 随机选择k个初始质心。
2. 将每个数据点分配到距离最近的质心所在的簇。
3. 更新每个簇的质心为簇内所有数据点的平均值。
4. 重复步骤2和3，直到质心不再变化或达到最大迭代次数。

<center>2024认证杯c题聚类后结果（k=2）</center> 如果把这些聚类看成定居点，2个肯定是有点少了，这里就有了一个问题，k值怎么选？ 按照原本的算法，k值是人为确定的，聚类的结果收到k值的影响，k值选的不好，结果可能就不好。以下两个方法确定更优k值

确定k值

肘部法（elbow method）

**“肘部法”（Elbow Method）**是一种常用于聚类分析中的方法，特别是在K-means聚类中，帮助选择最佳的聚类数目（K）。该方法的核心思想是通过计算不同聚类数目时的“聚类紧密度”来确定最佳的K值。

• 计算不同K值下的聚类结果：选择一系列可能的K值（如1到10），对于每个K值，运行聚类算法（如K-means），并计算聚类的“误差平方和”（Inertia）。误差平方和是指数据点到其所在聚类中心的距离的平方和，反映了聚类的紧密程度，值越小表示聚类越紧凑。
• 绘制误差平方和与K值的关系图：将K值与对应的误差平方和绘制在图上，通常X轴表示K值，Y轴表示误差平方和。
• 寻找肘部：图中会出现一个“肘部”，即误差平方和随K值增加而逐渐减小，但在某个K值后，误差平方和的下降速度变缓。肘部对应的K值通常就是最佳聚类数目。

轮廓系数（silhouette score）

**轮廓系数（Silhouette Coefficient）**是用于评估聚类结果质量的指标，它的值介于 -1 和 1 之间，表示聚类效果的好坏。轮廓系数越接近1，表示聚类效果越好；越接近-1，表示聚类效果越差。 上图的S(i)是相对于簇内单点而言的，如果要表示这个簇的聚类效果，则需要计算所有点的轮廓系数，然后取平均值。

<center>两个方法综合考虑确定较优k值</center>

随机森林(Random Forest)

概念

**随机森林（Random Forest）**是一种 集成学习（Ensemble Learning）方法，属于监督学习算法，主要用于分类和回归任务。它由 多棵决策树（通常是CART决策树）组成，通过投票（分类）或平均（回归）的方式输出最终结果。随机森林的核心思想是通过集成多个弱学习器（决策树），提升模型的泛化能力，降低过拟合风险。

解释

<!-- <div style="display: flex; justify-content: space-between; align-items: center;"> <img src="https://pub-141940ca1dac464db4ab5fa38943929e.r2.dev/legacy/learning/random1.webp" alt="random forest 1" style="width: 30%;"> <img src="https://pub-141940ca1dac464db4ab5fa38943929e.r2.dev/legacy/learning/random2.webp" alt="random forest 2" style="width: 30%;"> <img src="https://pub-141940ca1dac464db4ab5fa38943929e.r2.dev/legacy/learning/random3.webp" alt="random forest 3" style="width: 30%;"> </div> -->

如上三幅图，每幅图代表一个决策树，一颗决策树就是一个weak learner，它在样本集里面随机选择数据，从它的角度理解这个问题。

• 第一颗决策树，它学到了是动物且有羽毛的属于鸟类
• 第二颗决策树，它学到了是动物且会飞的是鸟类，是动物但不会飞的不是鸟类
• 第三颗决策树，它学到了会飞有羽毛的是鸟，会飞没羽毛的不是鸟 如果我们只从一个树的角度理解问题，很容易受限，这就是它叫weak learner的原因，但是如果我们结合众长，把多棵树结合起来成一个森林，看待问题的角度就比较全面，当再给出某个动物，预测它是不是鸟类就会更准确。会不会飞，有没有羽毛等属于特征变量（可以有多个），是不是鸟类属于目标变量（只有一个）。随机森林之所以属于机器学习算法，是因为我们要事先给定数据集（越多越好），让它学习（具备这些特征的动物，是不是鸟类），训练完后，当我们再给出某些特征变量让它预测时，它就可以根据之前训练的经验作出相对合理的预测了。

特点

• 随机性
  • 在构建每棵决策树时，随机抽取训练数据的一个子集（有放回的采样，称为袋外数据OOB），在上面三幅图中，分别抽取了动物1，4，动物4，5，动物1，2。
  • 在每次分裂节点时，随机选择部分特征进行分裂（特征随机性），选择动物、羽毛变量，选择动物、会飞变量，选择羽毛、会飞变量。
• 高效性
  • 不需要对数据进行特定的预处理（如标准化）。
  • 通过多棵树的投票或平均，大幅度减少了单棵树的过拟合。

流程

• 训练阶段（80%）：
  • 从训练数据集中通过Bootstrap采样生成多个样本子集。
  • 对每个样本子集，训练一棵决策树。分裂时随机选择部分特征进行最佳分割。
• 预测阶段（20%）：
  • 对分类任务：让每棵树投票，选择最多的类别作为最终输出。
  • 对回归任务：取所有树的预测值平均作为最终输出。

实战

在2024认证杯c题的第三问，它让我们预测出最可能新挖掘出遗址的地点（我们假设它说的遗址仅指铁器文明的遗址，不然我就不会了），我们将这些region，data，site-type等作为特征变量（id与结果预测没有关系所以把这项去掉），然后将period-name作为目标变量（如果包含early/middle/late-iron-age则为1，否则为0），训练模型后，当我们随机给出特征变量后，让它结合各个变量进行投票，最终投票出结果为1的概率值，由于题目想让我们找出这些地点，而不是问某个地点的概率，所以我们批量随机生成地点组合，再加上随机生成的其他特征，并从大量的预测结果中挑选出概率排名前列的样本，作为最可能出土新遗址的地点。但是如果你认真看完了上面这段话，就会发现有几个漏洞。

• region，site-type等特征变量是文字而非数字，模型的变量应该是数字，因此采用one-hot编码，将文字变量转换为唯一的二进制数字。
• 随机生成的region下这个city存在吗，随机生成city下这个administraive-division存在吗？因此我先生成了相应Region-city和city-administraive-division的映射。在随机生成的时候通过映射检查合理性。
• 这点不太能通过题目看出来，但是我们发现给定的数据集比例不平衡，样本中目标变量为1的与为0的比例为1:3，有点失衡了，所以我们用了smoteenn方法将样本比例平衡。smote是可以增加为1的比例，enn就是简单的取出噪点而已。

最小生成树(MST)

概念

最小生成树（Minimum Spanning Tree, MST） 是图论中的一个重要概念，适用于加权无向图。它具有两个特性：1.包括图中所有顶点，并且这些顶点之间是连通的；2.边的权重和在所有生成树中最小。

算法

Kruskal

核心思想：按边权值从小到大排序，依次加入树中，直到树包含所有顶点为止。

步骤：

1.所有边按照权值从小到大排序。

2.依次检查每条边，如果加入后不会形成环（并查集检测），则将此边加入生成树。

3.重复以上操作，直到树中包含 n-1 条边。

Prim

核心思想：从任意一个顶点开始，逐步将与当前生成树连接的最小权值的边加入生成树，直到包含所有顶点为止。

步骤：

1.任意选择一个顶点作为起点，加入生成树。

2.找出与当前生成树相连的所有边中权值最小的边，将其对应的顶点加入生成树。

3.重复以上步骤，直到树中包含所有顶点。