1. 聚类是针对给定的样本，依据它们属性的相似度或距离，将其归并到若干个“类”或“簇”的数据分析问题。一个类是样本的一个子集。直观上，相似的样本聚集在同类，不相似的样本分散在不同类。

聚类和分类最大的不同在于：分类的目标是事先已知的，而聚类则不一样，聚类事先不知道目标变量是什么，类别没有像分类那样被预先定义出来。

  1. 距离或相似度度量在聚类中起着重要作用。

常用的距离度量有闵可夫斯基距离，包括欧氏距离、曼哈顿距离、切比雪夫距离、以及马哈拉诺比斯距离。常用的相似度度量有相关系数、夹角余弦。 用距离度量相似度时，距离越小表示样本越相似；用相关系数时，相关系数越大表示样本越相似。

  1. 类是样本的子集，比如有如下基本定义： 用k均值聚类 - 图1表示类或簇，用k均值聚类 - 图2,k均值聚类 - 图3；等表示类中的样本，用k均值聚类 - 图4表示样本k均值聚类 - 图5与样本k均值聚类 - 图6之间的距离。如果对任意的k均值聚类 - 图7，有k均值聚类 - 图8则称k均值聚类 - 图9为一个类或簇。

描述类的特征的指标有中心、直径、散布矩阵、协方差矩阵。

  1. 聚类过程中用到类与类之间的距离也称为连接类与类之间的距离包括最短距离、最长距离、中心距离、平均距离。


  1. 层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中层次聚类又有聚合或自下而上、分裂或自上而下两种方法。

聚合聚类开始将每个样本各自分到一个类；之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件；得到层次化的类别。分裂聚类开始将所有样本分到一个类；之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件；得到层次化的类别。
聚合聚类需要预先确定下面三个要素：
（1）距离或相似度； （2）合并规则； （3）停止条件。
根据这些概念的不同组合，就可以得到不同的聚类方法。

  1. k均值聚类 - 图10均值聚类是常用的聚类算法，有以下特点。基于划分的聚类方法；类别数k事先指定；以欧氏距离平方表示样本之间的距离或相似度，以中心或样本的均值表示类别；以样本和其所属类的中心之间的距离的总和为优化的目标函数；得到的类别是平坦的、非层次化的；算法是迭代算法，不能保证得到全局最优。

k均值聚类 - 图11均值聚类算法，首先选择k个类的中心，将样本分到与中心最近的类中，得到一个聚类结果；然后计算每个类的样本的均值，作为类的新的中心；重复以上步骤，直到收敛为止。

层次聚类

  1. 聚合（自下而上）：聚合法开始将每个样本各自分裂到一个类，之后将相距最近的两类合并，建立一个新的类，重复次操作知道满足停止条件，得到层次化的类别。
  2. 分裂（自上而下）： 分裂法开始将所有样本分到一个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件，得到层次化的类别。 ```python import math import random import numpy as np from sklearn import datasets,cluster import matplotlib.pyplot as plt

iris = datasets.load_iris() gt = iris[‘target’];gt ‘’’ array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]) ‘’’

iris[‘data’][:,:2].shape

(150, 2)

data = iris[‘data’][:,:2] x = data[:,0] y = data[:,1]

plt.scatter(x, y, color=’green’) plt.xlim(4, 8) plt.ylim(1, 5) plt.show()

  2. <a name="vtg8K"></a>
  3. ### 层次聚类（聚合法）
  4. ```python
  5. # 定义聚类数的节点
  6. class ClusterNode:
  7.     def __init__(self, vec, left=None, right=None, distance=-1, id=None, count=1):
  8.         """
  9.         :param vec: 保存两个数据聚类后形成新的中心
  10.         :param left: 左节点
  11.         :param right:  右节点
  12.         :param distance: 两个节点的距离
  13.         :param id: 用来标记哪些节点是计算过的
  14.         :param count: 这个节点的叶子节点个数
  15.         """
  16.         self.vec = vec
  17.         self.left = left
  18.         self.right = right
  19.         self.distance = distance
  20.         self.id = id
  21.         self.count = count
  23. def euler_distance(point1: np.ndarray, point2: list) -> float:
  24.     """
  25.     计算两点之间的欧拉距离，支持多维
  26.     """
  27.     distance = 0.0
  28.     for a, b in zip(point1, point2):
  29.         distance += math.pow(a - b, 2)
  30.     return math.sqrt(distance)
  32. # 层次聚类（聚合法）
  33. class Hierarchical:
  34.     def __init__(self, k):
  35.         self.k = k
  36.         self.labels = None
  38.     def fit(self, x):
  39.         # enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标
  40.         nodes = [ClusterNode(vec=v, id=i) for i, v in enumerate(x)]
  41.         distances = {}
  42.         point_num, feature_num = x.shape
  43.         self.labels = [-1] * point_num
  44.         currentclustid = -1
  45.         while(len(nodes)) > self.k:
  46.             min_dist = math.inf
  47.             nodes_len = len(nodes)
  48.             closest_part = None
  49.             for i in range(nodes_len - 1):
  50.                 for j in range(i+1, nodes_len):
  51.                     d_key = (nodes[i].id, nodes[j].id)
  52.                     if d_key not in distances:
  53.                         distances[d_key] = euler_distance(nodes[i].vec, nodes[j].vec)
  54.                     d = distances[d_key]
  55.                     if d < min_dist:
  56.                         min_dist = d
  57.                         closest_part = (i, j)
  59.             part1, part2 = closest_part
  60.             node1, node2 = nodes[part1], nodes[part2]
  61.             new_vec = [ (node1.vec[i] * node1.count + node2.vec[i] * node2.count ) / 
  62.                         (node1.count + node2.count)
  63.                         for i in range(feature_num)]
  64.             new_node = ClusterNode(vec=new_vec,
  65.                                    left=node1,
  66.                                    right=node2,
  67.                                    distance=min_dist,
  68.                                    id=currentclustid,
  69.                                    count=node1.count + node2.count)
  70.             currentclustid -= 1
  71.             del nodes[part2], nodes[part1]
  72.             nodes.append(new_node)
  74.         self.nodes = nodes
  75.         self.calc_label()
  77.     def calc_label(self):
  78.         """
  79.         调取聚类的结果
  80.         """
  81.         for i, node in enumerate(self.nodes):
  82.             # 将节点的所有叶子节点都分类
  83.             self.leaf_traversal(node, i)
  85.     def leaf_traversal(self, node: ClusterNode, label):
  86.         """
  87.         递归遍历叶子节点
  88.         """
  89.         if node.left == None and node.right == None:
  90.             self.labels[node.id] = label
  91.         if node.left:
  92.             self.leaf_traversal(node.left, label)
  93.         if node.right:
  94.             self.leaf_traversal(node.right, label)
  96. # https://zhuanlan.zhihu.com/p/32438294
  98. my = Hierarchical(3)
  99. my.fit(data)
  100. labels = np.array(my.labels)
  101. print(labels)
  102. '''
  103. [2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  104.  2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 2 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0
  105.  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 2 0 0 0 1 0 0 1 2 1 0 1 0
  106.  0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
  107.  0 0]
  108. '''
  110. # visualize result
  112. cat1 = data[np.where(labels==0)]
  113. cat2 = data[np.where(labels==1)]
  114. cat3 = data[np.where(labels==2)]
  116. plt.scatter(cat1[:,0], cat1[:,1], color='green')
  117. plt.scatter(cat2[:,0], cat2[:,1], color='red')
  118. plt.scatter(cat3[:,0], cat3[:,1], color='blue')
  119. plt.title('Hierarchical clustering with k=3')
  120. plt.xlim(4, 8)
  121. plt.ylim(1, 5)
  122. plt.show()

scikit-learn

  1. sk = cluster.AgglomerativeClustering(3)
  2. sk.fit(data)
  3. labels_ = sk.labels_
  4. print(labels_)
  5. '''
  6. [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  7.  1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 2 0 2 0 1 0 1 1 0 2 0 2 0 2 2 2 2 0 0 2 0
  8.  0 0 0 0 0 2 2 2 2 0 2 0 0 2 2 2 2 0 2 1 2 2 2 0 1 2 0 2 0 0 0 0 1 0 0 0 0
  9.  0 0 2 2 0 0 0 0 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0
  10.  0 0]
  11.  '''
  13. # visualize result of sklearn
  15. cat1_ = data[np.where(labels_==0)]
  16. cat2_ = data[np.where(labels_==1)]
  17. cat3_ = data[np.where(labels_==2)]
  19. plt.scatter(cat1_[:,0], cat1_[:,1], color='green')
  20. plt.scatter(cat2_[:,0], cat2_[:,1], color='red')
  21. plt.scatter(cat3_[:,0], cat3_[:,1], color='blue')
  22. plt.title('Hierarchical clustering with k=3')
  23. plt.xlim(4, 8)
  24. plt.ylim(1, 5)
  25. plt.show()

k均值聚类

k均值聚类是基于中心的聚类方法，通过迭代，将样本分到k个类中，使得每个样本与其所属类的中心或均值最近，得到k个平坦的，非层次化的类别，构成对空间的划分。

K-means

  1. # kmeans
  3. class MyKmeans:
  4.     def __init__(self, k, n=20):
  5.         self.k = k
  6.         self.n = n
  8.     def fit(self, x, centers=None):
  9.         # 第一步，随机选择 K 个点, 或者指定
  10.         if centers is None:
  11.             idx = np.random.randint(low=0, high=len(x), size=self.k)
  12.             centers = x[idx]
  13.         #print(centers)
  15.         inters = 0
  16.         while inters < self.n:
  17.             #print(inters)
  18.             #print(centers)
  19.             points_set = {key: [] for key in range(self.k)}
  21.             # 第二步，遍历所有点 P，将 P 放入最近的聚类中心的集合中
  22.             for p in x:
  23.                 nearest_index = np.argmin(np.sum((centers - p) ** 2, axis=1) ** 0.5)
  24.                 points_set[nearest_index].append(p)
  26.             # 第三步，遍历每一个点集，计算新的聚类中心
  27.             for i_k in range(self.k):
  28.                 centers[i_k] = sum(points_set[i_k])/len(points_set[i_k])
  30.             inters += 1
  32.         return points_set, centers
  34. m = MyKmeans(3)
  35. points_set, centers = m.fit(data)
  36. centers
  37. '''
  38. array([[5.006     , 3.428     ],
  39.        [6.81276596, 3.07446809],
  40.        [5.77358491, 2.69245283]])
  41. '''
  43. # visualize result
  45. cat1 = np.asarray(points_set[0])
  46. cat2 = np.asarray(points_set[1])
  47. cat3 = np.asarray(points_set[2])
  49. for ix, p in enumerate(centers):
  50.     plt.scatter(p[0], p[1], color='C{}'.format(ix), marker='^', edgecolor='black', s=256)
  52. plt.scatter(cat1_[:,0], cat1_[:,1], color='green')
  53. plt.scatter(cat2_[:,0], cat2_[:,1], color='red')
  54. plt.scatter(cat3_[:,0], cat3_[:,1], color='blue')
  55. plt.title('Hierarchical clustering with k=3')
  56. plt.xlim(4, 8)
  57. plt.ylim(1, 5)
  58. plt.show()

sklearn

  1. # using sklearn
  3. from sklearn.cluster import KMeans
  5. # n_clusters: 即我们的k值, max_iter： 最大的迭代次数
  6. kmeans = KMeans(n_clusters=3, max_iter=100).fit(data)
  7. gt_labels__ = kmeans.labels_
  8. centers__ = kmeans.cluster_centers_
  10. gt_labels__
  11. '''
  12. array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  13.        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  14.        1, 1, 1, 1, 1, 1, 0, 0, 0, 2, 0, 2, 0, 2, 0, 2, 2, 2, 2, 2, 2, 0,
  15.        2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 0, 2,
  16.        2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0,
  17.        0, 0, 0, 2, 2, 0, 0, 0, 0, 2, 0, 2, 0, 2, 0, 0, 2, 2, 0, 0, 0, 0,
  18.        0, 2, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 2])
  19. '''
  21. centers__
  22. '''
  23. array([[6.81276596, 3.07446809],
  24.        [5.006     , 3.428     ],
  25.        [5.77358491, 2.69245283]])
  26. '''
  28. # visualize result
  30. cat1 = data[gt_labels__ == 0]
  31. cat2 = data[gt_labels__ == 1]
  32. cat3 = data[gt_labels__ == 2]
  34. for ix, p in enumerate(centers__):
  35.     plt.scatter(p[0], p[1], color='C{}'.format(ix), marker='^', edgecolor='black', s=256)
  37. plt.scatter(cat1_[:,0], cat1_[:,1], color='green')
  38. plt.scatter(cat2_[:,0], cat2_[:,1], color='red')
  39. plt.scatter(cat3_[:,0], cat3_[:,1], color='blue')
  40. plt.title('kmeans using sklearn with k=3')
  41. plt.xlim(4, 8)
  42. plt.ylim(1, 5)
  43. plt.show()

寻找 K 值

  1. from sklearn.cluster import KMeans
  3. loss = []
  5. for i in range(1, 10):
  6.     kmeans = KMeans(n_clusters=i, max_iter=100).fit(data)
  7.     loss.append(kmeans.inertia_ / len(data) / 3)  # 样本距离最近的聚类中心的距离总和,inertia值越小，说明聚类效果越好
  9. plt.title('K with loss')
  10. plt.plot(range(1, 10), loss)
  11. plt.show()

例 14.2

  1. X = [[0, 2], [0, 0], [1, 0], [5, 0], [5, 2]]
  2. np.asarray(X)
  3. '''
  4. array([[0, 2],
  5.        [0, 0],
  6.        [1, 0],
  7.        [5, 0],
  8.        [5, 2]])
  9. '''
  10. m = MyKmeans(2, 100)
  11. points_set, centers = m.fit(np.asarray(X))
  13. points_set
  14. '''
  15. {0: [array([0, 2]), array([0, 0]), array([1, 0])],
  16.  1: [array([5, 0]), array([5, 2])]}
  17.  '''
  18. centers
  19. '''
  20. array([[0, 0], [5, 1]])
  21. '''
  23. #---------------------------------------
  25. kmeans = KMeans(n_clusters=2, max_iter=100).fit(np.asarray(X))
  26. kmeans.labels_
  27. '''
  28. array([0, 0, 0, 1, 1])
  29. '''
  30. kmeans.cluster_centers_
  31. '''
  32. array([[0.33333333, 0.66666667], [5.        , 1.        ]])
  33. '''