数据挖掘十大经典算法笔记
重点梳理数据挖掘领域的十大经典算法，并对每个算法的优缺点进行详细阐述。这些算法在不同应用场景下表现各异。作为学习者的你可能会对此感到困惑：它们之间有什么区别？如何选择最适合自己的方法？为此我们整理出一份简明扼要的笔记供参考使用。
数据挖掘主要包含分类算法、聚类算法和关联规则三大大类, 这三大大类基本涵盖当前商业市场对各类各类算法的需求需求. 而这三大大类中又包含了众多经典的算子, 采用通俗易懂的语言来介绍数据挖掘十大经典算子的原理.
算法分类
连接分析：PageRank
关联分析：Apriori
分类算法：C4.5，CART，朴素贝叶斯，SVM，KNN，Adaboost
该文所探讨的聚类方法包括K-Means和Expectation-Maximization（EM）算法。通过使用conda manage channels命令，在本地镜像仓库中加入该镜像源。
该文所探讨的聚类方法包括K-Means和Expectation-Maximization（EM）算法。通过使用conda manage channels命令，在本地镜像仓库中加入该镜像源。
一、PageRank
以网页之间的超链接个数和质量作为主要因素分析网页的重要性
Pagerank核心思想，顺带了解两个基础概念（入链、出链）：
1、当一个网页受到大量其他页面的链接（入链）时，这表明该网页具有重要性；其PageRank值也会显著提升；
2、若拥有较高PageRank值的页面指向另一个页面（出链），则该目标页面的PageRank值将会得到显著提升。
原理：
网页影响力=阻尼影响力+所有入链页面的加权影响力之和
- 一个网页的权重：所有指向该网页的其他页面的重要性的加权总和。
- 一个网页对其他网页的影响分配：将其自身的权重值按照出链数量平均分配给所连接的其他网页。
- 阻尼权重：无法基于其来源页面的影响程度进行计算的一种特殊权重分布方式，在算法中引入阻尼系数来进行调整
damping coefficient q 是由特定情况决定的；它表示在任何时刻内，用户访问某一页面后继续向下浏览的概率；而 1−q=0.15 表示用户停止点击并随机跳转到新URL的概率。
类似的思路衍生出TextRank算法及其基于词频-逆文档频率模型。
其中, TF值计算公式为:某关键词在给定文章中的出现次数除以文章总词数。
其计算公式为:取语料库总文档数除以包含该关键词的文档数加一后的对数值。
从理论层面来看,在信息检索和文本分类任务中,TF-IDF方法的核心思想是通过衡量词汇的重要程度来优化搜索结果的相关性。具体而言,在同一份文件中某一关键词重复出现的程度越高(即其 TF 值越大),则其重要性越显著;而若该关键词普遍存在于大量不同的文件中(即其 IDI 值较小),则其独特的识别能力越强。
二、Apriori（关联分析）
最有影响的挖掘数据的关联规则，频繁项集的算法。（啤酒尿布例子）
频繁项集：经常一起出现的物品的集合
关联规则：两种物品之间可能存在很强的关系
原理：
1、支持度
某个物品组合（项集）出现的次数与总次数之间的比例
2、置信度
A发生的情况下B发生的概率是多少
3、提升度
衡量物品A的出现，对物品B的出现概率提升的程度
提升度(A>B) = 置信度(A>B) / 支持度(B)
提升度>1，有提升；提升度=1，无变化；提升度<1，下降
三、C4.5 属于分类决策树模型，在其核心技术源于ID3算法的基础上，在继承ID3算法优势的基础上，并在多个关键领域实现了显著的优化和改进。C4.5作为一种改进型决策树学习算法，在分类性能上相较于经典的ID3算法表现出更强的优势，并且在处理缺失值以及类别不平衡等方面也做出了相应的优化处理机制。
改进了基于信息增益选择属性时存在偏向取值多的问题；转而采用信息增益率作为选择标准；其中的信息增益率由 增益度量 与 分裂 信 息 度 量 共 同 定 义 。
- 采用剪枝方法优化树结构；
- 通过离散化技术将连续属性转化为离散形式；
- 针对缺失数据实施有效处理策略。
四、CART
Classification And Regression Tree（CART）是一种强大的机器学习算法，在既可以用于构建分类树模型也可以用于构建回归树模型方面具有显著的应用价值
分类树 ：处理分立数据（即数据种类有限的数据），其输出结果为样本所属的不同类别。例如：通过分类树模型可以判断明天的天气情况（阴、晴、雨）。
回归树 ：能够用于对连续变量进行预测（即数值在某个区间内都有可能取值），其输出结果是一个具体的数值。例如：利用回归树模型可以估计明天气温的具体数值。
CART是一棵二叉树
当CART是一种分类树时，则类似于C4.5算法，并且使用基尼指数来划分内部节点。
CART在构造分类树的时候会选择基尼系数最小的属性作为属性的划分。
基尼系数是衡量样本不确定度的标准。数值越低，则表明各样本之间的相似程度较高；同时其不确定性也较小。
当CART是回归树时，采用样本的最小方差值作为节点分裂的依据
五、SVM
为了在区分样本点的同时特意致力于保证边界样本点与分类器之间的距离被最大化，并使类别之间的间隔被扩大以实现更加容易的分类目标
原理
识别间距最小的样本点集合，并构建一条线段或平面到这些样本点总距离最大。
硬间隔：数据是线性分布的情况，直接给出分类。
软间隔：设置容错率，允许一定量的样本分类错误。
核函数：非线性分布的数据映射为线性分布的数据。
六、KNN
通过测量不同特征值之间的距离来进行分类（监督学习）
原理
计算待分类物与各物体之间的距离，在K个最近邻中出现频率最高的类别将其归类为此类
计算步骤
1、根据场景，定义空间（欧式空间）和选取距离计算方式
2、计算待分类物体与其他物体之间的距离。
3、统计距离最近的K个邻居。
4、找到K个最近的邻居，所占数量最多的类别，预测为该分类对象的类别。
缺点：1、在样本分布失衡的情况下（其中一类样本数量显著多于其他类别），例如一个类别的训练样例数量与其余类别相比差距悬殊，则可能导致分类器在处理新的测试样例时出现偏差；2、在进行分类任务时计算开销较大（即需要遍历所有已知训练数据集中的样本点），从而难以保证高效性；3、这种模型难以用直观的方式解释结果（即无法像传统的决策树模型那样提供明确的规则说明）
七、AdaBoost
原理：
用多个弱分类器训练成一个强分类器
将一系列的弱分类器以不同的权重比组合作为最终分类选择
计算过程
对于初始化训练数据中的每个样本来说，在其权值分布上均被赋予相同的权重；具体而言，在存在N个样本的情况下，每一个训练样本在初始阶段都会被赋予1/N的权重。
在训练阶段中进行弱分类器的训练。当某个样本已经被正确分类时，在后续构建新的训练集中该样本的权重会被降低；相反地，在未被正确分类的情况下该样本点的权重将会增加。同时计算出该弱分类器相应的权重值。随后将更新后的权值分配给新的样本集以用于训练下一个分类器，在此过程中不断重复这个过程直至达到预先设定的弱分类器数目为止
将各次训练所得出的弱判别式组合成为强判别式。各次训练后的弱判别式在集成后的判别函数中占据主导地位与否取决于其误分率高低：误分率较低的一类弱判别式，在集成后的判别函数中占据主导地位；而误分率较高的类则占据次要地位。换言之，在集成后的模型中权重较大的那一类弱判断单元对应的是那些误分率较低的数据类别。
八、朴素贝叶斯
朴素贝叶斯的朴素在于其基于特征之间的相互独立性假设（例如：身高、收入、教育水平）。
朴素贝叶斯原理：基于一定的先验概率推导出Y变量属于某特定类别的后验概率
P(A)：先验概率，即在B事件发生之前，对A事件概率的一个判断。
P(B|A)表示事件B在事件A已经发生的情况下发生的条件几率
P(A|B)：后验概率，即在B事件发生之后，对A事件概率的重新评估
P(A|B) = P(B|A) P(A) / P(B)
举个例子来说，在统计学中有时候会遇到这样的情况：我们先观察到某个现象（比如瓜蒂脱落），然后想要了解在该现象发生的条件下另一个事件（比如瓜是否成熟）的概率。具体来说，在统计学中有时候会遇到这样的情况：我们先观察到某个现象（比如瓜蒂脱落），然后想要了解在该现象发生的条件下另一个事件（比如瓜是否成熟）的概率。这时候我们已经计算出具体数值为P(瓜熟 | 瓜蒂脱落)，这个值被称为后验概率；也就是当我们知道某个结果发生时（如看到掉下的瓜蒂），想知道这个结果发生的原因可能是什么（比如判断瓜是否成熟）。那么反过来想，在知道原因（如知道瓜是成熟的）的情况下观察结果（判断瓜蒂是否会脱落）的概率是多少呢？
P(瓜熟|瓜蒂脱落)=P(瓜蒂脱落|瓜熟) P(瓜熟) / P(瓜蒂脱落)
九、K-Means
属于聚类分析方法的一种算法，在实际应用中常用于将有限数量的样本按照其特征划分为若干个互不重叠的子群体（其中k值小于样本总数）。该方法具有类似的优化目标与Expectation-Maximization算法相似之处，在尝试识别数据集中的自然聚集中心时发挥重要作用。其基本假设是样本的特征值服从某种空间向量分布模式，并通过最小化各簇内样本点与其所在簇质心之间距离平方和的方式来实现对数据的空间划分（无监督学习）
原理：
- 随机选择K个样本作为质心的代表点
- 对于数据集中的每一个样本点，在计算其与各个质心的距离值后，并将其归类到距离最近的那个聚类体中
- 重新计算并确定新的质心位置作为聚类的中心点
- 反复执行上述分类和质心更新的过程直至聚类中心不再发生变化的状态
优点：unsupervised learning无需人工标注数据
缺点：1、相比有监督学习而言，在性能上略逊一筹；2、k值的选取对分类效果具有显著影响；3、对样本分布的变化也较为敏感
十、EM
极大似然估计
为了探究我们学校学生身高的分布情况，请问有什么样的研究计划呢？为此，请您详细说明一下您的研究方法与预期目标。需要注意的是，在运用极大似然估计算法时，默认必须假定数据总体服从某种特定的概率分布；如果数据总体的概率分布在事前是未知的，则无法进行极大似然估计算法的应用。也就是说，在这种情况下，请您考虑其他适用于分析非参数型概率模型的方法或者算法选择策略等建议。其中该概率分布在事前的真实均值\mu与方差\sigma^2均为未知数；通过合理的方法估算出这两个参数\mu和\sigma^2后即可完成对身高的全面分析。那么请问您是如何计划去获得这些参数的具体数值结果呢？
前提条件存在哪些问题？
问题一：从这些学生中随机抽取200人的概率是多少？
各个样本之间相互独立抽取无关联性，在这种情况下所有被抽取学生的联合概率等于每位学生被抽中的概率相乘的结果
这里为什么要取对数？
1、取对数之后累积变为累和，求导更加方便
2、概率累积会出现数值非常小的情况，比如1e-30，由于计算机的精度是有限的，无法识别这一类数据，取对数之后，更易于计算机的识别(1e-30以10为底取对数后便得到-30)。
问题二：学校那么多学生，为什么就恰好抽到了这 200 个人 ( 身高) 呢？
问题三：那么怎么极大似然函数？
极大似然估计总结： 可以将其视为一种反向推理的方法。已知观察到的结果为y的情况下, 极大似然估计通过寻找能够使这一结果出现概率最大化的θ值, 从而作为参数θ的估计值进行求解。
假设我们不知道该校男女比例，在街上随机遇见了100人（样本），其中统计显示有90位是男性（结果）。根据这些数据结果（观察数据），我们可以推断出该学校最可能的比例是9:1（概率模型），这正是极大似然估计的基本原理
最大似然估计法是一种将概率论与统计学相结合应用的具体方法，在参数估计领域具有重要地位。基于已知随机样本的概率分布模型这一前提假设下，在具体应用中我们通常无法确切掌握其具体参数数值的情况。通过多次试验数据收集并系统地分析观察结果作为依据这一过程，则能够较为合理地推断出未知参数的大致取值范围
基于这一核心思想：已知某参数能够使该样本发生的概率达到最大值，则自然不会考虑其他低概率的样本；因此我们直接将该参数视为估计的真实值。
求极大似然函数估计值的一般步骤：
（1）写出似然函数；
（2）对似然函数取对数，并整理；
（3）求导数，令导数为 0，得到似然方程；
（4）解似然方程，得到的参数。
最大似然方法的应用
第一类应用：在回归问题中进行最小二乘法求解（最小化损失函数）
最小二乘估计：最佳的参数估计量能够使模型理想地契合样本数据；即其预测值与实际观测值之间的残差平方和达到最小
求解方法是通过梯度下降算法，训练数据不断迭代得到最终的值。
最大可能的方法：最优参数估计量应当使抽取m组样本观测数据的概率达到最大；即意味着对应的似然函数取得最大值；这也就意味着最大似然估计与最小化损失函数的方法实质上是相同的。
此时能够观察到的是，在这种情况下最大化的似然函数与最初采用最小二乘法所得到的结果之间具有相同性。然而需要注意的是，并非这两者之间仅存在表面的相似性；实际上其原理与基本思路存在本质差异
在应用二中，在分类问题中对应于最小化交叉熵损失（即最小化代价函数），其本质即是最大化似然函数。
另外开设一篇博客文章探讨《最大似然估计与最小化交叉熵损失函数或Kullback-Leibler散度之间的关系为何存在》，这是一个非常有趣的学术话题
EM算法
为解决这一问题升级模型，在原有假设基础上进一步细化：假设全体学生的身高服从一种正态分布已显不够精细；而更为贴近实际情况的做法是将男生和女生分别假定为各自独立的正态分布群体；那么在这种前提下如何评估整体学生的身高分布呢？
(注意：EM算法的应用基础在于对数据总体的分布做出假设；当数据的总体分布未知时，则无法应用该算法。)。
方案如下：从总体中随机选取了100名男性与100名女性，并将他们分别代入最大似然估计模型中进行计算；然而我们的目标是为了推断全体学生的身高是否服从正态分布；因此需要从整个群体中进行系统性的抽样；这样导致我们无法直接判断每个样本来自哪个原始分布。
EM算法主要处理的问题简化为两个核心问题：其一是样本性别分类问题（即判断样本属于男性还是女性），其二是估计不同性别对应的身高均值和方差（即确定每个性别的身高服从怎样的正态分布）。这两个问题在求解过程中具有相互依存的关系：反过来讲，在已知样本的性别信息后（即通过极大似然方法获得了男性和女性身高的概率分布模型），则能推断出该样本更可能是男性还是女性。反过来，在已知不同性别对应的身高参数后，则能推断出该样本更可能是男性还是女性。
这种相互依存的关系形成循环依赖的机制，在解决矛盾的过程中必须突破固有模式才能实现持续不断的改进，在每一次迭代中进行推导分析以获得更加优化的结果最终得出稳定的结果
EM的意思是“Expectation Maximization”，具体方法为：
首先设定男、女大学生身高的初始统计参数。
随后根据每个个体的特征数据计算其所属类别概率。
接下来通过上述方法初步将200名学生划分为男生与女生两个群体。
通过极大似然估计法分别推算出男、女学生身高的均值与标准差（其中前者称为E步）。
随后当更新这两个分布时每个学生的归属概率发生了变化
因此我们需要重新执行E步骤。
如此反复直至算法收敛达到稳定状态
这里是引用
https://zhuanlan.zhihu.com/p/36331115
https://zhuanlan.zhihu.com/p/147307853?utm_source=zhihu&utm_medium=social&utm_oi=43654882263040https://www.bilibili.com/video/BV1iA411e76Y?from=search&seid=2937006232799413669