advse/3.tex

%\documentclass[a4paper,12pt,UTF8,titlepage]{ctexart}

\documentclass[12pt,a4paper,titlepage]{article}
\usepackage{xltxtra,fontspec,xunicode}
\usepackage[slantfont,boldfont]{xeCJK}

\setmainfont{STSong} % 设置文档默认字体

\usepackage{setspace}%使用间距宏包
\usepackage{indentfirst}
\setlength{\parindent}{2em}


\usepackage{titlesec}
\titleformat*{\section}{\centering\huge\bfseries}

%页边距
\usepackage{geometry}
\geometry{left=2.0cm,right=2.0cm,top=2.5cm,bottom=2.5cm}

%页眉
\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{李志星 15060025 } 
\date{2016年6月20日}
\chead{KNN在Spark上的实现}
\rhead{\leftmark}

%文档信息/同时也用于生成报告封面
\author{李志星\\ 15060025}
\title{\Huge KNN在Spark上的实现}


\usepackage{graphicx}
\usepackage{subfigure}
\DeclareGraphicsExtensions{.eps,.ps,.jpg,.bmp,.gif,.png}

\usepackage{pythonhighlight}


\begin{document}
\begin{spacing}{1.5}
\maketitle

\section{实验内容}
Spark MLlib实现了常用的机器学习算法，包括Logistic回归、决策树、随机森林、K-menas等。和我了解到的机器学习算法相比，分类算法中的KNN算法Saprk MLlib并没有实现，因此本次实验我在Spark平台实现的KNN算法。由于首次接触Spark编程，而网上教程又比较少，所以大部分思路都是参考官方提供的实例结合自己的理解完成的。
\subsection{KNN}
KNN(K-Nearest Neighbors)算法是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法就是找出与未知样本x距离最近的k个训练样本，看这k个样本中多数属于哪一类，就把x归为那一类。k-近邻方法是一种懒惰学习方法，它存放样本，直到需要分类时才进行分类。

KNN算法流程大致如下：
\begin{itemize}
\item 选择一种距离计算方式, 通过数据所有的特征计算新数据与已知类别数据集中的数据点的距离
\item 按照距离递增次序进行排序，选取与当前距离最小的k个点
\item 返回k个点出现频率最多的类别作预测分类
\end{itemize}

\begin{figure}[h!] 
\centering
\includegraphics[width=8cm]{knn.png}
\caption{KNN示意图}
\label{knn}
\end{figure}
以上图为例，在这个图中我假设有三类数据：五角星、三角形和多边形。中间的圆形是未知类型的数据点，现在需要判断这个数据是属于五角星、三角形和多边形中的哪一类。按照NKK的思想，先把离这个圆圈最近的几个点找到，因为离圆圈最近的点对它的类别有判断的帮助。那到底要用多少个来判断呢？这个个数就是k了。如果k=3，就表示要选择离圆圈最近的3个点来判断，由于三角形所占比例为2/3，所以可以认为圆形表示的未知类是和三角形是一类的。如果k=6，由于多边形多占比例最大为1/2，为因此圆圈被认为是属于多边形一类的。从这个例子也可以看出k值对最后结果的影响还是挺大的。

在使用KNN算法的时候有些地方需要注意。数据的所有特征都要做可比较的量化，若是数据特征中存在非数值的类型，必须采取手段将其量化为数值。举个例子，若样本特征中包含颜色（红黑蓝）一项，颜色之间是没有距离可言的，可通过将颜色转换为灰度值来实现距离计算；另外，样本有多个参数，每一个参数都有自己的定义域和取值范围，他们对distance计算的影响也就不一样，如取值较大的影响力会盖过取值较小的参数。为了公平，样本参数必须做一些scale处理，最简单的方式就是所有特征的数值都采取归一化处置； 需要一个distance函数以计算两个样本之间的距离。距离的定义有很多，如欧氏距离、余弦距离、汉明距离、曼哈顿距离等等。 一般情况下，选欧氏距离作为距离度量，但是这是只适用于连续变量。通常情况下，如果运用一些特殊的算法来计算度量的话，K近邻分类精度可显著提高，如运用大边缘最近邻法或者近邻成分分析法；K值的确定，K是一个自定义的常数，K的值也直接影响最后的估计，一种选择K值得方法是使用 cross-validate（交叉验证）误差统计选择法。交叉验证的概念之前提过，就是数据样本的一部分作为训练样本，一部分作为测试样本，比如选择95\%作为训练样本，剩下的用作测试样本。通过训练数据训练一个机器学习模型，然后利用测试数据测试其误差率。 cross-validate（交叉验证）误差统计选择法就是比较不同K值时的交叉验证平均误差率，选择误差率最小的那个K值。例如选择K=1,2,3,… ， 对每个K=i做100次交叉验证，计算出平均误差，然后比较、选出最小的那个。


总的来说，KNN优点有：
\begin{itemize}
\item 简单，易于理解，易于实现，无需估计参数，无需训练。
\item 适合对稀有事件进行分类。
\item 特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好。
\end{itemize}

NKK缺点有：
\begin{itemize}
\item 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。
\item 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。
\end{itemize}

\subsection{安装实验环境}
\begin{itemize}
\item Spark：1.6.1，Spark官网提供多个下载形式，可以下载源代码也可以下载预编译好的。我下载的是编译好了的Pre-built for Hadoop 2.6。下载地址为：http://www.apache.org/dyn/closer.lua/spark/spark-1.6.1/spark-1.6.1-bin-hadoop2.6.tgz
\item 依赖：JDK，因为Spark运行在JVM之上，所以首先需要安装JDK并配置好系统环境变量。
\item 操作系统：Ubuntu 14.04，Spark声称是可以支持Windows和类Unix系统（Linux和Mac OS），不过我在我笔记本Windows系统试了下，会出现一些小问题，所以我干脆在虚拟机里的Ubuntu系统上跑的，运行状态良好，未出现问题。
\item 机器配置（虚拟机）：我使用的是Spark的单节点模式，2G内存，单CPU4核
\item 编程语言：Python，如报告2中所述，Spark本身使用scala语言编写的，但是它还提供了Java、Python和R的接口，综合考虑开发效率和编程语言的易用性，我最后选用的Python。相对Java来说，实现同样的功能，Python写出的代码更简洁些，因此Python很适合来做这种科学研究性质的程序。
\item 其他配置：conf目录下的log4j.properties用于配置Spark的日志输出，Spark默认是把INFO级别及以上的日志信息都进行输出，虽然这对了解它干了哪些工作很有帮助，但是我觉得过多的信息输出到控制台上会影响正常的输出。因此在这里可以把输出日志级别提高些，比如设置为WARN或者ERROR。
\end{itemize}

\subsection{数据集}
和报告2中的一样，我们还是采用MNIST的手写识别数据集，只不过这次用的数据更多，我想把0~9个数字都利用起来，对其进行一个多分类，每个数字都对应着差不多两百个左右的样本，其中训练样本有1934个，测试样本936个。并且每个样本都已经解析到单独的txt文件中，文件内容是个32*32的矩阵，用0、1串来表示数字。具体细节和报告2中是一样的，没什么大的变化。

\section{实验过程}


\subsection{算法模型设计}
本节中简要介绍我实现的KNN涉及到的主要类和算法的大致模型，下一节详细介绍具体实现细节。

\begin{table}[!h]
\renewcommand\arraystretch{2}
\centering
\begin{tabular}{c|c}
\hline
类名 & 功能 \\
\hline
KNN & 实现KNN主要逻辑功能，距离算法由子类实现\\
\hline
KNNWithEuclid &  利用欧几里得距离计算差异性的KNN \\
\hline
KNNWithCos &  利用余弦相似度计算差异性的KNN  \\
\hline
DataHelper & 数据操作的辅助类  \\
\hline
Statistics & 用于统计数据特性的辅助类  \\
\hline
\end{tabular}
\caption{主要相关类及其功能}
\end{table} 

其大致模型如类图所示。

\begin{figure}[h!] 
\centering
\includegraphics[width=16cm]{classfigure.jpg}
\caption{算法模型示意图}
\label{knnmodel}
\end{figure}

使用该算法解决实际问题时通常流程所对应的时序图为。
\begin{figure}[h!] 
\centering
\includegraphics[width=16cm]{seqfigure.jpg}
\caption{算法运行时序图}
\label{knnmodel}
\end{figure}


\subsection{实现KNN算法}
在实现KNN算法的时候，我尽量按照Spark库提供的API设计的，因此传递给KNN的数据都是DataFrame类型的。在新建KNN对象进行分类的时候，需要提供DataFrame的列信息，目前用到的有特征向量列和类标签列，所以初始化函数可疑传递测试数据DataFrame的信息，默认值分别是“features”和“label”。其代码如下所示：
\begin{python}
def __init__(self,featuresCol="features", labelCol="label"):
		self.featuresCol,self.labelCol = featuresCol,labelCol
\end{python}


由于KNN不需要训练因此就没有给他设计用于“训练”的接口，而是直接用classify函数对数据进行分类。函数接受四个参数：inXs，dataSet，K和disFunc，inXs表示要预测的样本，该样本的类标签未知，只包含它的特征向量，该参数类型是DenseVector，在Spark中用来表示本地向量；dataSet表示易知类标签的样本集合，每个样本既包含特征向量也包含类别标签，该参数类型为DataFrame，DataFrame在报告2中以进行过信息介绍，这里就不再赘述了；k是用于指定租后选出k距离最短的近邻的，类型就是int数值类型即可。disFun用于指定计算两个样本点之间“差异性”的距离函数，默认使用计算欧几里得距离的computedDist，关于距离计算后文会有详细介绍。
其主要代码如下：
\begin{python}
def classify(self,inXs,dataSet,k=10,disFun=computedDist):
		if len(inXs) != len(dataSet.first()[self.featuresCol].values):
			print "length of features of inXs is not corresponding with dataset's"
			return 
		dataSet = dataSet.select(self.featuresCol,self.labelCol)
		dis = dataSet.map(lambda row: (row[1],computeDist(row[0].toArray(),inXs.toArray())))
		orderedDis = dis.takeOrdered(k, key=lambda x: x[1])		
		groupLabel  = sc.parallelize(orderedDis).map(lambda row:(row[0],1)).reduceByKey(add).takeOrdered(1,key=lambda row:-row[1])[0][0]
		return groupLabel
\end{python}

上面的代码中，程序逻辑的开始是进行一些常规的数据有效性判断。我代码里写的是判断inXs的维度和dataSet中样本的维度是否一样，也就是特征（属性）数是否一样。其实还可以进行许多其他的判断，就像Spark库中所做的对测试数据（在这里指已经知道类标签的哪些数据样本，后文姑且用训练数据集指代）做的一些统计，在这里也可以进行一些类似的统计。比如可以统计一下所有已知的类标签是否都是属于一个类别，如果是的话，那么对于要预测的样本就不用进行距离的计算了，直接输出该类别即可。不过这些非核心业务逻辑我没有全都写到代码中，毕竟这次实验做得不是一个对外提供服务的库，主要目的是为了体验在Spark上做机器学习算法的开发，因此我在这里用这个维度测试代表一些系列的有效性判断和数据集特点统计。

下面这段代码用于从dataSet这个dataFrame中选择出以self.featuresCol和self.labelCol命名的两列，这两个属性值如前所述，有默认值，也可以经过用户设置。这个函数生成的是一个新的DataFrame，这个新的DataFrame就包含指定的这两个列，这个操作有点类似SQL查询语句。关于DataFram的一些操作细节报告1和2中都没有展开，所以在这里进行一个简单的介绍。DataFrame是基于RDD的，RDD就是一个不可变的分布式对象集合。每个RDD都被分为多个分区，这些分区运行在集群的不同节点上。RDD操作分为两种类型，转换和动作，其中转换时惰性计算的，Spark只会记录下这些转换操作，动作是触发Spark启动计算的动因。下面的select和map都是转换，他们返回的还是DataFrame。
\begin{python}
dataSet = dataSet.select(self.featuresCol,self.labelCol)
\end{python}

接着就是计算inXs与训练数据集每个样本之间的距离，计算距离函数可以有多种选择，常用的有欧几里得距离和余弦相似度，距离计算函数后面会进行详细介绍。这里对dataSet进行了一次map操作，Spark 中的map操作会把dataSet中的每一个元素进行映射，在得到的新的RDD中有且仅有一个新的元素与其对应，也就是说map操作是一一映射的。map函数接受一个函数作为参数，该函数的要求是接收一个参数，这个参数由map传递给它，表示的是dataSet中的一个元素，该函数执行具体的对该元素的映射操作，然后把该结果返回，返回的结果会放到新的DataFrame中，也就是map函数的返回值。
\begin{python}
dis = dataSet.map(lambda row: (row[1],distFun(row[0].toArray(),inXs.toArray())))
\end{python}

上面函数参数我用的python的lambda语法，lambda是一个表达式而不是一个语句，它能够出现在Python语法不允许def出现的地方用来编写简单的函数。返回的是该样本的类标签以及该样本和要预测的样本之间的距离，在计算距离的时候会调用vector的toArray（）方法把其转换为numpy中的array便于后面的计算过程。


这一行函数用于对表示距离的dis这个dataFrame进行排序，dis有两个列，类标号和距离值。排序是按照距离值排的，并且顺序是按照从小到大排的，k用于指定返回排序后的前k个数值。这个函数返回的就是k个和要预测的样本距离最近的数据点，返回的数据类型是list。
\begin{python}
orderedDis = dis.takeOrdered(k, key=lambda x: x[1])	
\end{python}

算法的最后一步就是从k个距离最短的样本点中选择所占比例最多的类别。由于上一步返回的结果是普通的list类型的数据，所以首先用paralelize函数把list转换为RDD数据便于后续进行并行化操作，这一步要对k个样本点进行归类技术，这是一个电信的MapReduce模型的问题，首先把数据格式转换为（类标号，1）的形式，这样的形式便于后面reduce利用add函数对其进行累加。计数完成后再用排序函数对其按从大到小的顺序进行排列，最后返回所占比例最大的的类别就是最终要预测的分类结果。
\begin{python}
label  = sc.parallelize(orderedDis).map(lambda row:(row[0],1)).reduceByKey(add).takeOrdered(1,key=lambda row:-row[1])[0][0]
\end{python}

距离函数（或者说为差异性函数）的计算有多种形式，一种是衡量空间各点间的绝对距离的“距离度量”；一种是衡量空间向量的夹角的“相似度度量”，更加的是体现在方向上的差异，而不是位置。“距离衡量”中常用的有欧几里得距离、明可夫斯基距离、曼哈顿距离和切比雪夫距离；“相似度度量”中常用的有向量空间余弦相似度、皮尔森相关系数和Jaccard相似系数等。其实很多的距离度量和相似度度量都是基于欧几里得距离和余弦相似度的变形和衍生，所以本报告重点比较了此两者对KNN在手写手别问题的影响，不过关于这两个度量标准的计算公式本报告就不再展开了，他们的计算过程还是比较简单的。在python中使用numpy进行向量的运算是很简便的，两个向量a和b之间的欧几里得距离和余弦相似度的计算过程如下：
\begin{python}
#Euclidean Distance
np.sqrt(np.sum((a-b)**2))
#Cosine Similarity
a.dot(b) / (np.sqrt(a.dot(a)) * np.sqrt(b.dot(b)))
\end{python}

\subsection{测试算法效果}
首先是加载数据，利用的还是报告2中编写的loadData函数。测试样本在testData中，我在程序中用的的迭代使用knn对每个样本进行预测，然后统计预测失败的个数，最后看其错误率。在这里我曾经做过一个尝试，把整个testData作为一个DataFrame传给knn的classify函数（这和库提供的API是一致的），然后利用map函数对每一个样本计算其预测结果。但是在具体运行的时候就出错了，因为在利用map函数对每一个样本预测的时候，预测过程会在每一个worker节点进行工作，但是预测过程又会对dataSet进行一系列的操作，这不符合Spark闭包函数的要求。这里不像报告2中使用的Spark库，它们先把模型训练出来，然后在预测的时候直接用模型来对其进行计算，在函数体内不会访问外部变量。因此我就设计classify每次针对一个样本进行预测，在程序外对所有样本的预测结果进行统计。
\begin{python}
for x in testData:
		prediction = knn.classify(x[0],datasetDF,4)
		if prediction != x[1]:
			errorCount += 1
		count += 1
	print "error rate is %f(%d/%d)" % (1.0 * errorCount / count,errorCount,count)
\end{python}

\subsection{运行算法}
我把KNN算法实现文件KNN.py放到了和Spark同级的目录中，因此要把该文件提交给Spark执行只需执行以下命令：
\begin{figure}[h!] 
\centering
\includegraphics[width=12cm]{launch_knn.jpg}
\caption{运行knn.py命令}
\label{launch_knn}
\end{figure}

\section{实验结果}
本次报告分别从K值和距离算法两个方面对实现的KNN算法进行测试，下面两个表分别是K值从1到10时利用欧几里得距离和余弦相似度对946个样本利用KNN预测得到的结果：

\begin{table}[!h]
\renewcommand\arraystretch{1.1}
\centering
\begin{tabular}{c c c}
\hline

K值 & 预测错误数 & 预测错误率 \\
\hline
1 & 13 & 0.013742  \\

2 & 12 & 0.012685  \\

3 & 11 & 0.011628  \\

4 & 12 & 0.012685  \\

5 & 17 & 0.017970  \\

6 & 17 & 0.017970  \\

7 & 20 & 0.021142  \\

8 & 19 & 0.020085  \\

9 & 22 & 0.023256  \\

10 & 20 & 0.021142  \\
\hline
\end{tabular}
\caption{利用欧几里得距离得到的结果}
\end{table} 

\begin{table}[!h]
\renewcommand\arraystretch{1.1}
\centering
\begin{tabular}{c c c}
\hline
K值 & 预测错误数 & 预测错误率 \\
\hline
1 & 11 & 0.011628  \\

2 & 17 & 0.017970  \\

3 & 13 & 0.013742  \\

4 & 14 & 0.014799  \\

5 & 14 & 0.014799  \\

6 & 15 & 0.015856  \\

7 & 18 & 0.019027  \\

8 & 20 & 0.021142  \\

9 & 25 & 0.026427  \\

10 & 26 & 0.027484  \\
\hline
\end{tabular}
\caption{利用余弦相似度得到的结果}
\end{table} 
从上面两个表中可以看出，K的取值对于距离函数取欧几里得距离还是余弦相似度都有很大的影响。在K值取1到10这个范围内，欧几里得算法随着K值的增加，错误率先是下降然后再增高，并且K=3的时候效果最好，错误率是最低的，并且在K=8的时候又出现了一个波动。对于余弦相似度来说，在K=1的时候效果最好，随着K值的增加，错误率是先增高后下降然后再增高。在取相同的K值时两个距离函数的错误率不好比较，都有表现好的情况也都有表现差的情况，很少有一样的情况。但是在K取值在1到10这个区间内，他们两个取到的最好效果是一样的，都是错判11个样本。当然如果K的取值范围更大一些的话，错误率肯定还会变化。通过上面的对比可以发现KNN算法对参数K和距离函数的选择还是很敏感的。


\section{实验总结}

通过本次实验，我基于Spark实现了KNN算法，Spark提供了非常丰富的API来支持分布式计算，同时KNN算法的计算过程又很简洁，所以本次的实验过程没有遇到太大的问题。在实现KNN算法的过程中，为了搞懂Spark的原理，需要翻阅很多的资料，虽然在完成报告2的过程中已经对Spark有了一定的了解，但是那还都是停留在基本的使用层次，大部分工作是学习官网提供的教程和网络相关介绍，只是对一些基本的概念和MLlib的API的使用有了个大概的认识。但是对于如何使用Spark 进行分布式编程还是了解的太少，这个时候我就找了些论文和书籍来看看，由于时间比较紧，虽然只看了部分内容，但是对于编程实现KNN我感觉还是起到了很大的帮助。这次实验让我感受到了Spark编程的强大以及简洁，往往几行代码就能够实现很复杂的功能。不过在实验过程中也还是遇到了很多的问题：
\begin{itemize}
\item Spark提供了丰富的API，但是因为是第一次接触，所以用起来不太熟悉，比如一个函数产生的dataframe得利用输出查看才晓得具体包含了哪些信息。Rdd的操作函数map， reduce等函数具体有什么效果或者返回的数据类型是什么，需要经常查看API以及结合具体的调试来体会。
\item 对Spark的编程模型理解不深，一开始我曾经试图在worker proggram中访问外部变量，但是这是不允许的，Spark要求函数必须是闭包函数，因此在运行的时候报了错。目前算法在预测大量测试数据的时候，运行时间有点长，这是在后续工作中需要改进的地方。
\end{itemize}

在前段时间召开的2016Spark峰会上，Spark2.0已经被发布了，据称新一代的Spark会更简单、快速和智能。Spark的迅猛发展已经收到业内各大公司的广泛关注，包括IBM、Microsoft在内的许多企业都在积极推广Spark。对于机器学习模块，
基于DataFrame的机器学习API也就是ml包将作为主要的ML API，尽管原本的mllib包仍然保留，但以后的开发重点会集中在基于DataFrame的API上。此外任何编程语言的用户都将可以保留与载入机器学习的管道与模型了。还是如报告2中所总结，通过谭老师的作业，我算是开始接触了Spark这门快速发展的技术，对于我以后的研究工作提供了更多思路，目前我正打算把Spark应用到我们正在开发的一个系统中来处理大量数据的匹配问题，希望能在处理效率方面有所提升。
\end{spacing}
\end{document}