聚类
定义
把数据集分成若干个互不相交的簇(一坨数据集)，使簇间相似度尽量的小，簇内相似度尽量的大
性能度量
外部指标
- 将聚类结果和某个参考模型进行比较
与外部模型的比较
假设样本在聚类中是ai，在模型中是bi
指标
Jaccard系数
FM指数
Rand指数
上述指标都是越大越好
内部指标
- 不使用参考模型将聚类结果进行比较
内部比较
是簇的中心点
指数
DB指数，简称DBI
Dunn指数，简称DI
DBI越小越好，DI越大越好
距离度量
对于有序属性—连续值
各种距离
对于无序属性—离散值
VDM(Value Difference Metric)
表示在属性u上取值为a的样本数
表示在第i个样本簇中在属性u上取值为a 的样本数
- k为簇数
则属性u上两个离散值a与b之间的VDM距离为
上面的两者结合可以处理混合属性
原型聚类
- 基于原型的聚类方法，假设聚类结构能通过一组原型进行刻画。
- 算法先对原型进行初始化，然后不断的迭代更新…
k-均值聚类
- 目的是最小化平方误差
是簇i的均值向量
由于这是一个NP难问题，所以我们用贪心的方式解决
- 1、随机初始化均值向量
- 2、根据均值向量分类
- 3、重新分配每个样本所属哪个簇
- 4、更新均值向量
- 5、重复上面的三个过程
def kMeansCluster(self):
dataSet = self.dataSet
K = self.K
bz = 1; n, m = dataSet.shape
self.dataBe = mat(zeros((n,1)))
while bz:
bz = 0
for i in range(n):
minn, minx = self.findMin(dataSet[i])
if (minx != self.dataBe[i]): bz = 1
self.dataBe[i] = minx
for i in range(K):
datK = dataSet[nonzero(self.dataBe[:, 0] == i)[0]]
if (datK.shape[0] == 0): continue
self.cen[i, :] = mean(datK, axis=0)
for i in range(K):
labK = []
for j in range(n):
if (self.dataBe[j, 0] == i): labK.append(self.labelSet[j])
self.cenbz.append(self.majority(labK))
DBSCAN
优点：不需要知道簇的数量
缺点：要确定距离r和minPoints
- 1、先确定距离r和minPoins：
- 从未访问过的点（没有被），半径r中点的数量是否大于或等于或小于minPoints来分类
- 大于或等于：central point，并建立一个类，把能从核点到核点围起来的所有点归为一类
- 小于：noise point
- 2、重复1步骤，直至所有的点均能被归类
学习向量量化(LVQ)
- 与k-均值分类的原理类似，也是最小化平方误差，但是它是已知各个样本的标签的。
- 假设每个样本的特征是向量x，标记是y，
，簇的个数是q
- 目标：我们试图对每个簇搞出一个向量，向量的长度与特征数是一样的，同时也有一个簇标记t
流程
- 1、初始化每个向量的类别标记，
，和每个向量的值，还有学习率
- 2、直到满足条件则停止(收敛,更新到小于阈值)
- 1、从样本中随机选取一些样本
- 2、计算这些样本与每个簇向量的距离
- 3、找出对于每个样本x最近的簇向量i
- a、假如样本x的标签和簇向量i的标签是一样的----->则我们希望他们更近
- b、假如样本x的标签和簇向量i的标签不一样---->则我们希望他们更远
- 更远和更近:向量
高斯混合聚类
定义
就是有很多个高斯分布搞在一起，然后要把他划分出来
例：假如有一组升高数据，不知道性别，然后拿一个数据出来问你性别的概率
答：假设是由两个高斯分布混合在一起的，高斯混合聚类可解
一维高斯分布到n维的高斯分布
一维：
~
多维：
~
，
- 高维就是把方差(一维相关性)转化成协方差矩阵(多维相关性)，所以我们只用考虑一维如何求解就能推到到多维
显然，我们假设已经知道了一个概率模型，我们需要知道系数----->极大似然估计
- 不过问题是，我们在对数似然估计后的求导难以求出解，因为它会有一些不知道的变量------>EM算法
EM算法在高斯混合模型上的应用
一维的高斯混合分模型如下
K是簇的个数,是第k个簇的高斯分布模型，
(≥0)是第k个簇的系数满足
，就是划分系数
一、明确隐变量，写出完全数据的对数似然函数
我们现在有k个簇，那么就有k个标签了
由于我们不知道每个样本属于哪个标签，所以我们定义，g不是0就是1，且
那么现在的概率模型为,一下的的定义为是0还是1，这样就能作为次幂乘起来
所以完全数的对数似然函数为
二、EM算法的E步：确实Q函数
把期望函数带入和隐函数相关的变量中
由于现在g的值还没有确定，所以我们要确定了g的值才能确定g函数
- 由上式g的函数被转化成g的期望
上下同时乘，转化乘联合概率
（完全数据的概率）
我们通过对g的期望计算g，然后确定出Q函数
- EM算法在确定Q函数的时候大致如此，用隐函数的最大期望来得到
三、EM算法的M步：极大化Q函数
我们在确定出Q函数的时候，就能求极值了，如果不能直接求极值,可以用梯度下降或牛顿迭代来求
对于每个变量偏导使其等于0
高斯分布一维的情况
是用拉格朗日乘数法推出来的
重复以上步骤直到收敛
收敛条件，由于Q的值与有关系，当
的变化小于阈值时，则收敛
PCA降维
要分散
- 对于一组二维的数据点，我们要投影到一维的话，那么最后的方式就是找到一条直线，使得这些点在直线上的投影尽量的分散。
- 而要分散，就是可以数值化为方差尽量的大
协方差矩阵
- 协方差所表示的是两个向量的同步程度。
- 而协方差矩阵也有类似的作用。协方差矩阵的所表示的超空间的凸起的地方就是最同步的地方，而我们沿着折最同步的地方垂直分解就能造成所谓的尽量的离散。
矩阵的特征向量
- 特征向量的性质就是，特征向量一直点乘矩阵，最后总是在特征向量的方向做变换。
- 意义上就相当于这个矩阵所表示的坐标系的最伸长的地方，特征值就相当于这个度
步骤
- 1、求解所有数据的协方差矩阵
- 2、然后根据这个协方差矩阵求解他们的特征向量和特征值
- 3、然后根据得到的特征值从大到小排序，将排序后的特征向量拼接成一个转移矩阵
- 4、然后整个数据点乘这个转移矩阵，得到投影后的矩阵
- 5、计算最适宜的分解维度，计算每一维的总方差，然后如果前k维的总方差大于一个阈值threshVal 的话，那么这个k就是最适宜分解的维度，一般threshVal可以设置在0.9左右