机器学习系列2:算法基础-K-Means

k-means 算法接受参数 k ;然后将事先输入的n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。

聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。 K-means算法是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一。K-means算法的基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果。

   KNN与K-Means对比

KNNK-Means
目的是为了确定一个点的分类目的是为了将一系列点集分成k类
KNN是分类算法K-Means是聚类算法
监督学习,分类目标事先已知非监督学习,将相似数据归到一起从而得到分类,没有外部分类
训练数据集有label,已经是完全正确的数据训练数据集无label,是杂乱无章的,经过聚类后才变得有点顺序,先无序,后有序
没有明显的前期训练过程,属于memory-based learning有明显的前期训练过程
K的含义:“k”是用来计算的相邻数据数。来了一个样本x,要给它分类,即求出它的y,就从数据集中,在x附近找离它最近的K个数据点,这K个数据点,类别c占的个数最多,就把x的label设为cK的含义:“k”是类的数目。K是人工固定好的数字,假设数据集合可以分为K个簇,由于是依靠人工定好,需要一点先验知识
K值确定后每次结果固定K值确定后每次结果可能不同,从 n个数据对象任意选择 k 个对象作为初始聚类中心,随机性对结果影响较大
时间复杂度:O(n)时间复杂度:O(n*k*t),t为迭代次数

 

In [1]:
import numpy as np
import matplotlib.pyplot as plt
from scipy import stats

# use seaborn plotting defaults
import seaborn as sns; sns.set()

简介

K-Means是用于无监督聚类的算法:即,仅基于数据属性(而不是标签)在数据中找到各自的类。
K均值是一个相对容易理解的算法。它搜索作为其中的点的平均值的聚类中心,使得每个点最接近它被分配给的聚类中心。让我们看看KMeans如何在我们之前看过的简单集群上运行。

概述

在scikit-learn中,包括两个K-Means的算法,一个是传统的K-Means算法,对应的类是KMeans。另一个是基于采样的Mini Batch K-       Means算法,对应的类是MiniBatchKMeans。一般来说,使用K-Means的算法调参是比较简单的。
用KMeans类的话,一般要注意的仅仅就是k值的选择,即参数n_clusters;如果是用MiniBatchKMeans的话,也仅仅多了需要注意调参的参数batch_size,即我们的Mini Batch的大小。
当然KMeans类和MiniBatchKMeans类可以选择的参数还有不少,但是大多不需要怎么去调参。下面我们就看看KMeans类和MiniBatchKMeans类的一些主要参数。

Keans类的主要参数

1) n_clusters: 即我们的k值,一般需要多试一些值以获得较好的聚类效果。k值好坏的评估标准在下面会讲。
2)max_iter: 最大的迭代次数,一般如果是凸数据集的话可以不管这个值,如果数据集不是凸的,可能很难收敛,此时可以指定最大的迭代次数让算法可以及时退出循环。
3)n_init:用不同的初始化质心运行算法的次数。由于K-Means是结果受初始值影响的局部最优的迭代算法,因此需要多跑几次以选择一个较好的聚类效果,默认是10,一般不需要改。如果你的k值较大,则可以适当增大这个值。
4)init: 即初始值选择的方式,可以为完全随机选择’random’,优化过的’k-means++’或者自己指定初始化的k个质心。一般建议使用默认的’k-means++’。
5)algorithm:有“auto”, “full” or “elkan”三种选择。”full”就是我们传统的K-Means算法, “elkan”是我们原理篇讲的elkan K-Means算法。默认的”auto”则会根据数据值是否是稀疏的,来决定如何选择”full”和“elkan”。一般数据是稠密的,那么就是 “elkan”,否则就是”full”。一般来说建议直接用默认的”auto”

MiniBatchKMeans类主要参数

1) n_clusters: 即我们的k值,和KMeans类的n_clusters意义一样。
2)max_iter:最大的迭代次数, 和KMeans类的max_iter意义一样。
3)n_init:用不同的初始化质心运行算法的次数。这里和KMeans类意义稍有不同,KMeans类里的n_init是用同样的训练集数据来跑       不同的初始化质心从而运行算法。而MiniBatchKMeans类的n_init则是每次用不一样的采样数据集来跑不同的初始化质心运行算法。
4)batch_size:即用来跑Mini Batch KMeans算法的采样集的大小,默认是100.如果发现数据集的类别较多或者噪音点较多,需要增加这个值以达到较好的聚类效果。
5)init: 即初始值选择的方式,和KMeans类的init意义一样。
6)init_size: 用来做质心初始值候选的样本个数,默认是batch_size的3倍,一般用默认值就可以了。
7)reassignment_ratio: 某个类别质心被重新赋值的最大次数比例,这个和max_iter一样是为了控制算法运行时间的。这个比例是占样本总数的比例,乘以样本总数就得到了每个类别质心可以重新赋值的次数。如果取值较高的话算法收敛时间可能会增加,尤其是那些暂时拥有样本数较少的质心。默认是0.01。如果数据量不是超大的话,比如1w以下,建议使用默认值。如果数据量超过1w,类别又比较多,可能需要适当减少这个比例值。具体要根据训练集来决定。
8)max_no_improvement:即连续多少个Mini Batch没有改善聚类效果的话,就停止算法, 和reassignment_ratio, max_iter一样是为了控制算法运行时间的。默认是10.一般用默认值就足够了。

范例

In [2]:
# 生成数据
from sklearn.datasets.samples_generator import make_blobs
X, y = make_blobs(n_samples=300, centers=4,
                  random_state=0, cluster_std=0.60)
plt.scatter(X[:, 0], X[:, 1], s=50);
/srv/env/lib64/python3.4/site-packages/matplotlib/font_manager.py:1297: UserWarning: findfont: Font family ['sans-serif'] not found. Falling back to DejaVu Sans
  (prop.get_family(), self.defaultFamily[fontext]))

肉眼可见,容易挑出四个类。但是,如果要对数据进行详细的分类,则搜索空间将是点数的指数。幸运的是,有一个众所周知的期望最大化画算法(EM算法)来帮助我们解决问题。

In [3]:
from sklearn.cluster import KMeans
est = KMeans(4)  # 4 clusters
est.fit(X)
y_kmeans = est.predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='rainbow');
/srv/env/lib64/python3.4/site-packages/matplotlib/font_manager.py:1297: UserWarning: findfont: Font family ['sans-serif'] not found. Falling back to DejaVu Sans
  (prop.get_family(), self.defaultFamily[fontext]))

小运用(数字识别)

        对于接近实际的例子,导入一些数字的数据。在这里,我们将使用KMeans自动聚集64个维度的数据,然后查看聚类中心来看看算法找到了什么。

In [6]:
from sklearn.datasets import load_digits
digits = load_digits()
In [7]:
est = KMeans(n_clusters=10)
clusters = est.fit_predict(digits.data)
est.cluster_centers_.shape
Out[7]:
(10, 64)
In [8]:
fig = plt.figure(figsize=(8, 3))
for i in range(10):
    ax = fig.add_subplot(2, 5, 1 + i, xticks=[], yticks=[])
    ax.imshow(est.cluster_centers_[i].reshape((8, 8)), cmap=plt.cm.binary)

我们看到,即使没有标签,KMeans能够找到识别数字的手段

In [9]:
from scipy.stats import mode

labels = np.zeros_like(clusters)
for i in range(10):
    mask = (clusters == i)
    labels[mask] = mode(digits.target[mask])[0]
In [10]:
from sklearn.decomposition import PCA

X = PCA(2).fit_transform(digits.data)

kwargs = dict(cmap = plt.cm.get_cmap('rainbow', 10),
              edgecolor='none', alpha=0.6)
fig, ax = plt.subplots(1, 2, figsize=(8, 4))
ax[0].scatter(X[:, 0], X[:, 1], c=labels, **kwargs)
ax[0].set_title('learned cluster labels')

ax[1].scatter(X[:, 0], X[:, 1], c=digits.target, **kwargs)
ax[1].set_title('true labels');
/srv/env/lib64/python3.4/site-packages/matplotlib/font_manager.py:1297: UserWarning: findfont: Font family ['sans-serif'] not found. Falling back to DejaVu Sans
  (prop.get_family(), self.defaultFamily[fontext]))
In [11]:
from sklearn.metrics import accuracy_score
accuracy_score(digits.target, labels)
Out[11]:
0.79298831385642743
In [12]:
from sklearn.metrics import confusion_matrix
print(confusion_matrix(digits.target, labels))

plt.imshow(confusion_matrix(digits.target, labels),
           cmap='Blues', interpolation='nearest')
plt.colorbar()
plt.grid(False)
plt.ylabel('true')
plt.xlabel('predicted');
[[177   0   0   0   1   0   0   0   0   0]
 [  0  55  24   1   0   1   2   0  99   0]
 [  1   2 148  13   0   0   0   3   8   2]
 [  0   0   0 155   0   2   0   7   7  12]
 [  0   5   0   0 164   0   0   8   4   0]
 [  0   0   0   1   2 136   1   0   0  42]
 [  1   1   0   0   0   0 177   0   2   0]
 [  0   2   0   0   0   1   0 174   2   0]
 [  0   6   3   2   0   6   2   3 100  52]
 [  0  20   0   6   0   7   0   7   1 139]]
/srv/env/lib64/python3.4/site-packages/matplotlib/font_manager.py:1297: UserWarning: findfont: Font family ['sans-serif'] not found. Falling back to DejaVu Sans
  (prop.get_family(), self.defaultFamily[fontext]))

同样,对于一个完全无监督的估计器,能够达到80的精度。

In [ ]:
 

 


机器学习系列目录

1. 机器学习系列1:算法基础-Logistic回归
当前阅读>  2. 机器学习系列2:算法基础-K-Means
3. 机器学习系列3:算法基础-决策树
4. 机器学习系列4:进阶算法-SVM
5. 机器学习系列5:进阶算法-随机森林
6. 数学教学系列6:ARMA模型
7. 数学教学系列7:拉格朗日对偶问题
8. 数学教学系列8:梯度下降法
9. 数学教学系列9:B-S期权定价模型