Zhihao's Blog

聚类

机器学习

聚类

K-means 聚类

k-Means算法是一种聚类算法，它是一种无监督学习算法，目的是将相似的对象归到同一个蔟中。蔟内的对象越相似，聚类的效果就越好。聚类和分类最大的不同在于，分类的目标事先已知，而聚类则不一样。其产生的结果和分类相同，而只是类别没有预先定义。

K-means使各个样本与所在簇的质心的均值的误差平方和达到最小（这也是评价K-means算法最后聚类效果的评价标准）。

复杂度为o(tknm)，t为迭代次数，k为类的个数、n为item个数、m为空间向量特征数。

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

from sklearn.cluster import KMeans
from sklearn import datasets

iris = datasets.load_iris()
X = iris.data
y = iris.target

fig = plt.figure()
ax = Axes3D(fig, rect=[0, 0, .95, 1], elev=48, azim=134)
est = KMeans(n_clusters=3)
est.fit(X)
labels = est.labels_

ax.scatter(X[:, 3], X[:, 0], X[:, 2],
           c=labels.astype(np.float), edgecolor='k')

ax.w_xaxis.set_ticklabels([])
ax.w_yaxis.set_ticklabels([])
ax.w_zaxis.set_ticklabels([])
ax.set_xlabel('Petal width')
ax.set_ylabel('Sepal length')
ax.set_zlabel('Petal length')

fig.show()

优点：

  • 只有一个参数K
  • 容易解释

缺点：

  • K值得确定是玄学(如果预先知道总共有几类会比较简单)
  • 对异常值(噪声和离群值)太敏感

层级聚类(Hierarchical clustering)

  • 自下而上：即最初将每个样本点看做一个类别，然后将最相似的两个样本聚合，不断迭代，直到只有一个类别。
  • 自上而下：即最初将所有样本看做一个类别，然后依据一定规则进行分裂，直到每个样本单独一个类别；这个方法在实际中应用很少。

Hierarchical Clustering最早出自”Johnson, Stephen C. “Hierarchical clustering schemes.” 1967”，步骤如下：

  1. Start by assigning each item to a cluster, so that if you have N items, you now have N clusters, each containing just one item. Let the distances (similarities) between the clusters the same as the distances (similarities) between the items they contain.
  2. Find the closest (most similar) pair of clusters and merge them into a single cluster, so that now you have one cluster less.
  3. Compute distances (similarities) between the new cluster and each of the old clusters.
  4. Repeat steps 2 and 3 until all items are clustered into a single cluster of size N.

其中在步骤3中计算距离，有几种不同的计算方式：

  • single-linkage: 当计算两个cluster之间的距离时，计算这两个cluster中距离最短的两个点的距离
  • complete-linkage: 当计算两个cluster之间的距离时，计算这两个cluster中距离最长的两个点的距离
  • average-linkage: 当计算两个cluster之间的距离时，计算这两个cluster中两两样本点距离的均值
  • median-linkage: 当计算两个cluster之间的距离时，计算这两个cluster中两两样本点距离的中值

谱聚类(Spectral clustering)

谱聚类(Spectral Clustering)是一种基于图论的聚类方法——把所有的数据看做空间中的点，这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，通过对所有数据点组成的图进行切图，让切图后不同的子图间边权重和尽可能的低，而子图内的边权重和尽可能的高，从而达到聚类的目的。

推导：略(逃

谱聚类算法的主要优点有：

  • 谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如 K-Means 很难做到
  • 由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好。

谱聚类算法的主要缺点有：

  • 如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好。
  • 聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同。

sklearn里面SpectralClustering的API比较简单：

SpectralClustering(n_clusters=3, affinity='nearest_neighbors', n_neighbors=5)

GMM clustering

单高斯模型

单高斯分布模型 or 正态分布模型反映了自然界普遍存在的有关变量的一种统计规律，例如身高，考试成绩等；而且有很好的数学性质，具有各阶导数，变量频数分布由μ、σ完全决定等等，在许多领域得到广泛应用。

高斯混合模型

K 个 GSM 混合成一个 GMM，每个 GSM 称为 GMM 的一个 component，也就是分为 K 个类，与 K-means 一样，K 的取值需要事先确定。


Original link：https://izhangzhihao.github.io//2017/11/19/聚类/

Search

    Table of Contents