EM
EM（Expectation Maximization）算法也叫最大期望算法，是求参数的最大似然估计的一种方法
原理是这样的：假设我们想要评估参数A和参数B，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A
可以考虑首先赋予A某个初值，以此得到B的估值，然后从B的估值出发，重新估计A的取值，这个过程一直持续到收敛为止
EM算法经常用于聚类和机器学习领域中
我们先看一个简单的场景：假设你炒了一份菜，想要把它平均分到两个碟子里，该怎么分？
很少有人用称对菜进行称重，再计算一半的分量进行平分。大部分人的方法是先分一部分到碟子A中，然后再把剩余的分到碟子B中，再来观察碟子A和B里的菜是否一样多，哪个多就匀一些到少的那个碟子里
然后再观察碟子A和B里的是否一样多...整个过程一直重复下去，直到份量不发生变化为止
从这个例子中可以看到三个主要的步骤：初始化参数、观察预期、重新估计
- 首先是先给每个碟子初始化一些菜量，然后再观察预期，这两个步骤实际上就是期望步骤（Expectation）
- 如果结果存在偏差就需要重新估计参数，这个就是最大化步骤（Maximization）。这两个步骤加起来也就是EM算法的过程
EM算法的工作原理
说到EM算法，我们先来看一个概念“最大似然”，英文是Maximum Likelihood，Likelihood代表可能性，所以最大似然也就是最大可能性的意思
什么是最大似然呢？举个例子，有一男一女两个同学，现在要对他俩进行身高的比较，谁会更高呢？根据我们的经验，相同年龄下男性的平均身高比女性的高一些，所以男同学高的可能性会很大。这里运用的就是最大似然的概念
最大似然估计是什么呢？它指的就是一件事情已经发生了，然后反推更有可能是什么因素造成的。还是用一男一女比较身高为例，假设有一个人比另一个人高，反推他可能是男性。最大似然估计是一种通过已知结果，估计参数的方法
那么EM算法是什么？它和最大似然估计又有什么关系呢？EM算法是一种求解最大似然估计的方法，通过观测样本，来找出样本的模型参数
回到分菜的例子，实际上最终我们想要的是碟子A和碟子B中菜的份量，可以把它们理解为想要求得的模型参数。然后我们通过EM算法中的E步来进行观察，然后通过M步来进行调整A和B的参数，最后让碟子A和碟子B的参数不再发生变化为止
实际我们遇到的问题，比分菜复杂。再举个一个投掷硬币的例子，假设我们有A和B两枚硬币，我们做了5组实验，每组实验投掷10次，然后统计出现正面的次数，实验结果如下：
投掷硬币这个过程中存在隐含的数据，即我们事先并不知道每次投掷的硬币是A还是B。假设我们知道这个隐含的数据，并将它完善，可以得到下面的结果：
我们现在想要求得硬币A和B出现正面次数的概率，可以直接求得：
而实际情况是我不知道每次投掷的硬币是A还是B，那么如何求得硬币A和硬币B出现正面的概率呢？
这里就需要采用EM算法的思想
①.初始化参数。我们假设硬币A和B的正面概率（随机指定）是θA=0.5和θB=0.9
②.计算期望值。假设实验1投掷的是硬币A，那么正面次数为5的概率为：
公式中的C(10,5)代表的是10个里面取5个的组合方式，也就是排列组合公式，0.5的5次方乘以0.5的5次方代表的是其中一次为5次为正面，5次为反面的概率，然后再乘以C(10,5)等于正面次数为5的概率
假设实验1是投掷的硬币B，那么正面次数为5的概率为：
所以实验1更有可能投掷的是硬币A
然后我们对实验2 ~ 5重复上面的计算过程，可以推理出来硬币顺序应该是{A,A,B,B,A}
这个过程实际上是通过假设的参数来估计未知参数，即“每次投掷是哪枚硬币”
③.通过猜测的结果{A,A,B,B,A}来完善初始化的参数θA和θB
然后一直重复第二步和第三步，直到参数不再发生变化
简单总结：EM算法中的E步骤就是通过旧的参数来计算隐藏变量。然后在M步骤中，通过得到的隐藏变量的结果来重新估计参数。直到参数不再发生变化，得到我们想要的结果
EM聚类的工作原理
EM算法最直接的应用就是求参数估计。如果我们把潜在类别当做隐藏变量，样本看做观察值，就可以把聚类问题转化为参数估计问题。这也就是EM聚类的原理
相比于K-Means算法，EM聚类更加灵活，比如下面这两种情况，K-Means会得到下面的聚类结果
因为K-Means是通过距离来区分样本之间的差别的，且每个样本在计算的时候只能属于一个分类，称之为是硬聚类算法。而EM聚类在求解的过程中，实际上每个样本都有一定的概率和每个聚类相关，叫做软聚类算法
我们可以把EM算法理解成为是一个框架，在这个框架中可以采用不同的模型来用EM进行求解。常用的EM聚类有GMM高斯混合模型和HMM隐马尔科夫模型。GMM（高斯混合模型）聚类就是EM聚类的一种。比如上面这两个图，可以采用GMM来进行聚类
和K-Means一样，我们事先知道聚类的个数，但是不知道每个样本分别属于哪一类。通常，我们可以假设样本是符合高斯分布的（也就是正态分布）。每个高斯分布都属于这个模型的组成部分（component），要分成K类就相当于是K个组成部分
这样我们可以先初始化每个组成部分的高斯分布的参数，然后再看来每个样本是属于哪个组成部分。这也就是E步骤
再通过得到的这些隐含变量结果，反过来求每个组成部分高斯分布的参数，即M步骤。反复EM步骤，直到每个组成部分的高斯分布参数不变为止
这样也就相当于将样本按照GMM模型进行了EM聚类
总结
EM算法相当于一个框架，可以采用不同的模型来进行聚类，比如GMM（高斯混合模型），或者HMM（隐马尔科夫模型）来进行聚类。GMM是通过概率密度来进行聚类，聚成的类符合高斯分布（正态分布）
而HMM用到了马尔可夫过程，在这个过程中，我们通过状态转移矩阵来计算状态转移的概率。HMM在自然语言处理和语音识别领域中有广泛的应用
在EM这个框架中，E步骤相当于是通过初始化的参数来估计隐含变量。M步骤就是通过隐含变量反推来优化参数。最后通过EM步骤的迭代得到模型参数
通过炒菜的例子，可以知道EM算法是一个不断观察和调整的过程
通过求硬币正面概率的例子，可以理解如何通过初始化参数来求隐含数据的过程，以及再通过求得的隐含数据来优化参数
通过GMM图像聚类的例子，可以知道很多K-Means解决不了的问题，EM聚类是可以解决的。在EM框架中，我们将潜在类别当做隐藏变量，样本看做观察值，把聚类问题转化为参数估计问题，最终把样本进行聚类
EM实战
以GMM高斯混合模型为例
from sklearn.mixture import GaussianMixture
'''
n_components：即高斯混合模型的个数，也就是我们要聚类的个数，默认值为1。如果不指定n_components，最终的聚类结果都会为同一个值
covariance_type：代表协方差类型。一个高斯混合模型的分布是由均值向量和协方差矩阵决定的，所以协方差的类型也代表了不同的高斯混合模型的特征。协方差类型有4种取值：
covariance_type=full，代表完全协方差，也就是元素都不为0
covariance_type=tied，代表相同的完全协方差
covariance_type=diag，代表对角协方差，也就是对角不为0，其余为0
covariance_type=spherical，代表球面协方差，非对角为0，对角完全相同，呈现球面的特性
max_iter：代表最大迭代次数，EM算法是由E步和M步迭代求得最终的模型参数，这里可以指定最大迭代次数，默认值为100
'''
gmm = GaussianMixture(n_components=1, covariance_type='full', max_iter=100)
创建完GMM聚类器之后，我们就可以传入数据让它进行迭代拟合
我们使用fit函数，传入样本特征矩阵，模型会自动生成聚类器，然后使用prediction=gmm.predict(data)来对数据进行聚类，传入你想进行聚类的数据，可以得到聚类结果prediction
拟合训练和预测可以传入相同的特征矩阵，这是因为聚类是无监督学习，不需要事先指定聚类的结果，也无法基于先验的结果经验来进行学习
只要在训练过程中传入特征值矩阵，机器就会按照特征值矩阵生成聚类器，然后就可以使用这个聚类器进行聚类了
使用EM算法对王者荣耀数据进行聚类
首先我们知道聚类的原理是“人以群分，物以类聚”。通过聚类算法把特征值相近的数据归为一类，不同类之间的差异较大，这样就可以对原始数据进行降维
通过分成几个组（簇），来研究每个组之间的特性。或者我们也可以把组（簇）的数量适当提升，这样就可以找到可以互相替换的英雄，比如你的对手选择了你擅长的英雄之后，你可以选择另一个英雄作为备选
我们收集了69名英雄的20个特征属性，这些属性分别是最大生命、生命成长、初始生命、最大法力、法力成长、初始法力、最高物攻、物攻成长、初始物攻、最大物防、物防成长、初始物防、最大每5秒回血、每5秒回血成长、初始每5秒回血、最大每5秒回蓝、每5秒回蓝成长、初始每5秒回蓝、最大攻速和攻击范围等
现在我们需要对王者荣耀的英雄数据进行聚类，我们先设定项目的执行流程：
- 首先我们需要加载数据源
- 在准备阶段，我们需要对数据进行探索，包括采用数据可视化技术，让我们对英雄属性以及这些属性之间的关系理解更加深刻，然后对数据质量进行评估，是否进行数据清洗，最后进行特征选择方便后续的聚类算法
- 聚类阶段：选择适合的聚类模型，这里我们采用GMM高斯混合模型进行聚类，并输出聚类结果，对结果进行分析
完整代码如下：
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.mixture import GaussianMixture
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import calinski_harabasz_score
data = pd.read_csv('./heros.csv', encoding='gb18030')
features = ['最大生命', '生命成长', '初始生命', '最大法力', '法力成长', '初始法力', '最高物攻', '物攻成长', '初始物攻', '最大物防', '物防成长', '初始物防', '最大每5秒回血',
'每5秒回血成长', '初始每5秒回血', '最大每5秒回蓝', '每5秒回蓝成长', '初始每5秒回蓝', '最大攻速', '攻击范围']
# 中文会乱码，随便翻译下
data_features = data[features].rename(columns={
'最大生命': 'max_hp',
'生命成长': 'grown_hp',
'初始生命': 'init_hp',
'最大法力': 'max_sp',
'法力成长': 'grown_sp',
'初始法力': 'init_sp',
'最高物攻': 'max_atk',
'物攻成长': 'grown_atk',
'初始物攻': 'init_atk',
'最大物防': 'max_def',
'物防成长': 'grown_def',
'初始物防': 'init_def',
'最大每5秒回血': 'max_repair_hp',
'每5秒回血成长': 'grown_repair_hp',
'初始每5秒回血': 'init_repair_hp',
'最大每5秒回蓝': 'max_repair_sp',
'每5秒回蓝成长': 'grown_repair_sp',
'初始每5秒回蓝': 'init_repair_sp',
'最大攻速': 'max_atk_speed',
'攻击范围': 'max_atk_distance'
})
# 对英雄属性之间的关系进行可视化分析
# 用热力图呈现features_mean字段之间的相关性
corr = data_features.corr()
plt.figure(figsize=(14, 14))
# annot=True显示每个方格的数据
sns.heatmap(corr, annot=True)
plt.show()
# 相关性大的属性保留一个，因此可以对属性进行降维
features = ['最大生命', '最大法力', '最高物攻', '最大物防', '最大每5秒回血', '最大每5秒回蓝', '最大攻速', '攻击范围']
data_features = data[features].copy()
data_features['最大攻速'] = data_features['最大攻速'].apply(lambda x: float(x.strip('%')) / 100)
data_features['攻击范围'] = data_features['攻击范围'].map({'远程': 1, '近战': 0})
# 采用Z-Score规范化数据，保证每个特征维度的数据均值为0，方差为1
ss = StandardScaler()
data_features = ss.fit_transform(data_features)
# 构造GMM聚类
gmm = GaussianMixture(n_components=30, covariance_type='full')
gmm.fit(data_features)
# 训练数据
prediction = gmm.predict(data_features)
# 评估聚类结果
print(calinski_harabasz_score(data_features, prediction))
# 将分组结果输出到excel文件中
data.insert(0, '分组', prediction)
data.to_excel('./hero_out.xlsx', index=False)
我们将20个英雄属性之间的关系用热力图呈现了出来，中间的数字代表两个属性之间的关系系数，最大值为1，代表完全正相关，关系系数越大代表相关性越大
从图中可以看出“最大生命”、“生命成长”和“初始生命”这三个属性的相关性大，我们只需要保留一个属性即可
同理我们也可以对其他相关性大的属性进行筛选，保留一个。用features_remain数组保留了特征选择的属性，这样就将原本的20个属性降维到了13个属性
“最大攻速”这个属性值是百分数，不适合做矩阵运算，因此我们需要将百分数转化为小数
“攻击范围”这个字段的取值为远程或者近战，也不适合矩阵运算，我们将取值做个映射，用1代表远程，0代表近战。然后采用Z-Score规范化，对特征矩阵进行规范化
聚类结果会输出到文件hero_out.csv中
第一列代表的是分组（簇），我们能看到张飞、程咬金分到了一组，牛魔、白起是一组，老夫子自己是一组，达摩、典韦是一组，聚类的特点是相同类别之间的属性值相近，不同类别的属性值差异大
因此如果你擅长用达摩这个英雄，不妨试试典韦这个英雄。同样你也可以在张飞和程咬金中进行切换。这样就算你的英雄被别人选中了，你依然可以有备选的英雄可以使用
评估
聚类和分类不一样，聚类是无监督的学习方式，也就是我们没有实际的结果可以进行比对，所以聚类的结果评估不像分类准确率一样直观，那么有没有聚类结果的评估方式呢？这里我们可以采用Calinski-Harabaz指标，代码如下：
from sklearn.metrics import calinski_harabasz_score
print(calinski_harabasz_score(data, prediction))
指标分数越高，代表聚类效果越好，也就是相同类中的差异性小，不同类之间的差异性大。当然具体聚类的结果含义，我们需要人工来分析，也就是当这些数据被分成不同的类别之后，具体每个类表代表的含义
另外聚类算法也可以作为其他数据挖掘算法的预处理阶段，这样我们就可以将数据进行降维了
实战总结
