机器学习之K-means及其python实现

k-Means算法是一种聚类算法,它是一种无监督学习算法,目的是将相似的对象归到同一个蔟中。蔟内的对象越相似,聚类的效果就越好。聚类和分类最大的不同在于,分类的目标事先已知,而聚类则不一样。其产生的结果和分类相同,而只是类别没有预先定义。

算法原理

设计的目的:使各个样本与所在簇的质心的均值的误差平方和达到最小(这也是评价K-means算法最后聚类效果的评价标准)。

K-均值聚类

  • 优点:容易实现
  • 缺点:可能收敛到局部最小值,在大规模数据上收敛较慢
  • 适合数据类型:数值型数据

    步骤

  1. 创建k个点作为k个簇的起始质心(经常随机选择)。
  2. 分别计算剩下的元素到k个簇中心的相异度(距离),将这些元素分别划归到相异度最低的簇。
  3. 根据聚类结果,重新计算k个簇各自的中心,计算方法是取簇中所有元素各自维度的算术平均值。
  4. 将D中全部元素按照新的中心重新聚类。
  5. 重复第4步,直到聚类结果不再变化。
  6. 最后,输出聚类结果。

    算法实现

    伪代码

    创建k个点作为K个簇的起始质心(经常随机选择)
    当任意一个点的蔟分配结果发生变化时(初始化为True)

    对数据集中的每个数据点,重新分配质心
        对每个质心
            计算质心到数据点之间的距离
        将数据点分配到距其最近的蔟
    对每个蔟,计算蔟中所有点的均值并将均值作为新的质心
    

    具体代码

    class KMeans():

    def __init__(self, k=2, max_iterations=500):
        self.k = k
        self.max_iterations = max_iterations
    
    # Initialize the centroids as random samples
    def _init_random_centroids(self, X):
        n_samples, n_features = np.shape(X)
        centroids = np.zeros((self.k, n_features))
        for i in range(self.k):
            centroid = X[np.random.choice(range(n_samples))]
            centroids[i] = centroid
        return centroids
    
    # Return the index of the closest centroid to the sample
    def _closest_centroid(self, sample, centroids):
        closest_i = None
        closest_distance = float("inf")
        for i, centroid in enumerate(centroids):
            distance = euclidean_distance(sample, centroid)
            if distance < closest_distance:
                closest_i = i
                closest_distance = distance
        return closest_i
    
    # Assign the samples to the closest centroids to create clusters
    def _create_clusters(self, centroids, X):
        n_samples = np.shape(X)[0]
        clusters = [[] for _ in range(self.k)]
        for sample_i, sample in enumerate(X):
            centroid_i = self._closest_centroid(sample, centroids)
            clusters[centroid_i].append(sample_i)
        return clusters
    
    # Calculate new centroids as the means of the samples
    # in each cluster
    def _calculate_centroids(self, clusters, X):
        n_features = np.shape(X)[1]
        centroids = np.zeros((self.k, n_features))
        for i, cluster in enumerate(clusters):
            centroid = np.mean(X[cluster], axis=0)
            centroids[i] = centroid
        return centroids
    
    # Classify samples as the index of their clusters
    def _get_cluster_labels(self, clusters, X):
        # One prediction for each sample
        y_pred = np.zeros(np.shape(X)[0])
        for cluster_i, cluster in enumerate(clusters):
            for sample_i in cluster:
                y_pred[sample_i] = cluster_i
        return y_pred
    
    # Do K-Means clustering and return cluster indices
    def predict(self, X):
        # Initialize centroids
        centroids = self._init_random_centroids(X)
    
        # Iterate until convergence or for max iterations
        for _ in range(self.max_iterations):
            # Assign samples to closest centroids (create clusters)
            clusters = self._create_clusters(centroids, X)
            prev_centroids = centroids
            # Calculate new centroids from the clusters
            centroids = self._calculate_centroids(clusters, X)
    
            # If no centroids have changed => convergence
            diff = centroids - prev_centroids
            if not diff.any():
                break
    
        return self._get_cluster_labels(clusters, X)
    

    虽然K-Means算法原理简单,但是也有自身的缺陷:

  • 首先,聚类的簇数K值需要事先给定,但在实际中这个 K 值的选定是非常难以估计的,很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。
  • Kmeans需要人为地确定初始聚类中心,不同的初始聚类中心可能导致完全不同的聚类结果,不能保证K-Means算法收敛于全局最优解。
  • 针对此问题,在K-Means的基础上提出了二分K-means算法。该算法首先将所有点看做是一个簇,然后一分为二,找到最小SSE的聚类质心。接着选择其中一个簇继续一分为二,此处哪一个簇需要根据划分后的SSE值来判断。
  • 对离群点敏感。
  • 结果不稳定 (受输入顺序影响)。
  • 时间复杂度高O(nkt),其中n是对象总数,k是簇数,t是迭代次数。