# 一、理论知识
## 1.1 K-Means
给定一组数据集,聚类算法将它们分成不同的子组。我们希望类内实例高度相似,类间实例低相似。
在样本集中,随机选取K个点作为中心$\bold \mu_k$,计算每个样本到中心点的距离,并将样本划分到离它最近的那个点的集群中。使用变量$r_{nk}$表示数据样本$\bold x^{(n)}$是否属于集群k:
$$
r_{nk}=\left\{\begin{matrix}1,k=arg\min_j||\bold x^{(n)}-\mu_j||^2\\0,otherwise\end{matrix}\right.
$$
对于每个集群,用所有样本的平均位置更新中心点的位置:
$$
\mu_k=\frac{\sum^N_{n=1}r_{nk}\bold x_n}{\sum^N_{n=1}r_{nk}}
$$
重复上面的样本分配和中心更新过程即可,该过程是保证收敛的。类内距离之和会随着K的增大而减小,因此选择K的时候考虑寻找使得距离基本收敛的K值或是依据下游应用需求选择K值。
K平均聚类的结果高度依赖于初始化的中心点。选择初始化中心点的一般方法有:
- 随机选择:随机选择数据样本作为初始中心。问题在于有可能选择了距离很近的多个样本作为初始中心
- 基于距离的方法:一开始随机选一个样本作为中心点,其他时候选择离各个中心最远的样本作为中心点。问题在于可能选到异常值
- 随机+距离方法:第一个中心点为随机选择的样本,从全部远离现有中心的样本中随机选择下一个中心
一个点要么属于一个集群,要么不属于,存在赋值难的问题。可以用软K平均算法解决:
$$
r_{nk}=\frac{e^{-\beta}||\bold x^{(n)}-\mu_k||^2}{\sum^K_{i=1}e^{-\beta}||\bold x^{(n)}-\mu_i||^2}
$$
这样一来,$r_{nk}$可以理解为样本属于某个集群的几率。
该算法还对异常值敏感。而且欧几里得距离决定了决策边界是球形的,当不同簇的形状不规则时,性能可能不佳。
## 1.2 GMM与EM算法
在监督学习中,回归和分类都可以理解为学习的条件概率分布。类似地,从概率建模的角度来看,无监督学习可以理解为对输入数据的概率分布进行学习,最简单的方法是假设该分布为高斯形式。但是一般情况下,样本的分布比高斯分布复杂得多。为了更好地建模,就需要更好的分布表示方法,即使用复杂的分布,但是训练成本又会增加。
因此,一个直观的思路是使用很多简单模型的加和表示复杂模型:
$$
p(\bold x)=\pi_1p_1(\bold x)+\pi_Kp_K(\bold x)
$$
其中,所有$\pi$的和为1,用来使得分布合法。而每个$p_i$表示简单的分布。上面的每一项又可以看作是联合分布的边缘分布:
$$
p_z(\bold x)\pi_z=p(\bold x|z)p(z)=p(\bold x,z)
$$
这种模型被称为潜变量模型LVM。我们将各个分布看做是高斯分布,则该模型又称为高斯混合模型,即GMM。如果一个高斯混合模型由$K$个高斯分布组成,则总的分布表达式为:
$$
p(\bold x)=\sum^K_{k=1}\pi_kN(\bold x;\bold\mu_k,\bold\Sigma_k)
$$
其中,$K$表示高斯分布的个数,$\pi_k$表示第$k$个分布的权重。$\sum^K_{k=1}\pi_k=1$。$\bold \mu_k$和$\bold \Sigma_k$是第$k$个高斯分布的均值向量和协方差矩阵。
EM算法可以学习高斯混合模型的参数,使得该模型在特定的数据集下获得更大的对数似然函数值。算法分为E和M两步。E指评估预期,M指更新数据:
- E-step:$Q(\bold\theta;\bold\theta^{(t)})=E_{p(\bold z|\bold x;\bold\theta^{(t)})}[\log p(\bold x,\bold z;\bold \theta)]$
- M-step:$\bold\theta^{(t+1)}=\arg\max_\bold\theta Q(\bold \theta;\bold\theta^{(t)})$
对于上述的高斯混合模型,在E-step中,可以求得对数似然函数为:
$$
\log p(\bold x,\bold z;\bold \theta)=\sum^K_{k=1}z_k\cdot[\log N(\bold x_n|\bold \mu_k,\bold\Sigma_k)+\log\pi_k]
$$
令:
$$
\gamma_k^{(t)}\triangleq\frac{N(\bold x_n|\bold \mu^{(t)}_k,\bold\Sigma^{(t)}_k)\pi_k}{\sum_{i=1}^KN(\bold x_n|\bold \mu^{(t)}_k,\bold\Sigma^{(t)}_k)\pi_i}
$$
则有:
$$
Q(\bold\theta;\bold\theta^{(t)})=\sum_{k=1}^K\gamma_k^{(t)}[\log N(\bold x_n|\bold \mu_k,\bold\Sigma_k)+\log\pi_k]
$$
然后在M-step更新各个参数:
$$
\bold\mu_k^{(t+1)}=\frac1{N_k}\sum^N_{n=1}\gamma_{nk}\bold x_n\\
\bold\Sigma_l^{(t+1)}=\frac1{N_k}\sum^N_{n=1}\gamma_{nk}(\bold x_n-\mu_n^{(t+1)})(\bold x_n-\mu_n^{(t+1)})^T
\pi_k^{(t+1)}=\frac{N_k}N
$$
其中$N_k=\sum^N_{n=1}\gamma_{nk}$,表示第$k$类的样本的有效数量。反复执行E和M两步训练参数,直至模型收敛或到达最大训练次数即可。
-----------
# 二、代码实现
## 2.1 K-means
在K-means算法中,我们将训练数据集分成若干个聚类,对每个类打上标签后对训练样本进行分类,将属于的类的标签当做预测结果即可。
### 2.1.1 中心点的选择
K平均算法的核心就是中心点的选择和更新。对于本次实验使用的MNIST数据集,样本共有10类,因此聚类时选择10个不同的中心点。初始化中心点有多种方法,我会在之后的实验结果分析中分析不同的初始化方法对结果的影响。
下面的代码以随机选择为例子。在全部样本点中选择十个样本点作为初始化中心:
```python
# 设置基本参数
k = 10 # 类别数
t = 100 # 迭代次数
# 生成初始中心
# 完全随机
center_points = np.random.choice(train_images.shape[0], k, replace = False).tolist()
for i in range(len(center_points)):
center_points[i] = train_images[center_points[i]]
center_points = np.asarray(center_points)
```
同时,我还对基于距离的方法进行了尝试。即,第一个中心点为随机选择的样本点,第二个中心点为离第一个中心点最远的样本点,第三个中心点为距离第一和第二个中心点距离之和最大的样本点,以此类推:
```python
center_points = genCenterPoints(train_images, k)
```
```python
# 基于距离选择中心点
def genCenterPoints(train_images, k):
# 第一个中心点随机选择
center_points = [train_images[random.randint(0,train_images.shape[0]-1)].tolist()]
while len(center_points) != k:
print(len(center_points))
dist = None
point = None
# 遍历每个样本点
for each in train_images:
# 不考虑已经作为中心点的样本点
if each.tolist() in center_points:
continue
# 计算当前样本到各个中心点的距离之和
tmp_dist = np.sum(np.linalg.norm(np.asarray(center_points) - each,axis = 1))
# 选择距离最短的样本点作为下一个中心点
if dist==None or tmp_dist<dist:
point = each
dist = tmp_dist
center_points.append(point.tolist())
return np.asarray(center_points)
```
### 2.1.2 训练过程
之后就是对各个样本点进行分类和中心点的迭代更新:
```python
# 进行迭代
for i in range(t):
# 对训练样本进行分类
r = classification(center_points,train_images, k)
# 更新中心点位置
center_points = updateCenterPoints(r, train_images, k)
```
对样本点进行分类时,使用数组`r[i][j]`表示第`i`个样本是否属于第`j`类。是则为1,否则为0。计算出当前样本和各个中心点之间的距离,选择最近的中心点作为该样本属于的类别即可。这里我调用了`np.linalg.norm`来计算距离,得到的是欧式距离,也就是各个特征值的平方和开根号作为距离。样本距离可以采用不同的标准,会对分类的结果产生不同的影响。
```python
def classification(center_points,train_images, k):
# r[i][j]表示第i个样本是(1)否(0)属于第j类
r = np.zeros((train_images.shape[0],k)).astype(np.int16)
for i in range(train_imag
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
聚类算法是机器学习中涉及对数据进行分组的一种算法。在给定的数据集中,我们可以通过聚类算法将其分成一些不同的组。在理论上,相同的组的数据之间有相同的属性或者是特征,不同组数据之间的属性或者特征相差就会比较大。聚类算法是一种非监督学习算法,并且作为一种常用的数据分析算法在很多领域上得到应用。
资源推荐
资源详情
资源评论
收起资源包目录
100011024-基于Python实现聚类算法.zip (5个子文件)
clusteralgorithm
LICENSE 1KB
README.md 19KB
code
K-Means.py 3KB
GMM.py 4KB
数据集.zip 16.61MB
共 5 条
- 1
资源评论
神仙别闹
- 粉丝: 2678
- 资源: 7667
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功