一、问题描述（实验目的）
使用K-means 对数据集data1.txt进行无监督学习聚类，将地理位置分组成多个互斥的组或簇，使得根据数据集的距离属性，在同一个簇中的对象是相似的，不同簇的对象是相异的。通过画图体现聚类效果。
二、主要设备
Ubuntu，python2.7
三、K-means算法
K-Means算法是一种聚类的算法，其主要是来计算数据聚集的算法，通过不断地迭代取离中心点最近均值的算法，是一种基于形心的技术，k-均值算法把簇的形心定义为簇内点的均值。
流程：
1.在D中随机选择k个对象，每个对象代表一个簇的初始均值或中心
2.对剩下的每个对象，根据其与各个簇中心的欧氏距离，分配到最近的簇
3.K-均值算法迭代的改善簇内变差，对于每个簇，使用上次迭代分配到该簇的对象，重新计算均值。
4.使用更新后的均值作为新的簇心，重新分配所有对象，直到分配稳定，即再分配时距离不变，本轮的簇与前一轮相同。返回结果簇。
时间复杂度：O（nkt）n:对象总数，k:簇数，t：迭代次数
缺点：
1.k-means不适合发现凹形状的簇或大小差别很大的簇。
2.对噪声和离群点敏感，少量的这类值对均值影响很大，如过出现奇异点会带偏整个簇。
四、实验过程
1、收集数据：文件data1.txt
2、读取数据：使用readlines()读取文件，删去首尾空格，用’\t‘分割元组，返回一个列表，用map函数将str转换为浮点数。添加到列表。
# -*- coding: utf-8 -*-
from numpy import *
# 读数据
def loadDataSet(fileName):
dataMat = [] # 创建列表，存储读取的数据
fr = open('/home/wangyuhang/数据挖掘/聚类分析/data1.txt')
for line in fr.readlines(): # 读每一行
line1 = line.strip() # 删头尾空白
curLine = line1.split('\t') # 以\t为分割，返回一个列表
fltLine = map(float, curLine) # str 转成 float
dataMat.append(fltLine) # 将元素添加到列表尾
return dataMat
# 算欧氏距离
def distEclud(vecA, vecB): # 两个向量间欧式距离
return sqrt(sum(power(vecA - vecB, 2))) # 0ñ = sqrt( (x1-x2)^2+(y1-y2)^2 ) |x| = √( x2 + y2 )
# 初始化聚类中心，给定数据集构建一个包含k个随机质心的集合，
def createCent(dataSet, k):
# 特征维度
n = shape(dataSet)[1] # 计算列数
# 创建聚类中心的矩阵 k x n
centroids = mat(zeros((k, n)))
# 遍历n维特征
for j in range(n):
# 第j维特征属性值min 取每列最小值
minJ = min(dataSet[:, j])
# 区间值max-min，float数值
rangeJ = float(max(dataSet[:, j]) - minJ)
# 第j维，每次随机生成k个中心 minJ + rangeJ*random.rand(k,1)自动扩充阵进行匹配，实现不同维数矩阵相加,列需相同
centroids[:, j] = mat(
minJ + rangeJ * random.rand(k, 1)) # random.rand(k,1)构建k行一列，每行代表二维的质心坐标 #random.rand(2,1)#产生两行一列0~1随机数
return centroids
# k-means算法 （#默认欧式距离，初始中心点方法randCent()）
def kMeans(dataSet, k, distMeas=distEclud):
m = shape(dataSet)[0] # 样本总数，行数
clusterAssment = mat(zeros((m, 2))) # 分配样本到最近的簇：存[簇序号,距离的平方]建立簇分配结果矩阵，第一列存索引，第二列存距离平方
# step1:#初始化聚类中心
centroids = createCent(dataSet, k)
clusterChanged = True
while clusterChanged: # 所有样本分配结果不再改变，迭代终止
clusterChanged = False
# step2:分配样本到最近的聚类中心对应的簇中
for i in range(m):
minDist = inf # 无穷大 对于每个样本，定义最小距离，初始化
minIndex = -1
for j in range(k): # 计算每个样本与k个中心点距离均值
distJI = distMeas(centroids[j, :], dataSet[i, :])
if distJI < minDist:
minDist = distJI
minIndex = j # 获取最小距离,及对应的簇序号--最小值所在位置
if clusterAssment[i, 0] != minIndex: clusterChanged = True # 若相等则说明位置索引没有发生改变
clusterAssment[i, :] = minIndex, minDist ** 2 # 分配样本到最近的簇
# step3:更新聚类中心
for cent in range(k): # 样本分配结束后，重新计算聚类中心
ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A == cent)[0]] # 对每个簇，从簇分配结果矩阵中找簇号等于本簇的，将bool数组转为整型数组，传入dataset,得出样本点， 获取该簇所有的样本点
# nonzero 元组的每个元素都是一个整数数组，作用是把布尔数组中，为True的下标放入元组
centroids[cent, :] = mean(ptsInClust, axis=0) # 对簇中的值求均值，赋给聚类中心，更新聚类中心：axis=0沿列方向求均值
print 'centroids=', centroids
return centroids, clusterAssment
# 2维数据聚类效果显示
def datashow(dataSet, k, centroids, clusterAssment): # 二维空间显示聚类结果
from matplotlib import pyplot as plt
num, dim = shape(dataSet) # 样本数num ,维数dim
if dim != 2:
return 1
marksamples = ['or', 'ob', 'og', 'ok', '^r', 'sb', '<g'] # 样本图形标记
if k > len(marksamples):
return 1
# 绘所有样本
for i in range(num):
markindex = int(clusterAssment[i, 0]) # 簇序号转为整型
plt.plot(dataSet[i, 0], dataSet[i, 1], marksamples[markindex], markersize=6) # 特征维对应坐标轴x,y；样本图形标记按簇标记；大小
# 绘中心点
markcentroids = ['dr', 'db', 'dg', 'dk', '^b', 'sk', '<r'] # 聚类中心图形标记
for i in range(k): # 为每个簇使用不同的中心点标记
plt.plot(centroids[i, 0], centroids[i, 1], markcentroids[i], markersize=15)
plt.title('k-means cluster result') # 标题
plt.show()
import matplotlib.pyplot as plt
if __name__ == '__main__':
# 原始样本图
datamat = mat(loadDataSet('/home/wangyuhang/数据挖掘/聚类分析/data1.txt')) # 获取样本数据
num, dim = shape(datamat) # 样本的个数和特征维数
marksamples = ['db'] # 样本图形标记
for i in range(num): # 为每个样本绘制
plt.plot(datamat[i, 0], datamat[i, 1], marksamples[0], markersize=6) # 自定义样本标记和大小
plt.title("data.txt sample") # 标题
plt.show()
# kmeans聚类图
k = 4 # 用户定义聚类数
# 获取样本数据
datamat = mat(loadDataSet('/home/wangyuhang/数据挖掘/聚类分析/data1.txt'))
mycentroids, clusterAssment = kMeans(datamat, k)
# 绘图显示
datashow(datamat, k, mycentroids, clusterAssment)
五、实验结果
k-means.png
