机器学习算法之KMeans聚类

以你之姓@ 2023-06-06 10:52 122阅读 0赞

算法原理

聚类指的是把集合，分组成多个类，每个类中的对象都是彼此相似的。K-means是聚类中最常用的方法之一，它是基于点与点距离的相似度来计算最佳类别归属。

在使用该方法前，要注意（1）对数据异常值的处理；（2）对数据标准化处理（x-min(x))/(max(x)-min(x)）；（3）每一个类别的数量要大体均等；（4）不同类别间的特质值应该差异较大。

算法流程

（1）选择k个初始聚类中心

（2）计算每个对象与这k个中心各自的距离，按照最小距离原则分配到最邻近聚类

（3）使用每个聚类中的样本均值作为新的聚类中心

（4）重复步骤（2）和（3）直到聚类中心不再变化

（5）结束，得到k个聚类

代码实现

  1. #coding=utf-8
  2. from collections import Counter
  3. from copy import deepcopy
  4. from time import time
  5. from random import randint, seed, random
  7. # 统计程序运行时间函数
  8. # fn代表运行的函数
  9. def run_time(fn):
  10.     def fun():
  11.         start = time()
  12.         fn()
  13.         ret = time() - start
  14.         if ret < 1e-6:
  15.             unit = "ns"
  16.             ret *= 1e9
  17.         elif ret < 1e-3:
  18.             unit = "us"
  19.             ret *= 1e6
  20.         elif ret < 1:
  21.             unit = "ms"
  22.             ret *= 1e3
  23.         else:
  24.             unit = "s"
  25.         print("Total run time is %.1f %s\n" % (ret, unit))
  26.     return fun()
  28. def load_data():
  29.     f = open("boston/breast_cancer.csv")
  30.     X = []
  31.     y = []
  32.     for line in f:
  33.         line = line[:-1].split(',')
  34.         xi = [float(s) for s in line[:-1]]
  35.         yi = line[-1]
  36.         if '.' in yi:
  37.             yi = float(yi)
  38.         else:
  39.             yi = int(yi)
  40.         X.append(xi)
  41.         y.append(yi)
  42.     f.close()
  43.     return X, y
  45. # 将数据归一化到[0, 1]范围
  46. def min_max_scale(X):
  47.     m = len(X[0])
  48.     x_max = [-float('inf') for _ in range(m)]
  49.     x_min = [float('inf') for _ in range(m)]
  50.     for row in X:
  51.         x_max = [max(a, b) for a, b in zip(x_max, row)]
  52.         x_min = [min(a, b) for a, b in zip(x_min, row)]
  54.     ret = []
  55.     for row in X:
  56.         tmp = [(x - b) / (a - b) for a, b, x in zip(x_max, x_min, row)]
  57.         ret.append(tmp)
  58.     return ret
  60. def get_euclidean_distance(arr1, arr2):
  61.     return sum((x1 - x2) ** 2 for x1, x2 in zip(arr1, arr2)) ** 0.5
  63. def get_cosine_distance(arr1, arr2):
  64.     numerator = sum(x1 * x2 for x1, x2 in zip(arr1, arr2))
  65.     denominator = (sum(x1 ** 2 for x1 in arr1) *
  66.                    sum(x2 ** 2 for x2 in arr2)) ** 0.5
  67.     return numerator / denominator
  70. class KMeans(object):
  71.     # k 簇的个数
  72.     # n_features 特征的个数
  73.     # clister_centers 聚类中心
  74.     # distance_fn 距离计算函数
  75.     # cluster_samples_cnt 每个簇里面的样本数
  76.     def __init__(self):
  77.         self.k = None
  78.         self.n_features = None
  79.         self.cluster_centers = None
  80.         self.distance_fn = None
  81.         self.cluster_samples_cnt = None
  83.     # 二分，查找有序列表里面大于目标值的第一个值
  84.     def bin_search(self, target, nums):
  85.         low = 0
  86.         high = len(nums) - 1
  87.         assert nums[low] <= target < nums[high], "Cannot find target!"
  88.         while 1:
  89.             mid = (low + high) // 2
  90.             if mid == 0 or target >= nums[mid]:
  91.                 low = mid + 1
  92.             elif target < nums[mid - 1]:
  93.                 high = mid - 1
  94.             else:
  95.                 break
  96.         return mid
  98.     # 比较两个向量是否为同一向量
  99.     def cmp_arr(self, arr1, arr2, eps=1e-8):
  100.         return len(arr1) == len(arr2) and \
  101.                all(abs(a- b) < eps for a, b in zip(arr1, arr2))
  103.     # 初始化聚类中心
  104.     def init_cluster_centers(self, X, k, n_features, distance_fn):
  105.         n = len(X)
  106.         centers = [X[randint(0, n-1)]]
  107.         for _ in range(k-1):
  108.             center_pre = centers[-1]
  109.             idxs_dists = ([i, distance_fn(Xi, center_pre)] for i, Xi in enumerate(X))
  110.             # 对距离进行排序
  111.             idxs_dists = sorted(idxs_dists, key=lambda x: x[1])
  112.             dists = [x[1] for x in idxs_dists]
  113.             tot = sum(dists)
  114.             for i in range(1, n):
  115.                 dists[i] /= tot
  116.             for i in range(1, n):
  117.                 dists[i] += dists[i-1]
  118.             # 随机选择一个聚类中心
  119.             while 1:
  120.                 num = random()
  121.                 # 查找>=num的距离
  122.                 dist_idx = self.bin_search(num, dists)
  123.                 row_idx = idxs_dists[dist_idx][0]
  124.                 center_cur = X[row_idx]
  125.                 if not any(self.cmp_arr(center_cur, center) for center in centers):
  126.                     break
  127.             centers.append(center_cur)
  128.         return centers
  131.     # 寻找距离Xi最近的聚类中心
  132.     def get_nearest_center(self, Xi, centers, distance_fn):
  133.         return min(((i, distance_fn(Xi, center)) for
  134.                     i, center in enumerate(centers)), key=lambda x: x[1])[0]
  136.     # 寻找X最近的聚类中心
  137.     def get_nearest_centers(self, X, distance_fn, centers):
  138.         return [self.get_nearest_center(Xi, centers, distance_fn) for Xi in X]
  140.     # 获取空的簇
  141.     def get_empty_cluster_idxs(self, cluster_samples_cnt, k):
  142.         clusters = ((i, cluster_samples_cnt[i]) for i in range(k))
  143.         empty_clusters = filter(lambda x: x[1] == 0, clusters)
  144.         return [empty_clusters[0] for empty_cluster in empty_clusters]
  145.     # 在X中找到到所有非空簇中心的最远样本
  146.     def get_furthest_row(self, X, distance_fn, centers, empty_cluster_idxs):
  147.         def f(Xi, centers):
  148.             return sum(distance_fn(Xi, centers) for center in centers)
  150.         non_empty_centers = map(lambda x: x[1], filter(
  151.             lambda x: x[0] not in empty_cluster_idxs, enumerate(centers)))
  152.         return max(map(lambda x: [x, f(x, non_empty_centers)], X), key=lambda x: x[1])[0]
  154.     # 处理空的簇
  155.     def process_empty_clusters(self, X, distance_fn, n_features, centers, empty_cluster_idxs):
  156.         for i in empty_cluster_idxs:
  157.             center_cur = self.get_furthest_row(X, distance_fn, centers, empty_cluster_idxs)
  158.             while any(self._cmp_arr(center_cur, center) for center in centers):
  159.                 center_cur = self.get_furthest_row(X, distance_fn, centers,
  160.                                                     empty_cluster_idxs)
  161.             centers[i] = center_cur
  162.         return centers
  164.     # 重新获取聚类中心
  165.     def get_cluster_centers(self, X, k, n_features, y, cluster_samples_cnt):
  166.         ret = [[0 for _ in range(n_features)] for _ in range(k)]
  167.         for Xi, cetner_num in zip(X, y):
  168.             for j in range(n_features):
  169.                 ret[cetner_num][j] += Xi[j] / cluster_samples_cnt[cetner_num]
  170.         return ret
  172.     # 训练
  173.     def fit(self, X, k, fn=None, n_iter=100):
  174.         n_features = len(X[0])
  175.         if fn is None:
  176.             distance_fn = get_euclidean_distance
  177.         else:
  178.             error_msg = "Parameter distance_fn must be eu or cos!"
  179.             assert fn in ("eu", "cos"), error_msg
  180.             if fn == "eu":
  181.                 distance_fn = get_euclidean_distance
  182.             if fn == "cos":
  183.                 distance_fn = get_cosine_distance
  185.         centers = self.init_cluster_centers(X, k, n_features, distance_fn)
  186.         for i in range(n_iter):
  187.             while 1:
  188.                 # 寻找X的最近聚类中心
  189.                 y = self.get_nearest_centers(X, distance_fn, centers)
  190.                 # 统计每个簇的样本个数
  191.                 cluster_samples_cnt = Counter(y)
  192.                 # 获取空的簇
  193.                 empty_cluster_idxs = self.get_empty_cluster_idxs(cluster_samples_cnt, k)
  194.                 # 如果有空的簇
  195.                 if empty_cluster_idxs:
  196.                     centers = self.process_empty_clusters(centers, empty_cluster_idxs, n_features)
  197.                 else:
  198.                     break
  199.             centers_new = self.get_cluster_centers(X, k, n_features, y, cluster_samples_cnt)
  200.             centers = deepcopy(centers_new)
  201.             print("Iteration: %d" % i)
  202.         self.k = k
  203.         self.n_features = n_features
  204.         self.distance_fn = distance_fn
  205.         self.cluster_centers = centers
  206.         self.cluster_samples_cnt = cluster_samples_cnt
  208.     def _predict(self, Xi):
  209.         return self.get_nearest_center(Xi, self.cluster_centers, self.distance_fn)
  211.     def predict(self, X):
  212.         return [self._predict(Xi) for Xi in X]
  215. @run_time
  216. def main():
  217.     print("Tesing the performance of Kmeans...")
  218.     # Load data
  219.     X, y = load_data()
  220.     X = min_max_scale(X)
  221.     # Train model
  222.     est = KMeans()
  223.     k = 2
  224.     est.fit(X, k)
  225.     print()
  226.     # Model performance
  227.     prob_pos = sum(y) / len(y)
  228.     print("Positive probability of X is:%.1f%%.\n" % (prob_pos * 100))
  229.     y_hat = est.predict(X)
  230.     cluster_pos_tot_cnt = {i: [0, 0] for i in range(k)}
  231.     for yi_hat, yi in zip(y_hat, y):
  232.         cluster_pos_tot_cnt[yi_hat][0] += yi
  233.         cluster_pos_tot_cnt[yi_hat][1] += 1
  234.     cluster_prob_pos = {k: v[0] / v[1] for k, v in cluster_pos_tot_cnt.items()}
  235.     for i in range(k):
  236.         tot_cnt = cluster_pos_tot_cnt[i][1]
  237.         prob_pos = cluster_prob_pos[i]
  238.         print("Count of elements in cluster %d is:%d." %
  239.               (i, tot_cnt))
  240.         print("Positive probability of cluster %d is:%.1f%%.\n" % (i, prob_pos * 100))

对肺癌数据集聚类100轮结果展示

在这里插入图片描述
可以看到经过100次聚类后，正负样本被大量聚集在了一起，证明了聚类算法的有效性。

github源码

https://github.com/BBuf/machine-learning

发表评论

表情：
评论列表 （有 0 条评论，122人围观）

还没有评论，来说两句吧...

相关阅读

    相关 机器学习算法之KMeans聚类

    算法原理 聚类指的是把集合，分组成多个类，每个类中的对象都是彼此相似的。K-means是聚类中最常用的方法之一，它是基于点与点距离的相似度来计算最佳类别归属。 在使用该

    以你之姓@以你之姓@/ 0 赞/ 123 阅读