K均值聚类算法介绍

k均值聚类算法(k-means clustering algorithm)是一种迭代求解的聚类分析算法。也算是无监督学习,聚类算法中最简单的一种了。

其整体思想为,预将数据分为K组,则随机选取K个对象作为初始的聚类中心,然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本,聚类的聚类中心会根据聚类中现有的对象被重新计算。

这个过程将不断重复直到满足某个终止条件。终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差的平方和局部最小。

接下来通过两张方式实现聚类算法,手写与库函数的调用。

K-means理解性编写

这是我关系十分不错朋友的一个作业,比较简单,但他还是不会。 真是的,他能不能想着提升一下自己啊,都大三了,还在这浪。 他们老师的目的就是理解K均值聚类算法的过程,自己写出来就行了。主要目标是补全mine_align(),与hero_move()两个函数,也是K均值里面最关键的两个部分了。以题目为例,下面说明一下。

import numpy as np
import matplotlib.pyplot as plt
import random
import time


class Map():
    def __init__(self, num_mine, num_hero):
        self.num_mine = num_mine
        self.num_hero = num_hero
        self.mines = []
        self.heros = []
        self.init_map()

    def init_map(self):
        for i in range(self.num_mine):
            x = random.random()
            y = random.random()
            self.mines.append([x, y])
        for j in range(self.num_hero):
            x1 = random.random()
            y1 = random.random()
            self.heros.append([x1, y1])

    def hero_move(self):
        #重新计算质心点
        for center in self.result_c:
            self.heros[center] = np.average(self.result_c[center], axis=0)
    def mine_align(self):
        #当前计算当前质心点所属的分类点有那些
        self.result_c = {}
        for i in range(self.num_hero):
            self.result_c[i] = []
        for it in self.mines:
            distance = []
            for center in self.heros:
                distance.append(np.linalg.norm(np.array(it) - np.array(center)))
            classification = distance.index(min(distance))
            self.result_c[classification].append(it)

    def map_visualization(self):
        tmp = np.array(self.mines)
        X = tmp[:, 0]
        Y = tmp[:, 1]
        plt.plot(X, Y, 'b*')
        tmp = np.array(self.heros)
        X = tmp[:, 0]
        Y = tmp[:, 1]
        plt.plot(X, Y, 'ro')

        plt.show()


def main():
    map = Map(num_mine=100, num_hero=3)
    while True:
        map.mine_align()
        map.hero_move()
        map.map_visualization()
        time.sleep(3)


if __name__ == '__main__':
    main()

mine_align()函数主要完成的就是现阶段矿石(分类点)的排列,我更喜欢称为分类。其实现的功能就是计算每一个分类点与英雄点(质心点)的距离,根据其结果,选取距离最小的作为该分类点的类别。之后就是迭代此过程,得到所有矿石所对应的英雄类别。关键的函数如下。

np.linalg.norm(np.array(it) - np.array(center))
#求两点间的距离

其使用了numpy库内的函数,原本的功能是求范数,实现向量范数的计算。这里单纯用于计算两个点之间的距离。

hero_move()实现的功能就是根据排列之后矿石的分类,再次计算属于原类别英雄所负责的所有分类点的平均值(距离该类别下所有矿石距离之和最近的点)来作为英雄的新坐标。

但是该模板并没有结束条件,相当于最终英雄的位置不再改变时,但是程序仍在运行。其应该是要和接下来的其他游戏程序结合起来吧,如果单纯编写K均值算法,结束条件是必须要有的。

K-means库函数编写

下面是我个人运用sklearn库函数完成的K均值算法。关键点在于求出一个数据最合适的K值。

import sklearn
import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
import matplotlib.pyplot as plt
import pandas as pd
from pandas.plotting import andrews_curves

path = 'tf_idf.csv'
data = np.loadtxt(path, dtype=float, delimiter=',')
#导入数据
print(data)
k = 33
model = KMeans(n_clusters=k)
model.fit(data)
#确定分类的簇,即K值。进行拟合计算
for index, label in enumerate(model.labels_, 1):
    print("index:{}⑧⑧⑧⑧⑧label:{}".format(index, label))
#打印出每一个分类点和其所属的簇(类别)。
# for i in range(5, 36):
#     model = KMeans(n_clusters=i)
#     s = model.fit(data)
#     y_pre = s.labels_
#     ans = silhouette_score(data, y_pre)
#     print(i, ans, sep='⑧⑧⑧⑧⑧')
#关键点 求出该数据其最佳的簇的个数,即K值。
df = pd.read_csv(path, header=None)
df[3296] = model.labels_
print(df)
#新增一列,代表其标签值,即label
plt.figure()
andrews_curves(df, 3296)#一种可视化表现方式,有两种还是不错的,安德鲁曲线和雷达图,其位于pandas库内,想了解的去看一下上面导入的最后的库
plt.savefig('1.jpg')
plt.show()
#保存图片,展示。

K-Means追求的是簇间距离尽量大,簇内距离尽量小。常用的为轮廓系数,对于一个样本集合,它的轮廓系数是所有样本轮廓系数的平均值。轮廓系数的取值范围是[-1,1],同类别样本距离越相近不同类别样本距离越远,分数越高。但依照实际情况考虑,143条文本,其内容也相差不多。分类的簇不易过多,因此选择在5-35直接选择K的最好值。 该数据最终选择33。

整体小结

个人经验之谈,初学者完全可以在学习了K均值算法后,手写出其代码,重点在于理解。但如果手写,其处理数据的维度可能较低,就是简单的2维X,Y轴问题,3维数据和4维勉强可以进行处理。当对K均值有一定的了解之后,就采用库函数的方式之间调用K均值算法,同时处理的数据量也会剧增,库函数的优点同样可以帮助我们完成任务。

个人心情

上周可以说是回归到了死肥宅的生活中去,也是理解了这个东西为什么会陪伴自己快9年。动漫这个兴趣爱好其实挺好的,上了大学之后,各种事情一直在忙,也没时间深入了解自己喜欢的作品了。哎,真是可惜啊,目前可能错过了不少好的作品。一个比较清闲的周末让我看见了我当初的爱,我决定重整旗鼓,再次成为死肥宅,重回当年的中二少年吧!!!

同时,Wish u all the best.

个人经验之谈,初学者完全可以在学习了K均值算法后,手写出其代码,重点在于理解。但如果手写,其处理数据的维度可能较低,就是简单的2维X,Y轴问题,3维数据和4维勉强可以进行处理。当对K均值有一定的了解之后,就采用库函数的方式之间调用K均值算法,同时处理的数据量也会剧增,库函数的优点同样可以帮助我们完成任务。