神经网络-K-means算法

发表于 | 更新于 | 分类于 ， | 阅读次数：

一、前言

K-means算法是一种分类算法，属于非监督式学习，以下对其原理分析和实现

  • 系统：win10
  • 环境：python3.7

二、K-means原理说明

如下图所示，我们可以很清楚的分辨出这里分为4类，并且可以确定这4类的位置，但是电脑需要如何分辨出来呢？

1566888075614

  • 在图中随机定义4个点A、B、C、D，表示分类（也就是事先知道分为4类）
  • 计算图中每个点和这4个随机点的距离（假设有n个点，需要计算4*n次），每个点选取和他最近的点确定该点属于那个分类。
  • 每个分类（A、B、C、D），根据选择它的数据点的位置，重新调整自己的坐标。
  • 重复上面2~3的过程，直道不再出现数据点变化分类。
  • 上述过程大致可以用下图描述：

1566888850751

使用第四节的代码进行测试，可以得到不错的效果，图片如下：

1567273404177

但是他的结果会波动，不太确定，输出结果和质点的初始化有关，有时候会出现以下结果：

1567273394332

三、二分K-Mean原理说明

根据上面K-Mean所描述的原理，由于是随机定义的中心分类，不同的随机结果很容易导致不同的结果出现，比如几个中心点移动到同一堆数据中（如下图所示），容易陷入局部最优。解决方法可以通过定义多个中心点来达到，但还是存在了一些不稳定的情况。这里介绍K-Mean的二分法。

1566894802309

对K-means的代码进行分析，可以看到，当只分两类的时候才会得到稳定的结果。所以先把原来的质点分为2类，然后对这两类在进行划分（选取效果最好的一类进行再次划分），迭代多次后，可以得到分类的点。对4类进行分类结果如下图：

1567273720088

结果很完美，但是由于其是KMeans的改进版，所以缺点都差不多。下面对5组数据点进行分类，可以看到有明显的缺陷，中间的一组划分明显不好，结果如下图所示：

1567273805316

解决方法是在二分Kmeans结束后，再使用普通kmeans处理一次，重新运行后结果如下：

1567274043866

四、K-mean代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
# -*- coding: utf-8 -*-
# @Time    : 2019/8/27 14:55
# @Author  : zwenc
# @File    : kMeans.py

import numpy as np
import matplotlib.pyplot as plt


def calcEclud(pointA, pointB):
    """
    :param pointA:np.array
    :param pointB:np.array
    :return: numpy.float64
    """
    return np.sqrt(np.sum(np.power(pointA - pointB, 2)))


def initCentCoord(dataSet, k, dim):
    CentCoord = np.zeros([k, dim])

    for i in range(dim):
        CentCoord[:, i] = dataSet[:, i].mean()  # 选择中心点

    for n in range(k):
        for i in range(dim):
            # 在中心点进行一点随机，主要是不能一开始全部选择一个点
            CentCoord[n, i] = CentCoord[n, i] + np.random.randn(1)[0] * 0.01

    return CentCoord


def Kmeans(dataSet, k, disloss=calcEclud, initCentCoord=initCentCoord, preCentCoord = None):
    """
    :param dataSet:       数据
    :param k:             特征点数量
    :param disloss:       损失计算方法
    :param initCentCoord: 初始化中心点的方法，这个会涉及到精确度
    :param preCentCoord:  预训练值（手动设置质点点或者其他训练好的质点）
    :return:              特征点坐标、数据的分类和对应分类的损失
    """
    datalen = dataSet.shape[0]  # 数据长度
    dim = dataSet.shape[1]  # 数据维度
    centCoord = initCentCoord(dataSet, k, dim)  # 初始化特征点
    dataClass = np.zeros([datalen, 2])
    dataClass[:, 0] = k + 1

    # 加载预质点训练值
    if preCentCoord is not None:
        centCoord = preCentCoord

    dataClassChanged = True
    while dataClassChanged:
        dataClassChanged = False
        for i in range(datalen):
            loss = np.inf
            classCoord = np.inf
            for n in range(k):
                loss_local = disloss(centCoord[n, :], dataSet[i, :])  # 计算损失

                if loss_local < loss:
                    loss = loss_local
                    classCoord = n

            if dataClass[i, 0] != classCoord:
                dataClass[i, 0] = classCoord  # 记录每一个数据对应的分类
                dataClass[i, 1] = loss        # 和损失
                dataClassChanged = True

        # 更新质心
        for n in range(k):
            if np.any([dataClass[:, 0] == n]) != False:
                for i in range(dim):
                    centCoord[n, i] = dataSet[dataClass[:, 0] == n, i].mean()

        # 更新误差
        for i in range(datalen):
            loss_local = disloss(centCoord[int(dataClass[i, 0]), :], dataSet[i, :])
            dataClass[i,1] = loss_local

    return centCoord, dataClass

def generateTestData(points, k):
    """
    :param points:  坐标点
    :param k:       干扰系数，越大则点分的越散
    :return:         dataset
    """

    dataSet = []
    for x, y in points:
        for i in range(20):
            randx = np.random.randn(1)[0]
            randy = np.random.randn(1)[0]
            dataSet.append([x + randx * k, y + randy * k])

    return np.array(dataSet)


if __name__ == '__main__':
    while True:
        dataSet = generateTestData([[3, 3], [12, 12], [1, 13], [13,4],[7,8]], 1)
        centCoord, dataClass = Kmeans(dataSet, 5)


        print(dataClass[:,1].mean())

        plt.axis([-1, 20, -1, 15])
        plt.scatter(dataSet[dataClass[:, 0] == 0, 0], dataSet[dataClass[:, 0] == 0, 1], c="b")
        plt.scatter(dataSet[dataClass[:, 0] == 1, 0], dataSet[dataClass[:, 0] == 1, 1], c="g")
        plt.scatter(dataSet[dataClass[:, 0] == 2, 0], dataSet[dataClass[:, 0] == 2, 1], c="y")
        plt.scatter(dataSet[dataClass[:,0] == 3, 0],dataSet[dataClass[:,0] == 3, 1],c = "k")
        plt.scatter(dataSet[dataClass[:,0] == 4, 0],dataSet[dataClass[:,0] == 4, 1])
        plt.scatter(centCoord[:, 0], centCoord[:, 1], c="r")
        plt.show()

五、二分K-mean代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
# -*- coding: utf-8 -*-
# @Time    : 2019/8/29 20:18
# @Author  : zwenc
# @File    : Kmeans2.py
import numpy as np
import matplotlib.pyplot as plt


def calcEclud(pointA, pointB):
    """
    :param pointA:np.array
    :param pointB:np.array
    :return: numpy.float64
    """
    return np.sqrt(np.sum(np.power(pointA - pointB, 2)))


def initCentCoord(dataSet, k, dim):
    CentCoord = np.zeros([k, dim])

    for i in range(dim):
        CentCoord[:, i] = dataSet[:, i].mean()  # 选择中心点

    for n in range(k):
        for i in range(dim):
            # 在中心点进行一点随机，主要是不能一开始全部选择一个点
            CentCoord[n, i] = CentCoord[n, i] + np.random.randn(1)[0] * 0.01

    return CentCoord


def Kmeans(dataSet, k, disloss=calcEclud, initCentCoord=initCentCoord, preCentCoord = None):
    """
    :param dataSet:       数据
    :param k:             特征点数量
    :param disloss:       损失计算方法
    :param initCentCoord: 初始化中心点的方法，这个会涉及到精确度
    :param preCentCoord:  预训练值（手动设置质点点或者其他训练好的质点）
    :return:              特征点坐标、数据的分类和对应分类的损失
    """
    datalen = dataSet.shape[0]  # 数据长度
    dim = dataSet.shape[1]  # 数据维度
    centCoord = initCentCoord(dataSet, k, dim)  # 初始化特征点
    dataClass = np.zeros([datalen, 2])
    dataClass[:, 0] = k + 1

    # 加载预质点训练值
    if preCentCoord is not None:
        centCoord = preCentCoord

    dataClassChanged = True
    while dataClassChanged:
        dataClassChanged = False
        for i in range(datalen):
            loss = np.inf
            classCoord = np.inf
            for n in range(k):
                loss_local = disloss(centCoord[n, :], dataSet[i, :])  # 计算损失

                if loss_local < loss:
                    loss = loss_local
                    classCoord = n

            if dataClass[i, 0] != classCoord:
                dataClass[i, 0] = classCoord  # 记录每一个数据对应的分类
                dataClass[i, 1] = loss        # 和损失
                dataClassChanged = True

        # 更新质心
        for n in range(k):
            if np.any([dataClass[:, 0] == n]) != False:
                for i in range(dim):
                    centCoord[n, i] = dataSet[dataClass[:, 0] == n, i].mean()

        # 更新误差
        for i in range(datalen):
            loss_local = disloss(centCoord[int(dataClass[i, 0]), :], dataSet[i, :])
            dataClass[i,1] = loss_local

    return centCoord, dataClass


def Kmeans2(dataSet, k, disloss=calcEclud, initCentCoord=initCentCoord):
    dim = dataSet.shape[1]
    centerCoords = np.zeros([k, dim])
    centCoord, dataClass = Kmeans(dataSet, 1, disloss, initCentCoord)
    centerCoords[0, :] = centCoord[0]

    nk = 1
    while nk < k:
        Loss = np.inf
        bestIndex = np.inf

        for index in range(nk):
            DataChoosed = dataSet[dataClass[:, 0] == index, :]


            newcentCoord, newdataClass = Kmeans(DataChoosed, 2, disloss, initCentCoord)
            newDataLoss = np.sum(newdataClass[:, 1])
            DataNotChoosedLoss = np.sum(dataClass[dataClass[:, 0] != index, 1])

            if (newDataLoss + DataNotChoosedLoss) < Loss:
                Loss = (newDataLoss + DataNotChoosedLoss)
                bestIndex = index
                bestCenterCoord = newcentCoord
                bestDataClass = newdataClass

        centerCoords[bestIndex, :] = bestCenterCoord[0, :]
        centerCoords[nk, :] = bestCenterCoord[1, :]

        bestDataClass[bestDataClass[:,0] != 0, 0] = nk
        bestDataClass[bestDataClass[:,0] == 0, 0] = bestIndex

        dataClass[dataClass[:, 0] == bestIndex, :] = bestDataClass[:, :]
        nk = nk + 1

    centerCoords, dataClass = Kmeans(dataSet, 5, preCentCoord=centerCoords)
    return centerCoords, dataClass


def generateTestData(points, k):
    """
    :param points:  坐标点
    :param k:       干扰系数，越大则点分的越散
    :return:         dataset
    """

    dataSet = []
    for x, y in points:
        for i in range(20):
            randx = np.random.randn(1)[0]
            randy = np.random.randn(1)[0]
            dataSet.append([x + randx * k, y + randy * k])

    return np.array(dataSet)


if __name__ == '__main__':
    while True:
        dataSet = generateTestData([[3, 3], [12, 12], [1, 13], [13,4],[7,8]], 1)
        centCoord, dataClass = Kmeans2(dataSet, 5)


        print(dataClass[:,1].mean())

        plt.axis([-1, 20, -1, 15])
        plt.scatter(dataSet[dataClass[:, 0] == 0, 0], dataSet[dataClass[:, 0] == 0, 1], c="b")
        plt.scatter(dataSet[dataClass[:, 0] == 1, 0], dataSet[dataClass[:, 0] == 1, 1], c="g")
        plt.scatter(dataSet[dataClass[:, 0] == 2, 0], dataSet[dataClass[:, 0] == 2, 1], c="y")
        plt.scatter(dataSet[dataClass[:,0] == 3, 0],dataSet[dataClass[:,0] == 3, 1],c = "k")
        plt.scatter(dataSet[dataClass[:,0] == 4, 0],dataSet[dataClass[:,0] == 4, 1])
        plt.scatter(centCoord[:, 0], centCoord[:, 1], c="r")
        plt.show()
-------------本文结束感谢您的阅读-------------
0%