《机器学习实战》2：K-近邻算法(kNN/K个好邻居)

写在前面的话   
从这一篇文章，开始讲述具体的算法。仍然是依照<机器学习实战>上的内容同步博客内容。在该博客中首先会简要介绍一下每个算法，主要篇幅放在代码的实现及代码的解释上，最后都会提供源代码的下载。我会保证每个程序都自己测试过再放上来，只要你使用的环境和我的环境是相同的，就应该可以运行。当然这些代码在原书提供的地址：http://www.manning.com/pharrington/ 中也可以下载到。
1、开发机器学习应用程序的步骤
(1)收集数据：收集各种样本数据，为了节省时间，可以使用公开的可用数据源
(2)准备输入数据：确保数据格式符合要求，本书采用的格式是Python语言的List。
(3)数据分析：人工分析以前得到的数据，确保数据集中没有垃圾数据。
(4)训练算法，这一步才是机器学习真正的开始，对于监督学习，我们把之前的格式化数据输入到算法中，得到分类模型，方便后续处理。对于无监督学习，不存在目标变量，因此也不需要训练算法。
(5)测试算法：这一步使用第4步机器学习的模型。这一步主要测试算法的工作效率。
(6)使用算法：将机器学习算法转换为应用程序，执行实际任务。

以后所有的算法我们都会依照以上的步骤进行开发。

2、kNN算法的工作原理：存在一个样本数据集合，也称作样本集，并且样本集中的每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中的数据对应的特征进行比较，然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般，我们只选择样本数据集中前k个最相似的数据，这就是k近邻算法的出处。
3、算法的实现：
(1)首先，我们使用一个简单的二维数据集作为训练集。
新建kNN.py文件，编辑代码如下：

#设置训练数据集，group表示具有多个属性的数据，labels的每个值对应group每行数据的标签
from numpy import *
import operator

def createDataSet():
	group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
	labels=['A','B','A','B']
	return group,labels

(2)有了训练数据，现在我们就需要实现算法，新建classify0()函数实现kNN算法

#k个好邻居算法 输入参数：inX用于分类的输入向量，dataSet训练样本集
#标签向量labels，k表示用于选择最近邻居的数目，必须是整数
def classify0(inX,dataSet,labels,k):
        #训练数据集的行数
        dataSetSize=dataSet.shape[0]
        #计算距离
        #这里要说一下tile()函数，以后我们还会多次用到它
        #tile(A,B)表示对A重复B次，B可以是int型也可以是数组形式
        #如果B是int，表示在行方向上重复A，B次，列方向默认为1
        #如果B是数组形式，tile(A,(B1,B2))表示在行方向上重复B1次，列方向重复B2次
        diffMat=tile(inX,(dataSetSize,1))-dataSet
        print diffMat
        sqDiffMat=diffMat**2
        print sqDiffMat
        sqDistances=sqDiffMat.sum(axis=1)
        distances=sqDistances**0.5
        #排序，这里argsort()返回的是数据从小到大的索引值,这里这就是第几行数据
        sortedDisIndicies =distances.argsort()
        print sortedDisIndicies
        classCount={}
        #选取距离最小的k个点，并统计每个类别出现的频率
        #这里用到了字典get(key,default=None)返回键值key对应的值；
        #如果key没有在字典里，则返回default参数的值，默认为None
        for i in range(k):
                voteIlabel=labels[sortedDisIndicies[i]]
                classCount[voteIlabel]=classCount.get(voteIlabel,0)+1;
        #逆序排序，找出出现频率最多的类别
        sortedClassCount=sorted(classCount.iteritems(),
                                key=operator.itemgetter(1),reverse=True)
        print sortedClassCount
        return sortedClassCount[0][0]

(3)写完了算法，有了训练数据集，下面我们就可以测试算法了
进入python界面：
>>>import kNN
回车
>>>group,labels=kNN.createDataSet()
回车
>>>kNN.classify0([0,0],group,labels,3)
回车

可见最后的输出结果为B，也就是说我们的kNN模型将数据[0，0]分到了B类。

这样我们就完成了整个模型的实现，还算简单吧。别得意，这只是一个hello world，我们来看一下具体的示例。

写到这里，不得不提一下，楼主之前没有用过python，今天用了之后发现python肯定是个爷们儿，简单、强大又直接。

4、示例一：约会网站
海伦用三个属性来测试自己对于约会对象的喜爱程度
  每年的飞行里程数
  玩视频游戏所耗时间百分比
  每周消费的冰激凌公升数
她积攒了一些数据，该数据保存在datingTestSet.txt中，共1000行。

（1）我们首先需要一个函数解析这些数据：

def file2matrix(filename):
        fr=open(filename)
        #读取文件
        arrayOLines=fr.readlines()
        #文件行数
        numberOfLines=len(arrayOLines)
        #创建全0矩阵
        returnMat=zeros((numberOfLines,3))
        #标签向量
        classLabelVector=[]
        index=0
        #遍历每一行，提取数据
        for line in arrayOLines:
                line=line.strip();
                listFromLine=line.split('\t')
                #前三列为属性信息
                returnMat[index,:]=listFromLine[0:3]
                #最后一列为标签信息
                classLabelVector.append(int(listFromLine[-1]))
                index +=1
        return returnMat,classLabelVector

重新加载kNN，得倒解析数据
>>>reload(kNN)
>>>datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt')

（2）图形展示数据

这样我们就得到了解析的数据，但是这么多的数据叫人怎么看啊，一点都看不出是干什么用的，好似一锅蚂蚁啊。好在python还给我们提供了强大的画图功能。
>>>import matplotlib
>>>import matplotlib.pyplot as plt
>>>from numpy import array
>>>fig = plt.figure()
>>>ax=fig.add_subplot(111)
>>>ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
>>>plt.show()
这样就可以直观的看到点的分布：

同样从以第一列和第二列画图更清晰一些：


（3）数据的归一化
由于每个属性的取值数量级相差过大，会造成每个属性的权重不同，这显然是海伦不希望的。所以我们还要写一个函数实现数据归一化，公式如下：
newValue=(oldValue-min)/(max-min)
这个公式可以将特征值转化为0~1之间的值。

#归一化特征值
def autoNorm(dataSet):
        #每列的最小值
        minVals=dataSet.min(0)
        #每列的最大值
        maxVals=dataSet.max(0)
        #最大值与最小值的差值
        ranges=maxVals-minVals
        normDataSet=zero(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

>>>reload(kNN)
>>>normMat,ranges,minVals=kNN.autoNorm(datingDataMat)

（4）接下来我们终于要测试分类器了

#测试分类器
def datingClassTest():
        hoRatio=0.10
        datingDataSetMat.datingLabels=file2matrix('datingTestSet.txt')
        normMat,ranges,minVals=autoNorm(datingTestSet)
        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))

>>>kNN.datingClassTest()

分类器处理约会数据集的错误率是0.05，说明我们的分类器还是可靠的。

（5）使用模型

我们给海伦提供一个接口，方便她通过我们的分类器筛选她的约会对象。

#使用算法
def classifyPerson():
        resultList=['not at all','in small doses','in large doses']
        percentTats=float(raw_input(\
                "percentage of time spent playing video games?"))
        ffMiles=float(raw_input(\
                "frequent flier miles earned per year?"))
        iceCream=float(raw_input(\
                "liters of ice cream consumed per year?"))
        datingDataSetMat,datingLabels=file2matrix('datingTestSet2.txt')
        normMat,ranges,minVals=autoNorm(datingDataMat)
        inArr=array([ffMiles,percentTats,iceCream])
        classiferResult=classify0((inArr-\
		minVals)/ranges,normMat,datingLabels,3)
        print "You will probably like this person:",\
              resultList[classifierResults-1]

>>>kNN.classifyPerson()

按照提示输入约会对象的信息，分类器就会给出海伦对这个对象的喜欢程度。

到这里我们就大功告成了。

累死了我了，容我喘口气，喝杯夏日特饮，凉白开.....


这样我们就完成了第一个算法的实现，也从整体上理解了机器学习的一个过程。

其实，我们可以把机器学习过程比作算命过程。我们要做的就是算命先生，算法就对应着周易啊风水啊八字啊等等。当客户来算命的时候，我们首先需要客户提供一些自身的知识，这些就是实际的应用数据。我们对客户的数据使用我们的算法（八字or属相or星座算法）给客户算命，客户提供的信息越多，我们算的就越准。所以，不要小看算命先生，他们每一个都是伟大的机器学习工程师。哈哈，楼主要歇歇啦。