您的位置: 首页  >  文章  >  学习笔记第五篇之聚类算法

学习笔记第五篇之聚类算法

分类: 文章 • 2023-04-02 12:02:11

      今年年初的时候学习了《机器学习》这本书中的算法，并实践了一些。现在整理成笔记，以后需要时还可以找到。

      今天先写个简单的聚类算法。

     1、K-means聚类

         K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇

是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。k个初始类聚类中心点的选取对聚类结果具有较大的影响，因为在该算法第一

步中是随机的选取任意k个对象作为初始聚类的中心，初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个对象，根据其与各个簇中心的距

离将每个对象重新赋给最近的簇。当考察完所有数据对象后，一次迭代运算完成，新的聚类中心被计算出来。如果在一次迭代前后，J的值没有发生变

化，说明算法已经收敛。

          

算法过程如下：
1）从N个文档随机选取K个文档作为质心
2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类
3）重新计算已经得到的各个类的质心
4）迭代2～3步直至新的质心与原质心相等或小于指定阈值，算法结束
具体如下：
输入：k, data[n];
（1） 选择k个初始中心点，例如c[0]=data[0],…c[k-1]=data[k-1]；
（2） 对于data[0]….data[n]，分别与c[0]…c[k-1]比较，假定与c[i]差值最少，就标记为i；
（3） 对于所有标记为i点，重新计算c[i]={ 所有标记为i的data[j]之和}/标记为i的个数；
（4） 重复(2)(3)，直到所有c[i]值的变化小于给定阈值。
算法优点
K-Means聚类算法的优点主要集中在:
1.算法快速、简单;
2.对大数据集有较高的效率并且是可伸缩性的;
3.时间复杂度近于线性，而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(nkt) ,其中n代表数据集中对象的数量，t代表着算法迭代的次数，k代表着簇的数目。
下面以2011年到2015年全国主要城市的国内生产总值实例，根据该数据将城市聚为三类，一线城市、二线城市和三线城市。
[python] view plain copy
  1. #coding:utf-8  
  2. from __future__ import division  
  3. from math import sqrt  
  4. import xlrd  
  5. import random  
  6. import numpy  
  7. import sys  
  8. reload(sys)  
  9. sys.setdefaultencoding('utf-8')  
  10. #数据存储函数，返回城市数据字典，键值为5年的数据列表  
  11. def storage():  
  12.     table = xlrd.open_workbook('E:/citydata.xls')  
  13.     sheet = table.sheets()[0]  
  14.     col = sheet.col_values(0)  
  15.     list1 = []  
  16.     for i in range(4, 40):  
  17.         row_data = sheet.row_values(i)  
  18.         list1.append(row_data)  
  19.     l = len(list1)  
  20.     list2 = []  
  21.     for j in range(l):  
  22.         temp = list1[j]  
  23.         list2.append(temp[0])  
  24.         del temp[0]  
  25.         list1[j] = temp  
  26.     dict1 = {}  
  27.     for k in range(l):  
  28.         temp1 = list2[k]  
  29.         dict1[temp1] = list1[k]  
  30.     return dict1  
  31.   
  32. #求两个城市向量的距离  
  33. def distance(elem, K_mean):  
  34.     global Sum  
  35.     length = len(elem)  
  36.     Sum = 0  
  37.     # print type(K_mean)  
  38.     for i in range(length):  
  39.         Sum = Sum + (elem[i] - K_mean[i])**2  
  40.     Sum = sqrt(Sum)  
  41.     return Sum  
  42.   
  43. #簇中心向量  
  44. def mean(cluster):  
  45.     length = len(cluster)  
  46.     S = [0.0, 0.0, 0.0, 0.0, 0.0]  
  47.     for every in cluster:  
  48.         a = numpy.array(every)  
  49.         S = S + a  
  50.     mean_value = S/length  
  51.     mean_value = list(mean_value)  
  52.     # print mean_value  
  53.     return mean_value  
  54.   
  55. #比较函数  
  56. def compare(list1, list2):  
  57.     a = len(list1)  
  58.     b = len(list2)  
  59.     # print a, b  
  60.     c = 0  
  61.     for i in range(a):  
  62.         if list1[i] == list2[i]:  
  63.             c = c + 1  
  64.     # print c  
  65.     if c == a:  
  66.         return True  
  67.     else:  
  68.         return False  
  69.   
  70. #代价函数，返回簇间的距离  
  71. def Cost_function(K1_cluster, K2_cluster, K3_cluster, K1_mean, K2_mean, K3_mean):  
  72.     global cost  
  73.     cost = 0  
  74.     for each in K1_cluster:  
  75.         cost = cost + distance(each, K1_mean)  
  76.     # print cost  
  77.     for every in K2_cluster:  
  78.         cost = cost + distance(every, K2_mean)  
  79.     for single in K3_cluster:  
  80.         cost = cost + distance(single, K3_mean)  
  81.     return cost  
  82.   
  83. #算法第一步，返回三个簇  
  84. def Step_one(dict1, K1, K2, K3):  
  85.     K1_cluster = []  
  86.     K2_cluster = []  
  87.     K3_cluster = []  
  88.     for each in dict1:  
  89.         dist1 = distance(dict1[each], K1)  
  90.         dist2 = distance(dict1[each], K2)  
  91.         dist3 = distance(dict1[each], K3)  
  92.         Min = min(dist1, dist2, dist3)  
  93.         if Min == dist1:  
  94.             K1_cluster.append(dict1[each])  
  95.         if Min == dist2:  
  96.             K2_cluster.append(dict1[each])  
  97.         if Min == dist3:  
  98.             K3_cluster.append(dict1[each])  
  99.     # print K1_cluster  
  100.     return K1_cluster, K2_cluster, K3_cluster  
  101.   
  102. #求簇的中心向量  
  103. def Step_two(K1_cluster, K2_cluster, K3_cluster):  
  104.     K1_mean = mean(K1_cluster)  
  105.     K2_mean = mean(K2_cluster)  
  106.     K3_mean = mean(K3_cluster)  
  107.     return K1_mean, K2_mean, K3_mean  
  108.   
  109. #聚类函数，返回聚类结果  
  110. def K_means(dict1, K):  
  111.     global K11_mean, K22_mean, K33_mean, error, cost1, cost2  
  112.     length = len(dict1)  
  113.     list1 = random.sample(dict1, K)  
  114.     K1 = dict1[list1[0]]  
  115.     K2 = dict1[list1[1]]  
  116.     K3 = dict1[list1[2]]  
  117.     clu1, clu2, clu3 = Step_one(dict1, K1, K2, K3)     #第一次聚类  
  118.     K1_mean, K2_mean, K3_mean = Step_two(clu1, clu2, clu3)  
  119.     cost1 = Cost_function(clu1, clu2, clu3, K1_mean, K2_mean, K3_mean)  
  120.     new_clu1, new_clu2, new_clu3 = Step_one(dict1, K1_mean, K2_mean, K3_mean)   #第二次聚类  
  121.     K11_mean, K22_mean, K33_mean = Step_two(new_clu1, new_clu2, new_clu3)  
  122.     cost2 = Cost_function(new_clu1, new_clu2, new_clu3, K11_mean, K22_mean, K33_mean)  
  123.     error = cost1 - cost2  
  124.     if error > 0.5:  
  125.         cost1 = cost2  
  126.         new_clu1, new_clu2, new_clu3 = Step_one(dict1, K11_mean, K22_mean, K33_mean)  
  127.         K11_mean, K22_mean, K33_mean = Step_two(new_clu1, new_clu2, new_clu3)  
  128.         cost2 = Cost_function(new_clu1, new_clu2, new_clu3, K11_mean, K22_mean, K33_mean)  
  129.         error = cost1 - cost2  
  130.     return new_clu1, new_clu2, new_clu3  
  131.   
  132.   
  133. if __name__ == '__main__':  
  134.     dict1 = storage()  
  135.     K = 3  
  136.     K1_cluster, K2_cluster, K3_cluster = K_means(dict1, K)  
  137.     list1 = []  
  138.     list2 = []  
  139.     list3 = []  
  140.     d = dict1.keys()  
  141.     L1 = len(K1_cluster)  
  142.     L2 = len(dict1)  
  143.     # print K1_cluster  
  144.     for each in d:  
  145.         for i in K1_cluster:  
  146.             # print i  
  147.             if compare(dict1[each], i):  
  148.                 list1.append(each)  
  149.         for j in K2_cluster:  
  150.             if compare(dict1[each], j):  
  151.                 list2.append(each)  
  152.         for k in K3_cluster:  
  153.             if compare(dict1[each], k):  
  154.                 list3.append(each)  
  155.     for i in list1:  
  156.         print i,  
  157.     print  
  158.     for j in list2:  
  159.         print j,  
  160.     print  
  161.     for k in list3:  
  162.         print k,  
  163.     print 
结果如下，我取的误差是0.5，也可以用迭代次数。
学习笔记第五篇之聚类算法

相关推荐