机器学习简介1--概念和KNN

从16年开始接触学习机器学习方向的各种知识，一直在学习，但却一直缺少总结。从本篇起，尝试总结下这几年自己学习过的一些经典算法。我会把文章分为两部分，尽可能让没有算法基础(非技术同学)和已有数学编程基础的同学都能有一些收获。

机器学习这个概念从14年再次火了起来。我们在总结机器学习，神经网络等知识前，有必要了解下机器学习的概念，以及机器学习目前到底可以做什么。机器学习(Machine Learning, ML)是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。
上面是百度百科的官方解释。我们再low一点具体一点：机器学习的核心是“使用算法解析数据，从中学习，然后对世界上的某件事情做出决定或预测”。简单说就是，让算法总结数据，总结规律，然后用这个总结的数据规律来预测与数据相关的问题。我们知道，在计算机的世界中，有了二进制和逻辑运算(与或非)，就可以表达所有的自然事务和规律。同样的在机器学习的世界里，是不是只要我们有了预测数据分类和逻辑的算法，就足以表述所有的逻辑？答案是肯定的或者说是类似的。

image.png

机器学习三种主要类型：监督学习、非监督学习和强化学习。

监督学习的两种主要类型是分类和回归。分类的作用就是，机器模型可以将数据划分成特定的两类。这里举个不太合适的简单例子，我们根据女性体重和身高，训练一个简单的分类模型。通过我们人为告诉机器美女数据样本的美丑，让模型总结，最终我们训练了一个鉴别美女和丑女的模型。当我们有一个新的女性的身高和体重的数据时，就可以让机器自动分类，判断这个女性是丑女或者美女了。这就是一个典型的分类问题。

回归是使用先前标记的数据，通过模型拟合数据，来预测将来的结果。这里也举个简单的例子。比如通过大量的历史房价涨跌数据，股票市场的涨跌数据，来拟合规律曲线，进而预测接下来的结果。这就是典型的回归问题。

在无监督学习中，数据都是没有标签的。无监督学习分为聚类和降维。聚类是算法根据数据的属性和特征，自发的把同类数据聚集在一起。我们还以上面鉴别妹子美丑为例。假如我们此时，只有大量的妹子们的身高和体重的数据，并没有见过她们，也没法判断那个身高和体重样本的妹子是美女。这种情况就是聚类算法擅长的。我们通过合适的聚类算法，可以把自发的把有相同特征的妹子，自动聚集在一起。仍然可以区分开，哪些是美女，哪些是丑女。

降维通过找到共同点来减少数据集的变量。大数据可视化使用降维来识别趋势和规则。降维的理解就更容易了。降维也常常用在计算机视觉的图片压缩上。核心就是保留图片的主要信息。

最后，强化学习使用机器的个人历史和经验来做出决定。与进化算法的思想基本一直。强化学习的经典应用是玩游戏。与监督和非监督学习不同，强化学习不涉及提供“正确的”答案或输出。他更像是进化算法的一种思路。

这里贴上这种非常经典的机器学习算法分类图。

image

传统机器学习的主要内容就包括这些。接下来我们一起从最常用的，分类算法看起。

常用的分类算法主要包括，KNN，Decision Tree,Naive Bayes,Logictic Regression,svm,Adaboost,GBDT等。本篇就介绍最经典的KNN算法。以KNN为例介绍机器学习从数据收集到模型训练，模型预测的过程。

首先我们一句话说明下KNN的思路：如果一个样本在特征空间中，k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。这个算法可以分为两个步骤：1. 找到与待预测样本最相近的k个样本 2. 查看这k个样本里，数量最多的那个类别。则待预测样本，属于数量最多的那个类别。这里举个简单直观的例子。

我们基于上面判断妹子美丑的例子来扩展。假设我们目前有一些这样的妹子数据{身高，体重，胸围，颜值等级}。(胸围A-D，我们用1-4表示。颜值的等级低，中，高，我们用1，2，3来表示),我们的目标是根据已有的数据，通过新来妹子的身高，体重和胸围，来预测此妹子的颜值等级。

我们假设已有的4个妹子数据如下。

妹子0 :{150,60,4,1}，妹子1 :{160,60,3,2}，妹子2 :{161,60,2,2}，妹子2 :{170,60,4,3}。

现在有一个新妹子的数据，妹子5:{160,60,2}。我们需要根据此妹子160的身高，60kg的体重和B的胸围来预测妹子5的颜值。我们只需要计算出，妹子5距离最近的K个妹子，在看看样本数据中最多颜值等级是哪个，即得到妹子5的颜值等级。我们设定k==2，通过计算妹子5与每个妹子的距离，来选出距离最近的前两个妹子。

这里距离的计算我们采用最常见的L2距离，即欧氏距离。当然衡量距离的计算方法有多种，这里以L2欧氏距离为准。

image

第一步，可以计算出，距离最近的两个妹子是妹子1和妹子2。第二步，统计距离最近的两个妹子分别属于哪一类。类别个数最多的，即为妹子5的所属类型。很明显，这个妹子5也属于颜值中等的类型。

上面就是KNN的一个非常简洁的例子。在实际的工程应用中，我们的样本数据往往会非常多。理论上样本数据越多，K值较大，我们预测的结果也越准确。但是，数据样本过多，K值选取过大，往往会造成，计算量乘数倍的增加，使算法的运算速度大大下降。例如在电商中广泛应用的协同过滤算法，其一部分即为Knn的思想。也存在数据量大时，算法性能下降，怎么优化算法，这里暂不讨论。

非开发的同学如果已经理解了上面的入门例子，不想再深究下面的代码，可以不用再继续看下去。这里我会给出一个入门级的knn算法python实现。如需要其他语言版本可在下方留言。

首先我们采用sklearn包自带的例子数据和knn实现方法：

from sklearnimport neighbors

from sklearnimport datasets

knn = neighbors.KNeighborsClassifier()

iris = datasets.load_iris()

knn.fit(iris.data,iris.target)

predictedLabel = knn.predict([[0.1,0.2,0.3,0.4]])

print(iris.target_names[predictedLabel])

通过调用datasets.load_iris()，我们可以获取一个150个样本的数据集，记录萼片长度，萼片宽度，花瓣长度，花瓣宽度(sepal length, sepal width, petal length and petal width），对应Iris setosa, Iris versicolor, Iris virginica类别。调用knn.predict([[0.1,0.2,0.3,0.4]])，内部会将该测试数据与所有数据求欧氏距离，然后取K个最近点，投票，算得最后的类别。

这里是采用了sklearn自带的样本数据和KNN实现。如果有兴趣可以点进KNeighborsClassifier去阅读下框架的实现代码。下面给出机器学习实战中的一个简单实现代码。（我做了一点调整，把代码改成了python3版本）

这里不太方便上传附件测试数据，我把数据格式做个说明。其中数据一共有4个熟悉，样本为男士。前三个属性代表样本的每年飞行里程数，玩游戏所占时间比，每周吃的冰激凌数。第四列代表男性的魅力值，没有魅力，一般，极有魅力。

数据样例如下：

40920 8.326976 0.953952 3

14488 7.153469 1.673904 2

26052 1.441871 0.805124 1

代码如下：

from numpyimport *

import operator

from osimport listdir

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 iin range(k):

voteIlabel = labels[sortedDistIndicies[i]]

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

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

return sortedClassCount[0][0]

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 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 linein fr.readlines():

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))# element wise divide

    return normDataSet, ranges, minVals

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 iin 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.0

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

print(errorCount)

def img2vector(filename):

returnVect = zeros((1,1024))

fr =open(filename)

for iin range(32):

lineStr = fr.readline()

for jin range(32):

returnVect[0,32 * i + j] =int(lineStr[j])

return returnVect

def handwritingClassTest():

hwLabels = []

trainingFileList = listdir('trainingDigits')# load the training set

    m = len(trainingFileList)

trainingMat = zeros((m,1024))

for iin range(m):

fileNameStr = trainingFileList[i]

fileStr = fileNameStr.split('.')[0]# take off .txt

        classNumStr =int(fileStr.split('_')[0])

hwLabels.append(classNumStr)

trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)

testFileList = listdir('testDigits')# iterate through the test set

    errorCount =0.0

    mTest = len(testFileList)

for iin range(mTest):

fileNameStr = testFileList[i]

fileStr = fileNameStr.split('.')[0]# take off .txt

        classNumStr =int(fileStr.split('_')[0])

vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)

classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels,3)

print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))

if (classifierResult != classNumStr): errorCount +=1.0

    print("\nthe total number of errors is: %d" % errorCount)

print("\nthe total error rate is: %f" % (errorCount /float(mTest)))

datingClassTest()

如果对代码部分有不理解的同学，欢迎在下面评论。我会一一解答。

相信通过这个例子，大家已经对基本的Knn算法有所认识。Knn实际也有许多其他的变种和回归应用。更多更深入的应用，大家可以去参考sk框架的实现源码。

下一章，我会总结下经典的墒增原理和决策树的算法原理以及剪枝操作。照例把文章分为两部分，前半段非程序同学以及后半段的代码实例讲解部分。