机器学习--k均值聚类(k-means)算法，--kk-means

文章由LinuxBoy分享于2019-03-27 09:03:27热评（353）

机器学习--k均值聚类(k-means)算法，--kk-means

一、基本原理

分类是指分类器根据已标注类别的训练集，通过训练可以对未知类别的样本进行分类。分类被称为监督学习。如果训练集的样本没有标注类别，那么就需要用到聚类。聚类是把相似的样本聚成一类，这种相似性通常以距离来度量。聚类被称为无监督学习。

聚类是指根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一个这样的簇进行描述的过程。它的目的是使得属于同一个簇的样本之间应该彼此相似，而不同簇的样本应该足够不相似。与分类规则不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪些空间区分规则来定义组。 k-means是聚类算法中常用的一种，其中k的含义是指有k个cluster（簇）。由聚类的定义可知，一个样本应距离其所属cluster的质心是最近的（相较于其他k-1个cluster）。为了表示cluster，最简单有效的是取所有样本点平均，即质心（cluster centroid），这便是取名means的来由。二、算法流程 1）随机选取k个初始点作为质心 2）计算每个点到k个质心的距离，并将其分给距离最近的质心所对应的簇 3）更新每个簇的质心，直到簇分配不发生改变为止伪代码表示如下：创建k个点作为起始质心（可以随机选择）当任意一个点的簇分配结果发生改变时对数据集中的每个数据点对每个质心计算质心与数据点之间的距离将数据点分配到距其最近的簇对每一个簇，计算簇中所有点的均值并将均值作为质心三、算法的特点优点：容易实现缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢。适用数据范围：数值型。四、python代码实现 1、将文本文件转换为矩阵

#############################
#功能：将文本文件导入到矩阵中
#输入变量：文本文件
#输出变量：文本文件转换后的矩阵
#############################
def load_data_set(file_name):
data_mat = []
fr = open(file_name)

    for line in fr.readlines():
        #先去除字符串两边的空格，再以tab分隔符分切字符串
        cur_line = line.strip().split('\t')

#用map函数将cur_line进行float运算，即转为float型
float_line = map(float, cur_line)

data_mat.append(float_line)

fr.close()
return data_mat

2、欧式距离的计算

############################
#功能：计算欧式距离
#输入变量：两个变量
#输出变量：两个变量的欧氏距离
############################
def dist_eclud(vec_a, vec_b):
return sqrt(sum(power(vec_a-vec_b, 2)))

3、构建一个k个随机质心的集合

##################################
#功能：构建一个k个随机质心的集合
#输入变量：原始数据集，初始化为k个质心
#输出变量：质心的坐标值
##################################
def rand_cent(data_set, k):
n = shape(data_set)[1] # 获得列数
centroids = mat(zeros((k, n))) # 创建k行n列的质心矩阵，初始值都为0

    for j in xrange(n): # 创建每个维度范围内的随机集群中心
        min_j = min(data_set[:, j]) # 取出对应列的值，并取最小值
        range_j = float(max(data_set[:, j]) - min_j)

# 生成0到1.0之间的随机数，确保随机点在数据的边界之内
centroids[:, j] = min_j + range_j*random.random()

return centroids

4、实现k-均值聚类算法

##################################
#功能：k均值聚类
#输入变量：原始数据集，初始化为k个质心，
# 距离函数，构建随机质心的函数

#输出变量：centroids 最终的质心，
# cluster_assment 每个质心包含的数据点的索引值及误差
##################################
def k_means(data_set, k):
m = shape(data_set)[0] # 获得行数

    cluster_assment = mat(zeros((m, 2))) # 一列记录簇索引值，一列存储误差
    centroids = rand_cent(data_set, k) # 生成随机质心
    cluster_changed = True

while cluster_changed:
cluster_changed = False

        for i in xrange(m): # 计算每一个数据点到质心的距离
            min_dist = inf
            min_index = -1

            # 计算每个数据点到质心的最小距离
            for j in xrange(k):
                dist_ji = dist_eclud(centroids[j, :], data_set[i, :])
                if dist_ji < min_dist:
                    min_dist = dist_ji
                    min_index = j

            # 如果该数据点的索引值改变，即该数据点不属于原来的质心
            if cluster_assment[i, 0] != min_index:
                cluster_changed = True

# 最小值的索引值，均方值
cluster_assment[i, :] = min_index, min_dist**2

print 'centroids=', centroids
for cent in xrange(k):

            # 去第一列等于cent的所有列
            # nonzero()返回值为元组，两个值分别为两个维度，第一个是行，第二个是列。
            # .A表示返回该矩阵数据的2维数组视图
            pts_in_clust = data_set[nonzero(cluster_assment[:, 0].A == cent)[0]]
            centroids[cent, :] = mean(pts_in_clust, axis=0)

return centroids, cluster_assment

def main():
    data_mat = mat(load_data_set('testSet.txt'))
    # print "data_mat=", data_mat
    centroids = rand_cent(data_mat, 2)
    print "centroids=", centroids

    my_centroids, cluster_assing = k_means(data_mat, 4)
    print 'my_centroids=', my_centroids
    print 'cluster_assing=', cluster_assing

if __name__ == '__main__':
main()

推荐文章：

机器学习--k均值聚类(k-means)算法，--kk-means