首页 > 编程语言 >简单易学的机器学习算法——K-Means++算法

简单易学的机器学习算法——K-Means++算法

时间:2023-06-14 18:38:58浏览次数:58  
标签:初始化 Means ++ 算法 聚类 np data


一、K-Means算法存在的问题

由于K-Means算法的简单且易于实现,因此K-Means算法得到了很多的应用,但是从K-Means算法的过程中发现,K-Means算法中的聚类中心的个数k需要事先指定,这一点对于一些未知数据存在很大的局限性。其次,在利用K-Means算法进行聚类之前,需要初始化k个聚类中心,在上述的K-Means算法的过程中,使用的是在数据集中随机选择最大值和最小值之间的数作为其初始的聚类中心,但是聚类中心选择不好,对于K-Means算法有很大的影响。对于如下的数据集:

简单易学的机器学习算法——K-Means++算法_K-Means++


如选取的个聚类中心为:

简单易学的机器学习算法——K-Means++算法_初始化_02


最终的聚类结果为:

简单易学的机器学习算法——K-Means++算法_初始化_03

为了解决因为初始化的问题带来K-Means算法的问题,改进的K-Means算法,即K-Means++算法被提出,K-Means++算法主要是为了能够在聚类中心的选择过程中选择较优的聚类中心。

二、K-Means++算法的思路

K-Means++算法在聚类中心的初始化过程中的基本原则是使得初始的聚类中心之间的相互距离尽可能远,这样可以避免出现上述的问题。K-Means++算法的初始化过程如下所示:

  • 在数据集中随机选择一个样本点作为第一个初始化的聚类中心
  • 选择出其余的聚类中心:
  • 计算样本中的每一个样本点与已经初始化的聚类中心之间的距离,并选择其中最短的距离,记为d_i
  • 以概率选择距离最大的样本作为新的聚类中心,重复上述过程,直到k个聚类中心都被确定
  • 对k个初始化的聚类中心,利用K-Means算法计算最终的聚类中心。

在上述的K-Means++算法中可知K-Means++算法与K-Means算法最本质的区别是在k个聚类中心的初始化过程。

Python实现:

# coding:UTF-8
'''
Date:20160923
@author: zhaozhiyong
'''

import numpy as np
from random import random
from KMeans import load_data, kmeans, distance, save_result

FLOAT_MAX = 1e100 # 设置一个较大的值作为初始化的最小的距离

def nearest(point, cluster_centers):
    min_dist = FLOAT_MAX
    m = np.shape(cluster_centers)[0]  # 当前已经初始化的聚类中心的个数
    for i in xrange(m):
        # 计算point与每个聚类中心之间的距离
        d = distance(point, cluster_centers[i, ])
        # 选择最短距离
        if min_dist > d:
            min_dist = d
    return min_dist

def get_centroids(points, k):
    m, n = np.shape(points)
    cluster_centers = np.mat(np.zeros((k , n)))
    # 1、随机选择一个样本点为第一个聚类中心
    index = np.random.randint(0, m)
    cluster_centers[0, ] = np.copy(points[index, ])
    # 2、初始化一个距离的序列
    d = [0.0 for _ in xrange(m)]

    for i in xrange(1, k):
        sum_all = 0
        for j in xrange(m):
            # 3、对每一个样本找到最近的聚类中心点
            d[j] = nearest(points[j, ], cluster_centers[0:i, ])
            # 4、将所有的最短距离相加
            sum_all += d[j]
        # 5、取得sum_all之间的随机值
        sum_all *= random()
        # 6、获得距离最远的样本点作为聚类中心点
        for j, di in enumerate(d):
            sum_all -= di
            if sum_all > 0:
                continue
            cluster_centers[i] = np.copy(points[j, ])
            break
    return cluster_centers

if __name__ == "__main__":
    k = 4#聚类中心的个数
    file_path = "data.txt"
    # 1、导入数据
    print "---------- 1.load data ------------"
    data = load_data(file_path)
    # 2、KMeans++的聚类中心初始化方法
    print "---------- 2.K-Means++ generate centers ------------"
    centroids = get_centroids(data, k)
    # 3、聚类计算
    print "---------- 3.kmeans ------------"
    subCenter = kmeans(data, k, centroids)
    # 4、保存所属的类别文件
    print "---------- 4.save subCenter ------------"
    save_result("sub_pp", subCenter)
    # 5、保存聚类中心
    print "---------- 5.save centroids ------------"
    save_result("center_pp", centroids)

其中,KMeans所在的文件为:

# coding:UTF-8
'''
Date:20160923
@author: zhaozhiyong
'''
import numpy as np

def load_data(file_path):
    f = open(file_path)
    data = []
    for line in f.readlines():
        row = []  # 记录每一行
        lines = line.strip().split("\t")
        for x in lines:
            row.append(float(x)) # 将文本中的特征转换成浮点数
        data.append(row)
    f.close()
    return np.mat(data)

def distance(vecA, vecB):
    dist = (vecA - vecB) * (vecA - vecB).T
    return dist[0, 0]

def randCent(data, k):
    n = np.shape(data)[1]  # 属性的个数
    centroids = np.mat(np.zeros((k, n)))  # 初始化k个聚类中心
    for j in xrange(n):  # 初始化聚类中心每一维的坐标
        minJ = np.min(data[:, j])
        rangeJ = np.max(data[:, j]) - minJ
        # 在最大值和最小值之间随机初始化
        centroids[:, j] = minJ * np.mat(np.ones((k , 1))) + np.random.rand(k, 1) * rangeJ
    return centroids

def kmeans(data, k, centroids):
    m, n = np.shape(data) # m:样本的个数,n:特征的维度
    subCenter = np.mat(np.zeros((m, 2)))  # 初始化每一个样本所属的类别
    change = True  # 判断是否需要重新计算聚类中心
    while change == True:
        change = False  # 重置
        for i in xrange(m):
            minDist = np.inf  # 设置样本与聚类中心之间的最小的距离,初始值为争取穷
            minIndex = 0  # 所属的类别
            for j in xrange(k):
                # 计算i和每个聚类中心之间的距离
                dist = distance(data[i, ], centroids[j, ])
                if dist < minDist:
                    minDist = dist
                    minIndex = j
            # 判断是否需要改变
            if subCenter[i, 0] <> minIndex:  # 需要改变
                change = True
                subCenter[i, ] = np.mat([minIndex, minDist])
        # 重新计算聚类中心
        for j in xrange(k):
            sum_all = np.mat(np.zeros((1, n)))
            r = 0  # 每个类别中的样本的个数
            for i in xrange(m):
                if subCenter[i, 0] == j:  # 计算第j个类别
                    sum_all += data[i, ]
                    r += 1
            for z in xrange(n):
                try:
                    centroids[j, z] = sum_all[0, z] / r
                except:
                    print " r is zero"   
    return subCenter

def save_result(file_name, source):
    m, n = np.shape(source)
    f = open(file_name, "w")
    for i in xrange(m):
        tmp = []
        for j in xrange(n):
            tmp.append(str(source[i, j]))
        f.write("\t".join(tmp) + "\n")
    f.close()

最终的结果为:

简单易学的机器学习算法——K-Means++算法_聚类_04

参考文献

  • Arthur D, Vassilvitskii
    S. k-means++: the advantages of careful seeding[C]//Eighteenth Acm-Siam Symposium
    on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, Usa, January.
    2007:1027-1035.


标签:初始化,Means,++,算法,聚类,np,data
From: https://blog.51cto.com/u_16161414/6479818

相关文章

  • 数据结构和算法——二叉排序树
    一、二叉排序树对于无序的序列“62,58,88,47,73,99,35,51,93,29,37,49,56,36,48,50”,是否存在一种高效的查找方案,使得能够快速判断在序列中是否存在指定的数值?二叉排序树是一种简单,高效的数据结构。二叉排序树,又称为二叉查找树。二叉排序树或者是一棵空树,或者是具有以下性质的二叉树:若其左子树不为......
  • C/C++中的变长结构体
    1.问题来源首先看下如下的一段代码:#include<stdlib.h>#include<stdio.h>#include<string.h>#defineMAX_LEN1024typedefstructKDtree{doubledata[MAX_LEN];//数据intdim;//选择的维度structKDtree*left;//左子树structKDtree*right;......
  • C/C++——排序
    在C/C++中的排序,使用到的函数主要有:sort()qsort()下面详细分析sort()函数和qsort()函数。1、sort()函数sort()是STL中提供的算法,头文件为:#include<algorithm>usingnamespacestd;函数原型如下:template<classRandomAccessIterator>voidsort(RandomAccessIteratorfirst,Ran......
  • 挑战数据结构和算法面试题——最大差值
    题目来自伯乐在线,欢迎有不同答案的同学来一起讨论。分析:基本方法是遍历数组,找到当前值前面所有数组元素的最小值。方法:intget_max_distance(int*a,constintn){intmax_distance=0;//纪录最大距离if(n==0)returnmax_distance;intmin=a[0];//纪录最小的......
  • C/C++——map的基本操作总结
    标准库map类型是一种以键-值(key-value)存储的数据类型。以下分别从以下的几个方面总结:map对象的定义和初始化map对象的基本操作,主要包括添加元素,遍历等1、pair类型1.1、pair类型的定义和初始化pair类型是在有文件utility中定义的,pair类型包含了两个数据值,通常有以下的一些定义和初......
  • 推荐算法——基于图的推荐算法PersonalRank算法
    一、推荐的概述在推荐系统中,通常是要向用户推荐商品,如在购物网站中,需要根据用户的历史购买行为,向用户推荐一些实际的商品;如在视频网站中,推荐的则是不同的视频;如在社交网站中,推荐的可能是用户等等,无论是真实的商品,还是视频,再或者是用户,都可以假设成一种物品,如下图所示:(图片来自参考......
  • C/C++——vector的基本操作总结
    标准库vector类型是C++中使用较多的一种类模板,vector类型相当于一种动态的容器,在vector中主要有一些基本的操作,接下来分别从以下的几个方面总结:vector对象的定义和初始化vector对象的基本操作,主要包括添加元素,遍历等1、vector对象的定义和初始化在vector中主要有四种定义和初始化的......
  • 【数据结构与算法面试题】求和
    题目来源“数据结构与算法面试题80道”。问题分析:可以使用类的构造方法,在类的每次实例化对象时都会调用构造方法,那么只需要实例化n个对象,就会调用n次构造方法,这就模拟了循环的过程,此时,只需要有一个全局变量记录累加的值即可。方法:#include<stdio.h>classcalnum{ public: cal......
  • GCC/G++选项 -Wl,-Bstatic和-Wl,-Bdynamic
    GCC/G++选项-Wl,-Bstatic和-Wl,-Bdynamic参考https://gcc.gnu.org/onlinedocs/gcc/Link-Options.html gcc使用-Wl传递连接器参数,ld使用-Bdynamic强制连接动态库,-Bstatic强制连接静态库。所以部分静态,部分动态连接这么写:gcc...-Wl,-Bstatic-l<your-static-lib>-Wl,-Bdyn......
  • 专访快手传输算法负责人周超博士:LAS标准的推出离不开信念感
    6月21日,快手正式对外发布基于流式的直播多码率自适应标准LAS(LiveAdaptiveStreaming),用于提供低延迟、平滑、流畅的直播多码率体验。LAS的端到端解决方案同时开源,包括服务端、客户端、业界领先的多码率自适应算法等,从而帮助业界实现零门槛接入和使用LAS。图:《搏击俱乐部》采访专家:......