《机器学习 算法原理与编程实践》--doing

机器学习 读书笔记

---

1 机器学习的基础

1.1 编程语言与开发环境

使用Python语言

1.2 对象、矩阵和矢量化编程

对象，特征，维度，行向量
矩阵是具有相同特征和维度的对象集合
对象为矩阵的一行，特征为矩阵的一列

Linalg

行列式 det(A)
逆 inv(A)
对称 A.T
秩 matrix_rank(A)
可逆矩阵求解 solve(A,T(b))

1.3 机器学习的数学基础

概率论：说明事物可能会是怎么样？
数值分析：揭示其为什么这样？
线性代数：告诉我们事物从来不只有一个样子，从多个角度观察事物

相似性的度量

范数
余弦 dot(v1,v2)/(linalg.norm(v1)*linalg.norm(v2))
汉明
杰卡德相似系数

概率论基本概念

样本点：实验的一个结果
样本空间：所有实验的可能结果
随机事件：样本空间的一个子集
随机变量：指向某个事件的一个变量
随机变量的概率分布：给定随机变量的取值范围，其导致某种随机事件出现的可能性

多元随机变量：联合概率分布，边缘分布

期望：特征取值范围的平均值
方差：特征取值范围的离散程度
协方差矩阵和相关系数：衡量样本特征列之间线性相关性

相关系数

$$E((X-EX)(Y-EY))\over\sqrt{D(X)}\sqrt{D(Y)}$$
python numpy : corrcoef(A)

马氏距离：排除量纲干扰

空间变换：

向量

是一个有方向有大小的量，坐标只不过表征该量与原点的距离、与坐标轴的方向，向量的长度和方向都是相对于其他向量的量。向量由基底表征。

向量与矩阵乘法

就是将向量从一个线性坐标通过选择新基底映射到另一个线性空间

矩阵乘法

向量组映射，或变换的再变换

特征值与特征向量

原向量发生旋转、伸缩，总有些向量在该过程中不发生旋转
evals, evecs = linalg.eig(A);A=evecs*(evals*eye(m))*linalg.inv(evecs)

1.4 数据处理与可视化

matplotlib

1.5 部署开发环境

略

2 中文文本分类

2.1 文本挖掘与文本分类的概念

文本挖掘是指从大量文本数据中抽取事先未知的、可理解的、最终可用的知识的过程，同时运用这些知识更好地组织信息以便将来参考。

• 搜索和信息检索
• 文本聚类
• 文本分类
• Web挖掘
• 信息抽取
• 自然语言处理
• 概念提取

2.2 文本分类项目

• 文本预处理
  
  • 选择处理的文本的范围，全文、段落还是句子
  • 建立分类文本语料库
    
    • 训练集数据，谭松波中文文本分类语料库、搜狗新闻分类语料库
    • 测试集
  • 文本格式转换，编码、html的标签等
  • 检测句子边界：标记句子的结束
• 分词：词的定义，驴肉、肉
  
  • 张华平中文分词，哈大语言云
  • 使用sklearn的Bunch进行文本的分词的持久化
  • 停用词：http://www.threedweb.cn/thread-1294-1-1.heml
  • TF-IDF权重策略
    
    • TF归一化：$TF_{ij}={n_{i,j}\over \sum_kn_{k,j}}$
    • IDF:$IDF_i=\log{|D|\over |{j:t_i\in d_j}|}$，防止除0，分母为1+

2.3 分类算法：朴素贝叶斯

Python实现略

2.4 分类算法：kNN

Python实现略

3 决策树的发展

3.1 决策树的基本思想

算法框架

• 主函数，本质上为递归函数，按照规则生长出决策树的各个分支节点
• 计算最优特征子函数
• 划分数据集函数
• 分类器

信息熵测度

每次选择均选择特征集中无序度最大的一个进行划分

3.2 ID3决策树实现

使用 信息增益

3.3 C4.5决策树实现

使用 信息增益率
$GainRatio(S,A)={Gain(S,A)\over SplitInfo(S,A)};SplitInfo(S,A)=-\sum_{i=0}^c{|S_i|\over |S|}\log_2{(|S|\over|s_i|)}$

3.4 Sklearn与回归树

使用最小剩余方差来判定回归树的最优划分

4 推荐系统原理

搜索引擎的缺点：1）关键词信息不足，不能准确深刻反映用户的潜在需求;2）必须对用户提供尽量丰富而无差别的信息

4.1 推荐系统概述

推荐系统的由起

• 需求定位角度看，用户的需求很难用关键字表述
• 需求个性角度看，需求的差异性
• 衍生需求的模糊性

推荐列表组成部分

• 经常一起购买的产品：打包销售
• 购买此商品的客户同时也购买了：协调过滤，作用：促销或定位用户购买需求（用户不一定是需要本书而是本类另外一本书）
• 看过此商品购买的其他商品：反映的是隐式需求
• 用户的商品评论列表
  
  • 文字评价
  • 数字评分

系统架构

• 数据来源

  • 物品信息
  • 用户信息
  • 用户对物品或信息的偏好
    
    • 显式用户反馈：评分、评论等
    • 隐式用户反馈：用户浏览记录、订单等

• 算法

  • 基于人口统计学的推荐机制：根据用户基本信息发现用户相关程度，然后将相似用户喜好进行推荐
  • 基于内容的推荐：基于用户的偏好，推荐相似物品
  • 基于协调过滤的推荐：根据用户对物品的偏好，发现用户之间或物品之间的相似性
  • 基于隐语义的推荐模型：

todo http://ibillxia.github.io/blog/2014/03/10/top-10-open-source-recommendation-systems/#tc_qz_original=691102124

4.2 协调过滤及其算法

通过用户和产品以及用户的偏好信息产生推荐，基本策略有两种：找到具有相似品味的人所喜欢的物品；从一个人喜欢的物品中找出类似的物品

数据预处理

• 多种行为的处理方式
  1）将不同的行为分组，一般可分为查看和购买，基于不同行为计算不同的用户/物品相似度
  2）根据不同行为反映用户偏好的程度将它们进行加权
• 减噪：一般是离群点
• 归一化：最简单办法就是除以最大值
  
  • 可以按照用户的购买总体为1，每个物品计算其比例
• 聚类：原始数据是基于单个用户和单个物品的，将用户或物品进行聚类，降低计算量

基于kNN获得距离最近的用户或者物品
用SVD模型进行推荐

4.3 Kmeans

4.4 聚类的改进：二分Kmeans算法

4.5 SVD算法详解

方阵可以通过特征值 $A = Q\sum Q^{-1}$
SVD分解

$$A_{m*n}=U_{m*m}\sum_{m*n} V_{n*n}^T$$
U:向量正交，为左奇异向量
$\sum$:奇异值，仅对角线有值，可以使用前面部分替代整体
$V^T$:右奇异矩阵

U, S, VT = linalg.svd(dataSet.T)
test = testevc * Ur * linalg.inv(Sr)
diss = [discalc(test, vi) for vi in Vr]

5 梯度寻优

5.1 最优化与计算复杂性

最优化理论的基础

矩阵理论，表征多元问题
数值分析，导数
计算机

基本数学模型

$$min/max_{x\in R} f(x)$$ $$s.t. h_i(x)=0;g_i(x)\le 0;(s.t. = subject\ to受限于)$$
h、f、g均为线性，则称线性规划；其中一个非线性，则为非线性规划；若目标函数为二次函数，约束为线性，则称二次规划；若目标为向量函数，则为多目标规划

凸集

在实数域R上的向量空间中，如果集合S中任意两点的连线上的点都在S内，则称S为凸集

超平面

定义为点集$X=\{x|c^Tx=z\}$

支撑超平面

凸集X的边界点w，得到$c^Tw=z$超平面，并使凸集中所有点都位于超平面的一侧

凸函数

对于凸集中任意点有$f(\alpha x_1+(1-\alpha)x_2)\le f(\alpha x_1)+f((1-\alpha)x_2)$
性质：1)任一局部极小（极大）也是全局极小（极大）点，且全体极小（极大）点的集合为凸集；2）任一局部最优解都是它的整体最优解

确定性有限状态机与非确定有限状态自动机
某些NP问题可以通过多项式时间的非确定算法进行判定或求解

逐次逼近法：
有Ax=b 可得 x=Bx+f （x1=...(x2..xn)+f1; x2=..(x1,x3,..)+f2; ...）,取x初值为全0，则代入上式可迭代计算
取决于方程，有些方程并不收敛

5.2 Logistic 梯度下降法

梯度是f(x)变化最快的方向

线性分类器是是最早的神经网络模型，也称为感知器模型。
最开始是采用hardlim硬限幅模型， $error = classLabel-hardlim(f); w_{k+1}=w_k+\alpha*x^T*error$，非连续函数，阶跃从0到1，决策边界过于狭窄，在跨越时，目标函数发生震荡

Logistic函数

令$p=P(Y=1|x)={1\over 1+e^{-w^Tx}},则P(Y=0|x)={1\over 1+e^{w^Tx}},{P(Y=1|x)\over P(Y=0|x)}=e^{w^tx},logit(x)=ln{P(Y=1|x)\over P(Y=0|x)}=w^tx$

todo 推理理解

gradient = dataMat * mat(weights)
output = logistic(gradient)
errors = target - output
weights = weights + alpha*dataMat.T*errors

5.3 算法分析

超平面的变化趋势，越来越接近分界
超平面的收敛评估，截距斜率变化

5.4 随机梯度下降法