机器学习实战-KNN

KNN
k-近邻算法(knn)是机器学习分类算法中最简单而且相当高效的算法,它的主要思想就是,选择与测试样本最相似的前K个训练样本,其中同一标签个数最多的标签就是测试样本的结果。一般来说,我们只选择样本数据集中前K个最相似的数据,这就是knn算法中k的出处,通常k是不大于20的整数。
下面我们使用Python语言实现简单的knn分类算法(按照《机器学习实战》),代码如下:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from numpy import *
import operator

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

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)
return sortedClassCount[0][0]

def file2matrix(filename):
fr = open(filename)
arrayOLines = fr.readlines()
numberOfLines = len(arrayOLines)
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

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))
return normDataSet, ranges, minVals

def datingClassTest(k):
hoRatio = 0.10
datingDataMat, datingLabels = file2matrix('datingTestSet2.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], k)
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))

knn算法比较简单,并且使用python语言,所以可以很快地实现该算法。动手跟着《机器学习实战》这本书敲了一遍代码之后,对knn的理解更加深入了一点。千里之行,始于足下。

了解word2vec

image

一、什么是word2vec

word2vec是Google在2013年中开元的一款将词表征为实数值向量的高效工具,采用的模型有CBOW(Continuous Bag-Of-Words,即连续的词袋模型)和Skip-Gram两种。word2vec项目主页地址点击,它遵循Apache License 2.0 开源协议,是一种对商业友好的许可,需要充分尊重原作者的著作权。
word2vec一般被外界认为是一个Deep Learning(深度学习)的模型,究其原因,可能和作者Tomas Mikolov的Deep Learning背景以及word2vec是一种神经网络模型相关,但我们认为该模型层次较浅,严格来讲还不能算是深层模型。当然如果word2vec上层再套一层与具体应用相关的输出层,比如Softmax,此时更像是一个深层模型。
word2vec通过训练,可以把对文本内容处理简化为K维向量空间中的向量运算,而向量空间上的相似度可以用来表示文本语义上的相似度。因此,word2vec输出的词向量可以被用来做很多NLP相关的工作,比如聚类、找同义词、词性分析等。而word2vec被人广为传颂的地方是其他向量的假发组合运算(Additive Compositionality),官网上的例子是:vector(‘Paris’) - vector(‘France’) + vector(‘Italy’) ≈ vector(‘Rome’)。但我们认为这个多少有点被过度炒作了,很多其他降维或主题模型在一定程度也能达到类似效果,而word2vec也只是少量的例子完美符合这种加减法操作,并不是所有的case都满足。
word2vec大受欢迎的另一个原因是其高效性,Mikolov在论文中支出优化的单机版本一天可训练上千亿词。

二、快速入门

  1. 代码下载
  2. 针对个人需求修改makefile文件,也可以不做修改
  3. 运行“make”编译word2vec工具
  4. 运行demo脚本,查看效果

三、背景知识

1.One-hot Representation
NLP相关任务中最常见的第一步是创建一个词表库并把每个词顺序编号。

聚类基本概念

基本概念

聚类是对点集进行考察并按照某种距离测度将它们聚成多个“簇”的过程。聚类的目标是使得同一簇内的点之间距离较小,而不同簇之间的距离较大。聚类的过程即是发现簇的过程。

聚类技术介绍

按照聚类算法所使用的两种不同的基本策略,可以将聚类分为两类。

  1. 一类称为层次聚类或凝聚式算法。这类算法一开始将每个点都看成一个簇。簇与簇之间是按照接近度来组合,而接近度可以基于“接近”的不同含义采用不同的定义。当进一步的组合导致多个原因之一下的非期望结果时,上述组合过程结束。例如,达到预先给定数目的簇时,或者簇内点分散到达一定程度。
  2. 另一类算法涉及点分配过程,即按照某个顺序依次考虑某个点,并将它分配到最适合的簇中,该过程通常都有一个短暂的初始簇估计阶段。

维数灾难

高维的欧氏空间具有一些非直观的有时被称为“维数灾难的性质。非欧空间也往往有同样的反常情况。“灾难”的一个表现是,在高维空间下,几乎所有的点对之间的距离都差不多相等。另一个表现是,几乎任意两个向量之间都是近似正交的。