机器学习 --- k-means

k-means是属于机器学习里面的非监督学习，通常是大家接触到的第一个聚类算法，其原理非常简单，是一种典型的基于距离的聚类算法。
聚类算法中，将相似的数据划分为一个集合，一个集合称为一个簇。 k-means（k均值）聚类，之所以称为 k均值，是因为它可以发现k个簇，且每个簇的中心采用簇中所含值的均值计算而成。
本实训项目将基于Python语言搭建出一个k-means模型，并基于sklean实现对红酒数据进行聚类。

第1关：距离度量

任务描述
本关任务：使用Python编写一个能计算样本间欧式距离与曼哈顿距离的方法。

相关知识
为了完成本关任务，你需要掌握：1.欧氏距离，2.曼哈顿距离。

欧氏距离
欧氏距离是最容易直观理解的距离度量方法，我们小学、初中和高中接触到的两个点在空间中的距离一般都是指欧氏距离。

曼哈顿距离
顾名思义，在曼哈顿街区要从一个十字路口开车到另一个十字路口，驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。曼哈顿距离也称为“城市街区距离”。

编程要求
请仔细阅读右侧代码，结合相关知识，在 Begin-End 区域内进行代码补充，完成使用Python编写一个能计算样本间欧式距离与曼哈顿距离的方法。

测试说明
平台会对你的代码进行运行测试，如果实际输出结果与预期结果相同，则通关；反之，则 GameOver。

#encoding=utf8    
import numpy as np
def distance(x,y,p=2):
    '''
    input:x(ndarray):第一个样本的坐标
          y(ndarray):第二个样本的坐标
          p(int):等于1时为曼哈顿距离，等于2时为欧氏距离
    output:distance(float):x到y的距离      
    ''' 
    #********* Begin *********#
    dis2 = np.sum(np.abs(x-y)**p)
    dis = np.power(dis2,1/p)
    return dis
    #********* End *********#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第2关：什么是质心

任务描述
本关任务：使用Python编写一个能计算质心的方法。

相关知识
为了完成本关任务，你需要掌握：1.欧氏距离。

欧氏距离
欧氏距离是最容易直观理解的距离度量方法，我们小学、初中和高中接触到的两个点在空间中的距离一般都是指欧氏距离。

编程要求
请仔细阅读右侧代码，结合相关知识，在 Begin-End 区域内进行代码补充，完成质心的计算。

测试说明
平台会对你的代码进行运行测试，如果实际输出结果与预期结果相同，则通关；反之，则 GameOver。

#encoding=utf8
import numpy as np
#计算样本间距离
def distance(x, y, p=2):
    '''
    input:x(ndarray):第一个样本的坐标
          y(ndarray):第二个样本的坐标
          p(int):等于1时为曼哈顿距离，等于2时为欧氏距离
    output:distance(float):x到y的距离      
    '''
    #********* Begin *********#    
    dis2 = np.sum(np.abs(x-y)**p)
    dis = np.power(dis2,1/p)
    return dis
    #********* End *********#
#计算质心
def cal_Cmass(data):
    '''
    input:data(ndarray):数据样本
    output:mass(ndarray):数据样本质心
    '''
    #********* Begin *********#
    Cmass = np.mean(data,axis=0)
    #********* End *********#
    return Cmass
#计算每个样本到质心的距离，并按照从小到大的顺序排列
def sorted_list(data,Cmass):
    '''
    input:data(ndarray):数据样本
          Cmass(ndarray):数据样本质心
    output:dis_list(list):排好序的样本到质心距离
    '''
    #********* Begin *********#
    dis_list = []
    for i in range(len(data)):
        dis_list.append(distance(Cmass,data[i][:]))
    dis_list = sorted(dis_list)
    #********* End *********#
    return dis_list

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

第3关：k-means算法流程

任务描述
本关任务：使用Python实现k-means算法，并根据红酒的13个特征对红酒数据进行聚类。

相关知识
为了完成本关任务，你需要掌握：1.k-means算法原理，2.k-means算法流程，3.如何确定k的值。

数据集介绍
数据集为一份红酒数据，一共有178个样本，每个样本有13个特征，这里不会提供你红酒的标签，你需要自己根据这13个特征对红酒进行聚类，部分数据如下图：

编程要求
请仔细阅读右侧代码，结合相关知识，在 Begin-End 区域内进行代码补充，完使用Python实现k-means算法的任务。

测试说明
平台会对你的代码进行运行测试，如果实际输出结果与预期结果相同，则通关；反之，则 GameOver。

# encoding=utf8
import numpy as np


# 计算一个样本与数据集中所有样本的欧氏距离的平方
def euclidean_distance(one_sample, X):
    one_sample = one_sample.reshape(1, -1)
    distances = np.power(np.tile(one_sample, (X.shape[0], 1)) - X, 2).sum(axis=1)
    return distances


def cal_dis(old_centroids, centroids):
    dis = 0
    for i in range(old_centroids.shape[0]):
        dis += np.linalg.norm(old_centroids[i] - centroids[i], 2)
    return dis


class Kmeans():
    """Kmeans聚类算法.
    Parameters:
    -----------
    k: int
        聚类的数目.
    max_iterations: int
        最大迭代次数.
    varepsilon: float
        判断是否收敛, 如果上一次的所有k个聚类中心与本次的所有k个聚类中心的差都小于varepsilon,
        则说明算法已经收敛
    """

    def __init__(self, k=2, max_iterations=500, varepsilon=0.0001):
        self.k = k
        self.max_iterations = max_iterations
        self.varepsilon = varepsilon
        np.random.seed(1)

    # ********* Begin *********#
    # 从所有样本中随机选取self.k样本作为初始的聚类中心
    def init_random_centroids(self, X):
        m, n = X.shape
        center = np.zeros((self.k, n))
        for i in range(self.k):
            index = int(np.random.uniform(0, m))
            center[i] = X[index]
        return center

    # 返回距离该样本最近的一个中心索引[0, self.k)
    def _closest_centroid(self, sample, centroids):
        distances = euclidean_distance(sample, centroids)
        return np.argsort(distances)[0]

    # 将所有样本进行归类，归类规则就是将该样本归类到与其最近的中心
    def create_clusters(self, centroids, X):
        m, n = X.shape
        clusters = np.mat(np.zeros((m, 1)))
        for i in range(m):
            index = self._closest_centroid(X[i], centroids)
            clusters[i] = index
        return clusters

    # 对中心进行更新
    def update_centroids(self, clusters, X):
        centroids = np.zeros([self.k, X.shape[1]])
        for i in range(self.k):
            pointsInCluster = []
            for j in range(clusters.shape[0]):
                if clusters[j] == i:
                    pointsInCluster.append(X[j])
            centroids[i] = np.mean(pointsInCluster, axis=0)  # 对矩阵的行求均值
        return centroids

    # 将所有样本进行归类，其所在的类别的索引就是其类别标签
    def get_cluster_labels(self, clusters, X):
        return

    # 对整个数据集X进行Kmeans聚类，返回其聚类的标签
    def predict(self, X):
        # 从所有样本中随机选取self.k样本作为初始的聚类中心
        centroids = self.init_random_centroids(X)
        clusters = []
        iter = 0
        # 迭代，直到算法收敛(上一次的聚类中心和这一次的聚类中心几乎重合)或者达到最大迭代次数
        while iter < self.max_iterations:
            iter += 1

            # 将所有进行归类，归类规则就是将该样本归类到与其最近的中心
            clusters = self.create_clusters(centroids, X)

            # 计算新的聚类中心
            old_centroids = centroids[:]
            centroids = self.update_centroids(clusters, X)
            if cal_dis(old_centroids, centroids) < self.varepsilon:
                break

            # 如果聚类中心几乎没有变化，说明算法已经收敛，退出迭代
        return np.array(clusters).reshape([X.shape[0], ])

    # ********* End *********#

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

第4关：sklearn中的k-means

任务描述
本关任务：：你需要调用 sklearn 中的K-means模型，对红酒数据进行聚类。

相关知识
为了完成本关任务，你需要掌握：1.KMeans。

数据集介绍
数据集为一份红酒数据，一共有178个样本，每个样本有13个特征，这里不会提供你红酒的标签，你需要自己根据这13个特征对红酒进行聚类，部分数据如下图：

编程要求
请仔细阅读右侧代码，结合相关知识，在 Begin-End 区域内进行代码补充，完使用 sklearn 中的K-means模型实现红酒聚类任务。

测试说明
平台会对你的代码进行运行测试，如果实际输出结果与预期结果相同，则通关；反之，则 GameOver。

#encoding=utf8
from sklearn.cluster import KMeans
def kmeans_cluster(data):
    '''
    input:data(ndarray):样本数据
    output:result(ndarray):聚类结果
    '''
    #********* Begin *********#
    km = KMeans(n_clusters=3,random_state=888)
    result = km.fit_predict(data)
    #********* End *********# 
    return result

1
2
3
4
5
6
7
8
9
10
11
12
13

欢迎大家加我微信学习讨论