机器学习--物以类聚（k-means算法）

k-means算法是无监督学习算法，没有标签值，通过自身分析自身的数据，自己进行分类。

此次实现参考了其他博客的实现。

k-means中k的意思表示的是分类数目。

数据集下载地址：链接：http://pan.baidu.com/s/1cfhvAY 密码：7nk8

思想：

1.将数据集中的每条数据视为空间中的一个点

2.随机选取k条作为基准的数据

3.遍历数据集，分别计算每条数据转化为数据点后到每条k中记录的距离，选取距离最短的k作为该条数据的类别

4.遍历完所有数据集后，对所有属于对应的k中的类别的数据进行重新选择中心点操作，可以通过x=(x1+x2+x3+...+xn)/n来计算中心点

5.重复对数据集进行遍历操作，重复步骤3和步骤4，直到中心点不再发生变化为止，此时停止操作。

6.最后数据集所属的类别和各个中心点即为最终分类的结果

算法实现步骤：

1.设计一个方法：导入数据，对数据进行切割，转化为矩阵

2.设计一个方法：计算两个点的距离

3.设计一个方法：随机生成k条作为基准的数据集

4.设计一个方法：遍历所有数据集，对所有数据进行判别类型操作

5.设计一个方法：对最后的中心点、数据集所属的类型、数据集进行数据图展示

python实现：

# coding = utf-8
import numpy
import matplotlib.pyplot as plt

#导入文件，转化为矩阵返回
def getdatamat(file):
    file = open(file)
    lines = file.readlines()
    arr = []
    for line in lines:
        temp = line.split("\t")
        arr.append([float(temp[0]), float(temp[1])])
    dataset = numpy.mat(arr)
    return dataset

#计算两个数据点之间的距离，返回距离
def getdis(pointA, pointB):
    return numpy.sqrt(numpy.sum(numpy.power(pointA - pointB, 2)))

#获取k条随机的基准数据并返回
def getinitpoints(dataset, k):
    length, width = dataset.shape
    points = numpy.zeros((k, width))
    for i in range(k):
        index = int(numpy.random.uniform(0, length))
        points[i:, ] = dataset[index]
    return points

#对数据进行分类操作，直到中心点不再变化为止
def kmeans(dataset, k):
    time = 0
    initpoints = getinitpoints(dataset, k)
    print initpoints
    length, width = dataset.shape
    labels = numpy.mat(numpy.zeros((length, 2)))
    isChanged = True
    while isChanged:
        isChanged = False
        for i in xrange(length):
            pointA = dataset[i, :]
            distance = 1000
            index = -1
            for j in range(k):
                pointB = initpoints[j, :]
                resultDis = getdis(pointB, pointA)
                if distance > resultDis:
                    distance = resultDis
                    index = j
            if labels[i, 0] != index:
                isChanged = True
            labels[i, 0] = index
        for i in range(k):
            temp = dataset[numpy.nonzero(labels[:, 0].A==i)[0]]
            initpoints[i, :] = numpy.mean(temp, axis=0)
        time += 1
        print time
        if time>100:
            return initpoints, labels
    return initpoints, labels

#通过matplotlib展示最后的结果。
def show(dataSet, k, centroids, clusterAssment):
    numSamples, dim = dataSet.shape
    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    for i in xrange(numSamples):
        markIndex = int(clusterAssment[i, 0])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])
    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
    for i in range(k):
        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)
    plt.show()

if __name__ == '__main__':
    k = 4
    dataset = getdatamat("test.txt")
    initpoints, labels = kmeans(dataset, k)
    show(dataset, k, initpoints, labels)

k为4的时的结果图：

k为3的时的结果图：

k为2的时的结果图（与初始基准点选取有关）：