机器学习之K近邻算法
概述
AI不断的火起来了，作为工程化的码农，也得奔向国际化轨道了。至于机器学习是什么，不知道找百科。现在大多数机器学习都是采用监督学习形式。我们学习一下KNN算法。
KNN
KNN(K近邻)算法属于监督学习的分类问题，采用不同feature之间的距离方法进行分类。 1.优点:精度高、对异常值不敏感、无数据输入规定，不需要训练算法。 2.缺点:计算复杂度和空间复杂度高。 3.原理:依据训练样本集中的每个数据对应一个标签，每个数据集中每一个数据与分类一一对应关系，输入没有标签的数据后KNN算法将新数据的每个特征与样本集中数据对应的特征进行比较，然后提出样本集中特征醉相思的数据的分类标签。比如：依据花瓣、花蕊等features标记的类，对输入的测试数据进行最佳匹配。或者依据打斗镜头、接吻镜头等Features将电影分为爱情片、动作片等。
Demo
标量文本数字的KNN
比如对一个约会网站寻找自己的最适合的约会对象，比如将约会的人分类为:
- 不喜欢的人
- 魅力一般的人
- 极具魅力的人
周一至周五我一般会选择魅力一般的人，周末选择极具魅力的人。我手中大约有1000多个约会对象，每个约会对象具有以下三个特征
- 每年飞行常客里程数
- 玩视频游戏时间百分比
- 每周消费的冰淇淋公升数
我要将1000多个对象依据这三个features分为上述三类人。下面请看具体的流程
准备数据
数据是在<机器学习实战>中datingTestSet.txt,由于”每年飞行常客里程数”是一个非常大的整数，且”玩视频游戏时间百分比”和”每周消费的冰淇淋公升数”是一个非常小的数值，如果不经过归一化处理之后那么相似性的判断上主要取决于”每年飞行常客里程数”，所以需要经过归一化处理。每个特征的贡献度都是一样的，所以需要将每个特征值进行归一化处理。归一化处理有以下几部分： 0-1归一化，将数据映射到[0-1]范围内。
x^*=\frac{x-min}{max-min}
0-均值规范化(标准差标准化),经过处理的数据的均值为0，标准差为1.
x^*=\frac{x_i-x}{\sigma}
小数定标准规范化
x^*=\frac{x}{10^k}
import pandas as pd
data = pd.read(file)
#0-1归一化
t1=(data-data.min())/(data.max()-data.min())
#0-均值标准化
t2=(data-data.mean())/data.std()
#小数定标规范化
t3=data/10**np.ceil(np.log10(data.abs().max()))我们看一下测试数据中的数据的格式，然后将“每年飞行常客里程数”0-1归一化，然后数据的格式进行处理即可。
# [每年飞行常客里程数 玩视频游戏时间百分比 每周消费的冰淇淋公升数 样本分类]
40920 8.326976 0.953952 3
14488 7.153469 1.673904 2
26052 1.441871 0.805124 1
75136 13.147394 0.428964 1
38344 1.669788 0.134296 1
72993 10.141740 1.032955 1
35948 6.830792 1.213192 3
42666 13.276369 0.543880 3
67497 8.631577 0.749278 1pandas走起，代码如下：
test = pd.read_table('./datingTestSet2.txt',names=['year','game','ice','class'])
In [99]: test[:3]
Out[99]:
year game ice class
0 40920 8.326976 0.953952 3
1 14488 7.153469 1.673904 2
2 26052 1.441871 0.805124 1
#归一化处理
In [102]: f = lambda x:(((x-x.min())/(x.max()-x.min())) if x.name!='class' else x)
In [103]: test=test.apply(f)
In [104]: test[:3]
Out[104]:
year game ice class
0 0.448325 0.398051 0.562334 3
1 0.158733 0.341955 0.987244 2
2 0.285429 0.068925 0.474496 1下面我们来看一下完整的书写代码的两种方式第一种采用DataFrame结构，第二种采用numpy的array结构。
def class_knn(x,data,label,k=1):
#归一化处理函数
f = lambda x:(x-x.min())/(x.max()-x.min())
#构造一个数据集，并对数据采用同样的归一化
test = (DataFrame(x,index=data.index) - data.min())/(data.max()-data.min())
data = data.apply(f)
diff = ((test-data)**2).sum(axis=1)**0.5
indexs = diff.sort_values(axis=0,ascending=True)[:k].index
return label[indexs].values
if __name__ == "__main__":
test = pd.read_table('datingTestSet2.txt',names=['year','game','ice','class'])
data,label = test.ix[:,['year','game','ice']],test['class']
x = {'year':10000,'ice':0.5,'game':10}
print class_knn(x, data, label)第二种，也就是机器学习实战中的代码片段。
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
sortedDistIndicies = distances.argsort()
classCount={}
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)
print sortedClassCount
return sortedClassCount[0][0]
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m,1))
normDataSet = normDataSet/tile(ranges, (m,1)) #element wise divide
return normDataSet, ranges, minVals
# 文件转矩阵处理函数
def file2matrix(filename):
fr = open(filename)
numberOfLines = len(fr.readlines()) #get the number of lines in the file
returnMat = zeros((numberOfLines,3)) #prepare matrix to return
classLabelVector = [] #prepare labels return
fr = open(filename)
index = 0
for line in fr.readlines():
line = line.strip()
listFromLine = line.split('\t')
returnMat[index,:] = listFromLine[0:3]
classLabelVector.append(int(unicode(listFromLine[-1])))
index += 1
return returnMat,classLabelVector你也可以对数据进行分析和可视化，由于博主只是学习算法的思想。对于计算相似性，不仅可以采用欧氏距离，还有很多计算相似性的重要方法。比如：Pearson相关系数和Spearman秩相关系数。
参考书籍
《机器学习实战》 《统计学习方法》