K-means与K-means++

转载：https://www.cnblogs.com/wang2825/articles/8696830.html

K-means与K-means++：

原始K-means算法最开始随机选取数据集中K个点作为聚类中心，

而K-means++按照如下的思想选取K个聚类中心：

• 假设已经选取了n个初始聚类中心(0<n<K)，则在选取第n+1个聚类中心时：距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。
• 在选取第一个聚类中心(n=1)时同样通过随机的方法。

可以说这也符合我们的直觉：聚类中心当然是互相离得越远越好。这个改进虽然直观简单，但是却非常得有效。

经典K-means算法：

image

值得一提的是关于聚类中心数目（K值）的选取，的确存在一种可行的方法，叫做Elbow Method：

通过绘制K-means代价函数与聚类数目K的关系图，选取直线拐点处的K值作为最佳的聚类中心数目。

上述方法中的拐点在实际情况中是很少出现的。

比较提倡的做法还是从实际问题出发，人工指定比较合理的K值，通过多次随机初始化聚类中心选取比较满意的结果。

python实现：

# -*- coding: utf-8 -*-

#!/usr/bin/env python
# @Time    : 18-2-3 下午6:01
# @Author  : wang shen
# @web    : 
# @File    : kmeans.py
from collections import defaultdict
from random import  uniform
from math import sqrt


def point_avg(points):
    '''
    Accepts a list of points, each with the same number of dimensions.
    NB. points can have more dimensions than 2
    Returns a new points which is the center of all the points
    :param points:
    :return:
    '''
    dimensions = len(points[0])

    new_center = []

    for dimension in range(dimensions):
        dim_sum = 0
        for p in points:
            dim_sum += p[dimension]

        # average of each dimension
        new_center.append(dim_sum / float(len(points)))

    return new_center


def update_centers(date_set, assignments):
    '''
    Accepts a dataset and a list of assignments; the indexes of both lists correspond
    to each other.
    compute the center for each of the assigned groups.
    Reture 'k' centers where  is the number of unique assignments.
    :param date_set:
    :param assignments:
    :return:
    '''
    new_means = defaultdict(list)
    centers = []
    for assigment, point in zip(assignments, date_set):
        new_means[assigment].append(point)

    for points in new_means.values():
        centers.append(point_avg(points))

    return centers


def distance(a, b):
    dimensions = len(a)

    _sum = 0
    for dimension in range(dimensions):
        difference_seq = (a[dimension] - b[dimension]) ** 2
        _sum += difference_seq

    return sqrt(_sum)


def assign_points(data_points, centers):
    '''
    Given a data set and a list  of points between other points,
    assign each point to an index that corresponds to the index
    of the center point on its proximity to that point.
    Return a an array of indexes of the centers that correspond to
    an index in the data set; that is, if there are N points in data set
    the list we return will have N elements. Also If there ara Y points in centers
    there will be Y unique possible values within the returned list.
    :param data_points:
    :param centers:
    :return:
    '''
    assigments = []
    for point in data_points:
        shortest = float('Inf')
        shortest_index = 0
        for i in range(len(centers)):
            val = distance(point, centers[i])
            if val < shortest:
                shortest = val
                shortest_index = i
        assigments.append(shortest_index)

    return assigments


def generate_k(data_set, k):
    '''
    Given data set , which is an array of arrays,
    find the minimum and maximum foe each coordinate, a range.
    Generate k random points between the ranges
    Return an array of the random points within the ranges
    :param data_set:
    :param k:
    :return:
    '''
    centers = []
    dimensions = len(data_set[0])
    min_max = defaultdict(int)

    for point in data_set:
        for i in range(dimensions):
            val = point[i]
            min_key = 'min_%d' % i
            max_key = 'max_%d' % i
            if min_key not in min_max or val < min_max[min_key]:
                min_max[min_key] = val
            if max_key not in min_max or val > min_max[max_key]:
                min_max[max_key] = val

    for _k in range(k):
        rand_point = []
        for i in range(dimensions):
            min_val = min_max['min_%d' % i]
            max_val = min_max['max_%d' % i]

            rand_point.append(uniform(min_val, max_val))

        centers.append(rand_point)
    return centers


def k_means(dataset, k):
    k_points = generate_k(dataset, k)
    assignments = assign_points(dataset, k_points)
    old_assignments = None
    times = 0
    while assignments != old_assignments:
        times += 1
        print('times is :', times)
        new_centers = update_centers(dataset, assignments)
        old_assignments = assignments
        assignments = assign_points(dataset, new_centers)

    return (assignments, dataset)

K-means++算法：

起步

由于 K-means 算法的分类结果会受到初始点的选取而有所区别，因此有提出这种算法的改进: K-means++ 。

算法步骤

其实这个算法也只是对初始点的选择有改进而已，其他步骤都一样。初始质心选取的基本思路就是，初始的聚类中心之间的相互距离要尽可能的远。

算法描述如下：

• 步骤一：随机选取一个样本作为第一个聚类中心 c1；
• 步骤二：
  • 计算每个样本与当前已有类聚中心最短距离（即与最近一个聚类中心的距离），用 D(x)表示；
  • 这个值越大，表示被选取作为聚类中心的概率较大；
  • 最后，用轮盘法选出下一个聚类中心；
• 步骤三：重复步骤二，知道选出 k 个聚类中心。

选出初始点后，就继续使用标准的 k-means 算法了。

效率

K-means++ 能显著的改善分类结果的最终误差。

尽管计算初始点时花费了额外的时间，但是在迭代过程中，k-mean 本身能快速收敛，因此算法实际上降低了计算时间。

网上有人使用真实和合成的数据集测试了他们的方法，速度通常提高了 2 倍，对于某些数据集，误差提高了近 1000 倍。

image

下面结合一个简单的例子说明K-means++是如何选取初始聚类中心的。

数据集中共有8个样本，分布以及对应序号如下图所示：

image

假设经过图2的步骤一后6号点被选择为第一个初始聚类中心，

那在进行步骤二时每个样本的D(x)和被选择为第二个聚类中心的概率如下表所示：

image

其中的P(x)就是每个样本被选为下一个聚类中心的概率。

最后一行的Sum是概率P(x)的累加和，用于轮盘法选择出第二个聚类中心。

方法是随机产生出一个0~1之间的随机数，判断它属于哪个区间，那么该区间对应的序号就是被选择出来的第二个聚类中心了。

例如1号点的区间为[0,0.2)，2号点的区间为[0.2, 0.525)。

从上表可以直观的看到第二个初始聚类中心是1号，2号，3号，4号中的一个的概率为0.9。

而这4个点正好是离第一个初始聚类中心6号点较远的四个点。

这也验证了K-means的改进思想：即离当前已有聚类中心较远的点有更大的概率被选为下一个聚类中心。

可以看到，该例的K值取2是比较合适的。当K值大于2时，每个样本会有多个距离，需要取最小的那个距离作为D(x)。

python实现：

# coding: utf-8
import math
import random
from sklearn import datasets

def euler_distance(point1: list, point2: list) -> float:
    """
    计算两点之间的欧拉距离，支持多维
    """
    distance = 0.0
    for a, b in zip(point1, point2):
        distance += math.pow(a - b, 2)
    return math.sqrt(distance)

def get_closest_dist(point, centroids):
    min_dist = math.inf  # 初始设为无穷大
    for i, centroid in enumerate(centroids):
        dist = euler_distance(centroid, point)
        if dist < min_dist:
            min_dist = dist
    return min_dist

def kpp_centers(data_set: list, k: int) -> list:
    """
    从数据集中返回 k 个对象可作为质心
    """
    cluster_centers = []
    cluster_centers.append(random.choice(data_set))
    d = [0 for _ in range(len(data_set))]
    for _ in range(1, k):
        total = 0.0
        for i, point in enumerate(data_set):
            d[i] = get_closest_dist(point, cluster_centers) # 与最近一个聚类中心的距离
            total += d[i]
        total *= random.random()
        for i, di in enumerate(d): # 轮盘法选出下一个聚类中心；
            total -= di
            if total > 0:
                continue
            cluster_centers.append(data_set[i])
            break
    return cluster_centers

if __name__ == "__main__":
    iris = datasets.load_iris()
    print(kpp_centers(iris.data, 4))