@spiritnotes 2016-04-08T10:33:51.000000Z 字数 19153 阅读 5662

《机器学习实战》

机器学习 读书笔记

机器学习实战封面

第1章机器学习基础

1.1 何为机器学习

机器学习就是将无序的数据转换成有用的信息

特征或者属性通常是训练样本集的列，他们是独立测量得到的结果，多个特征联系在一起共同组成一个训练样本
知识表示，计算机算法通过学习获得的知识，某些算法可以产生很容易理解的知识表示，而某些算法的知识表示也许只能为计算机所理解

1.3 主要任务

分类
回归，预测数值型数据
聚类
密度估计

1.5 通用步骤

收集数据
准备输入数据
分析输入数据
训练算法
测试算法
使用算法

1.6 Python语言的优势

可执行伪代码
使用广泛，库多
缺点：性能问题

第2章 K-近邻算法

2.1 特点

优点：精度高、对异常值不敏感、无数据输入假定
缺点 : 计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型

抽象取样样本集中特征最相似（最近邻）的数据的分类标签

2.2 算法

计算已知类别数据集中的点与当前点的距离
按照距离递增次序排序
选取与当前点距离最小的k个点
确定前k个点所在类别的出现概率，返回前k个点出现频率最高的类别作为当前点的预测分类

归一化

归一化数据：将数据取值范围处理为0~1、-1～1之间。
$new = (value - min)/(max-min)$

实例

电影分类，根据电影中特殊镜头的个数
约会网站的对象魅力分类
手写数字的识别

第3章决策树

3.1 特点

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相干特征数据
缺点：可能产生过度匹配问题
适用数据类型：数值型和标称型

3.2 熵

信息的定义：待分类的事务可能处于多个类中，则符号 $x_i$ 的信息定义如下：

$l(x_i) = -log_2p(x_i)$
计算熵，需要计算所有类别所有可能值包含的信息期望值：

$H = - \sum^n_i p(x_i)log_2p(x_i)$ 其中n指的是可能的类别，而p指的是为某一类的可能性

3.3 递归构建决策树

得到原始数据集，然后基于最好的属性划分数据集；可能存在多个分支的数据集划分；
划分后，将子数据集递归调用决策树构建方法；直到所有属性都已经使用完毕或者每个分支下的所有实例都具有相同的分类；

3.4 实例

用决策树预测隐形眼镜类型；

第4章基于概率论的分类方法：朴素贝叶斯

4.1 特点

优点：在数据较少的情况下仍然有效，可以处理多类别问题；
缺点：对于输入数据的准备方式较为敏感；
适用数据类型：标称型数据

4.2 条件概率

$p(c|x) = {p(x|c)*p(c)\over p(x)}$

4.3 2个假设

假设特征之间相互独立，也即是说一个特征或者说单词的出现的可能性与其他单词没有关系；
假设每个特征同等重要；

使用档词袋模型

4.4 实例

过滤网站中的恶意留言
使用朴素贝叶斯过滤垃圾邮件
使用朴素贝叶斯分类器从个人广告中获取区域倾向

第5章 Logistic回归

利用逻辑回归进行分类的主要思想：根据现有数据对分类边界线建立回归公式，以此进行分类。

一般过程

收集数据：任意
准备数据：由于需要进行距离计算，因此要求数据类型为数值型，结构化最佳
分析数据：任意
训练算法：大部分时间用于训练数据，目的是为了找到最佳的分类回归系数
测试算法：一旦训练步骤完成，分类将会很快
使用算法：直接判定类别

5.1 基于Logistic回归和Sigmoid函数的分类

优点：计算代价不高，易于理解和实现
缺点：容易欠拟合，分析精度可能不高
适用数据类型：数值型和标称型数据

Sigmoid函数

$\sigma(z)={1\over1+e^{-z}}$

5.2 基于最优化方法的最佳回归系数确定

Sigmoid输入值记为z

$z=w_0x_0+w_1x_1+...+w_nx_n$

$z=W^TX$

$X$ 是分类器的输入数据，

$W$ 是最佳参数（系数）

梯度上升法

要找到函数的最大值，最好的办法是沿着该函数的梯度方向探寻

$\nabla f(x,y) = \begin{pmatrix} \partial f(x,y)\over \partial x\\ \partial f(x,y)\over \partial y \\ \end{pmatrix}$
迭代公式，一直迭代，直到迭代次数到达或者算法达到某个允许的误差范围：

$w:=w+\alpha \nabla_wf(w)$

梯度上升用以求最大值，梯度下降用以求最小值

$w:=w-\alpha \nabla_wf(w)$

推导过程：
1. $h(x) = {1\over 1 + e^{-W^TX}}$
2. $J(w) = {1\over m}\sum_1^m{1\over 2}(h(x)-y)^2$
3. $Cost(h(x), y) = -log(h(x))$ if y=1
$Cost(h(x), y) = -log(1 - h(x))$ if y=0
$Cost(h(x), y) = -y log(h(x)) - (1-y)log(1 - h(x))$
4. $min({1\over m}\sum_1^mCost(h(x),y))$
5. $w:=w+\alpha*(y-h(x))*x$

def sigmoid(inX):
    return 1.0/(1+exp(-inX))
def gradAscent(dataMatIn, classLabels):
    m,n = shape(dataMatrix)
    alpha = 0.001
    maxCycles = 500
    weights = ones((n,1))
    for k in range(maxCycles):              #heavy on matrix operations
        h = sigmoid(dataMatrix*weights)     #matrix mult
        error = (labelMat - h)              #vector subtraction
        weights = weights + alpha * dataMatrix.transpose()* error #matrix mult
    return weights

随机梯度上升

随机梯度上升是一个在线学习算法，只使用一个样本来更改回归系数
- alpha每次迭代的时候都会调整，会缓解数据波动或者高频波动；j< - 随机选择样本来更新回归系数

def stocGradAscent1(dataMatrix, classLabels, numIter=150):
    m,n = shape(dataMatrix)
    weights = ones(n)   #initialize to all ones
    for j in range(numIter):
        dataIndex = range(m)
        for i in range(m):
            alpha = 4/(1.0+j+i)+0.0001    #apha decreases with iteration, does not 
            randIndex = int(random.uniform(0,len(dataIndex)))#go to 0 because of the constant
            h = sigmoid(sum(dataMatrix[randIndex]*weights))
            error = classLabels[randIndex] - h
            weights = weights + alpha * error * dataMatrix[randIndex]
            del(dataIndex[randIndex])
    return weights

5.3 示例：从疝气病症状预测病马的死亡率

数据准备：处理数据中的缺失值

可选做法：

使用可用特征的均值来填补缺失值
使用特殊值来填补缺失值，如-1
忽略有缺失值的样本
使用相似样本的均值填补缺失值
使用另外的机器学习算法预测缺失值

本处选择用0作为缺失值：

回归系数的更新公式中如果为0，则其对应系数不更新
sigmoid(0) = 0.5，对结果的预测不具有任何倾向性

如果标签数据缺失，则可以简单丢弃该数据

5.4 本章小结

随机梯度上升法与梯度上升法相当，但占用更少的计算资源。

第6章支持向量机

关注支持向量机的SMO（序列最小优化：Sequential Minimal Optimization）实现

优点：泛化错误率低，计算开销不大，结果易理解
缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题
适用数据类型：数值型和标称型数据

6.1 基于最大间隔分隔数据

线性可分，分割超平面
希望找到离分割超平面最近的点，确保它们离分割面的距离尽可能远
间隔（margin）：点到分隔面的距离
支持向量（support vector）：离超平面最近的那些点
需要最大化支持向量到分割面的距离

6.2 寻找最大间隔

A点到超平面的法线的长度:

$|W^TA+b|\over||W||$

分类器求解的优化问题

使用单位阶跃函数对 $W^TX+b$ 作用使其标签值为-1（ $W^TX+b<0$ ）或者+1（ $W^TX+b>0$ ），这样计算间隔就可以采用 $label*(W^TX+b)$
现在目标是为了找出分类器的 w 和 b：

$arg\max_{w,b}{\{min_n(label*(w^Tx+b))*{1\over||w||}\}}$
令所有支持向量的

$label*(w^Tx+b)$ 都为1，可以通过求

$1\over||w||$ 的最大值。
转化为带约束条件的最优化问题。

SVM应用的一般框架

收集数据：任意
准备数据：需要数值型数据
分析数据：有利于可视化分割超平面
训练算法：SVM的大部分时间都源自训练，该过程主要实现两个参数的调优
测试算法：十分简单的计算过程可以实现
使用算法：几乎所有分类问题都可以使用SVM，值得一提的是，SVM本身是一个二类分类器，对多类问题应用SVM需要对代码做一些修改

6.3 SMO高效优化算法

工作原理：每次循环中选择两个alpha进行优化处理，一旦找到一系列alpha和b

SMO伪代码

创建一个alpha向量并将其初始化为0
当迭代次数小于最大迭代次数时（外循环）
- 对数据集中的每个数据向量（内循环）：
  - 如果该数据向量可以被优化;
    - 随机选择另外一个数据向量
    - 同时优化这两个向量
    - 如果两个向量都不能被优化，退出内循环
- 如果所有向量都没有被优化，增加迭代次数，继续下一次循环

6.4 利用完整PlatSMO算法加速优化

6.5 在复杂数据上应用核函数

核函数：将低维特征空间映射到高维空间。SVM所有的运算都写成内积的形式，而直接将内积运算替换成核函数，称为核技巧。

高斯函数，径向基函数的一种。

是 确 定 函 数 值 跌 落 到 的 速 度 参 数

$k(x,y)=exp({-||x-y||^2\over 2\theta^2}),\theta是确定函数值跌落到0的速度参数$

支持向量过少就会得到一个很差的决策边界。支持向量太多，也就相当于每次利用整个数据集进行分类，相当于k近邻。

第7章利用AdaBoost元算法提高分类性能

元算法是对其他算法进行组合的一种方式

优点：泛化错误率低，易编码，可以应用在大部分分类器上，无参数调整
缺点：对离群点敏感
适用数据类型：数值型和标称型数据

AdaBoost（adaptive boosting）的一般流程：
收集数据：任意
准备数据：依赖于所使用的弱分类器类型。作为弱分类器，简单分类器的效果更好
分析数据：任意
训练算法：大部分时间用于训练，分类器将多次在同一数据集上训练弱分类器
测试算法：计算分类的错误率
使用算法：预测两个分类中的一个。如果需要应用到多个分类，则需要修改

7.1 基于数据集多重抽样的分类器

bagging:基于数据随机重抽样的分类器构建方法

自举汇聚法，是从原始数据集选择S词后得到S个新数据集的一种技术。新数据集与原始数据集大小相等。每个数据集都是通过在原始数据集中随机选择一个样本来进行替换而得到的。这里的替换意味着可以多次地选择同一样本。当需要对新数据进行分类时，则使用上面S个数据集训练的分类器进行分类，选择投票结果中最多的类别作为结果。

boosting

与bagging类似，多个分类器的类型都是一样的。boosting中，不同的分类器是通过串行训练而获得的，每个新分类器都根据已训练出的分类器的性能来进行训练。boosting是通过集中关注被已有分类器错分的那些数据来获得新的分类器。boosting分类中各个分类器的权重是不一样的。

弱分类器：分类器性能比随机猜测要好，但是也不会好太多

7.2 训练算法

对每个分类器定义一个权重alpha，错误率epsion

未 正 确 分 类 的 样 本 数 目 所 有 样 本 数 目

$\epsilon= {未正确分类的样本数目\over所有样本数目}$

$\alpha = {1\over2}ln({1-\epsilon \over \epsilon})$
如果某个样本被正确分类，那么该样本的权重更新为：

$D_i^{(t+1)} = {D_i^{(t)}e^{-\alpha} \over{Sum(D)}}$
如果某个样本被错分，那么该样本的权重更改为：

$D_i^{(t+1)} = {D_i^{(t)}e^{\alpha} \over{Sum(D)}}$
迭代进行，直到错误率为0或者弱分类器个数达到用户指定值

7.3 基于单层决策树构建弱分类器

单层决策树（decision stump，也称决策树桩），是一种简单的决策树。
针对每个特征，每个步长来选择合适的分割点，使其以该特征该分割点分割的数据具有最小的错误率。

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data
    retArray = ones((shape(dataMatrix)[0],1))
    if threshIneq == 'lt':
        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
    else:
        retArray[dataMatrix[:,dimen] > threshVal] = -1.0
    return retArray
def buildStump(dataArr,classLabels,D):
    dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
    m,n = shape(dataMatrix)
    numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m,1)))
    minError = inf #init error sum, to +infinity
    for i in range(n):#loop over all dimensions
        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();
        stepSize = (rangeMax-rangeMin)/numSteps
        for j in range(-1,int(numSteps)+1):#loop over all range in current dimension
            for inequal in ['lt', 'gt']: #go over less than and greater than
                threshVal = (rangeMin + float(j) * stepSize)
                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)#call stump classify with i, j, lessThan
                errArr = mat(ones((m,1)))
                errArr[predictedVals == labelMat] = 0
                weightedError = D.T*errArr  #calc total error multiplied by D
                #print "split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError)
                if weightedError < minError:
                    minError = weightedError
                    bestClasEst = predictedVals.copy()
                    bestStump['dim'] = i
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal
    return bestStump,minError,bestClasEst

7.4 完整AdaBoost算法的实现

对每次迭代：
利用buildStump函数找到最佳的单层决策树
将最佳单层决策树加入到单层决策树数组
计算alpha
计算新的权重向量D
更新累计类别估计值
如果错误率等于0.0，则退出循环

classEst = clster.predict(X)
expon = multiply(-1*alpha*mat(Y).T, classEst)
D = multiply(D, exp(expon))
D = D / D.sum()
aggclassest += alpha * classEst
aggerror = multiply(sign(aggclassest) != mat(Y).T, ones((m,1)))
errorrate = aggerrors.sum() / m
if errorate == 0: break

7.5 测试算法：基于AdaBoost的分类

通过所有的分类器进行预测，其结果与权重内积再取符号

$\alpha*cls\_est$

7.6 示例：在一个难的数据集上应用AdaBoost

马得疝病是否会死亡预测

AdaBoost测试错误率在达到一个最小值后随着分类器的个数增加变差了，发生了过拟合。对于好的数据集来说，AdaBoost算法会稳定在一个错误率，而不会再变大。AdaBoost与SVM是监督学习中最强大的两种算法。

7.7 非均衡分类问题

其他分类性能指标：正确率、召回率和ROC曲线

可以使用混淆矩阵（confusion matrix）来了解分类中的错误。

正确率： TP/(TP+FP)
召回率： TP/(TP+FN)
ROC曲线（接受者操作特征 receiver operating characteristic）：横轴为假阳率（FP/(FP+TN)，阴判断为阳性的比例），纵轴为真阳率（TP/(TP+FN)，实际阳中判断为阳的比例）
AUC（Area Unser the Curve），ROC曲线下的面积，完美分类器为1，随机猜测为0.5。

为了画ROC，分类器必须提供每个样例被判为阳性或者阴性的可信程度值。朴素贝叶斯，逻辑回归中输入sigmod函数中的值，Adaboost和SVM传递给sign函数的值。

创建算法：
将所有预测按照预测强度排序
从最低点开始（也即是之前的点判为负例，之后判为正例，也即是全判正），此时点为 1， 1
以正例的个数作为Y轴的最大的长度，1/num_pos作为步长，1/num_neg为X轴步长
依次移动分界线，也即是真阳率每次下降一个步长，计算伪阳率，从右上往下画图

AUC： ysum*xstep

基于代价函数的分类器的决策控制

调节分类器输出阀值

代价敏感的学习（cost sensitive learning）
正常代价为 TP*0 + FN*1 + FP*1 + TN*0
可调整为 TP*-5 + FN*1 + FP*50 + TN*0

分类算法中引入代价信息：
AdaBoost中，基于代价函数来调整错误权重向量D
朴素贝叶斯中，可以选择具有最小期望而不是最大概率的类作为输出结果
SVM中，可以在代价函数中对于不同的类别选择不同的参数C
以上做法都会给较小类更多的权重，即训练时，小类中只允许更少的错误

抽样方法

欠抽样（undersampling）：删除部分样例
过抽样（oversampling）：复制部分样例

第8章预测数值型数据：回归

8.1 用线性回归找到最佳拟合直线

线性回归: 优点：结果易于理解，计算上不复杂
缺点：对非线性的数据拟合不好
适用数据类型：数值型和标称型数据
线性回归: 线性回归意味着可以将输入项分别乘以一些常量，再将结果加起来得到输出。
平方误差: 由平方误差计算方式可得 $\sum_{i=1}^m(y_i-x_i^Tw)^2=(y-Xw)^T(y-Xw)$ ，求解w导数可得
$\hat w=(X^TX)^{-1}X^Ty;(OLS, ordinary least squares)$

XTX = xMat.T*xMat
if linalg.det(XTX) == 0.0: #奇异矩阵，不可逆
    rasie ....
#可以使用 ws = linalg.solve(xTx, xMat.T*yMatT)

可以通过相关系数来查看预测y，与实际y的相关系数

corrcoef(yEstimate, yActual)

8.2 局部加权线性回归（Locally Wrighted Linear Regression，LWLR）

$\hat w = (X^TWX)^{-1}X^TWy$ 使用核函数来对附近的点赋予更高的权重，最常见的核就是高斯核

$w(i,i)=exp({|x^{(i)}-x|\over -2k^2})$ 构建了一个只包含对角元素的权重矩阵w，x为需要预测的点，且x与x(i)越接近，其权重越大

k的取值: k值越大，表示选择的点的权重范围越广，越接近于线性回归
k值越小，表示选择的点的范围越小，越拟合

LWLR需要针对每一个点都要进行整个数据集的耦合。

8.3 示例：预测鲍鱼的年龄

采用rsserror来计算在新数据上的误差

8.4 缩减系数来“理解”数据

如果数据的特征比样本点还多，则其输入矩阵不是满秩矩阵，求逆会出问题

岭回归（ridge regression）

岭回归是在矩阵XTX上加一个矩阵使其非奇异。其中I为m×m的单位矩阵，对角线上元素全是1，其他全为0.

$\hat w = (X^TX+\lambda I)^{-1}X^Ty$
最先用于处理特征数较多的情况，现在也用于在估计中加入偏差，从而得到更好的估计。引入lambda来限制了所有的w之和，通过引入该惩罚项，能够减少不重要的参数，这就是缩减（shrinkage）。岭回归中的“岭”就是指的在0的平面上有一条1组成的岭。

lambda的计算，是通过交叉验证，看lambda的取值最佳值。首先需要对数据进行标准化，原值-均值/方差，保证所有特征维度一致

$x = {x-x_{mean}\over (x-x_{mean}).std};y=y-y_{mean}$

lambda值的选择: lambda值越小，越接近线性回归
lambda值越大，其回归系数越接近0

lasso

增加约束 $\sum_{k=1}^nw_k^2\le \lambda$ 就会得到岭公式
lasso方法为增加约束 $\sum_{k=1}^n|w_k|\le \lambda$ ，其结果在lambda足够小的时候就会有一些系数缩减到0.可以帮忙理解数据。lasso需要采用二次规划算法解决。

前向逐步回归

属于贪心算法，即每一步尽量减少误差。刚开始，所有的权重设置为1，每一步所做的决策就是将某个权重增加或者减少一个很小的值，最大迭代次数设定。

数据标准化，使其分布满足0均值和单位方差
在每轮迭代过程中：
- 设置当前最小误差lowestError为正无穷大
- 对每个特征：
  - 增大或者缩小：
    - 改变一个系数得到一个新的w
    - 计算新w下的误差
    - 如果误差Error小于当前最小误差，设置wbest，更新lowestError
- 将w设置为新的wbest

迭代次数越多与线性回归越接近。步长过长则会容易导致震荡。
逐步线性回归算法可以帮忙人们理解现有模型并做出改进，可以找出重要的特征，并停止那些不重要特征的收集。
用于测试，该算法可以每100次迭代后构建一个模型，交叉验证，最终选择使误差最小化的模型。

8.5 权衡偏差与方差

训练误差和测试误差之间由三部分组成：偏差、随机误差和随机噪声。
方差可以度量，例如从数据中取一个随机样本集，用线性模型拟合，得出一组回归系数。同样再取另一组，进行拟合，两者系数的差异大小就是模型方差大小的反映。

8.6 示例：预测乐高玩具套装的价格

使用Google购物的API

第9章树回归

9.1 复杂数据的局部性建模

决策树不断将数据切分成小数据集，直到所有目标变量完全相同，或者数据不能再切分为止。决策树是一种贪心算法，在给定时间内作出最佳选择，并不关心能否达到全局最优。

树回归: 优点：可以对复杂进而非线性的数据建模
缺点：结果不易理解
适用数据类型：数值型和标称型数据

CART使用二元切分来处理连续型变量。对CART稍作修改就可以处理回归问题。

9.2 连续和离散型特征的树的构建

构建算法:

找到最佳的待切分特征：
- 如果该节点不能再分，将该节点存为叶节点
- 执行二元切分
- 在左子树构建本方法
- 在右子树构建本方法

9.3 将CART算法用于回归

回归树假设叶节点是常数值，这种策略认为数据中的复杂关系可以用树结构来概括。

连续型数值的混乱度计算: 计算均值，计算每个点到均值的绝对值或者平方。类似总方差。

切分函数

对每个特征：
- 对每个特征值：
  - 将数据集切分成两份
  - 计算切分的误差
  - 如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新
返回最佳切分的特征和阀值

9.4 树剪枝（tree pruning）

通过降低决策树的复杂度来避免过拟合的过程称为剪枝。

预剪枝（prepruning）

预剪枝通过算法中的参数min_sample_num, min_delta_error来进行控制

后剪枝（postpruning）

后剪枝方法将数据集分成测试集和训练集。首先指定参数，使得构建出来的树足够大、足够复杂，便于剪枝。接下来从上而下找到叶节点，用测试集判断将这些叶节点合并能否降低测试误差，如果是就合并。

基于已有的树切分测试数据：
- 如果存在任一子集是一棵树，则在该子集递归剪枝过程
- 计算将当前两个叶节点合并后的误差
- 计算不合并的误差
- 如果合并会降低误差的话，就将叶节点合并

9.5 模型树

除了可以把叶节点设置为常数值外，还可以将叶节点设置为分段线性函数(piecewise linear)，所谓的分段线性是指模型由多个线性片段组成。

叶节点产生为函数

def model_leaf(dataset):
    ws, x, y = linesolve(dataset)
    return ws
def model_error(dataset):
    ws, x, y = linesolve(dataset)
    yhat = x*ws
    return sum(power(y - yhat, 2)

回归判断哪个模型好：
用y与预测y计算相关性进行判断， corrcoef

9.6 示例：树回归与标准回归的比较

树回归方法一般比标准回归更有效

第10章使用K-均值聚类算法对未标注数据分组

聚类是一种无监督的学习，它将相似的对象归到同一个簇中。有点像全自动分类，聚类方法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果越好。簇识别（cluster identification）给出聚类结果的含义。
聚类分析试图将相似对象归入同一簇，将不相似对象归到不同簇。相似这一概念取决于所选择的相似度计算方法。

10.1 K-均值聚类方法

优点：容易实现
缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢
适用数据类型：数值型数据

伪代码:

创建k个点作为起始质心（经常是随机选择）
当任意一个点的簇分配结果发生变化时
- 对数据集中的每个数据点
  - 对每个质心
    - 计算质心与数据点之间的距离
  - 将数据点分配到距其最近的簇
- 对每一个簇，计算簇中所有点的均值并将均值作为质心

10.2 使用后处理来提高聚类性能

K均值收敛但是聚类效果差的原因是，K-均值算法收敛到了局部最小值，而非全局最小值。

用于度量聚类效果的指标是SSE（Sum of Squared Error，误差平方和），SSE值越小表示数据点越接近于它们的质心，聚类效果也越好。对误差取了平方，因此更加重视那些远离中心的点。可以通过降低SSE值的方法是增加簇的个数，但违背聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。

将具有最大SSE值的簇划分成两个簇。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行K-均值算法，k为2.

合并最近的质心
合并两个使得SSE增幅最小的质心

10.3 二分K-均值算法

首先将所有点作为一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值，上述划分过程不断重复，直到用户指定的簇数目为止

伪代码：

将所有点看成一个簇
当数目小于k时
- 对于每一个簇
  - 计算总误差
  - 在给定的簇上面进行K-均值聚类（k=2）
  - 计算将该簇一分为二后的总误差
- 选择使得误差最小的那个簇进行划分操作

两种选择方法: 1.选择总误差降低量最大的簇进行划分
2.选择SSE最大的簇进行划分

10.4 示例：对地图上的点进行聚类

采用经纬度进行计算

第11章使用Apriori算法进行关联分析

从大规模数据集中寻找物品间的隐含关系被称为关联分析（association analysis）或者关联规则学习（association rule learning）。

11.1 关联分析

Apriori分析: 优点：易编码实现
缺点：在大数据集上可能较慢
适用数据类型：数值型或者标称数据型
频繁项集（frequent item sets）: 是经常出现在一块的物品的集合
关联规则（association rules）: 暗示两者之间有可能存在很强的关系
支持度（support）: 一个项集的支持度（support）被定义为数据集中包含该项集的记录所占的比例。支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留满足最小支持度的项集。
可信度或置信度（confidence）: 是针对一条诸如{尿布} $\rightarrow$ {葡萄酒}的关联规则来定义的。定定义为
$支持度尿布、葡萄酒支持度尿布$
$支持度({尿布、葡萄酒})\over 支持度(尿布)$

11.2 Apriori原理

某个项集是频繁的，那么它的所有子集也是频繁的。反过来说，如果一个项集是非频繁集，那么它所有的超集也是非频繁的。

是 非 频 繁 的 是 非 频 繁 的

$\{A,..\}是非频繁的\rightarrow \{A,..,X\}是非频繁的$

11.3 使用Apriori算法来发现频繁集

Apriori算法是发现频繁项集的一种方法。Apriori算法的输入参数分别是最小支持度和数据集。首先生成所有单个物品的频繁项集列表，接着扫描交易记录来查看哪些项集满足最小支持度要求，那么不满足的的集合被去掉，对剩下的集合进行组合以生成包含两个元素的项集。重新扫描，去除。。。

数据集扫描伪代码：

对数据集中的每条交易记录tran
- 对每个候选项集can：
  1. 检查一下can是否是tran的子集
  2. 如果是，增加can的计数器
对每个候选集项集：
- 如果其支持度不低于最小值，则保留该项集
返回所有频繁项集列表

Apriori算法伪代码：

当集合中的项的个数大于0时
- 构建一个k个项组成的候选项集的列表
- 检查数据以确认每个项集都是频繁的
- 保留频繁项集并构建k+1项组成的候选项集的列表

生成新集合的伪代码：

遍历项集i
- 从i+1开始遍历项集j
  - 如果ij两个项集的前面k-1个相同
  - 则保存两个合并生成k+1项集
返回k+1项集列表

只比较k-1个项的目的，假设能够生成某k+1项集，则当前项集集合中会存在k+1个项集，而这k+1个项集是只对应于该k+1项集，如果L1，L2为排序的话，则只有一种会存在L1和L2中前k-1相同，即[1,...,k-1,k]和[1,...,k-1,k+1]，而其他情况下两者的不同不会是最后一位。

11.4 从频繁项集中挖掘关联规则

前件后件
规则的可信度定义为

$support({P|H})\over support(P)$

如果某条规则不满足最小可信度要求，则该规则的前件的所有子集以及后件的超集都不会满足可信度要求

不 满 足 要 求 不 满 足 要 求 ； 不 满 足 要 求

$012-3不满足要求\rightarrow 12-3不满足要求；12-34不满足要求$

生成规则的方法：分级法

对一个频繁集
依次产生新的单一元素的后件列表
频繁集减去后件计算出前件，根据confidence计算其支持度，保留达标的后件
如果当前长度后件列表大于1，通过Apriori算法来产生+1长度的后件集，转3

11.5 示例：发现国会投票中的模式

购物
搜索引擎的查询词
国会投票记录

11.6 示例：发现毒蘑菇的相似特征

通过发现蘑菇有毒的频繁集来发现相关特征

第12章使用FP-growth算法来高效发现频繁项集

FP-growth算法发现频繁项集的基本过程如下：
1. 构建FP树
2. 从FP树中挖掘频繁项集

12.1 FP（Frequent Pattern）树：用于编码数据集的有效方式

FP-growth算法: 优点：一般要快于Apriori算法
缺点：实现比较困难，在某些数据集上性能会下降
适用数据类型：标称型数据

一个元素可以在FP树中出现多次。FP树会存储项集的出现频率，而每个项集以路径的方式存储在树中。存在相似元素的集合会共享树的一部分。只有当集合完全不同时才会分叉。树节点上给出集合中单个元素以及其在序列中出现的次数，路径给出该序列的出现次数。

12.2 构建FP树

创建一个树node类
在构建前，需要按照绝对出现频率排序。从空集开始，向其不断添加频繁项集。过滤、排序后的事务依次添加到树中，如果树中已存在现有元素，则增加现有元素的值，如果现有元素不存在，则向树中添加一个分支。

创建头表，计数各个单元素的出现次数，去掉不满足最低支持度要求的元素
创建根节点
针对每条事务
- 对事务进行处理，删除掉不满足要求的元素，并将每个事务中的元素按照出现频率倒序排序
- 判断当前元素是否位于Fp树中，是则增加数目计数，否则增加分支，并添加到头表

12.3 从一棵FP树中挖掘频繁项集

基本步骤: 从FP树中获得条件模式基
利用条件模式基，构建一个条件FP树
迭代执行上述步骤，直到树包含一个元素项为止

抽取条件模式基（conditional pattern base）

条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实是一条前缀路径（prefix path），是介于所查找元素项与树根节点之间的所有内容。可以通过FP树的头表达到计算该元素的所有前缀路径。

创建条件FP树

对于每一个频繁项，都要创建一个条件FP树。

def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
    bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])]#(sort header table)
    for basePat in bigL:  #start from bottom of header table
        newFreqSet = preFix.copy()
        newFreqSet.add(basePat)
        #print 'finalFrequent Item: ',newFreqSet    #append to set
        freqItemList.append(newFreqSet)
        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
        #print 'condPattBases :',basePat, condPattBases
        #2. construct cond FP-tree from cond. pattern base
        myCondTree, myHead = createTree(condPattBases, minSup)
        #print 'head from conditional tree: ', myHead
        if myHead != None: #3. mine cond. FP-tree
            #print 'conditional tree for: ',newFreqSet
            #myCondTree.disp(1)            
            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)

12.4 示例：在Twitter源里发现一些共现词

12.5 示例：从新闻网站点击流中挖掘

采用kosarak数据,Hungarian online news portal clickstream
http://fimi.ua.ac.be/data/

第13章利用PCA来简化数据

人们看电视将电视屏幕的百万像素点维度转换成了实际的空间三维。在低维下，数据更易于处理。其相关特征可能在数据中明确地显示出来。

13.1 降维技术

数据简化的原因: 使得数据更易于显示与可视化
使得数据集更易于使用
降低很多算法的计算开销
去除噪声
使得结果易懂

PCA（Principal Component Analysis，主成分分析）。在PCA中，数据从原来的坐标系转换到了新的坐标系，新坐标的选择由数据本身确定。第一个新坐标轴选择的是原始数据中方差最大的方向，第二个选择的是和第一个坐标轴正交且具有最大方差的方向。该过程一直重复，次数为原始数据中特征的数目。

因子分析（Factor Analysis）。假设在观察数据的生成中有一些观察不到的隐变量（latent variable）。假设观测数据是这些隐变量和某些噪声的线性组合。那么隐变量的数据可能比观测数据的数目少。

独立成因分析（Independent Component Analysis，ICA）。假设数据是从n个数据源生成的。假设数据为多个源的混合观测结果。这些数据源在统计上是相互独立的。如果数据源的数目少于观察数据的数目，则可以实现降维。

13.2 PCA

优点：降低数据的复杂度，识别最重要的多个特征
缺点：不一定需要，且可能损失有用信息
适用数据类型：数值型数据

移动坐标轴

第一条坐标轴旋转到覆盖数据的最大方差位置，数据的最大方差给出了数据的最重要的信息。然后正交选择第二坐标轴。

坐标轴的旋转并没有减少数据的维度。通过PCA进行降维处理，我们可以同时获得SVM和决策树的优点：一方面，得到和决策树一样简单的分类器，同时分类和SVM一样好。

在numpy中实现PCA

伪码如下: 去除平均值
计算协方差矩阵
计算协方差矩阵的特征值和特征向量
将特征值从大到小排序
保留最上面的N个特征向量
将数据转到上述N个特征向量构建的空间中

def pca(dataMat, topNfeat=9999999):
    meanVals = mean(dataMat, axis=0)
    meanRemoved = dataMat - meanVals #remove mean
    covMat = cov(meanRemoved, rowvar=0)
    eigVals,eigVects = linalg.eig(mat(covMat))
    eigValInd = argsort(eigVals)            #sort, sort goes smallest to largest
    eigValInd = eigValInd[:-(topNfeat+1):-1]  #cut off unwanted dimensions
    redEigVects = eigVects[:,eigValInd]       #reorganize eig vects largest to smallest
    lowDDataMat = meanRemoved * redEigVects#transform data into new dimensions
    reconMat = (lowDDataMat * redEigVects.T) + meanVals
    return lowDDataMat, reconMat

可视化

fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(data_mat[:,0],...)
ax.scatter(recon_mat[:,0],...)

13.3 示例：利用PCA对半导体制造数据降维

uci上面secom数据集

将NAN替换成平均值

for i in range(numfeat):
    meanval = mean(dataMat[nonzero(~isnan(datamat[:,i].A))[0],i])
    dataMat[nonzero(isnan(datamat[:,i].A))[0],i] = meanval

计算协方差矩阵并进行PCA分解
很多权重值为0，说明这些特征是其他特征的副本，对权重数据进行可视化。
保留前6个覆盖了大部分的方差。而且舍弃了噪声的影响。

第14章利用SVD简化数据

SVD（Singular Value Decomposition），奇异值分解。

14.1 SVD的应用

优点：简化数据，去除噪声，提高算法的结果
缺点：数据的转化可能难以理解
适用数据类型：数值型数据

利用SVD实现，我们可以适用小得多的数据集来表示原始数据集。实际上是去除了噪声和冗余信息。

隐性语义索引/分析（Latent Semantic Indexing/Analysis）

一个矩阵由文档和词语组成，应用SVD时，会构建出多个奇异值。这些奇异值代表了文档中的概念或主题，可以用于更高效的文档搜索。

词语拼写错误的问题
同义词的使用，使用SVD，同义词会映射成同一概念

14.2 矩阵分解

SVD将原始的聚则Data分解成三个矩阵

$Data_{m*n}=U_{m*m}\sum\ _{m*n}V^T_{n*n}$ 矩阵

$\sum$ 为对角矩阵，这些值从大到小排列，称为奇异值（sigular value）。奇异值就是

$Data*Data^T$ 特征值的平方根。

科学和工程中，一直存在这样一个普遍事实，在某个奇异值的数目（r个）后，其他的特征值都置为0。意味着数据集中仅有r个重要特征，而其余特征则是噪声或者冗余特征。

14.3 利用Python实现SVD

U,Sigma,VT = linalg.svd(data)
#Sigma理应为矩阵，在输出中为数组，只记录对角值

一般情况下是保留矩阵中90%的能量信息。将所有奇异值求平方，然后累计和到90%即可。另一种如果奇异值太多，可以保留前面的20%到30%。

14.4 基于协同过滤的推荐引擎

相似度计算

协同过滤不关心物品的描述属性，而是严格地按照许多用户的观点来计算相似度。

欧式距离
皮尔逊相关系数
余弦相似度

基于物品的相似度还是基于用户的相似度

根据具体的用户数和物品数来选择。

14.4 示例：餐馆菜肴推荐引擎

利用SVD提高推荐的效果

对矩阵进行SVD分解，选择达到90%的个数

def svdEst(dataMat, user, simMeas, item):
    n = shape(dataMat)[1]
    simTotal = 0.0; ratSimTotal = 0.0
    U,Sigma,VT = la.svd(dataMat)
    Sig4 = mat(eye(4)*Sigma[:4]) #arrange Sig4 into a diagonal matrix
    xformedItems = dataMat.T * U[:,:4] * Sig4.I  #create transformed items
    for j in range(n):
        userRating = dataMat[user,j]
        if userRating == 0 or j==item: continue
        similarity = simMeas(xformedItems[item,:].T,\
                             xformedItems[j,:].T)
        print 'the %d and %d similarity is: %f' % (item, j, similarity)
        simTotal += similarity
        ratSimTotal += similarity * userRating
    if simTotal == 0: return 0
    else: return ratSimTotal/simTotal

构建推荐引擎面临的挑战

不必每次评估都计算SVD，SVD分解可以周期进行
离线计算并保存相似度评分
冷启动：基于内容的推荐

14.6 示例：基于SVD的图像压缩

对手写体图片进行压缩

def imgCompress(numSV=3, thresh=0.8):
    myl = []
    for line in open('0_5.txt').readlines():
        newRow = []
        for i in range(32):
            newRow.append(int(line[i]))
        myl.append(newRow)
    myMat = mat(myl)
    print "****original matrix******"
    printMat(myMat, thresh)
    U,Sigma,VT = la.svd(myMat)
    SigRecon = mat(zeros((numSV, numSV)))
    for k in range(numSV):#construct diagonal matrix from vector
        SigRecon[k,k] = Sigma[k]
    reconMat = U[:,:numSV]*SigRecon*VT[:numSV,:]
    print "****reconstructed matrix using %d singular values******" % numSV
    printMat(reconMat, thresh)

只需要使用2个奇异值就可以重构图像，而实际的空间需要为U（32*2），VT（32*2）， $\sum$ 为2。

第15章大数据与MapReduce

15.1 MapReduce：分布式计算的框架

优点：可在短时间内完成大量工作
缺点：算法必须经过重写，需要对系统工程有一定的了解
适用数据类型：数值型和标称型数据

学习要点：

主节点控制MapReduce的作业流程
MapReduce的作业可以分成map任务和reduce任务
map任务之间不做数据交流，reduce任务也一样
在map和reduce阶段中间，有一个sort和combine阶段
数据被重复放到不同的机器上，以防某个机器失效
mapper和reducer传输的数据形式为key/value对

15.2 Hadoop流

Hadoop可以使用其余语言在Hadoop流上运行

分布式计算均值和方差的mapper

mapper产生： $num,mean(\sum x_i),mean(\sum x_i^2)$
reducer:

cumVal=0.0
cumSumSq=0.0
cumN=0.0
for instance in mapperOut:
    nj = float(instance[0])
    cumN += nj
    cumVal += nj*float(instance[1])
    cumSumSq += nj*float(instance[2])
#calculate means
mean = cumVal/cumN
meanSq = cumSumSq/cumN
varsum = (cumSumSq - 2*mean*cumval + cumN*mean*mean)/cumM

15.3 在Amazon网络服务上运行Hadoop程序

15.4 MapReduce上的机器学习

简单贝叶斯
k-近邻算法
支持向量机，Pegasos算法
奇异值分解，Lanczos算法
K-均值聚类，canopy聚类

15.5 在Python中使用mrjob来自动化mapreduce

15.6 示例：分布式SVM的Pegasos算法

Pegasos算法

15.7 你真的需要MapReduce吗？

一般情况下是不需要MapReduce的

附录 numpy入门

包括两种数据结构

array数组
matrix矩阵
矩阵的元素之间相乘使用np.multipy

附录矩阵

矩阵范数

向量范数会给予向量赋予一个正标量值

$||Z||_p=(\sum_{i=1}^n|Z_i|^p)^{1\over p}$ 向量的2范式常常写作

或

$||z||或||z||^2$

矩阵求导

$A=[A1, A2],B=[x,y,z]$

${dA\over dB}=\begin{bmatrix}dA1/dx&dA2/x\\dA1/dy &dA2/dy\\dA1/dz&dA2/dz\end{bmatrix}$