class pattern:
    x=0
    y=0
    def __init__(self,x,y):
        self.x=x
        self.y=y

def dis(a,b):
    return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))**0.5

eps=0.00001
maxn=1000050
inf=4000000000000000000
print("请输入需要将模式分为的类别数 c ：")
c=input()
c=int(c)
print("请输入模式总数 n ：")
n=input()
n=int(n)
print("请输入各模式的两个特征点 ：")
a=[]
b=[]
for i in range(n):
    x,y=map(int,input().split())
    tmp=pattern(x,y)
    a.append(tmp)
for i in range(c):
    tmp=pattern(a[i].x,a[i].y)
    b.append(tmp)
ans=0
while ans<c:
    cnt=[0]*maxn
    belong=[-1]*maxn
    for i in range(n):
        minn=4000000000000000000
        mini=-1
        for j in range(c):
            dis_to_center=dis(a[i],b[j])
            if dis_to_center<minn:
                minn=dis_to_center
                mini=j
        belong[i]=mini
        cnt[mini]=cnt[mini]+1
    sum=[]
    for i in range(c):
        tmp=pattern(0,0)
        sum.append(tmp)
    for i in range(n):
        sum[belong[i]].x+=a[i].x
        sum[belong[i]].y+=a[i].y
        print(a[i].x,a[i].y,belong[i],sum[belong[i]].x,sum[belong[i]].y)
    ans=0
    for i in range(n):
        print(i,"号点",a[i].x,a[i].y)
    for i in range(c):
        if cnt[i]!=0:
            sum[i].x=sum[i].x/cnt[i]
            sum[i].y=sum[i].y/cnt[i]
            if abs(sum[i].x-b[i].x)<eps and abs(sum[i].y-b[i].y)<eps:
                ans=ans+1
            b[i].x=sum[i].x
            b[i].y=sum[i].y
        if a[1].x!=1 or a[1].y!=0:
            print("i=",i)
    for i in range(n):
        print(i,"号点",a[i].x,a[i].y)
print("C均值聚类算法已经完成！\n\nc个类中心分别为\n")
for i in range(c):
    print("第",i+1,"类的聚类中心的两个特征值分别为",b[i].x,b[i].y)

print()
for i in range(c):
    print("属于第",i+1,"类的点有：")
    for j in range(n):
        if belong[j]==i:
            print(j+1,"号点",a[j].x,a[j].y)
    print()

之前做大作业的时候本来想用聚类法给点集分类的，但是太复杂了，于是最后没有采用这个方案。现在把之前做的一些工作整理出来写个小博客。

K-means聚类法原理：

聚类是一个将数据集中在某些方面相似的数据成员进行分类组织的过程，聚类就是一种发现这种内在结构的技术，聚类技术经常被称为无监督学习。

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

如何计算？

如果用数据表达式表示，假设簇划分为$(C_1,C_2,...C_k)$，则我们的目标是最小化平方误差E：
$$E=\sum _{i=1}^k\sum _{x\in C_i}{\Vert x-{\mu }_i\Vert }_2^2$$
其中${\mu }_i$是簇$C_i$的均值向量，有时也称为质心，表达式为：
$${\mu }_i=\frac{1}{\left|C_i\right|}\sum _{x\in C_i}x$$
如果我们想直接求上式的最小值并不容易，这是一个NP难的问题，因此只能采用启发式的迭代方法。
下图是K均值聚类法的一个示意图：

上图a表达了初始的数据集，假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图4所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。

当然在实际K-Mean算法中，我们一般会多次运行图c和图d，才能达到最终的比较优的类别。

我的解决方案是在代码中使用的是循环10次（可调），选择总距离最小的那个方案。

代码部分：

class KMeansClusterer:  # k均值聚类
    def __init__(self, ndarray, cluster_num):
        self.ndarray = ndarray
        self.cluster_num = cluster_num
        self.points = self.__pick_start_point(ndarray, cluster_num)

    def cluster(self):
        result = []
        for i in range(self.cluster_num):
            result.append([])
        for item in self.ndarray:
            distance_min = sys.maxsize
            index = -1
            for i in range(len(self.points)):
                distance = self.__distance(item, self.points[i])
                if distance < distance_min:
                    distance_min = distance
                    index = i
            result[index] = result[index] + [item.tolist()]
        new_center = []
        for item in result:
            new_center.append(self.__center(item).tolist())
        # 中心点未改变，说明达到稳态，结束递归
        if (self.points == new_center).all():
            sum=self.__sumdis(result)
            return result,self.points,sum
        self.points = np.array(new_center)
        return self.cluster()

    def __sumdis(self,result):
        #计算总距离和
        sum=0
        for i in range(len(self.points)):
            for j in range(len(result[i])):
                sum+=self.__distance(result[i][j],self.points[i])
        return sum

    def __center(self, list):
        # 计算每一列的平均值
        return np.array(list).mean(axis=0)

    def __distance(self, p1, p2):
        #计算两点间距
        tmp = 0
        for i in range(len(p1)):
            tmp += pow(p1[i] - p2[i], 2)
        return pow(tmp, 0.5)

    def __pick_start_point(self, ndarray, cluster_num):
        if cluster_num < 0 or cluster_num > ndarray.shape[0]:
            raise Exception("簇数设置有误")
        # 取点的下标
        indexes = random.sample(np.arange(0, ndarray.shape[0], step=1).tolist(), cluster_num)
        points = []
        for index in indexes:
            points.append(ndarray[index].tolist())
        return np.array(points)

运行结果如下：

结果如上图所示，这是之前大作业得到的点集，不同颜色的点分属于不同类型的点集，五角星为每个点集的中心点。

调用函数后得到的是点集以及总距离。代码使用示例我放在资源包里，有需要自取。

K均值聚类（K-Means）

        k-means 算法：根据给定的数据样本构建 k 个划分聚类，每个划分聚类即为一个簇。

        该算法是一个典型的基于距离的聚类算法，采用距离作为相似性的评价指标（两个样本的距离越近，相似度就越大）。

每个数据样本必须属于而且只能属于一个簇。

同一簇中的数据样本相似度高，不同簇中的数据样本相似度较小。

聚类相似度是利用各簇中样本的均值来进行计算的。

注：因为在该算法第一步中是随机的选取任意k个对象作为初始聚类的中心，初始地代表一个簇，因此k个初始类聚类中心点的选取对聚类结果具有较大的影响。

聚类步骤：
1）随机指定k个质心点（中心点）
2）根据距离分类（靠近质心点的划归为同一类）
3）采用平均值更新质心点
4)重复迭代步骤2-3，直到质心点不在变化或者达到指点具体迭代次数。

python代码实现

import numpy as np
import matplotlib.pyplot as plt
# 引入scipy中的距离函数，默认欧式距离
from scipy.spatial.distance import cdist
# 从sklearn中直接生成聚类数据
from sklearn.datasets._samples_generator import make_blobs


# -------------1. 数据加载---------
x, y = make_blobs(n_samples=100, centers=6, random_state=1234, cluster_std=0.6)

#plt.figure(figsize=(6, 6))
#plt.scatter(x[:, 0], x[:, 1], c=y)
#plt.show()

# --------------2. 算法实现--------------
class K_Means(object):
    # 初始化，参数 n_clusters（K）、迭代次数max_iter、初始质心 centroids
    def __init__(self, n_clusters=5, max_iter=300, centroids=[]):
        self.n_clusters = n_clusters
        self.max_iter = max_iter
        self.centroids = np.array(centroids, dtype=np.float)

    # 训练模型方法，k-means聚类过程，传入原始数据
    def fit(self, data):
        # 假如没有指定初始质心，就随机选取data中的点作为初始质心
        if (self.centroids.shape == (0,)):
            # 从data中随机生成0到data行数的6个整数，作为索引值
            self.centroids = data[np.random.randint(0, data.shape[0], self.n_clusters), :]

        # 开始迭代
        for i in range(self.max_iter):
            # 1. 计算距离矩阵，得到的是一个100*6的矩阵
            distances = cdist(data, self.centroids)

            # 2. 对距离按有近到远排序，选取最近的质心点的类别，作为当前点的分类
            c_ind = np.argmin(distances, axis=1)

            # 3. 对每一类数据进行均值计算，更新质心点坐标
            for i in range(self.n_clusters):
                # 排除掉没有出现在c_ind里的类别
                if i in c_ind:
                    # 选出所有类别是i的点，取data里面坐标的均值，更新第i个质心
                    self.centroids[i] = np.mean(data[c_ind == i], axis=0)

    # 实现预测方法
    def predict(self, samples):
        # 跟上面一样，先计算距离矩阵，然后选取距离最近的那个质心的类别
        distances = cdist(samples, self.centroids)
        c_ind = np.argmin(distances, axis=1)

        return c_ind


dist = np.array([[121, 221, 32, 43],
                 [121, 1, 12, 23],
                 [65, 21, 2, 43],
                 [1, 221, 32, 43],
                 [21, 11, 22, 3], ])
c_ind = np.argmin(dist, axis=1)
print(c_ind)
x_new = x[0:5]
print(x_new)
print(c_ind == 2)
print(x_new[c_ind == 2])
np.mean(x_new[c_ind == 2], axis=0)

# --------------3. 测试------------
# 定义一个绘制子图函数
def plotKMeans(x, y, centroids, subplot, title):
    # 分配子图，121表示1行2列的子图中的第一个
    plt.subplot(subplot)
    plt.scatter(x[:, 0], x[:, 1], c='cyan')
    # 画出质心点
    plt.scatter(centroids[:, 0], centroids[:, 1], c=np.array(range(5)), s=100)
    plt.title(title)

kmeans = K_Means(max_iter=300, centroids=[[2, 1], [2, 2], [2, 3], [2, 4], [2, 5]])

plt.figure(figsize=(16, 6))
plotKMeans(x, y, kmeans.centroids, 121, 'start')

# 开始聚类
kmeans.fit(x)

plotKMeans(x, y, kmeans.centroids, 122, 'k-means')

# 预测新数据点的类别
x_new = np.array([[0, 0], [10, 7]])
y_pred = kmeans.predict(x_new)

print(kmeans.centroids)
print(y_pred)

plt.scatter(x_new[:, 0], x_new[:, 1], s=100, c='black')
plt.show()