【机器学习算法基础+实战系列】KNN算法

k 近邻法（K-nearest neighbor）是一种基本的分类方法

基本思路：

给定一个训练数据集，对于新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例多数属于某个类别，就把输入实例分为这个类。

算法：

输入：训练数据集 \(T=\{(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n})\}\) 其中 \(x_{i}\) 是训练集实例的特征向量（features vectors），\(y_{i}\) 是训练集实例的类别，\(i=1,2,3,\cdot\cdot\cdot,N\) (N 代表的是训练集实例的数量)

输出：训练数据集实例的列别\(y\)

模型：

三个基本要素：距离度量（欧几里得距离），k值的选择，分类决策规则（多数表决 )

距离度量：首先特征向量是\(n\)维，\(x_{i}\)是训练数据集中的特征向量，\(x_{j}\)是输入实例的特征向量。

其中\(x_{i}=(x_{i}^{(1)},x_{i}^{(2)},...,x_{i}^{(n)}), x_{j}=(x_{j}^{(1)},x_{j}^{(2)},...,x_{j}^{(n)})\).

两者之间的距离定义为：\(L_{p}(x_{i},x_{j})=(\sum_{t=1}^{n}{|x_{i}^{(t)}-x_{j}^{(t)}|^{p}})^{1/p}\).

在这里\(p\geq1\), 当\(p=2\)时，我们称之为欧氏距离（Euclidean distance），即\(L_{p}(x_{i},x_{j})=(\sum_{t=1}^{n}{|x_{i}^{(t)}-x_{j}^{(t)}|^{2}})^{1/2}\);

当p=1 时，我们称之为曼哈顿距离（Manhattan distance）即\(L_{p}(x_{i},x_{j})=\sum_{t=1}^{n}{|x_{i}^{(t)}-x_{j}^{(t)}|}\). 使用不同的距离度量方法会产生不同的结果。
k值得选择问题：会采取交叉验证的方法选择合适k值
分类决策规则：多数表决

在电影分类中的KNN算法

import numpy as np

import operator #运算符模块

def createDataSet():#创建数据集合标签

    group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])

    labels = ['A','A','B','B']

    return group, labels

group,labels=createDataSet()

def classify0(inx, dataSet, labels, k):

    dataSetSize = dataSet.shape[0]

    diffMat = np.tile(inx, (dataSetSize,1)) - dataSet # tile

    sqDiffMat = diffMat ** 2 #**乘方

    sqDistances = sqDiffMat.sum(axis=1)

    distances = sqDistances ** 0.5

    sortedDistIndicies = distances.argsort()# argsort

    classCount={}#dic

    for i in range(k):

        voteIlabel = labels[sortedDistIndicies[i]]

        classCount[voteIlabel] = classCount.get(voteIlabel,0)+1 #get

    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) # sorted &items()

    return sortedClassCount[0][0]

classify0([0,0],group,labels,3)

在这里我们是自己实现了一个KNN的分类器，我们也可以使用sklearn 中的KNeighborsClassifier 去直接分类，参考这里中的实例

对代码中的基础知识进行总结:

shape( ):numpy

>>> C = np.array([[1,1],[1,2],[1,3],[1,4]])

>>> C.shape()

>>> (4,2)

>>> C.shape[0]

>>> 4

>>> C.shape[1]

>>> 2

tile( ): 重复某个数组(numpy)

>>>A=[1,2,3]

>>>np.tile(A,3)

>>>array([1, 2, 3, 1, 2, 3, 1, 2, 3])

>>>np.tile(A,(3,1))

>>>array([[1, 2, 3],

       [1, 2, 3],

       [1, 2, 3]])

>>>np.tile(A,(3,2))

>>>array([[1, 2, 3, 1, 2, 3],

       [1, 2, 3, 1, 2, 3],

       [1, 2, 3, 1, 2, 3]])

argsort( )

对于一维数组来讲：

>>>x=np.array([3,1,2])

>>>np.argsort(x)

>>>array([1,2,0])  #把索引从小到大列了出来

>>>np.argsort(-x) #按照降序排列

>>>array([0,2,1])

>>>x[np.argsort(x)] #重新排序之后的数组

>>>array([1,2,3])

对于二维数组来说

>>> x=np.array([[0,3],[2,2]])

>>>np.argsort(x,axis=0) #按列排序

>>> array([[0, 1],

           [1, 0]])

>>>np.argsort(x,axis=1)#按行排序

>>>array([[0, 1],

           [0, 1]])

Dictionary get( ):

dict.get(key,default=None) 字典的get()函数返回指定键的值，如果键或者值不存在，返回默认值

sorted( ):

sort 和 sorted 的区别

sort 是应用在list上的方法，sorted是可以对所有可迭代的对象进行排序操作的函数

sort是作用在列表本身，改变原列表 sorted是生成一个新的可迭代的对象

sorted用法

sorted(iterable, key=None, reverse=False)

对由tuple组成的list排序:

>>> students = [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

#使用key函数

>>> sorted(students, key=lambda student : student[2])   # sort by age

>>>[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]  #返回由tuple组成的list

#用 operator 函数来加快速度

>>> sorted(students, key=itemgetter(2))  

#用 operator 函数进行多级排序 

>>> sorted(students, key=itemgetter(1,2))  # sort by grade then by age

>>>[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]  

对由字典排序 ，返回由tuple组成的List,不再是字典

>>> d = {'data1':3, 'data2':1, 'data3':2, 'data4':4}

>>> sorted(d.items(), key=itemgetter(1), reverse=True)

>>>[('data4', 4), ('data1', 3), ('data3', 2), ('data2', 1)]

items( )

dict.items():

>>>dict = {'Google': 'www.google.com', 'Runoob': 'www.runoob.com', 'taobao': 'www.taobao.com'}

>>>dict.items()

>>>dict_items([('Google', 'www.google.com'), ('Runoob', 'www.runoob.com'), ('taobao', 'www.taobao.com')]) #返回的是一个列表

在约会网站使用KNN算法

#对TXT文件中的数据进行处理

import numpy as np

def file2matrix(filename):

    fr = open(filename)#打开某个文件

    arrayOLines = fr.readlines()

    numberOfLines = len(arrayOLines)

    returnMat = np.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

datingDataMat, datingLabels = file2matrix('datingTestSet.txt')

read( ) & readline( ) & readlines( ):

>>>f=open('test_read()&readlines().txt')

>>>f.read()

>>>'Monday \nTuesday \nWednesday\nThursday\nFriday\nSaturaday\nSunday'   #一次性读取文本中全部的内容，以字符串的形式返回结果

>>>f.readline()

>>>'Monday\n'     #只读取文本第一行的内容，以字符串的形式返回结果

>>> f.readlines()

>>>['Tuesday\n', 'Wednesday\n', 'Thursday\n', 'Friday\n', 'Saturday\n', 'Sunday\n']    #读取文本所有内容，并且以数列的格式返回结果，一般配合for in使用

strip( ):

strip() 用于移除字符串头尾指定的字符，默认为空格

>>>str = "0000000     Runoob  0000000";

>>>print str.strip( '0' );  # 去除首尾字符 0

>>>str2 = "   Runoob      ";   # 去除首尾空格

>>>print str2.strip();

>>>     Runoob

>>>Runoob

split( ):

>>>str = "Line1-abcdef \nLine2-abc \nLine4-abcd";

>>>print (str.split( ));

>>>print (str.split(' ', 1 ));

>>>['Line1-abcdef', 'Line2-abc', 'Line4-abcd']

>>>['Line1-abcdef', '\nLine2-abc \nLine4-abcd']

归一化特征值

在K-means的方法中，我们采取的是欧几里得距离。我们观察特征值的大小发现不同特征值在数值上差别很大，这就导致某一个特征值发生一点变化之后，导致欧几里得距离发生很大的变化，所以为了避免这种情况的出现我们决定归一化数据。

def autoNorm(dataSet):

    minVals = dataSet.min(0)

    maxVals = dataSet.max(0)

    ranges = maxVals - minVals

    normDataSet = np.zeros(np.shape(dataSet))

    m = dataSet.shape[0]

    normDataSet = dataSet - np.tile(minVals, (m,1))

    normDataSet = normDataSet/np.tile(ranges,(m,1))

    return normDataSet, ranges, minVals

normMat,ranges,minVals = autoNorm(datingDataMat)

normMat

min( ):numpy

>>>a=np.array([[1,5,3],[4,2,6]])

>>>print(a.min()) #无参数，所有值中的最小值

>>>1

>>>print(a.min(0))#axis=0,每列中的最小值

>>>[1 2 4]

>>>print(a.min(1))#axis=1,每行中的最小值

>>>[1 2]

测试代码

def datingClassTest():

    hoRatio = 0.1

    datingDataMat, datingLabels = file2matrix('datingTestSet.txt')

    normMat,ranges,minVals = autoNorm(datingDataMat)

    m = normMat.shape[0]

    numTestVecs = int(m * hoRatio)

    errorCount = 0.0

    for i in range(numTestVecs):

        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

    print('the total error rate is : %f ' % (errorCount/float(numTestVecs)))  

datingClassTest()

构建完整的可用系统

def classifyperson():

    resultList = ['not at all','in small doses','in large doses']

    percenTats = float(input('percentage of time spent playing video games?'))

    ffMiles = float(input('frequent flier miles earned per year?'))

    iceCream= float(input('liters of ice cream consumed per year?'))

    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')

    normMat,ranges,minVals= autoNorm(datingDataMat)

    inArr = np.array([ffMiles,percenTats,iceCream])

    classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)

    print('you will probbably like this person: ',resultList[classifierResult -1]) 

classifyperson()

巴特西

【机器学习算法基础+实战系列】KNN算法

基本思路：

算法：

模型：

在电影分类中的KNN算法

在约会网站使用KNN算法

最新文章

热门文章