1.K-Means聚类算法
1.1 K-Means聚类算法基本原理
聚类就是将一大堆数据集中，将具有相同特征的数据自动的归到一类，每一类都称为一个簇。很显然这是一种无监督学习方法。所谓的K-Means（K-均值）算法就是用来发现数据集中K个簇的算法，并且每个簇的中心使用簇中的均值来确定，每个簇的中心叫做质心。
这里的距离一般采用欧式距离来进行计算： 两者欧式距离计算公式为:
1.2 K-Means聚类算法流程简述
算法流程简述：
- 1.随机创建K个点作为初始质心（不一定是数据集中的点）
- 2.分别计算每个数据和质心的欧式距离，并将该数据分类至距离最近的簇，如果簇发生变化则进行记录
- 3.对每一个簇，统计簇中所有的数据点特征的平均值作为新的质心
- 4.弱在上述步骤中不存在簇发生变化的情况发现则算法结束，否则跳转至第2步
1.3 K-Means聚类算法评价标准
K-Means聚类算法一般采用SSE (Sum of Squared Error, 误差平方和 ）作为评价标准，也就是每一个点到其所在簇质心的距离的平方的总和。SSE值越小，表明簇内所有点越接近质心，分类效果越好。
1.4 K-Means聚类算法实例
给定的数据集是一个八十行的数据文件，每行两个特征值。现在要求根据这个特征值进行聚类，部分数据集如下：
1.658985 4.285136
-3.453687 3.424321
4.838138 -1.151539
-5.379713 -3.362104
0.972564 2.924086
-3.567919 1.531611
0.450614 -3.302219
-3.487105 -1.724432
2.668759 1.594842
首先从文件中，读入数据，将原始数据转换成np数组
import numpy as np
#数据读入函数
def loadData(filename):
with open(filename,"r") as f:
fileContent = f.read()
data = fileContent.split("\n")
dataMat = []
for row in data:
if row!="":
item = row.split("\t")
dataMat.append(item)
dataMat = np.array(dataMat,dtype="float64")
return dataMat
dataSet = loadData("attach/1.8/testSet.txt")
各个数据特征分布如下图所示：
#特征分布图
from matplotlib import pyplot as plt
for row in dataSet:
plt.plot(row[0], row[1], 'o', color='green', markeredgewidth=2, markersize=10) #画点
从图中，我们可以观察出给定数据整体可以分为四个簇，为方便后续计算我们先构建一个计算两个特征向量欧式距离的函数。
import numpy as np
def distCalc(vecX,vecY):
dist = np.sqrt(np.sum(np.power((vecX-vecY),2)))#神奇的数组计算大大降低了代码量
return dist
#print(distCalc(dataSet[0],dataSet[1]))
完成准备工作开始，算法编写，根据算法的基本流程，第一步是要构建k个随机质心
import numpy as np
def makeRandCent(dataSet,k): #随机质心创建的时候要注意，质心要在范围空间内
n = dataSet.shape[1] #获取特征数量
centList = np.zeros((k,n))
for i in range(n):
minI = np.min(dataSet[:,i])
rangeI = np.max(dataSet[:,i])-minI
centList[:,i] = minI + rangeI*np.random.rand(1,k)
return centList
centList = makeRandCent(dataSet,4) #生成随机的质心
print(centList)
[[ 0.65663247 0.77717004]
[-0.84559261 -0.73683408]
[-0.61538579 0.69684389]
[ 0.70073271 -0.68287865]]
def kMeans(dataSet,k):
typeChange = True
numOfdata = dataSet.shape[0]
dataClassifyRes = [-1]*80
while typeChange:
typeChange = False
indexOfData = 0
for data in dataSet:
num=0
minDist = np.inf
minIndex = -1
for cent in centList:
dist = distCalc(data,cent)
if dist<minDist:
minDist = dist
minIndex = num
num+=1
if minIndex==dataClassifyRes[indexOfData]:
pass
else:
dataClassifyRes[indexOfData]=minIndex
#print(indexOfData,"------》",minIndex)
typeChange = True
indexOfData+=1
#更新k个质心的特征值
for i in range(k):
indexListOfThisType = []
for index,value in enumerate(dataClassifyRes):
if value==i:
indexListOfThisType.append(index)
for j in range(centList.shape[1]):
SUM = 0.0
for index in indexListOfThisType:
SUM += dataSet[index][j]
centList[i][j] = (SUM/(len(indexListOfThisType)))
return dataClassifyRes
res = kMeans(dataSet,4)
from matplotlib import pyplot as plt
for index,value in enumerate(res):
if value==0:
plt.plot(dataSet[index][0], dataSet[index][1], 'x', color='green', markeredgewidth=2, markersize=10) #画点
if value==1:
plt.plot(dataSet[index][0], dataSet[index][1], 'x', color='red', markeredgewidth=2, markersize=10) #画点
if value==2:
plt.plot(dataSet[index][0], dataSet[index][1], 'x', color='blue', markeredgewidth=2, markersize=10) #画点
if value==3:
plt.plot(dataSet[index][0], dataSet[index][1], 'x', color='orange', markeredgewidth=2, markersize=10) #画点
#画出四个质心点
plt.plot(centList[0][0], centList[0][1], 'o', color='green', markeredgewidth=2, markersize=10) #画点
plt.plot(centList[1][0], centList[1][1], 'o', color='red', markeredgewidth=2, markersize=10) #画点
plt.plot(centList[2][0], centList[2][1], 'o', color='blue', markeredgewidth=2, markersize=10) #画点
plt.plot(centList[3][0], centList[3][1], 'o', color='orange', markeredgewidth=2, markersize=10) #画点
[<matplotlib.lines.Line2D at 0x119bc2e10>]
