KNN K近邻算法

 

算法特点

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

缺点：计算复杂度高、空间复杂度高。

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

算法内容

选择样本数据集中前k个最相似的数据，k个最相似数据中出现次数最多的分类，作为新数据的分类。

通俗地讲，想判定某个数据的类别，先找到距离最近的k个数(平方和再开方求距离)，再看k个数据中处在哪个类别的数最多

 

 归一化数值

     将任意取值范围的特征值转化为0到1区间内的值   newValue = {oldValue - min) / (max-min)

def datingClassTest():    hoRatio = 0.50      #hold out 10%    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file    normMat, ranges, minVals = autoNorm(datingDataMat)    m = normMat.shape[0]    numTestVecs = int(m*hoRatio)    errorCount = 0.0    for i in range(numTestVecs):        #参数1 normMat[i,:]    1-500行 的1行        #参数2 normMat[numTestVecs:m,:]    500-1000行 的500行         #参数3 datingLabels[numTestVecs:m],3) 500-1000行 的500行 result         #参数4 k=3        classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)        print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])        if (classifierResult != datingLabels[i]): errorCount += 1.0    print "the total error rate is: %f" % (errorCount/float(numTestVecs))    print errorCount

 每判定一次，需要比较500次，计算量比较大

在这里k定为3，一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k近邻算法中k的出处,通常k是不大于20的整数。

最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

def classify0(inX, dataSet, labels, k):     #计算距离，行的个元素的平方差    dataSetSize = dataSet.shape[0]    diffMat = tile(inX, (dataSetSize,1)) - dataSet    sqDiffMat = diffMat**2    sqDistances = sqDiffMat.sum(axis=1)    distances = sqDistances**0.5        #排序，选择k个最小的距离    sortedDistIndicies = distances.argsort()         classCount={}       # k个数据当中每个类型次数统计,然后从大到小排序, 选择次数最多作为判定结果         # 例如 分类1:1次   分类2:3次  分类3:2次    最终选择 分类2    for i in range(k):        voteIlabel = labels[sortedDistIndicies[i]]        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)    return sortedClassCount[0][0]

知识点 

机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的90%作为训练样本来训练分类

器，而使用其余的10%数据去测试分类器，检测分类器的正确率