Q：分类和聚类有什么不同？
两者的区别可以主要从两个方面看出。第一，它们面对的根本问题不同。分类的根本问题是判断给定的某一个样本属于那一个类别；聚类的根本问题是探索给定的数据集可以分成哪几种类别。第二，两者使用的训练数据集有差异。分类任务使用的训练数据集中每个样本除了有属性数据外，还必须有一个标记值，用以表示该样本属于哪一类；聚类任务的数据集中每个样本可以只有属性值，没有标记值（当然也可以有）。这也可以认为是我们常说的，监督学习与无监督学习。
Q：聚类的一般方法有哪些？
聚类算法多种多样，但是万变不离其宗，最基本的思想还是先提出一中衡量样本之间相似程度的的手段，如距离、相关系数等，然后逐一计算数据集中各样本之间的相似度，尽量把相似度高的样本放到同一类。
一般来说聚类算法有三类：基于原型的聚类、基于密度的聚类、和基于层次的聚类。当然，还可以有更多，比如混合高斯模型也能用于聚类任务。
Q：衡量样本间相似度的指标有那些？
所谓样本，其数学本质就是向量。所以样本间的相似度常用距离来表示。
最简单的距离就是内积距离
最直观的距离则是欧氏距离
更一般的距离有明可夫斯基距离，其中p值视情况而定
上面提到的距离都是适用于有序属性的。所谓有序属性，就是指属性的取值有大小之分。比如西瓜的“含糖率”这个属性，0.1就比0.9要小。无序属性这位是指属性取值无大小之分的属性。比如西瓜的“颜色”属性，取“0”表示浅绿、取“1”表示深绿，但不能说0比1小，“颜色”属性的取值不能比较大小。此时，要更亮无序属性的距离要用到VDM距离，即
所以，对于属性中既含有有序属性，又含有无序属性的样本，则需要统一明可夫斯基距离和VDM距离
Q：k-means聚类算法的思路是怎样的？
当我们去考察一堆数据的时候，一般会通过平均数和方差来获取一个大致的了解。也就是说，平均数和方差可以代表一组数据。那么我们就会想，有没有一个均值向量可以代表一组向量？
自然是有的（反正概念什么的都是人定的）。
上式代表类中所有向量的均值向量。
那么，如果有k个均值向量，就代表有k个类。可以分别计算某个向量与这k个均值向量的距离，哪个距离更短，就将该向量（样本）归到哪一类。这便是k-means（k均值）算法的基本思想。
实际的算法过程是一个循环。首先人为设定k值大小，即要划分多少个类。然后第一轮在数据集中随机挑选k个样本作为初始的均值向量，接着计算剩下的样本与这几个均值向量的距离，并且聚类，可以得到k个类别，每个类别至少一个样本。此时重新计算各个类别的均值向量，得到k个新的均值向量。下面重新计算距离，再度分类，再度重新计算均值向量，得到k个新的均值向量，如此循环往复，直到得到的k个均值向量与上一轮的均值向量一样，也就是两轮的聚类结果一样的时候，循环结束。
Q：虽说聚类术语无监督学习，不需要用到样本标记信息，但是既然存在标记信息，可不可以利用一下？
LVQ（学习向量量化）算法就是利用样本标记信息来辅助聚类的算法。LVQ算法利用和k-means的均值向量类似的代表性向量（也可以叫原型向量），同样也使用距离计算然后根据最短距离分类的的思想。不过LVQ算法的目的不是直接得到划分好的几个类，而是得到t个原型向量。也就是说，LVQ的输出是t个原型向量。先上一张抽象的算法流程
LVQ算法同样人为设定一个t值，也就是要划分的类别数。然后初始化t个原型向量——不是像k-means一样随便选，而是根据预先说好了的标记，在随便选。比如预先说好要选3个好瓜，2个坏瓜，就从好瓜中随便选三个，坏瓜中随便选两个。
选好初始原型向量后，开始和k-means一样不断循环计算距离，不过LVQ每次都是随机抽取训练数据集的一个样本，计算抽到的样本和各个原型向量的距离。距离最短的一个原型向量，如果其标记和抽到的标记一样，就“使原型向量向抽到的样本向量靠近”，如果其标记和抽到的标记不同，就“使原型向量向抽到的样本向量远离”——
如此循环往复直到达到最大循环次数，或者原型向量的调整幅度已经小于某个阀值。
Q：有没有不是基于原型向量的聚类算法？
除了基于原型向量的聚类算法，还有基于密度的聚类算法，如DBSCAN，和基于层次的聚类算法，如AGNES。
在了解什么是基于密度的算法前，先参考一下人际社交的生活经验。“物以类聚，人以群分”，人群中会自发地诞生多个人际关系圈子。圈子中的核心人物一般来说往往是人脉最丰富的，或者直接说认识人最多的，这些人暂且称为社交领袖。一个人一般来说可以很迅速地和自己的朋友建立联系。只要两个人处于同一个圈子之中，或者说他们处于不同的圈子，但是两个圈子的人有交集，那么即使他们不认识，也可以通过朋友的朋友的朋友······建立联系。弱两个人分属不同的圈子，且两个圈子没有交集，但是两个圈子都和第三个圈子有交集，那么这两个人同样可以通过朋友的朋友的朋友······建立联系。
根据上面这个例子，我们可以建立一个样本密度模型
DBSCAN算法中的簇类比于交际关系里的圈子，邻域类比于一个人的朋友圈，核心对象类比于社交领袖，密度直达、可达、相连分别类比于三种人与人知啊今建立联系的方式。DBSCAN算法中的一个簇是指所有可以相互之间密度直达、可达、相连的样本的集合。
而DBSCAN算法的原理也就很简单了，首先确定数据集中所有核心对象，然后随机从一个核心对象出发找出所有与之密度可达的样本，找完以后这些样本就是一个簇了，然后再随机选一个不在现有的簇范围内的核心对象，继续上面的步骤，知道所有核心对象都被分到某个簇中。
DBSCAN算法最后可能会产生几个不在任何簇里的样本，他们被称为噪声，同时也可以视为异常数据。
基于层次的聚类算法试图用自顶向下或者自底向上的方式在不同层次上对数据进行划分。AGNES算法是一中自底向上的算法。算法的基本思想是在一开始把所有样本都看作一个簇类。那么有n个样本的数据集就有n个初始簇。接下来两两计算簇间距离，距离最小的两个簇合并为一个簇（有点像霍夫曼树的子树合并），直到所有的簇合并为一个簇为止。各种簇间距离计算公式如下，视情况挑选
AGNES算法最终得到的结果如下图
我们可以通过选择簇间距离来确定到底分几个簇。簇间距离越大，得到的簇越少，簇间距离越小，得到的簇越多。
Talk is cheap, show me the code!
下面是一个KMeans模型的简单实现
"""
K-means clustering model
:file: supervised.py
:author: Richy Zhu
:email: rickyzhu@foxmail.com
"""
import numpy as np
class MyKMeans:
def __init__(self, k=3):
'''
K-means clustering model
:k: int, number of clusters
'''
self.k = k
self.X = None
self.labels = None
self.cluster_centers = None
def fit(self, X):
'''
Train the K-means clustering model
Parameters
----------
X: ndarray of shape (m, n)
sample data where row represent sample and column represent feature
Returns
-------
self
trained model
'''
ran_index = np.random.choice(np.arange(0,len(X)), self.k)
centres = [X[i] for i in ran_index]
prev_labels = np.zeros(len(X))
i = 0
while True:
labels = []
for x in X:
labels.append(np.argmin([np.linalg.norm(x - c) for c in centres]))
if np.array_equal(prev_labels, labels):
break
prev_labels = labels
for i in range(len(centres)):
centres[i] = np.mean(X[np.array(labels)==i], axis=0)
i += 0
self.labels = np.array(labels)
self.cluster_centers = np.array(centres)
return self
def predict(self, X):
'''
Make prediction by the trained model.
Parameters
----------
X: ndarray of shape (m, n)
data to be predicted, the same shape as trainning data
Returns
-------
C: ndarray of shape (m,)
Predicted class label per sample.
'''
labels = []
for x in X:
labels.append(np.argmin([
np.linalg.norm(x - c) for c in self.cluster_centers
]))
return np.array(labels)
测试代码如下
import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from unsupervised import *
X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y)
print('\nK-means clustering')
print('---------------------------------------------------------------------')
mykm = MyKMeans(k=3)
mykm.fit(X_train)
print('My KMeans:')
print(mykm.cluster_centers)
print(mykm.predict(X_test))
print()
from sklearn.cluster import KMeans
skkm = KMeans(n_clusters=3)
skkm.fit(X_train)
print('Sk KMeans:')
print(skkm.cluster_centers_)
print(skkm.predict(X_test))
测试结果为
$ python unsupervised_examples.py
K-means clustering
---------------------------------------------------------------------
[[4.78333333 3.11666667 1.50555556 0.26666667]
[6.24 2.87866667 4.90133333 1.66933333]
[5.25789474 3.74210526 1.49473684 0.26315789]]
[2 1 2 1 2 1 2 1 1 0 1 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 2 1 1 2 1 1 1 0 0 1 1
0]
Sk KMeans:
[[5.025 3.46388889 1.45833333 0.24166667]
[6.78888889 3.08888889 5.72962963 2.08888889]
[5.91428571 2.75510204 4.40612245 1.42653061]]
[0 1 0 1 0 2 0 2 2 0 1 1 2 2 0 1 1 2 0 0 0 2 0 1 1 2 0 2 1 0 1 2 2 2 0 2 1
0]
更多代码请参考https://github.com/qige96/programming-practice/tree/master/machine-learning
本作品首发于简书 和 博客园平台，采用知识共享署名 4.0 国际许可协议进行许可。
