该笔记基于视频：机器学习升级版VII（讲师：邹博）
概念
之前做LR（Logistic Regression）, SVM（支持向量机）, DT（决策树）, RF（随机森林），都会根据一堆特征值（X），得到分类（y）。
但是如果没有分类（y），只有x，则只能够通过x自身的相似性，分成若干个部分。
我们将这若干个部分，称为“簇”。
比如n个样本，分为k个簇，则我们称其做了k个簇的聚类。
机器学习有监督与无监督
- 有监督
-- 回归 （Regression）
-- 分类（Classification） - 无监督
-- 几乎都是聚类 （Clustering）
使用聚类的例子
-
自然语言处理
-- 语义库（Corpus），构建词典
-- 从具体文档文本，进行比对获得词向量
-- 从而进一步获得词频数据
-- 如果有一个词在当前文档总是重复出现，但是在其他文档不怎么出现，这个词就很重要。
-- 比如萧峰这个词总是在天龙八部出现，但是在其他文档不怎么出现。说明萧峰对天龙八部非常重要。所以需要将萧峰这个词的比重，在天龙八部进行扩大。
-- 进行公式化就是：tf (词的频率)/ idf(在其他文档中的频率取逆(i代表取逆))。这个公式是非常著名的对于词的权重的度量结果。
2018-05-22 18_53_11-【邹博_chinahadoop】机器学习升级版VII（七）.png
-- 如果词库的维度特别高，比如MxV，当V超过一万时，那么把相近的词聚在一堆，从一万个词降维到200个堆中去。
即将Xmxv (v >= 200)降维到Ymx200，所以X -> Y就是一次降维
-- 还可以根据矩阵乘法公式：Xmxv . Cvx200 = Ymx200
-- 其中Xmxv是我们观测到的实际存在的m个文档和词之间的矩阵；Ymx200是最终映射出来，m个文档映射低维度空间当中的一个表现方式；Cvx200,我们认为是如何做的线性的映射。
-- 所以矩阵乘法与降维，无监督学习和聚类之间，都是有一定关系的。
-- 举例: KMeans (K均值聚类)就是矩阵的分解
课堂问答
问：请问“的”是否记为词向量
答：NLP处理中，经常设置stopword，常为助词，语气词等。即停止词，比如的，和，你等。问：聚类的应用在哪块啊？
答：聚类的应用，如果指望聚类做大的应用不太现实。但是用聚类做中间模块，还是靠谱的。
-
预处理聚类
将大类做降采样，一般这里就会使用聚类。
2018-05-22 19_12_00-【邹博_chinahadoop】机器学习升级版VII（七）.png
注意：如何判断数据不平衡？一般来说差一个数量级就是不平衡。
- 后处理聚类
比如推荐系统，已经将用户分类为某种类型，然后再进行聚类。比如高价，中价，低价用户等，然后再根据不同的用户进行不同的营销手段。
但是指望聚类做核心模块，其他算法做辅助，比如PCA, SVM，xgboost，这种可能不太合适。
但是用卷积神经网络，SVM，xgboost做主算法，聚类做辅助算法，是合适的。
问：多音多义词怎么办？
答：比如大理在天龙八部中是国家，但是现在却是代指云南的一座城市。之后会在主题模型中尝试解决这个问题。问：如何分析情感，是不是就不能去某些停用词了？
答：情感分析，还是会去停用词的。问: Xgboost构建的决策树也随机抽出部分数据，随机选择部分变量么？是否可以理解xgboost也利用了随机森林的思想呢？那么能说xgboost是随机森林的改进和升级么？
答：算法并没有鸿沟。其实是有可能会在比如xgboost先做一个特征的降采样，然后再去构建这些决策树。并不排斥算法的综合使用。问：十倍以上就算是差数量级了么？
答：是的，算不平衡数据。问：聚类需要指定个数么？
答：有些需要，有些不需要。问：无监督学习虽然效果不好，如果有突破就给机器学习升级了
答：是的，大部分学术甚至一些工业实践者是很看好无监督学习的。因为大部分数据是没标记的
本次目标
聚类的定义
聚类如何定义相似度：距离可以看成相似度相反的定义。
即相似度越大，距离越小；
相似度越小，距离越大。
最简单的距离计算就是欧式距离
此时距离为x向量与y向量之间的二范式，即它们之间平方和的开方根。即欧式距离
当P等1时，即为一范式，此时我们称A与B之间的距离是街区距离，又名曼哈顿距离
当P为∞时，
如图，仅剩下|xk - yk|
即|AB|p = [|x1 - y1|p + |x2 - y2|p + ... + |xn - yn|p]1/p的值最终化为：|xk - yk|
将上述各个距离公式做总结，统称为闵可夫斯基距离
做相似度，需要定义范数P，即定义为几阶的，往往使用平方，但有时也使用3次方或4次方。表明衰减的快一些。
课堂问答
问：上周刚听了关于距离的数学课，科普了什么拓扑，距离，范数，欧式空间，希尔伯特空间，测度，勒贝格积分什么的。咱们机器学习如果研究的深入了，能用上这些知识么？
答：用不上。我们用的是应用数学还是最基本的应用数学。
问：为什么需要用到无穷大阶的距离呢？
答：只是一种定义方式，我们看看范式如何选择而已
杰卡德相似系数
亦即交并比
往往可以作为相似性的度量
如果A与B完全重合，则交并比为1
如果A与B交集为空，则交并比为0
应用领域：
-
图像识别
2018-05-24 14_41_25-【邹博_chinahadoop】机器学习升级版VII（七）.png - 推荐系统
- 文章相似度
题外话：机器学习中的算法很重要，在众多算法中选择哪一个，更重要
余弦相似度
cosθ = x向量 与 y向量做点乘 / x向量和y向量之间模的方向
通过cosθ来衡量x与y的距离
如果值为1，方向相同，则距离最小，最相似
如果值为0，方向垂直，表示最不相似
如果值为-1，方向相反，相似性最差
对于文档，往往使用余弦相似度用于相似度的衡量
以图搜图的算法，其实本质也是用余弦相似度
Pearson相似系数
X向量: x1, x2, x3, ..., xn，将X认为是随机变量： r.v
可以计算X的均值μx，方差θx
Y向量: y1, y2, y3, ..., yn，将Y认为是随机变量：r.v
也可以计算Y的均值μy，方差θy
于是可以计算X与Y的协方差cov(X, Y)，协方差是:
1/(n-1)Σi=1 to n(xi-μx) * (yi-μy) 得到的。
xi的标准差θx: (1/(n-1)Σi=1 to n(xi-μx) 2)1/2
xi的标准差θy: (1/(n-1)Σi=1 to n(yi-μy) 2)1/2
于是可以计算X与Y的相关系数 = cov(X, Y)/ (θx θy)，即Pearson相似系数
即得到X向量与Y向量之间的一阶线性关系
如果令μx = μy = 0，则:
PXY = Σi=1 to nxi * yi / ((Σi=1 to nxi2)1/2 * (Σi=1 to nyi2)1/2)
即等价于：X与Y的点乘/ X的模*Y的模，即与 夹角余弦 是异曲同工的。它们二者之间是有相关性的。
课堂问答
- 问：Pearson系数是线性关系，如果使用非线性的树模型，那么是不是不能用Pearson系数进行特征选择？
答： 是的。之所以将Pearson系数与余弦相似度一起比较，也是为了说明这个问题。余弦相似度这个算法也不是放之四海而皆准，在文档相关性往往用它，在其他地方用的地方并不多。因为我们认为特征独立了。
相对熵 (K-L距离)
随机变量：
X: (x1,x2, ... , xk)
Y: (y1,y2, ... , yk)
取出不重复的变量，记为：
Dict: (a1,a2, ... , ak)
形成了字典
所以可以获得X中的变量出现的次数统计：
X: a1 a2 a3 ... ak
N: 8 0 3 ... 1 => n
概率P(x):8/n 0 3/n ... 1/n => 1
既然得到概率，则可以求信息熵：
H(X) = -Σi=1 to kPi*lnPi
同理，也可以求Y的信息熵。
由此，我们可以得到X与Y的互信息：
I(X, Y) = H(X) - H(X|Y)
或者
I(X, Y) = H(Y) - H(Y|X)
相对熵相对Pearson相似系数的好处：如果D(p||q) == 0，则p与q一定是独立的。
但是如果Pearson相似系数 = 0, 我们只能说x与y是不相关的。
但是相对熵并不是对称的，p到q的距离与q到p的距离，一般不相同
但是可以通过
W(p||q) = 1/2 (D(p||q) + D(q||p))，得到加权距离，即对称的。
Hellinger距离
即为对称的方式
当α为1的时候，趋近于相对熵
当α为0的时候，满足如下定义：
聚类的基本思想
k-Means算法
目的：将上图绿色的点进行二聚类
即簇的个数为两个
a图：
随机给定两个初值，分别为蓝色与红色
如何处理“随机”？
几种方法：
- 真的是随机取样本
- 根据经验进行初值划分
- kmean++?(没听清楚)
b图：
任何一个样本到这两个随机值中心的距离（一般用欧式距离），距离蓝色近的分类为蓝色，距离红色近的分类为红色
换句话说，两个点之间取垂直平分线，一部分取红色一部分取蓝色。
这就是第一次迭代过程。
c图：
之后蓝色取均值，红色取均值，构成新的蓝、红两个点
d图：
重新做一条垂直平分线，将所有点分成两部分
然后定义为新的蓝色与红色
e图：
之后蓝色取中心，红色取中心，再次构成新的蓝、红两个点
f图：
重新做一条垂直平分线，将所有点分成两部分
然后定义为新的蓝色与红色
g图：
之后蓝色取中心，红色取中心，再次构成新的蓝、红两个点
h图：
重新做一条垂直平分线，将所有点分成两部分
然后定义为新的蓝色与红色
i图：
之后蓝色取中心，红色取中心，再次构成新的蓝、红两个点
此时新的蓝红两个点，与之前两个点的距离没有那么远了
如此，整个过程就结束了
这就是k-均值的过程。
课堂问答
问：k-means不再迭代计算的条件是，i+1次计算的中心与i次计算的中心相等么？
答：k-means不再迭代计算的条件可能有多个，比如说迭代次数、簇的中心不再进行变化，最小平方误差，即MSE
问：还有k-近邻算法呢？
答：k-近邻算法是无参的监督学习算法。
问：有没有不用告诉簇几类，算法自适应聚类？
答：有，比如密度聚类。
问：这里说的平均值，是指什么的值求平均？
答：是指X的值求平均，即样本值取平均
问：初值敏感么？
答：敏感。如图：
问：监督学习可以通过计算特征与Y的相关性进行特征选择，那聚类如何做特征选择呢？
答：如果做聚类特征选择的话，可以尝试做PCA（主成分分析），但是不建议这样做。因为PCA对特征没法解释。因为它会将特征之间进行加权的相乘或相加，使得特征值变得面目全非。所以，除非做中间过程，不用向用户解释特征用的是什么，权值是什么，可以尝试做PCA。
问：k-Means要求数据正态么？
答：要求。
问：样本无标签，如何使用MSE?
答：如图i:
聚类已经分成蓝红两色，对蓝色点而言，均值为圆圈部分的样本，则可以：
1/|蓝色样本个数| * Σ(i=1 to |蓝色样本个数|)(X蓝i - μ蓝i)2
其中μ为均值，则这个值，即为蓝色样本的均方误差，即MSE蓝
同样可以求MSE红
最终可以获得：
MSE = MSE蓝 + MSE红
MSE的值越小越好。
问：k如何选择最优
答：这是个大问题。
如图，假如K是横轴，纵轴是MSE （均方误差），圆圈中是分类的样本，样本共M个。
如果K取1， 表明所有样本取一个簇，就是方差值
如果K取2，表明所有样本取两个簇，MSE会变小了
如果K取3，MSE会变得更小
。。。
如果K取M，则一个样本为一个簇，MSE为0
无监督学习找不到极值点，但是可以根据MSE分成两段，然后取中间部分的K值
理论上K可以这么选，这也称为Elbow-method
但是K值选择需要先验知识。
如性别问题，就是三分类（男性，女性与未知），如果先验搞不定，就可以使用Elbow-method
衍生问题：
- 中心点是一个真实的样本点，还是一个计算值？初始值呢？
答：中心点不一定是真实的，可能是相加得到的 - 拐点不好判断？
答：其实可以根据MSE，然后计算斜率，得到近似拐点。 - 簇中心变化率可以用来作为停止条件么？
答：可以的
对k-Means的思考
可以尝试改造成为k-Mean++这个算法：
选择K个聚类中心，然后做k-Means聚类，即通过做初值的变化，从而称为k-Mean++
先进行聚类划分，如果发现不好，可以再次进行k-Mean聚类
k-Means的公式化解释
其中，Nj代表样本的个数
其实k-Means这个算法，相当于我们认为这些样本是服从混合的高斯分布，即混合高斯模型:GMM是它的理论依据。即我们认为方差相等。
驻点为对使用方差作为的目标函数，做了一次梯度下降。
课堂问答
问：实际应用中，如何将聚类和SVM算法相结合使用呢？
答：例子：如果用SVM对用户做推荐，然后用聚类进行分类营销。
问：SVM的推导为什么不用最大似然估计？
答：因为我们用SVM的时候，是通过另外一种方式给出目标函数了。而目标函数，并不是用可导的函数。
问：如果x变量中存在离散变量或均为离散变量，有方法可以进行聚类么？是否离散变量不适合进行聚类呢？
答：这里离散变量，应该是指类别数据。如有些数据不是天然适合做均值。比如喝了一瓶50度白酒，和一瓶10度啤酒，并不意味着喝了两瓶30度的白酒。因为这个不具有可加性。
如果数据是可排序的，如例2：不及格，及格，优秀，这是可排序的，但是离散的，这种数据可以用k中值聚类然后做聚类。但是用k均值聚类就不行，因为没法加。
提前看一下k-Means聚类方法总结：
k-Means对符合高斯混合分布，效果还是合理的，但如果不是符合高斯混合分布，效果可能就差了。
问： K中值算法是混合拉普拉斯分布么？
答：K中值算法其实就是对应混合拉普拉斯分布
Canopy算法
Canopy算法，做空间索引。好处是不需要指定簇的个数，只需要给定r1与r2即可。
聚类的衡量指标
均一性与完整性：最优值是1，最差值是0
因为均一性与完整性不能同时满足，所以我们用V-measure折中结果
ARI
ARI，本身是混淆矩阵的推广，取1最优，取0最差
AMI
取1最优，取0最差
ARI与AMI共同的缺点：必须知道Y，才能得到这些指标。
但是从逻辑上就说不通，因为我们没有Y，所以做聚类，将数据分为若干簇，但是要得到指标，必须有Y，才能做指标，才能判断好坏。
这怎么用ARI与AMI?
只能先从样本中，人工挑出一部分样本，构成x1到xn，然后人工打标签，构成y1到yn。
之后将x1与xn做聚类，比如k-Means聚类或者密度聚类或者谱聚类等等，得到结果后，然后可以用均一性，完整性，V-measure，判断孰好孰坏。
然后选择一个最优的聚类方式，上到实际当中再去做。
轮廓系数
不需要事先给定Y
层次聚类方法
有两个方法：
- 自上向下的层次聚类
-
自下向上的层次聚类
2018-06-23 17_40_54-【邹博_chinahadoop】机器学习升级版VII（七）.png
重点考虑自下向上的层次聚类，因为这个更适合于我们的一些应用。
因为自顶向下做分裂比较麻烦。
自下向上：如何来对这个聚类的当前的这些值做相似性的定义
即需要判断簇之间的相似性
为什么要这么认真的做簇之间的距离判定呢？
因为需要对簇做合并。
课堂问答
问：带标签的可以用聚类么？
答：可以的，但是没必要。因为已经有标签了。
没标签，可以用PCA
有标签，可以用QDA，LDA，做降维
问：已知某个用户最近一天的微博互动（转评赞），如何预测三天后，五天后的互动呢？
答：属于经典的时间序列的分析。可以用经典的ARIMA（差分整合移动平均自回归模型）时序分析，LSTM, RNN等。
问：不要增长太快是什么意思？
答：控制MSE中心不要太远
