KNN And K-means Algorithm

Posted on | Edited on | In | Views:

K-means方法是一种非监督学习的算法，它解决的是聚类问题。

1、算法简介：K-means方法是聚类中的经典算法，数据挖掘十大经典算法之一；算法接受参数k,然后将事先输入的n个数据对象划分为k个聚类以便使得所获得的聚类满足聚类中的对象相似度较高，而不同聚类中的对象相似度较小。

2、算法思想：以空间中k个点为中心进行聚类，对最靠近他们的对象归类，通过迭代的方法，逐次更新各聚类中心的值，直到得到最好的聚类结果。

3、算法描述：

（1）适当选择c个类的初始中心；
（2）在第k次迭代中，对任意一个样本，求其到c各中心的距离，将该样本归到距离最短的那个中心所在的类；
（3）利用均值等方法更新该类的中心值；
（4）对于所有的C个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束；否则继续迭代。

4、算法举例：

我们假设药物A、B、C、D有两个特征值，分别是药物重量以及PH值。

药物名称 药物重量 药物PH值
A 1 1
B 2 1
C 4 3
D 5 4

现在我们要对这四个药物进行聚类，已知我们要分成两类，那么我们该怎么做呢？

首先我们把上面的数据画到二位坐标系当中 A(1,1),B(2,1),C(4,3),D(5,4):

这里写图片描述

初始时，由于假设K=2 (表示将所有数据集分为两组，我们称之为聚类) 我们先假设药物A为聚类1的中心点，B为聚类2的中心点。
那么初始时的中心坐标分别为c1=(1,1),c2=(2,1)c1=(1,1),c2=(2,1)，矩阵D的第一行代表各个点到中心点c1的距离，第二行代表各个点到中心点c2的距离；那么初始矩阵D0表示成如下：
矩阵 D0向我们展示了除了中心点之外的其他所有点距离K个中心点的距离大小，每个点距离各个中心点的距离都不尽相同。所谓近水楼台先得月，所以将点归入离点最近的中心点一类。以后每开始一次的迭代，都会重新算出每个聚类的中心点，然后根据相同的操作进行点的归类，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止。
矩阵G0代表样本应该归属于哪个聚类，第一行代表各个点是否属于中心c1所在的类（0代表不在，1代表在），第二行代表各个点是否属于中心c2所在的类（0代表不在，1代表在）；那么此时G0表示成如下：
由矩阵D0可知A药物属于一个类，B、C、D属于一类；
然后，利用均值等方法更新该类的中心值。
c1=（1,1）
c2=（(2+4+5)/3,(1+3+4)/3）= (13/3,8/3)

这里写图片描述

上图是更新后的坐标图，对应的中心点也发生了变化。
因为中心点跟上次不一样了，所以我们又可以对样本点进行重新划分。划分的方法还是跟以前一模一样，我们先计算出矩阵D1表示成如下：
此时G1表示成如下：
由矩阵G1可知A、B药物属于一个类，C、D属于一类；
然后，利用均值等方法再次更新该类的中心值。
c1=（(1+2)/2,(1+1)/2）=(1.5,1)
c2=（(4+5)/2,(3+4)/2）=(4.5,3.5)

这里写图片描述

上图是更新后的坐标图，对应的中心点也发生了变化。

因为中心点跟上次不一样了，所以我们又可以对样本点进行重新划分。划分的方法还是跟以前一模一样，我们先计算出矩阵D2表示成如下：

此时G2表示成如下：

由矩阵G2可知A、B药物属于一个类，C、D属于一类；
然后，利用均值等方法再次更新该类的中心值。
c1=（(1+2)/2,(1+1)/2）=(1.5,1)
c2=（(4+5)/2,(3+4)/2）=(4.5,3.5)
因为对应的中心点并没有发生变化，所以迭代停止，计算完毕。

本算法的时间复杂度：O(tkmn)，其中，t为迭代次数，k为簇的数目，m为记录数，n为维数；

空间复杂度：O((m+k)n)，其中，k为簇的数目，m为记录数，n为维数。

适用范围:

K-means算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tkmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。

缺点：

1、聚类中心的个数K 需要事先给定，但在实际中这个 K 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适；

2、K-means需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。（可以使用K-means++算法来解决）

K-means 算法代码实现： 

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
import numpy as np
from matplotlib import pyplot


class K_Means(object):
    # k是分组数；tolerance为'中心点误差'；max_iter是最大迭代次数
    # 类构造方法
    def __init__(self, k=2, tolerance=0.0001, max_iter=300):
        self.k_ = k
        self.tolerance_ = tolerance
        self.max_iter_ = max_iter

    def fit(self, data):
        self.centers_ = {}  # 中心点集合
        for i in range(self.k_):
            self.centers_[i] = data[i]

        for i in range(self.max_iter_):
            self.clf_ = {} # 定义为字典，每一类都有一个名称
            for i in range(self.k_):
                self.clf_[i] = []  # 聚类字典，根据k组数确定最大长度

            # print("此时的中心点集合: ",self.centers_)

            # 遍历样本所有点
            for feature in data:
                # distances = [np.linalg.norm(feature-self.centers[center]) for center in self.centers]
                distances = []
                # 对每个样本点，遍历所有中心点，计算它与每个聚类的中心的距离，然后取最小距离进行归类
                for center in self.centers_:
                    # 欧拉距离
                    # 可使用np.sqrt(np.sum((features-self.centers_[center])**2))计算距离
                    # norm()可以直接计算出距离
                    distances.append(np.linalg.norm(feature - self.centers_[center]))
                # 在distances中取最小距离
                classification = distances.index(min(distances)) # 返回最小距离在distances数组中的下标
                self.clf_[classification].append(feature) # 将点加入clf_数组相应位置

            # print("分组情况:",self.clf_)
            prev_centers = dict(self.centers_)  # 复制centers_字典
            # print(prev_centers) # {0: array([1., 2.]), 1: array([1.5, 1.8])} → {0: array([1., 2.]), 1: array([4.9 , 5.88])}
            # print(self.clf_)
            # {0: [array([1., 2.])],1: [array([1.5, 1.8]), array([5., 8.]), array([8., 8.]), array([1., 0.6]), array([9., 11.])]}
            # {0: [array([1., 2.]), array([1.5, 1.8]), array([1., 0.6])],1: [array([5., 8.]), array([8., 8.]), array([9., 11.])]}
            # {0: [array([1., 2.]), array([1.5, 1.8]), array([1., 0.6])],1: [array([5., 8.]), array([8., 8.]), array([9., 11.])]}
            # 根据聚类名遍历每个聚类
            for c in self.clf_:
                # print(c)  0 1
                # 取每个聚类的均值作为正在遍历的类的新中心点，axis=0为二维数组纵向取均值
                self.centers_[c] = np.average(self.clf_[c], axis=0)

            # '中心点'是否在误差范围
            optimized = True
            # 根据聚类名遍历每个聚类
            # print("prev")
            # print(prev_centers)
            # # print("centers")
            # print(self.centers_)
            for center in self.centers_:
                org_centers = prev_centers[center]
                cur_centers = self.centers_[center]
                # 比较类上次的中心点以及本次计算的中心点的差值，计算偏差
                if np.sum((cur_centers - org_centers) / org_centers * 100.0) > self.tolerance_:
                    optimized = False
            if optimized:
                break

    # 预测数据所属的聚类，根据所测点距中心点的大小进行判定
    def predict(self, p_data):
        distances = [np.linalg.norm(p_data - self.centers_[center]) for center in self.centers_]
        index = distances.index(min(distances))
        return index


if __name__ == '__main__':

    x = np.array([[1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11]])

    k_means = K_Means(k=2)
    k_means.fit(x)

    # 打印最终的中心点
    # print(k_means.centers_)  # {0: array([1.16666667, 1.46666667]), 1: array([7.33333333, 9.        ])}
    for center in k_means.centers_:
        # 将最终的中心点使用五角星标志出来
        pyplot.scatter(k_means.centers_[center][0], k_means.centers_[center][1], marker='*', s=150)

    # 遍历每个聚类的所有点
    for cat in k_means.clf_:
        for point in k_means.clf_[cat]:
            pyplot.scatter(point[0], point[1], c=('r' if cat == 0 else 'b'))

    # 预测数据
    predict = [[2, 1], [6, 9]]
    for feature in predict:
        # 获取聚类所在的下标
        cat = k_means.predict(predict)
        # 参数依次为坐标x,y,使用字母代号表示的颜色，以及显示的样式（为x表示是x号）
        pyplot.scatter(feature[0], feature[1], c=('r' if cat == 0 else 'b'), marker='x')
        
    pyplot.show()

执行结果：

使用Python实现K-Means算法

K-Means算法需要你指定K值，也就是需要人为指定数据应该分为几组。下一帖我会实现Mean Shift算法，它也是一种聚类算法(Hierarchical)，和K-Means(Flat)不同的是它可以自动判断数据集应该分为几组。

在实际数据上应用K-Means算法

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
import numpy as np
from sklearn.cluster import KMeans
from sklearn import preprocessing
import pandas as pd
 
'''
数据集：titanic.xls(泰坦尼克号遇难者/幸存者名单)
<http://blog.topspeedsnail.com/wp-content/uploads/2016/11/titanic.xls>
***字段***
pclass: 社会阶层(1，精英；2，中产；3，船员/劳苦大众)
survived: 是否幸存
name: 名字
sex: 性别
age: 年龄
sibsp: 哥哥姐姐个数
parch: 父母儿女个数
ticket: 船票号
fare: 船票价钱
cabin: 船舱
embarked
boat
body: 尸体
home.dest
******
目的：使用除survived字段外的数据进行k-means分组（分成两组:生/死），然后和survived字段对比，看看分组效果。
'''
 
# 加载数据
df = pd.read_excel('titanic.xls')
#print(df.shape)  (1309, 14)
#print(df.head())
#print(df.tail())
"""
    pclass  survived                                            name     sex  \
0       1         1                    Allen, Miss. Elisabeth Walton  female
1       1         1                   Allison, Master. Hudson Trevor    male
2       1         0                     Allison, Miss. Helen Loraine  female
3       1         0             Allison, Mr. Hudson Joshua Creighton    male
4       1         0  Allison, Mrs. Hudson J C (Bessie Waldo Daniels)  female
    
       age  sibsp  parch  ticket      fare    cabin embarked boat   body  \
0  29.0000      0      0   24160  211.3375       B5        S    2    NaN
1   0.9167      1      2  113781  151.5500  C22 C26        S   11    NaN
2   2.0000      1      2  113781  151.5500  C22 C26        S  NaN    NaN
3  30.0000      1      2  113781  151.5500  C22 C26        S  NaN  135.0
4  25.0000      1      2  113781  151.5500  C22 C26        S  NaN    NaN
    
    home.dest
0                     St Louis, MO
1  Montreal, PQ / Chesterville, ON
2  Montreal, PQ / Chesterville, ON
3  Montreal, PQ / Chesterville, ON
4  Montreal, PQ / Chesterville, ON
"""
 
# 去掉无用字段
df.drop(['body','name','ticket'], 1, inplace=True)
 
df.convert_objects(convert_numeric=True)
df.fillna(0, inplace=True)  # 把NaN替换为0
 
# 把字符串映射为数字，例如{female:1, male:0}
df_map = {}  # 保存映射关系
cols = df.columns.values
for col in cols:
    if df[col].dtype != np.int64 and df[col].dtype != np.float64:
        temp = {}
        x = 0
        for ele in set(df[col].values.tolist()):
            if ele not in temp:
                temp[ele] = x
                x += 1
 
        df_map[df[col].name] = temp
        df[col] = list(map(lambda val:temp[val], df[col]))
 
#for key, value in df_map.iteritems():
#    print(key,value)
#print(df.head())
 
# 由于是非监督学习，不使用label
x = np.array(df.drop(['survived'],1 ).astype(float))
x = preprocessing.scale(x)
 
clf = KMeans(n_clusters=2)
clf.fit(x)
# 上面已把数据分成两组
 
# 下面计算分组准确率是多少
y = np.array(df['survived'])
 
correct = 0
for i in range(len(x)):
    predict_data = np.array(x[i].astype(float))
    predict_data = predict_data.reshape(-1, len(predict_data))
    predict = clf.predict(predict_data)
    #print(predict[0], y[i])
    if predict[0] == y[i]:
        correct+=1
 
print(correct*1.0/len(x))

执行结果：

1
2
3
4
5
6
7
$ python sk_kmeans.py 
0.692131398014  # 泰坦尼克号的幸存者和遇难者并不是随机分布的，在很大程度上取决于年龄、性别和社会地位
$ python sk_kmeans.py 
0.307868601986  # 结果出现很大波动，原因是它随机分配组(生:0,死:1）(生:1,死:0）
                # 1-0.307868601986是实际值
$ python sk_kmeans.py 
0.692131398014

K-means、和KNN算法比较

KNN(K-Nearest Neighbor)介绍

算法思路：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

看下面这幅图：

这里写图片描述

KNN的算法过程是是这样的：
　　从上图中我们可以看到，图中的数据集是良好的数据，即都打好了label，一类是蓝色的正方形，一类是红色的三角形，那个绿色的圆形是我们待分类的数据。
　　如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形
　　如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形
　　我们可以看到，KNN本质是基于一种数据统计的方法！其实很多机器学习算法也是基于数据统计的。
　　KNN是一种memory-based learning，也叫instance-based learning，属于lazy learning。即它没有明显的前期训练过程，而是程序开始运行时，把数据集加载到内存后，不需要进行训练，就可以开始分类了。
　　具体是每次来一个未知的样本点，就在附近找K个最近的点进行投票。

代码实现：

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
# k-近邻算法根据特征比较，然后提取样本集中特征最相似数据(最邻近)的分类标签
# 假设样本有两个特征，那么大致从样本集分布的散点图判断，也就是二维空间来体现它们的位置关系
# 这时采用点与点的距离可以计算出特定点与其他点的距离远近并加以排序，我们就可以知道谁离它最近了
# 在从前k名最近的点中判断属于特征1和特征2的点的比例，比例大的特征为该特定点的特征
# 所以k-近邻算法的步骤如下：
# 计算已知类别数据集中的点与当前点之间的距离；
# 按照距离递增次序排序；
# 选取与当前点距离最小的k个点；
# 确定前k个点所在类别的出现频率；
# 返回前k个点所出现频率最高的类别作为当前点的预测分类。
"""
函数说明：创建数据集
Parameters:
    无
Returns:
    dataset - 数据集
    labels - 分类标签
"""
import  numpy as np
import operator
def createDataSet():
    dataset=np.array([[1,101],[5,89],[108,5],[115,8]])
    labels=['爱情片','爱情片','动作片','动作片']
    return dataset,labels

"""
函数说明：KNN算法，分类器
Parameters:
    inX - 用于分类的特定数据(测试集)
    dataSet - 用于训练的数据(训练集)
    labes - 分类标签
    k - kNN算法参数,选择距离最小的k个点
Returns:
    sortedClassCount[0][0] - 分类结果
"""
def classfy(inX,dataSet,labels,k):
    # 返回数据集的行数
    dataSetSize=dataSet.shape[0]
    # 使用tile数组实现inX的多行复制，满足矩阵相减的条件
    diffMat=np.tile(inX,(dataSetSize,1))-dataSet
    # 计算距离（矩阵各行取平方和，最后开方）
    # 使用sum函数中的axis参数可以决定按行（1）相加
    distances=((diffMat**2).sum(axis=1))**0.5
    # 返回索引排序
    sortedDistIndies=distances.argsort()
    # 记录类别次数
    classCount={}
    # 取出前k个元素的类别
    for i in range(k):
        # 根据索引获取类别值
        voteIlabel = labels[sortedDistIndies[i]]
        # dict.get(key,default=None)，在classCount字典里查找类别，如果没有则返回1
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
    # reverse降序排序字典
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

if __name__=='__main__':
    # 创建数据集
    dataset,labels=createDataSet()
    # 打印数据集
    # print(dataset)
    # print(labels)

    # 测试集
    test=[101,20]
    test_class=classfy(test,dataset,labels,3)

    #打印分类结果
    print(test_class)

总结：

KNN和K-Means的区别

KNN计算方法为：

1计算测试数据与各个训练数据之间的距离；

2按照距离的递增关系进行排序；

3选取距离最小的K个点；

4确定前K个点所在类别的出现频率；

5返回前K个点中出现频率最高的类别作为测试数据的预测分类。

K-means的计算方法为：

1 随机选取k个中心点；

2 遍历所有数据，将每个数据划分到最近的中心点中；

3 计算每个聚类的平均值，并作为新的中心点 ；

4 重复2-3，直到这k个中线点不再变化（收敛了），或执行了足够多的迭代。

不要投钱给我
0%