机器学习实战六（K-均值聚类算法）

发表于 | 更新于: | 分类于 |
字数统计: 1,165字

一、概述

1. 原理：

  • 工作机制：给定测试样本，基于某种距离度量找出训练集中的与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测.
  • 通常k是不大于20的整数

2. 优缺点

  • 优点：精度高、对异常值不敏感、无数据输入假定

  • 缺点：计算复杂度高、空间复杂度高，占用存储空间。无法给出数据的内在含义

  • 适用数据范围：数值型和标称型

3. 懒惰算法：

  • 此类学习技术在训练阶段仅仅把样本保存起来
  • 训练开支为零，待收到测试样本后再进行处理

二、算法流程

  1. 收集数据
  2. 准备数据
  3. 分析数据
  4. 训练算法（不适合KNN算法，因为K是“懒惰算法”的著名代表）
  5. 测试算法
  6. 使用算法

三、算法框架

1. classify0()函数的4个输入参数：

  • inX：用于分类的输入向量
  • dataSet：用于输入的训练样本集
  • labels：标签向量
  • k：参数k用于选择最佳邻居的数目

4. 数据的归一化

  • 由于每个属性的取值数量级相差过大，会造成每个属性的权重不同，这显然是海伦不希望的。所以我们还要写一个函数实现数据归一化，公式如下:
  • newValue=(oldValue-min)/(max-min)
  • 这个公式可以将特征值转化为0~1之间的值。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #归一化特征值
    def autoNorm(dataSet):
            #每列的最小值
            minVals=dataSet.min(0)
            #每列的最大值
            maxVals=dataSet.max(0)
            #最大值与最小值的差值
            ranges=maxVals-minVals
            normDataSet=zeros(shape(dataSet))
            m=dataSet.shape[0]
            #minVals是1*3的矩阵，使用tile函数复制成和dataSet同样大小的矩阵，方便计算
            normDataSet=dataSet-tile(minVals,(m,1))
            normDataSet=normDataSet/tile(ranges,(m,1))
            return normDataSet,ranges,minVals
1
2
>>>reload(kNN) 
>>>normMat,ranges,minVals=kNN.autoNorm(datingDataMat)

5. 原始分类器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#原始测试分类器
def datingClassTest():
        hoRatio=0.10
        datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')
        normMat,ranges,minVals=autoNorm(datingDataMat)
        m=normMat.shape(0)
        #10%的数据用于测试数据集
        numTestVecs=int(m*hoRatio)
        errorCount=0.0
        for i in range(numTestVecs):
                classifierResults=classify0(normMat[i,:],normMat[numTestVecs:m,:], datingLabels[numTestVecs:m],3)
                print("the classifier came back with: %d,the real answer id: %d"%(classifierResults,datingLabels[i]))
                if(classifierResults!=datingLabels[i]):errorCount +=1.0
        print("the total error rate is: %f" %(errorCount/float(numTestVecs)))

6. 接口

1
2
3
4
5
6
7
8
9
10
11
# 约会网站预测函数
def classifyPerson():
        resultList=['not at all','in small doses','in large doses']
        percentTats=float(input("在游戏上花费的时间占比( )?"))
        ffMiles=float(input("每年航空的里程数?"))
        iceCream=float(input("每年吃的冰淇淋（升）?"))
        datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')
        normMat, ranges, minVals=autoNorm(datingDataMat)
        inArr=array([ffMiles,percentTats,iceCream])
        classifierResult=classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
        print("你可能是属于以下这类人：",resultList[classifierResult - 1])

7. 识别手写数字

1
2
3
4
5
6
7
8
9
10
11
# 将图片格式处理为一个向量（把一个32*32的二进制图形矩阵转换为1*1024的向量）,然后使用分类器处理图形信息
def img2vector(filename):
    # 创建一个1*1024的NumPy数组
    returnVect = zeros((1,1024))
    fr = open(filename)
    # 循环读出文件的前32行，并将每行的头32个字符值存储在NumPy数组中，最后返回数组
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def handwritingClassTest():
    hwLabels = []
    # 将trainingDigits目录中的文件存储在列表中
    trainingFileList = listdir('trainingDigits')
    # 获得文件数赋值给m
    m = len(trainingFileList)
    # 创建一个m行1024列的训练矩阵，每行数据存储一个图像
    trainingMat = zeros((m,1024))
    for i in range(m):
        # 从文件名解析分类数字（eg：文件9_45.txt表示数字9的第45个实例）
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        # 将类代码存储在 hwLabels向量中
        hwLabels.append(classNumStr)
        # 使用 img2vector函数载入图像
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)

    # 将testDigits目录中的文件存储在列表中，步骤同上
    testFileList = listdir('testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        # 不同的是要使用 classify0函数测试目录下的每个文件（文件中的值介于0-1之间，无需用autoNorm()函数
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr): errorCount += 1.0
    print("\nthe total number of errors is: %d" % errorCount)
    print("\nthe total error rate is: %f" % (errorCount/float(mTest)))

github代码