概念

1.K-Means

　　K-means算法是最为经典的基于划分的聚类方法，算法的目的是使各个样本与所在类均值的误差平方和达到最小（这也是评价K-means算法最后聚类效果的评价标准）。

　　K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。

1 算法流程

　　假设要把样本集分为c个类别，算法描述如下：

1）适当选择c个类的初始中心；
2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类；
3）利用均值等方法更新该类的中心值；
4）对于所有的c个聚类中心，如果利用2）3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。

2 优点

简单，易于理解，易于实现，无需估计参数，无需训练；

3 缺点

不能保证找到定位聚类中心的最佳方案，但是它能保证能收敛到某个解决方案（不会无限迭代）。　　解决方法：多运行几次K-means,每次初始聚类中心点不同，最后选择方差最小的结果。
无法指出使用多少个类别。在同一个数据集中，选择不同初始类别数获得的最终结果是不同的。　　解决方法：首先设类别数为1，然后逐步提高类别数，在每一个类别数都用上述方法，一般情况下，总方差会很快下降，直到到达一个拐点；这意味着再增加一个聚类中心不会显著减少方差，保存此时的聚类数。

2.代价函数（Cost Function）

\[J(c,\mu )=\sum_{i=1}^{m}\begin{Vmatrix} x^{(i)}-\mu _{c}(i) \end{Vmatrix}^{2}\]

　　假设有M个数据源，C个聚类中心。µc为聚类中心。该公式的意思也就是将每个类中的数据与每个聚类中心做差的平方和，J最小，意味着分割的效果最好。

3.最小化J($\theta$)的方法

　　通过遍历查找使J最小的分类方案

4.KNN和K-Means的区别

KNN	K-Means
分类算法	聚类算法
监督学习	非监督学习
喂给它的数据集是带label的数据，已经是完全正确的数据	喂给它的数据集是无label的数据，是杂乱无章的，经过聚类后才变得有点顺序，先无序，后有序
没有明显的前期训练过程，属于memory-based learning	有明显的前期训练过程
K的含义：来了一个样本x，要给它分类，即求出它的y，就从数据集中，在x附近找离它最近的K个数据点，这K个数据点，类别c占的个数最多，就把x的label设为c	K的含义：K是人工固定好的数字，假设数据集合可以分为K个簇，由于是依靠人工定好，需要一点先验知识

　　相似点：都包含这样的过程，给定一个点，在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法，一般用KD树来实现NN。

scikit-learn示例

from time import time
import numpy as np
import matplotlib.pyplot as plt

from sklearn import metrics
from sklearn.cluster import KMeans
from sklearn.datasets import load_digits
from sklearn.decomposition import PCA
from sklearn.preprocessing import scale

np.random.seed(42)#用于初始化聚类中心
"""
digits数据集：1797个样本，每个样本包括8*8像素的图像和一个[0, 9]整数的标签
print digits.keys()
['images', 'data', 'target_names', 'DESCR', 'target']
images:ndarray类型，保存8*8的图像，里面的元素是float64类型，共有1797张图片
data:ndarray类型，将images按行展开成一行，共有1797行
target:ndarray类型，指明每张图片的标签，也就是每张图片代表的数字
target_names:ndarray类型，数据集中所有标签值
DESCR:数据集的描述，作者，数据来源等
"""
digits = load_digits() #载入数据   
data = scale(digits.data) #中心标准化数据 

n_samples, n_features = data.shape #1797，64  
n_digits = len(np.unique(digits.target)) #10，类别数  
labels = digits.target #数据真实标签 

sample_size = 300

print("n_digits: %d, \t n_samples %d, \t n_features %d"
      % (n_digits, n_samples, n_features))


print(82 * '_')
print('init\t\ttime\tinertia\thomo\tcompl\tv-meas\tARI\tAMI\tsilhouette')

#算法评估函数，包括处理时间、最终代价函数值、以及不同的聚类评价指标  
def bench_k_means(estimator, name, data):
    t0 = time()
    estimator.fit(data)
    print('%-9s\t%.2fs\t%i\t%.3f\t%.3f\t%.3f\t%.3f\t%.3f\t%.3f'
          % (name, (time() - t0), estimator.inertia_,
             metrics.homogeneity_score(labels, estimator.labels_),
             metrics.completeness_score(labels, estimator.labels_),
             metrics.v_measure_score(labels, estimator.labels_),
             metrics.adjusted_rand_score(labels, estimator.labels_),
             metrics.adjusted_mutual_info_score(labels,  estimator.labels_),
             metrics.silhouette_score(data, estimator.labels_,
                                      metric='euclidean',
                                      sample_size=sample_size)))
#Kmeans++，随机初始化10次  
bench_k_means(KMeans(init='k-means++', n_clusters=n_digits, n_init=10),
              name="k-means++", data=data)
#Kmeans，随机初始化10次
bench_k_means(KMeans(init='random', n_clusters=n_digits, n_init=10),
              name="random", data=data)

 
#Pca+kmeans，采用如下调用方式聚类中心是确定的，只初始化一次 
pca = PCA(n_components=n_digits).fit(data)
bench_k_means(KMeans(init=pca.components_, n_clusters=n_digits, n_init=1),
              name="PCA-based",
              data=data)
print(82 * '_')

# #############################################################################
# PCA可视化结果
#fit_transform得到是用降维度处理后的数据
reduced_data = PCA(n_components=2).fit_transform(data)
kmeans = KMeans(init='k-means++', n_clusters=n_digits, n_init=10)
kmeans.fit(reduced_data)

#定义网格步长
h = .02     # point in the mesh [x_min, x_max]x[y_min, y_max].

#定义边界坐标，定义网格坐标
x_min, x_max = reduced_data[:, 0].min() - 1, reduced_data[:, 0].max() + 1
y_min, y_max = reduced_data[:, 1].min() - 1, reduced_data[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))

#用训练模型获得网格预测每一点的类值  
Z = kmeans.predict(np.c_[xx.ravel(), yy.ravel()])

#绘制函数 
Z = Z.reshape(xx.shape)
plt.figure(1)
plt.clf()
plt.imshow(Z, interpolation='nearest',
           extent=(xx.min(), xx.max(), yy.min(), yy.max()),
           cmap=plt.cm.Paired,
           aspect='auto', origin='lower')

plt.plot(reduced_data[:, 0], reduced_data[:, 1], 'k.', markersize=2)
# Plot the centroids as a white X
centroids = kmeans.cluster_centers_
plt.scatter(centroids[:, 0], centroids[:, 1],
            marker='x', s=169, linewidths=3,
            color='w', zorder=10)
plt.title('K-means clustering on the digits dataset (PCA-reduced data)\n'
          'Centroids are marked with white cross')
plt.xlim(x_min, x_max)
plt.ylim(y_min, y_max)
plt.xticks(())
plt.yticks(())
plt.show()

n_digits: 10,    n_samples 1797,     n_features 64
__________________________________________________________________________________
init        time    inertia homo    compl   v-meas  ARI AMI silhouette
k-means++   0.27s   69432   0.602   0.650   0.625   0.465   0.598   0.146
random      0.18s   69694   0.669   0.710   0.689   0.553   0.666   0.147
PCA-based   0.03s   70804   0.671   0.698   0.684   0.561   0.668   0.118
__________________________________________________________________________________

png

Python (17)

置顶文章

最新发表

链接

机器学习－K-Means

概念

1.K-Means

2.代价函数（Cost Function）

3.最小化J($\theta$)的方法

4.KNN和K-Means的区别

scikit-learn示例