import numpy as np

import matplotlib.pyplot as plt

import operator

def createDataSet():

    '''创建数据'''

    #创建一个二维数组(4, 2)

    group = np.array([

        [1.0,1.1],

        [1.0,1.0],

        [0,0],

        [0,0.1]

    ])

    #定义好对应的标签

    labels = ['A','A','B','B']

    return group,labels

def classify(inX,dataset,labels,k):

    '''分类'''

    dataSetSize = dataset.shape[0] #获取0轴的值，第一个维度的值  4

    diffMat = np.tile(inX,(dataSetSize,1))-dataset  #广播，然后用新数组减去原先的数组

    # print(diffMat)

    sqDiffMat = diffMat**2   #取diffMat的平方值

    sqDistance = sqDiffMat.sum(axis=1)  #求和，把1轴中每个数组中的和 [0.61 0.5  0.5  0.41]

    distance = sqDistance ** 0.5   #对sqDistance进行开方，即获取当前点和其它4个点的距离

    sortedDistanceIndex = distance.argsort()  #对索引排序,对数值从小到大排序

    #存放最终的投票结果

    classCount = {}

    #循环k值对应的次数

    for i in range(k):

        voteIlabel = labels[sortedDistanceIndex[i]]  #根据k值的数量，选出上面排序后，前面的标签名称，即A或者B

        classCount[voteIlabel] = classCount.get(voteIlabel,0)+1 #对相应的标签出现的数量计数

    print(classCount)

    #排序，将次数最多的排到第一的位置

    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

    return sortedClassCount[0][0]  #返回最多值的名称

def show_data(group,labels):

    '''画图'''

    labels = np.array(labels)

    index_a = np.where(labels == "A") #获取A的下标

    index_b = np.where(labels == "B") #获取B的下标

    #画图，A点为红色，B点为绿色

    for i in labels:

        if i == "A":

            plt.scatter(group[index_a][:,:1],group[index_a][:,1:2],c='red')

        elif i == "B":

            plt.scatter(group[index_b][:,:1],group[index_b][:,1:2],c="green")

    plt.show() #显示

if __name__ == '__main__':

    #导入数据

    dataSet,labels = createDataSet()

    #新数据坐标

    inX = [0.5,0.5]

    #定义k值

    k = 3

    className = classify(inX,dataSet,labels,k)  #获取新数据的类型，即标签A或B（前面定义的标签）

    print("该数据属于{}类".format(className))

    dataSet = np.vstack((dataSet,inX)) #把新数据坐标加入数据中

    labels.append(className)  #将新数据的标签加入labels中

    show_data(dataSet,labels) #画图

import numpy as np

import matplotlib.pyplot as plt

# 加载数据

def loadDataSet(fileName):

    data = np.loadtxt(fileName,delimiter='\t')  #按照符号\t分隔

    print(data.shape)   #(10, 2)

    return data

# 欧氏距离计算

def distEclud(x,y):

    return np.sqrt(np.sum((x-y)**2))  # 计算欧氏距离

# 为给定数据集构建一个包含K个随机质心的集合

def randCent(dataSet,k):

    m,n = dataSet.shape #m为数据的个数,n为数据长度

    centroids = np.zeros((k,n))  #创建(k,n)的0数组，用于初始化质心

    print(dataSet[5,:])

    for i in range(k):

        index = int(np.random.uniform(0,m))  #使用uniform均匀分布获取0-m的随机数值

        centroids[i,:] = dataSet[index,:]  #生成质心的坐标

    return centroids  #返回质心的列表坐标

# k均值聚类

def KMeans(dataSet,k):

    m = np.shape(dataSet)[0]  #行的数目

    # 第一列存样本属于哪一簇

    # 第二列存样本的到簇的中心点的误差

    clusterAssment = np.mat(np.zeros((m,2)))  #创建(m, 2)的0数组

    clusterChange = True

    # 第1步 初始化centroids

    centroids = randCent(dataSet,k)

    while clusterChange:

        clusterChange = False

        # 遍历所有的样本（行数）

        for i in range(m):

            minDist = 100000.0

            minIndex = -1

            # 遍历所有的质心

            #第2步 找出最近的质心

            for j in range(k):

                # 计算该样本到质心的欧式距离

                distance = distEclud(centroids[j,:],dataSet[i,:])

                if distance < minDist:

                    minDist = distance

                    minIndex = j

            # 第 3 步：更新每一行样本所属的簇

            if clusterAssment[i,0] != minIndex:

                clusterChange = True

                clusterAssment[i,:] = minIndex,minDist**2

        #第 4 步：更新质心

        for j in range(k):

            pointsInCluster = dataSet[np.nonzero(clusterAssment[:,0] == j)[0]]  # 获取簇类所有的点

            centroids[j,:] = np.mean(pointsInCluster,axis=0)   # 对矩阵的行求均值

    print('===========',centroids)

    print("Congratulations,cluster complete!")

    print(clusterAssment)

    return centroids,clusterAssment  #返回centroids质心坐标，质心对应的聚类结果

def showCluster(dataSet,k,centroids,clusterAssment):

    '''画图显示'''

    m,n = dataSet.shape

    if n != 2:

        print("数据不是二维的")

        return 1

    #定义点的颜色和风格

    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']

    if k > len(mark):

        print("k值太大了")

        return 1

    # 绘制所有的样本

    for i in range(m):

        markIndex = int(clusterAssment[i,0])

        plt.plot(dataSet[i,0],dataSet[i,1],mark[markIndex])

    #定义质心的颜色和风格

    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']

    # 绘制质心

    for i in range(k):

        plt.plot(centroids[i,0],centroids[i,1],mark[i])

    plt.show()

#导入数据

'''

1.65    4.28

-3.45    3.42

4.84    -1.15

-5.37    -3.36

0.97    2.92

-3.57    1.53

0.45    -3.30

-3.49    -1.72

2.67    1.59

-3.16    3.19

'''

if  __name__  == '__main__':

    dataSet = loadDataSet("test.txt")

    print(dataSet)

    #定义质心数

    k = 4

    centroids,clusterAssment = KMeans(dataSet,k)

    showCluster(dataSet,k,centroids,clusterAssment)