用Python实现机器学习算法—— K均值聚类算法

Python 被称为是最接近 AI 的语言。最近一位名叫Anna-Lena Popkes（德国波恩大学计算机科学专业的研究生，主要关注机器学习和神经网络）的小姐姐在GitHub上分享了自己如何使用Python（3.6及以上版本）实现7种机器学习算法的笔记，并附有完整代码。所有这些算法的实现都没有使用其他机器学习库。这份笔记可以帮大家对算法以及其底层结构有个基本的了解，但并不是提供最有效的实现。

K-Means 是一种非常简单的聚类算法(聚类算法都属于无监督学习)。给定固定数量的聚类和输入数据集，该算法试图将数据划分为聚类，使得聚类内部具有较高的相似性，聚类与聚类之间具有较低的相似性。

算法原理

1. 初始化聚类中心，或者在输入数据范围内随机选择，或者使用一些现有的训练样本(推荐)

2. 直到收敛

• 将每个数据点分配到最近的聚类。点与聚类中心之间的距离是通过欧几里德距离测量得到的。
• 通过将聚类中心的当前估计值设置为属于该聚类的所有实例的平均值，来更新它们的当前估计值。

目标函数

聚类算法的目标函数试图找到聚类中心，以便数据将划分到相应的聚类中，并使得数据与其最接近的聚类中心之间的距离尽可能小。

给定一组数据X1，...，Xn和一个正数k，找到k个聚类中心C1，...，Ck并最小化目标函数：

这里：

• 决定了数据点是否属于类
• 表示类的聚类中心
• 表示欧几里得距离

K-Means 算法的缺点：

• 聚类的个数在开始就要设定
• 聚类的结果取决于初始设定的聚类中心
• 对异常值很敏感
• 不适合用于发现非凸聚类问题
• 该算法不能保证能够找到全局最优解，因此它往往会陷入一个局部最优解

In [21]:

import numpy as np
import matplotlib.pyplot as plt
import random
from sklearn.datasets import make_blobs
np.random.seed(123)

% matplotlib inline

数据集

In [22]:

X, y = make_blobs(centers=4, n_samples=1000)
print(f'Shape of dataset: {X.shape}')

fig = plt.figure(figsize=(8,6))
plt.scatter(X[:,0], X[:,1], c=y)
plt.title("Dataset with 4 clusters")
plt.xlabel("First feature")
plt.ylabel("Second feature")
plt.show()

Shape of dataset: (1000, 2)

K均值分类

In [23]:

class KMeans():
    def __init__(self, n_clusters=4):
        self.k = n_clusters

    def fit(self, data):
        """
        Fits the k-means model to the given dataset
        """
        n_samples, _ = data.shape
        # initialize cluster centers
        self.centers = np.array(random.sample(list(data), self.k))
        self.initial_centers = np.copy(self.centers)

        # We will keep track of whether the assignment of data points
        # to the clusters has changed. If it stops changing, we are 
        # done fitting the model
        old_assigns = None
        n_iters = 0

        while True:
            new_assigns = [self.classify(datapoint) for datapoint in data]

            if new_assigns == old_assigns:
                print(f"Training finished after {n_iters} iterations!")
                return

            old_assigns = new_assigns
            n_iters += 1

            # recalculate centers
            for id_ in range(self.k):
                points_idx = np.where(np.array(new_assigns) == id_)
                datapoints = data[points_idx]
                self.centers[id_] = datapoints.mean(axis=0)

    def l2_distance(self, datapoint):
        dists = np.sqrt(np.sum((self.centers - datapoint)**2, axis=1))
        return dists

    def classify(self, datapoint):
        """
        Given a datapoint, compute the cluster closest to the
        datapoint. Return the cluster ID of that cluster.
        """
        dists = self.l2_distance(datapoint)
        return np.argmin(dists)

    def plot_clusters(self, data):
        plt.figure(figsize=(12,10))
        plt.title("Initial centers in black, final centers in red")
        plt.scatter(data[:, 0], data[:, 1], marker='.', c=y)
        plt.scatter(self.centers[:, 0], self.centers[:,1], c='r')
        plt.scatter(self.initial_centers[:, 0], self.initial_centers[:,1], c='k')
        plt.show()

初始化并调整模型

kmeans = KMeans(n_clusters=4)
kmeans.fit(X)

Training finished after 4 iterations!

描绘初始和最终的聚类中心

kmeans.plot_clusters(X)