MachineLearning | HoleLin's Blog

参考文献

机器学习实战 - Peter Harrington
极客时间数据分析实战45讲陈旸

数学基础

线性代数

在线性代数中,由单独的数 a 构成的元素被称为标量(scalar):一个标量 a 可以是整数、实数或复数.如果多个标量 a1, a2, ⋯ , an 按一定顺序组成一个序列,这样的元素就被称为向量(vector).显然,向量可以看作标量的扩展.原始的一个数被替代为一组数, 从而带来了维度的增加,给定表示索引的下标才能唯一地确定向量中的元素.
每个向量都由若干标量构成,如果将向量的所有标量都替换成相同规格的向量,得到的就是如下的矩阵(matrix)

$\begin{pmatrix} &a_{11} ,a_{12} ,a_{13} & \\ &a_{21} ,a_{22} ,a_{23} & \\ &a_{31} ,a_{32} ,a_{33} & \end{pmatrix}$
相对于向量,矩阵同样代表了维度的增加,矩阵中的每个元素需要使用两个索引(而非一个)确定.同理,如果将矩阵中的每个标量元素再替换为向量的话,得到的就是张量(tensor).直观地理解,张量就是高阶的矩阵
描述作为数学对象的向量需要有特定的数学语言,范数和内积就是代表.范数(norm)是对单个向量大小的度量,描述的是向量自身的性质,其作用是将向量映射为一个非负的数值.通用的 $L^{p}$ 范数定义如下:

$\left | x \right | _{p} =\left( \sum_{i}^{} \left | x_{i} \right |^{p} \right ) ^{\frac{1}{p} }$
对⼀个给定向量, $L^{1}$ 范数计算的是向量所有元素绝对值的和, $L^{2}$ 范数计算的是通常意义上的向量长度, $L^{\infty }$ 范数计算的则是向量中最大元素的取值.
范数计算的是单个向量的尺度,**内积(inner product)**计算的则是两个向量之间的关系. 两个相同维数向量内积的表达式为

$\left \langle x ,y \right \rangle =\sum_{i}^{} x_{i} \cdot y_{i}$
- 即对应元素乘积的求和.内积能够表示两个向量之间的相对位置,即向量之间的夹角.一种特殊的情况是内积为 0,即 $\left \langle x ,y \right \rangle =0$ .在二维空间上,这意味着两个向量的夹角为 90度,即相互垂直.而在高维空间上,这种关系被称为正交(orthogonality).如果两个向量正交,说明他们线性无关,相互独立,互不影响.
在内积空间中,一组两两正交的向量构成这个空间的正交基(orthogonal basis),假若正交基中基向量的 $L^{2}$ 范数都是单位长度 1,这组正交基就是标准正交基(orthonormal basis).正交基的作用就是给内积空间定义出经纬度.⼀旦描述内积空间的正交基确定了,向量和点之间的对应关系也就随之确定.
- 值得注意的是,描述内积空间的正交基并不唯一.对二维空间来说,平面直角坐标系和极坐标系就对应了两组不同的正交基,也代表了两种实用的描述方式.
线性空间的一个重要特征是能够承载变化.当作为参考系的标准正交基确定后,空间中的点就可以用向量表示.当这个点从一个位置移动到另一个位置时,描述它的向量也会发生改变.点的变化对应着向量的线性变换(linear transformation),而描述对象变化抑或向量变换的数学语言,正是矩阵.
在这种情况下,矩阵的作用就是对正交基进行变换.因此,对于矩阵和向量的相乘,就存在不同的解读方式:

$Ax=y$
- 这个表达式既可以理解为向量 $x$ 经过矩阵 A 所描述的变换,变成了向量 $y$ ;也可以理解为一个对象在坐标系 A 的度量下得到的结果为向量 $x$ ,在标准坐标系 $l$ (单位矩阵:主对角线元素为1,其余元素为 0)的度量下得到的结果为向量 $y$ .
- 这表示矩阵不仅能够描述变化,也可以描述参考系本身.引用网络上一个精当的类比:表达式 $Ax$ 就相当于对向量 x 做了一个环境声明,用于度量它的参考系是 A.如果想用其他的参考系做度量的话,就要重新声明.而对坐标系施加变换的方法,就是让表示原始坐标系的矩阵与表示变换的矩阵相乘.
描述矩阵的⼀对重要参数是特征值(eigenvalue)和特征向量(eigenvector).对于给定的矩阵 A,假设其特征值为 $\lambda$ ,特征向量为 $x$ ,则它们之间的关系如下:

$Ax=\lambda x$
矩阵代表了向量的变换,其效果通常是对原始向量同时施加方向变化和尺度变化.可对于有些特殊的向量,矩阵的作用只有尺度变化而没有方向变化,也就是只有伸缩的效果而没有旋转的效果.对于给定的矩阵来说,这类特殊的向量就是矩阵的特征向量,特征向量的尺度变化系数就是特征值.
矩阵特征值和特征向量的动态意义在于表示了变化的速度和方向。如果把矩阵所代表的变化看作奔跑的人，那么矩阵的特征值就代表了他奔跑的速度，特征向量代表了他奔跑的方向。但矩阵可不是普通人，它是三头六臂的哪吒，他的不同分身以不同速度（特征值）在不同方向（特征向量）上奔跑，所有分身的运动叠加在⼀起才是矩阵的效果。
求解给定矩阵的特征值和特征向量的过程叫做特征值分解，但能够进行特征值分解的矩阵必须是 n 维方阵。将特征值分解算法推广到所有矩阵之上，就是更加通用的奇异值分解。

概率论

数理统计

最优化方法

信息论

形式逻辑

机器学习

根据训练数据是否具有标签信息，可以将机器学习的任务分成以下三类
- 监督学习：基于已知类别的训练数据进行学习；
- 无监督学习：基于未知类别的训练数据进行学习；
- 半监督学习：同时使用已知类别和未知类别的训练数据进行学习

名词解释

标称型数据:一般在有限的数据中取,而且只存在‘是’和‘否’两种不同的结果(一般用于分类)
数值型数据:可以在无限的数据中取,而且数值比较具体化,例如4.02,6.23这种值(一般用于回归分析)
误差: 在机器学习中，误差被定义为学习器的实际预测输出与样本真实输出之间的差异。在分类问题中，常用的误差函数是错误率，即分类错误的样本占全部样本的比例
- 误差可以进一步分为训练误差和测试误差两类。训练误差指的是学习器在训练数据集上的误差，也称经验误差；测试误差指的是学习器在新样本上的误差，也称泛化误差。
- 训练误差描述的是输入属性与输出分类之间的相关性，能够判定给定的问题是不是一个容易学习的问题。测试误差则反映了学习器对未知的测试数据集的预测能力，是机器学习中的重要概念。实用的学习器都是测试误差较低，即在新样本上表现较好的学习器。
- 测试误差与模型复杂度之间呈现的是抛物线的关系
过拟合现象: 把训练数据的特征错当做整体的特征。
- 过拟合出现的原因通常是学习时模型包含的参数过多，从而导致训练误差较低但测试误差较高
- 过拟合是机器学习中不可避免的问题，可通过选择合适的模型降低其影响；
欠拟合现象: 如果说造成过拟合的原因是学习能力太强，造成欠拟合的原因就是学习能力太弱，以致于训练数据的基本性质都没能学到。如果学习器的能力不足，甚至会把黑猩猩的图像误认为人，这就是欠拟合的后果。

预测问题

预测问题可以分为以下三类:
- 分类问题：输出变量为有限个离散变量，当个数为 2 时即为最简单的二分类问题；
- 回归问题：输入变量和输出变量均为连续变量；
- 标注问题：输入变量和输出变量均为变量序列。

监督学习

监督学习假定训练数据满足独立同分布的条件，并根据训练数据学习出一个由输入到输出的映射模型。反映这一映射关系的模型可能有无数种，所有模型共同构成了假设空间。监督学习的任务就是在假设空间中根据特定的误差准则找到最优的模型。
根据学习方法的不同，监督学习可以分为生成方法与判别方法两类。
- 生成方法是根据输入数据和输出数据之间的联合概率分布确定条件概率分布 $P(Y |X)$ ，这种方法表示了输入 X 与输出 Y 之间的生成关系；
- 判别方法则直接学习条件概率分布 $P(Y |X) $或决策函数 $f(X)$ ，这种方法表示了根据输入 X 得出输出 Y 的预测方法。
- 两相对比，生成方法具有更快的收敛速度和更广的应用范围，判别方法则具有更高的准确率和更简单的使用方式

算法

监督学习的用途
`k-`近邻算法	线性回归
朴素贝叶斯算法	局部加权线性回归
支持向量机	`Ridge`回归
决策树	`Lasso`最小回归系数估计

无监督学习的用途
`K-`均值	最大期望算法
`DBSCAN`	`Parzen`窗设计

开发步骤

收集数据. 网络爬虫,API等
准备输入数据
分析输入数据
训练算法

`k-`近邻算法(`kNN`)

k-近邻算法采用测量不同特征之间的距离的方法进行分类.
优点: 精度高,对异常值不敏感,无数据输入假定.
缺点: 计算复杂度高,空间复杂度高
使用数据范围: 数值型和标称型

工作原理

存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系.
输入没有标签的新数据后,将新数据的每个特征与样本集数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签.
一般来说,我们只选择样本数据集中前k个最相似的数据,通常k不大于20的整数.最后选择k个最相似数据中次数最多的分类,作为新数据的分类.

一般流程

收集数据: 可以使用任何方法.
准备数据: 距离计算所需要的数值,最好是结构化的数据格式.
分析数据: 可以使用任何方法
训练算法: 此步骤不适用k-近邻算法
测试算法: 计算错误率
使用算法: 首选需要输入样本数据和结构化的输出结果,然后运行k-近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续处理.

实例

from matplotlib.font_manager import FontProperties
from numpy import *
import numpy as np
import operator
import matplotlib
import matplotlib.pyplot as plt
import matplotlib.lines as mlines


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


"""
对未知类别属性的数据集中的每个点依次执行以下操作:
    1. 计算已知类别数据集中的点与当前点之间的距离
    2. 按照距离递增次序排序
    3. 选取与当前点距离最小的k个点
    4. 确定前k个点所在类别的出现频率
    5. 返回前k个点出现频率最高的类别作为当前点的预测分类
    
函数说明:kNN算法,分类器

    Parameters:
        inX - 用于分类的数据(测试集)
        dataSet - 用于训练的数据(训练集)
        labes - 分类标签
        k - kNN算法参数,选择距离最小的k个点
    Returns:
        sortedClassCount[0][0] - 分类结果
"""


def classify0(inX, dataSet, labels, k):
    # numpy函数shape[0]返回dataSet的行数
    dataSetSize = dataSet.shape[0]
    # 在列向量方向上重复inX共1次(横向),行向量方向上重复inX共dataSetSize次(纵向)
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    # 二维特征相减后平方
    sqDiffMat = diffMat ** 2
    # sum()所有元素相加,sum(0)列相加,sum(1)行相加
    sqDistances = sqDiffMat.sum(axis=1)
    # 开方,计算出距离
    distances = sqDistances ** 0.5
    # 返回distances中元素从小到大排序后的索引值
    sortedDistIndices = distances.argsort()
    # 定一个记录类别次数的字典
    classCount = {}
    for i in range(k):
        # 取出前k个元素的类别
        voteIlabel = labels[sortedDistIndices[i]]
        # dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值.
        # 计算类别次数
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # python3中用items()替换python2中的iteritems()
    # key=operator.itemgetter(1)根据字典的值进行排序
    # key=operator.itemgetter(0)根据字典的键进行排序
    # reverse降序排序字典
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    print(sortedClassCount)
    # 返回次数最多的类别,即所要分类的类别
    return sortedClassCount[0][0]


"""
函数说明:打开并解析文件,对数据进行分类:1代表不喜欢,2代表魅力一般,3代表极具魅力

    Parameters:
        filename - 文件名
    Returns:
        returnMat - 特征矩阵
        classLabelVector - 分类Label向量
"""


def file2matrix(filename):
    # 打开文件,此次应指定编码,

    fr = open(filename, 'r', encoding='utf-8')
    # 读取文件所有内容
    arrayOLines = fr.readlines()
    # 针对有BOM的UTF-8文本,应该去掉BOM,否则后面会引发错误.
    arrayOLines[0] = arrayOLines[0].lstrip('\ufeff')
    # 得到文件行数
    numberOfLines = len(arrayOLines)
    # 返回的NumPy矩阵,解析完成的数据:numberOfLines行,3列
    returnMat = np.zeros((numberOfLines, 3))
    # 返回的分类标签向量
    classLabelVector = []
    # 行的索引值
    index = 0

    for line in arrayOLines:
        # s.strip(rm),当rm空时,默认删除空白符(包括'\n','\r','\t',' ')
        line = line.strip()
        # 使用s.split(str="",num=string,cout(str))将字符串根据'\t'分隔符进行切片.
        listFromLine = line.split('\t')
        # 将数据前三列提取出来,存放到returnMat的NumPy矩阵中,也就是特征矩阵
        returnMat[index, :] = listFromLine[0:3]
        # 根据文本中标记的喜欢的程度进行分类,1代表不喜欢,2代表魅力一般,3代表极具魅力
        # 对于datingTestSet2.txt  最后的标签是已经经过处理的 标签已经改为了1, 2, 3
        if listFromLine[-1] == 'didntLike':
            classLabelVector.append(1)
        elif listFromLine[-1] == 'smallDoses':
            classLabelVector.append(2)
        elif listFromLine[-1] == 'largeDoses':
            classLabelVector.append(3)
        index += 1
    return returnMat, classLabelVector


def show_datas(datingDataMat, datingLabels):
    # 设置汉字格式
    font = FontProperties(fname="./data/AlibabaPuHuiTi-3-75-SemiBold.ttf", size=14)  ##需要查看自己的电脑是否会包含该字体
    # 将fig画布分隔成1行1列,不共享x轴和y轴,fig画布的大小为(13,8)
    # 当nrow=2,nclos=2时,代表fig画布被分为四个区域,axs[0][0]表示第一行第一个区域
    fig, axs = plt.subplots(nrows=2, ncols=2, sharex=False, sharey=False, figsize=(13, 8))

    numberOfLabels = len(datingLabels)
    LabelsColors = []
    for i in datingLabels:
        if i == 1:
            LabelsColors.append('black')
        if i == 2:
            LabelsColors.append('orange')
        if i == 3:
            LabelsColors.append('red')
    # 画出散点图,以datingDataMat矩阵的第一(飞行常客例程)、第二列(玩游戏)数据画散点数据,散点大小为15,透明度为0.5
    axs[0][0].scatter(x=datingDataMat[:, 0], y=datingDataMat[:, 1], color=LabelsColors, s=15, alpha=.5)
    # 设置标题,x轴label,y轴label
    axs0_title_text = axs[0][0].set_title(u'每年获得的飞行常客里程数与玩视频游戏所消耗时间占比', fontproperties=font)
    axs0_xlabel_text = axs[0][0].set_xlabel(u'每年获得的飞行常客里程数', fontproperties=font)
    axs0_ylabel_text = axs[0][0].set_ylabel(u'玩视频游戏所消耗时间占比', fontproperties=font)
    plt.setp(axs0_title_text, size=9, weight='bold', color='red')
    plt.setp(axs0_xlabel_text, size=7, weight='bold', color='black')
    plt.setp(axs0_ylabel_text, size=7, weight='bold', color='black')

    # 画出散点图,以datingDataMat矩阵的第一(飞行常客例程)、第三列(冰激凌)数据画散点数据,散点大小为15,透明度为0.5
    axs[0][1].scatter(x=datingDataMat[:, 0], y=datingDataMat[:, 2], color=LabelsColors, s=15, alpha=.5)
    # 设置标题,x轴label,y轴label
    axs1_title_text = axs[0][1].set_title(u'每年获得的飞行常客里程数与每周消费的冰激淋公升数', fontproperties=font)
    axs1_xlabel_text = axs[0][1].set_xlabel(u'每年获得的飞行常客里程数', fontproperties=font)
    axs1_ylabel_text = axs[0][1].set_ylabel(u'每周消费的冰激淋公升数', fontproperties=font)
    plt.setp(axs1_title_text, size=9, weight='bold', color='red')
    plt.setp(axs1_xlabel_text, size=7, weight='bold', color='black')
    plt.setp(axs1_ylabel_text, size=7, weight='bold', color='black')

    # 画出散点图,以datingDataMat矩阵的第二(玩游戏)、第三列(冰激凌)数据画散点数据,散点大小为15,透明度为0.5
    axs[1][0].scatter(x=datingDataMat[:, 1], y=datingDataMat[:, 2], color=LabelsColors, s=15, alpha=.5)
    # 设置标题,x轴label,y轴label
    axs2_title_text = axs[1][0].set_title(u'玩视频游戏所消耗时间占比与每周消费的冰激淋公升数', fontproperties=font)
    axs2_xlabel_text = axs[1][0].set_xlabel(u'玩视频游戏所消耗时间占比', fontproperties=font)
    axs2_ylabel_text = axs[1][0].set_ylabel(u'每周消费的冰激淋公升数', fontproperties=font)
    plt.setp(axs2_title_text, size=9, weight='bold', color='red')
    plt.setp(axs2_xlabel_text, size=7, weight='bold', color='black')
    plt.setp(axs2_ylabel_text, size=7, weight='bold', color='black')
    # 设置图例
    didntLike = mlines.Line2D([], [], color='black', marker='.',
                              markersize=6, label='didntLike')
    smallDoses = mlines.Line2D([], [], color='orange', marker='.',
                               markersize=6, label='smallDoses')
    largeDoses = mlines.Line2D([], [], color='red', marker='.',
                               markersize=6, label='largeDoses')
    # 添加图例
    axs[0][0].legend(handles=[didntLike, smallDoses, largeDoses])
    axs[0][1].legend(handles=[didntLike, smallDoses, largeDoses])
    axs[1][0].legend(handles=[didntLike, smallDoses, largeDoses])
    # 显示图片
    plt.show()


"""
函数说明:对数据进行归一化

    Parameters:
        dataSet - 特征矩阵
    Returns:
        normDataSet - 归一化后的特征矩阵
        ranges - 数据范围
        minVals - 数据最小值
"""


def autoNorm(dataSet):
    # 获得数据的最小值
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    # 最大值和最小值的范围
    ranges = maxVals - minVals
    # shape(dataSet)返回dataSet的矩阵行列数
    normDataSet = np.zeros(np.shape(dataSet))
    # 返回dataSet的行数
    m = dataSet.shape[0]
    # 原始值减去最小值
    normDataSet = dataSet - np.tile(minVals, (m, 1))
    # 除以最大和最小值的差,得到归一化数据
    normDataSet = normDataSet / np.tile(ranges, (m, 1))
    # 返回归一化数据结果,数据范围,最小值
    return normDataSet, ranges, minVals


def datingClassTest():
    # 打开的文件名
    filename = './data/knn/datingTestSet.txt'
    # 将返回的特征矩阵和分类向量分别存储到datingDataMat和datingLabels中
    datingDataMat, datingLabels = file2matrix(filename)
    # 取所有数据的百分之十
    hoRatio = 0.10
    # 数据归一化,返回归一化后的矩阵,数据范围,数据最小值
    normMat, ranges, minVals = autoNorm(datingDataMat)
    # 获得normMat的行数
    m = normMat.shape[0]
    # 百分之十的测试数据的个数
    numTestVecs = int(m * hoRatio)
    # 分类错误计数
    errorCount = 0.0
    for i in range(numTestVecs):
        # 前numTestVecs个数据作为测试集,后m-numTestVecs个数据作为训练集
        classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :],
                                     datingLabels[numTestVecs:m], 4)
        print("分类结果:%s\t真实类别:%d" % (classifierResult, datingLabels[i]))
        if classifierResult != datingLabels[i]:
            errorCount += 1.0
    print("错误率:%f%%" % (errorCount / float(numTestVecs) * 100))


if __name__ == '__main__':
    # group, labels = createDataSet()
    # print(classify0([0, 10], group, labels, 3))
    # datingDataMat, datingLabels = file2matrix('./data/knn/datingTestSet.txt')
    # show_datas(datingDataMat, datingLabels)
    datingClassTest()

朴素贝叶斯算法

用于解决分类问题，即将连续取值的输入映射为离散取值的输出
解决分类问题的依据是数据的属性。朴素贝叶斯分类器假定样本的不同属性满足条件独立性假设，并在此基础上应用贝叶斯定理执行分类任务。其基本思想在于分析待分类样本出现在每个输出类别中的后验概率，并以取得最大后验概率的类别作为分类的输出。
假设训练数据的属性由n维随机向量x表示，其分类结果用随机变量y表示，那么x和y的统计规律就可以用联合概率分布 $P(X,Y)$ 描述，每一个具体的样本 $(x_{i},y_{i})$ 都可以通过 $P(X,Y)$ 独立同分布地产生。
朴素贝叶斯分类器的出发点就是这个联合概率分布，根据条件概率的性质可以得到

$P(X,Y) = P(Y)\cdot P(X|Y) \\ = P(X)\cdot P(Y|X)$
在上式中， $P(Y)$ 代表着每个类别出现的概率，也就是类先验概率； $P(X|Y)$ 代表着在给定的类别下不同属性出现的概率，也就是类似然概率

决策树

工作原理

构造

构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点：
- 根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点；
- 内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”；
- 叶节点：就是树最底部的节点，也就是决策结果。
在构造过程中，要解决三个重要的问题
- 选择哪个属性作为根节点；
- 选择哪些属性作为子节点；
- 什么时候停止并得到目标状态，即叶节点。

剪枝

剪枝就是给决策树瘦身，这一步想实现的目标就是，不需要太多的判断，同样可以得到不错的结果。之所以这么做，是为了防止“过拟合”（Overfitting）现象的发生。

剪枝的方法

“预剪枝”（Pre-Pruning）
- 预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。
“后剪枝”（Post-Pruning）
- 后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。方法是：用这个节点子树的叶子节点来替代该节点，类标记为这个节点子树中最频繁的那个类

参考文献

数学基础

线性代数

概率论

数理统计

最优化方法

信息论

形式逻辑

机器学习

名词解释

预测问题

监督学习

算法

开发步骤

k-近邻算法(kNN)

工作原理

一般流程

实例

朴素贝叶斯算法

决策树

工作原理

构造

剪枝

剪枝的方法

`k-`近邻算法(`kNN`)