机器学习-监督学习基础知识总结

一、机器学习基础概念

1.机器学习分为：监督学习、无监督学习、半监督学习等几类:
(1)监督学习：从给定的训练数据集中学习出一个函数，当新的数据到来时，可以根据这个函数预测结果。监督学习的训练集要求是包括输入和输出，也可以说是特征和目标。训练集中的目标是由人标注的。常见的监督学习算法包括回归分析和统计分类。
(2)无监督学习：与监督学习相比，训练集没有人为标注的结果。常见的无监督学习算法有聚类。
(3)半监督学习：是监督学习和无监督学习相结合的一种学习方法。它主要考虑如何利用少量的样本标注和大量的未标注样本进行训练和分类的问题。半监督学习对于减少标注代价，提高学习机器性能具有非常大的实际意义。

2.监督学习主要研究的两块内容是分类和回归，即分类和回归归属于监督学习的范畴:
(1) 分类：在监督学习中，如果预测的变量是离散的（例如 -1，+1 这种）我们就称为分类。常见的分类算法有：决策树，K近邻算法（KNN），朴素贝叶斯，支持向量机（SVM），神经网络,Logistic回归等。
(2) 回归：在监督学习中，如果预测的变量是连续的，就称其为回归。在回归分析中如果只包含一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归称为一元线性回归。如果回归分析中包括两个或两个以上的自变量，且因变量和自变量之间是线性关系，则称为多元线性回归。回归和分类的主要区别是预测的值域不一样，分类常用算法大多也适用于回归。

3.开发机器学习应用程序的步骤：
(1) 收集数据。
(2) 准备输入数据：不同的算法对数据的格式要求可能不同，所以有时需要对收集的数据进行格式转换。
(3) 分析输入数据：这一步只要通过观察来确保数据集中没有垃圾数据。
(4) 训练算法：机器学习算法从这一步才真正的开始学习，主要的通过特定的训练集输入到分类算法，确定算法模型的过程。 (5) 测试算法：用于检测训练算法阶段训练出来的模型是否靠谱，通常使用已知目标值的样本作为输入，观察其准确率。
(6) 使用算法：将机器学习算法转换为应用程序，执行实际任务。

1. 常用于实现机器学习算法的 python语言:
   python的语法清晰，易于操作纯文本文件，开发文档丰富，且有许多线程的数据函数库（例如：NumPy）。鉴于这些特点，python是常用的机器学习程序的开发语言之一。
   

二、监督学习常用算法

1. K-近邻算法（KNN）：
   简述：简单的说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。工作原理是：存在一个训练样本集，且样本集中的每个数据都存在类别标签。将待预测类别的一条数据输入，计算这条数据与训练样本集中数据的距离（距离的计算方式一般是将数据特征值数值化，用概率统计等数学工具计算），然后选取训练样本集中与待测数据距离最近的K条数据（通常K是小于20的整数）。这K条训练样本中类别出现最频繁的类别标签即作为带预测数据的类别标签。
   一个python版本的KNN算法实现：
   

   #!/usr/bin/evn python
   import numpy as np
   import operator
   def classify0(intX,dataSet,labels,k):
       ‘‘‘获取行数，第二个为列数 shape返回tuple‘‘‘
       dataSetSize = dataSet.shape[0]
       ‘‘‘生成dateSetSize行，1列的矩阵，值都是intX，并且求出每一项与dataSet差‘‘‘
       diffMat = np.tile(intX,(dataSetSize,1)) - dataSet
       ‘‘‘针对每项差值取平方‘‘‘
       sqDiffMat = diffMat ** 2
       ‘‘‘将每一行向量相加‘‘‘
       sqDistances = sqDiffMat.sum(axis=1)
       ‘‘‘对结果开根号‘‘‘
       distances = sqDistances ** 0.5
       ‘‘‘排序 选取距离最小的K个点‘‘‘
       sortedDistIndicies = distances.argsort()
       classCount = {}
       for i in range(k):
           voteLabel = labels[sortedDistIndicies[i]]
           classCount[voteLabel] = classCount.get(voteLabel,0) + 1
       sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse=True)
       return sortedClassCount[0][0]
   

   ps:参数说明：待分类的输入向量inX,训练样本集dataSet，类别标签向量 labels，带选取的k值。采用的是欧式距离公式。
   

1.1 归一化数值：
简述：在进行K邻近算法计算时，需要计算待分类数据的每个特征值和训练样本每个特征值的距离，但是每个特征值的量级或单位可能是不同的（例如特征向量[0.1,12000,1.1,500]），所以需要将各个维度的特征值进行归一化（说白了就是统一单位和量级，在同一把标尺下衡量各个特征的距离）。
常用来归一化数值的公式为：newValue = （oldValue-min）/(max-min)

1.2 总结：k-近邻算法（KNN）是分类数据最简单最有效的算法。k-近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数据。k-近邻算法必须保存全部的数据集，如果训练数据集很大，必须使用大量的存储空间。同时可能非常耗时。k-近邻算法的另一个缺陷是无法给出任何数据的基础结构信息，因此我们无法知晓平均样本和典型事例样本的具体特征。但是概率测量的分类方法则可以解决这个问题。

2.决策树：
简述：决策树是由一个决策图和可能的结果组成，用来创建到达目标的规划。决策树建立并用来辅助决策，是一种特殊的树结构。决策树是一个预测模型，他代表的对象属性和对象值之间的一种映射关系。树中每个结点表示某个对象，而每个分叉路径则代表某个可能的属性值。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，也可以用来预测。

2.1决策树的构建：
在构造决策树时，需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征，划分出最好的结果，必须评估每个特征。完成测试评估之后，原始数据被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如何划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据都在一个数据子集。
2.2 香农熵：
熵定义为信息的期望值，是集合信息的一种度量方式。熵这个名字来源于信息论之父 克劳德.香农。
计算香农熵的公式： H = -F（i=1,n）P(Xi)logxP(Xi), -F(i=i,n)代表求和函数。
ps:另一个度量集合无序程度的方法是基尼不纯度（Gini impurity），简单的说就是从一个数据集中随机选取子项，度量其被错误的划分到其他组里的概率。

2.3 构建树的python代码：

def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]
    ‘‘‘类别完全相同则停止划分‘‘‘
    if classList.count(classList[0] == len(classList):
        return classList[0]
    ‘‘‘遍历所有特征时返回出现次数最多的
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}]
    del(labels[bestFeat])
    ‘‘‘得到列表包含所有属性值‘‘‘
    featValues = [example[beatFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = label[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree

3.朴素贝叶斯（基于概率论的分类方法）：
朴素贝叶斯是贝叶斯决策理论的一部分，贝叶斯理论的核心思想是为数据选择高概率的类别。（而朴素贝叶斯之所以"朴素",是因为这个形式化过程只做最原始，最简单的假设）
3.1 贝叶斯公式：p(c|x) = p(x|c)p(c)/p(x)
简述：当x发生时c发生的概率等于当c发生时x的概率乘以c发生的概率除以x发生的概率。（以条件概率为基础推导所得）
3.2 朴素贝叶斯的条件假设（就说说究竟朴素在哪）:
由统计学得知，如果每个特征需要N个样本，那么对于10个特征将需要N的10次方个样本，样本数是随着特征数成指数增长的。但是如果特征之间相互独立，则样本数就可以从N的10次方，减少为 N*10个。所以朴素贝叶斯基于贝叶斯理论做出的两个假设是：
(1) 数据的特征之间相互独立，即特征A发生与否不会影响特征B的发生的概率。
(2) 各个特征之间同等重要（决策树的理论则是一定要找出一个关键特征）。
3.3 先验概率和后验概率：
(1) 先验概率：是通过现有掌握的部分资料计算出来的概率，通常由经验丰富的专家纯主观的估计所得。（贝叶斯公式中的 p（x|c）即为先验概率，通过训练样本计算所得） (2) 后验概率：可以通过Bayes定理，用先验概率和似然函数计算出来。（贝叶斯公式中的 p（c|x）即为后延概率，也是我们需要计算的概率）。
ps:贝叶斯公式计算的过程即为，通过训练样本数据计算 先验概率 P(x|c)和P(c)，然后计算测试样本的特征概率 p（x），由此可以推导出测试样本的后验概率 p（c|x）.其实说白了朴素贝叶斯就是根据已知样本的概率去推断总体的概率，整个模型的准确性的关键就是样本先验概率的计算的准确性。
3.3 实现贝叶斯计算的DEMO：

‘‘‘计算类别的在总体数据中的概率 即 P(c)
def P(data,cls_val,cls_name="class"):
cnt = 0.0
for e in data:
    if e[cls_name] == cls_val:
        cnt += 1
return cnt/len(data)

‘‘‘计算某个类别下某个属性的概率 即先验概率 P(x|c)
def PT(data,cls_val,attr_name,attr_val,cls_name="class"):
cnt1 = 0.0
cnt2 = 0.0
for e in data:
    if e[cls_name] == cls_val:
        cnt1 += 1
        if e[attr_name] == attr_val:
            cnt2 += 1

return cnt2/cnt1

‘‘‘根据测试数据统计特征概率P（x），并计算后验概率 p（c|x）
def NB(data,test,cls_y,cls_n):
PY = P(data,cls_y)
PN = P(data,cls_n)
for key,val in test.items():
    print (key,val)
    PY *= PT(data,cls_y,key,val)
    PN *= PT(data,cls_n,key,val)
return {cls_y:PY,cls_n:PN}

4.支持向量机(SVM):
简述：支持向量机（SVM）是一种监督学习的方法，通俗来讲它是一种二分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即学习支持向量机的策略便是间隔最大话，最终可转化为一个凸二次规划问题的求解。
4.1基础概念：
(1)分隔超平面：分隔超平面即为分类的决策边界，分布在超平面一侧的数据都属于某个类别，而分布在另一侧的数据则属于另外一个类别。
(2)支持向量（support vector）：就是离分隔超平面最近的那些点。
(3)SVM有很多实现，其中最流行的一种实现是SMO（最小优化算法）。
(4)核方法或者说核技巧会将数据（有时是非线性数据）从一个低维的空间映射到一个高维的空间，可以将一个在低维空间中的非线性问题转换成高维的线性问题来求解。

4.2 SVM通俗解释：
SVM对数据进行分类的时候就是寻找一个最优化超平面的过程。这个最优化超平面使得离它比较近的点能有更大的间隔。也就是不考虑所有点都必须远离超平面，而是只关心求得超平面能够让所有点中离它最近的点（支持向量）有更大间距。形象的说，如果要在纸上寻找一条折线，按照某条折线折叠后，里折线最近的点的间距比其它折线都要大。
4.3 SVM的推到实现还是很复杂的，可以参考一篇blog
http://blog.sina.com.cn/s/blog_4298002e010144k8.html

5.人工神经网络(ANN):
简述：简称神经网络（NN），是一种模仿生物神经网络的结构和功能的数学模型。现代神经网络是一种非线性统计数据建模工具，常用来对输入和输出间的关系进行建模，或用来探索数据的模式。其一个比较贴切的定义是：人工神经网络是由人工建立的以有向图为拓扑结构的动态系统，它通过对连续或断续的输入作状态响应而进行信息处理。
5.1 人工神经网络的特点：
(1) 可以充分逼近任意复杂的非线性关系。
(2) 所有定量或定性的信息都等势分布储存于网络内各神经元，故有很强的鲁棒性和容错性。
(3) 采用并行分布处理方法，使得快速进行大量运算称为可能。
(4) 可学习和自适应不知道或不确定的系统。
(5) 能够同时处理定量、定性标识。

5.2 有监督的神经网络模型训练:
将一组训练集输入人工神经网络，根据网络的实际输出和期望输出间的差别来调整链接权。监督学习算法的主要步骤包括：
(1) 从样本结合中取一个样本（Ai,Bi） ps：Ai为输入，Bi为期望输出。
(2) 计算人工神经网络的实际输出O。
(3) 求D = Bi-O。
(4) 根据D调整矩阵W。
(5) 对每个样本重复上述过程，直到整个样本集来说，误差不超过规定范围。
ps:1.BP算法是一种出色的监督学习算法。2.在训练过程中通常要对数据做归一化处理。
bp神经网络的推导：http://www.cnblogs.com/jzhlin/archive/2012/07/28/bp.html