数据挖掘经典十大算法_K-Means算法

数据挖掘经典十大算法_K-Means算法

一、从故事理解K-Means Clustering Algorithm

1.有四个牧师去郊区布道,一开始牧师们随意选了几个布道点,并且把这几个布道点的情况公告给了郊区所有的居民,于是每个居民到离自己家最近的布道点去听课。
2.第一次听课之后,大家觉得距离太远了,于是每个牧师统计了一下自己的课上所有的居民的地址,搬到了所有地址的中心地带,并且在海报上更新了自己的布道点的位置。
3.牧师每一次移动不可能离所有人都更近,有的人发现A牧师移动以后自己还不如去B牧师处听课更近,于是每个居民又去了离自己最近的布道点…就这样,牧师每个礼拜更新自己的位置,居民根据自己的情况选择布道点,最终稳定了下来。

二、K-means算法步骤

  1. 先定义总共有多少个类/簇(cluster)
  2. 将每一个簇心(cluster centers)随机定在一个点上
  3. 将每个数据点关联到最近的簇中心所属的簇上
  4. 对于每一个簇找到其所有关联点的中心点(取每一个点坐标的平均值)
  5. 将上述点变为新的簇心
  6. 重复上述过程,直至每个簇所拥有的点不变

三、举个栗子
(一)若有A1~A6六个样本点,将其分为两个簇,其中A3,A4为两个簇的初始簇心,表格中的数据为样本点的X,Y坐标。

X Y
A1 1 2
A2 1 4
A3 3 1
A4 3 5
A5 5 2
A6 5 4

(二)计算每个点到簇心的距离(采用距离公式计算),将距离近的点归为一类。

X Y G1 distance G2 distance
A1 1 2 ((3-1)**2+(1-2)**2)**0.5=2.24 3.61
A2 1 4 3.61 2.24
A3 3 1 0.00 4.00
A4 3 5 4.00 0.00
A5 5 2 2.24 3.61
A6 5 4 3.61 2.24

对于A3作为簇心来说,A1,A3,A5距离最近,故将其归为一类;
对于A4作为簇心来说,A2,A4,A6距离最近,故将其归为一类.

(三)将第一类A1,A3,A5和第二类A2,A4,A6的X,Y值分别求平均,得到新的簇心。

X Y
new M1 3.00 (2+1+2)/3=1.67
new M2 3.00 4.43

(四)计算每个点到簇心的新距离,将距离近的点归为一类。

X Y G1 distance G2 distance
A1 1 2 ((3-1)**2+(1.67-2)**2)**0.5=2.03 3.07
A2 1 4 3.07 2.03
A3 3 1 0.67 3.33
A4 3 5 3.33 0.67
A5 5 2 2.03 3.07
A6 5 4 3.07 2.03

对于M1作为簇心来说,A1,A3,A5距离最近,故将其归为一类;
对于M2作为簇心来说,A2,A4,A6距离最近,故将其归为一类.

(五)此时发现关联的点没有发生变化,所以之后的计算结果不会改变,停止计算。

(六)故,第一簇为A1,A3,A5,第二簇为A2,A4,A6.

四、算法特性

  1. 典型的无监督算法.why? 由于我们拿到的数据样本没有标签,需要通过算法执行来得到标签结果.
  2. K表示样本类别数,也是就在确定K值后,算法执行过后会分成K个簇.
  3. 距离的度量,常用欧几里得距离和余弦相似度计算 (先标准化)
  4. 优点:简单易实现,快速,适合常规数据集
  5. 缺点:K值难确定,复杂度与样本呈线性关系,很难发现任意形状的簇。

五、算法实现
1.导入第三方库

import random
from math import *
import matplotlib.pyplot as plt

2.读取文件数据

#从文件种读取数据
def read_data():
    data_points = [] # 初始化空的列表
    with open('data.txt','r') as fp:
        for line in fp:
            if line =='n':
                continue
            data_points.append(tuple(map(float,line.split(' '))))#去掉空格,并将data中数据的类型转为tuple
        fp.close()
        return data_points

3.初始化聚类中心

#初始化聚类中心
def begin_cluster_center(data_points,k):
    center=[]
    length=len(data_points)#获取传入的数据长度
    rand_data = random.sample(range(0,length), k)#生成k个不同随机数 作为样本初始簇中心
    for i in range(k):#得出k个聚类中心(随机选出)
        center.append(data_points[rand_data[i]]) # 将初始样本簇中心追加到列表中
    return center

4.计算欧氏距离

#计算欧氏距离
def distance(a,b):
    length=len(a)
    sum = 0
    for i in range(length):
        sq = (a[i] - b[i]) ** 2 # 先平方
        sum += sq
    return sqrt(sum) # 开根号

5.分配样本,按照欧氏距离将所有的初始样本分配到k个聚类中心中的某一个

# 
def assign_points(data_points,center,k):
    assignment=[]
    for i in range(k):
        assignment.append([])
    for point in data_points:
        min = 10000000
        flag = -1
        for i in range(k):
            value=distance(point,center[i])#计算每个点到聚类中心的距离
            if value<min:
                min=value#记录距离的最小值
                flag=i   #记录此时聚类中心的下标
        assignment[flag].append(point)
    return assignment

6.更新聚类中心,计算每一簇中所有点的平均值

#更新聚类中心,计算每一簇中所有点的平均值
def update_cluster_center(center,assignment,k):
    for i in range(k):#assignment中的每一簇
        x=0
        y=0
        length=len(assignment[i])#每一簇的长度
        if length!=0:
            for j in range(length):  # 每一簇中的每个点
                x += assignment[i][j][0]  # 横坐标之和
                y += assignment[i][j][1]  # 纵坐标之和
            center[i] = (x / length, y / length)
    return center

7.计算平方误差

#计算平方误差
def getE(assignment,center):
    sum_E=0
    for i in range(len(assignment)):
        for j in range(len(assignment[i])):
            sum_E+=distance(assignment[i][j],center[i])
    return sum_E

8.计算各个聚类中心的新向量,更新距离,即每一类中每一维均值向量。
然后再进行分配,比较前后两个聚类中心向量是否相等,若不相等则进行循环,
否则终止循环,进入下一步。

def k_means(data_points,k):
    # 由于初始聚类中心是随机选择的,十分影响聚类的结果,聚类可能会出现有较大误差的现象
    # 因此如果由初始聚类中心第一次分配后有结果为空,重新选择初始聚类中心,重新再聚一遍,直到符合要求
    while 1:
        # 产生初始聚类中心
        begin_center = begin_cluster_center(data_points, k)
        # 第一次分配样本
        assignment = assign_points(data_points, begin_center, k)
        for i in range(k):
            if len(assignment[i]) == 0:#第一次分配之后有结果为空,说明聚类中心没选好,重新产生初始聚类中心
                continue
        break
    #第一次的平方误差
    begin_sum_E=getE(assignment,begin_center)
    # 更新聚类中心
    end_center = update_cluster_center(begin_center, assignment, k)
    # 第二次分配样本
    assignment = assign_points(data_points, end_center, k)
    # 第二次的平方误差
    end_sum_E = getE(assignment, end_center)
    count = 2  # 计数器
    #比较前后两个聚类中心向量是否相等
    #print(compare(end_center,begin_center)==False)
    while( begin_sum_E != end_sum_E):
        begin_center=end_center
        begin_sum_E=end_sum_E
        # 再次更新聚类中心
        end_center = update_cluster_center(begin_center, assignment, k)
        # 进行分配
        assignment = assign_points(data_points, end_center, k)
        #计算误差
        end_sum_E = getE(assignment, end_center)
        count = count + 1      #计数器加1
    return assignment,end_sum_E,end_center,count

9.打印计算结果

def print_result(count,end_sum_E,k,assignment):
    # 打印最终聚类结果
    print('经过', count, '次聚类,平方误差为:', end_sum_E)
    print('---------------------------------分类结果---------------------------------------')
    for i in range(k):
        print('第',i+1,'类数据:',assignment[i])
    print('--------------------------------------------------------------------------------n')

10.可视化展示

def plot(k, assignment,center):
    #初始坐标列表
    x = []
    y = []
    for i in range(k):
        x.append([])
        y.append([])
    # 填充坐标 并绘制散点图
    for j in range(k):
        for i in range(len(assignment[j])):
            x[j].append(assignment[j][i][0])# 横坐标填充
        for i in range(len(assignment[j])):
            y[j].append(assignment[j][i][1])# 纵坐标填充
        plt.scatter(x[j], y[j],marker='o')
        plt.scatter(center[j][0], center[j][1],c='b',marker='*')#画聚类中心
    # 设置标题
    plt.title('K-means Scatter Diagram')
    # 设置X轴标签
    plt.xlabel('X')
    # 设置Y轴标签
    plt.ylabel('Y')
    # 显示散点图
    plt.show()
 
def main():
    # 4个聚类中心
    k = 4
    data_points =read_data()
    assignment, end_sum_E, end_center, count = k_means(data_points, k)
    min_sum_E = 1000
    #返回较小误差
    while min_sum_E>end_sum_E:
        min_sum_E=end_sum_E
        assignment, end_sum_E, end_center, count = k_means(data_points,k)
    print_result(count, min_sum_E, k, assignment)#输出结果
    plot(k, assignment,end_center)#画图
main()

在这里插入图片描述
在这里插入图片描述

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>