数据挖掘学习笔记

记笔记的方式，先听课程，然后回忆复述课程里的重要知识点及相关概念，将其写到笔记上，随后看PPT核对

通过这三轮的反复强化一定可以把知识学牢！

数据挖掘在高校内没有对应的课程或者方向，它是一个融合了数学、统计学、计算机、以及各领域知识的综/合性方向，它涵盖范围很广，遍及互联网的各个角落。它能够实现”数据->信息->知识->决策支持“的转变。

走进数据科学

相关资料点击下载

大数据的三个特征

• 高容量：从TB到ZB
• 多样性：从结构化数据到结构与非结构数据的混合
• 高速度：从批处理到如今的实时流数据处理

应用领域

• 公共安全：美国各地区犯罪预测
• 健康医疗：根部人不同的DNA开出个性化药方
• 城市规划：哪些地方是人口密集区、交通、市场如何部署
• 零售行业：针对性广告投放
• 运动：美国小棒球社如何挑选潜力球员

基本概念

• 交叉验证：将数据分为训练集和测试集
• 混淆矩阵：分为TP(True Positive)、FP(False Positive)、FT和TN，用来评估模型准确率
• ROC曲线：AUC是ROC曲线与x轴围成的面积，用来评估模型的准确率

数据预处理

缺失值处理----->重复值处理----->类型转换与采样----->数据描述与可视化

异常值与重复值检测

数据缺失的原因

• 设备故障
• 隐私数据没有提供
• 数据不适用

数据缺失的种类

• 完全随机的缺失
• 跟属性相关的缺失
• 不是随机的缺失

离群点（Outliers）：跟整体数据差异比较大

异常点（Anomaly）：数据由于某种特定的原因导致异常

LOF（Local Outlier Factor）：离群点检测算法

当一个点距离周围的点越近$lrd$的值就会越大，$lrd$的分母相当于平均距离。

LOF的值表示的是相对距离的概念，当$lrd(B)$远大于$lrd(A)$就说明A的近邻B到它附近的点的距离远小于A到它近邻的距离，那么就是表明A是一个离群点了。LOF值越大表明是离群点可能越大

重复数据（Duplicate Data）：不同统计方式的列名不同、统计方式不同、存储方式也可能不同，但是统计的都是同类数据，解决方法是先排序(需要根据背景知识用key排序)再用滑动窗口进行比较去重。

类型转换与采样

对于某个属性的不同类别，不能采用简单的012的方式进行编码，因为这改变了不同属性之间的距离，从而可能改变问题复杂度。例子如下

仅仅是将绿色和蓝色交换了位置，分界线就从两条曲线变成了两条直线，问题求解的方式就发生了改变。

因此在处理这些数据时，往往采用one-hot独热编码，解决了分类器不好处理属性数据的问题，让特征之间的距离计算更加合理

One-Hot和word2vec

One-Hot

• 优点：一是解决了分类器不好处理离散数据的问题，二是在一定程度上也起到了扩充特征的作用
• 缺点：在文本特征表示上有些缺点就非常突出了。首先，它是一个词袋模型，不考虑词与词之间的顺序（文本中词的顺序信息也是很重要的）；其次，它假设词与词相互独立（在大多数情况下，词与词是相互影响的）；最后，它得到的特征是离散稀疏的

word2vec

**采样的原因：**1.数据量非常大计算机处理不过来 2.没有办法得到完整的用户数据

采样的优点：能够用于调整类别比例，例如理工科男女比例，如果采用完整数据集，则明显男生比例很高，不利于模型处理

**不平衡数据：**不同类别的样本数相差较大，尽管分类器A的准确率高，但是其误判了很重要的5%的数据，并不合理

解决办法

• 扩充数据集
• 对数据集进行重采样，包括过采样和欠采样
• 改变分类算法
• 改变评价指标，如PR曲线

在实际中可以采用除了Acc以外的其它的度量方式如G-mean、F-measure、Recall等等

边缘采样：对于几百万的数据，其中有很多数据都是作用不大的，提取其中的边缘点进行计算更有价值，能够节约计算资源

数据描述与可视化

Norlization：Min-max norlization、Z-score

数据描述：平均值、中位数、变化程序

数据可视化：一维数据直方图、二位数据坐标系、三维数据三维坐标系、高维数据Parallel
Coordinates

特征选择

从多个属性中，找出与问题有一定关联性的属性。

信息增益

怎么评价属性好不好？

答：查看该属性对结果的区分度，用熵Entropy衡量

信息增益ID3（Information gain）越大属性越好，表示它的跟结果越有关联，通常应用在决策树中

特征子集搜索

优化算法

• 模拟退火
• 禁忌搜索
• 遗传算法

特征提取

特征选择和特征提取的区别

特征提取的方法主要是通过属性间的关系，如组合不同的属性得到新的属性，这样就改变了原来的特征空间。
特征选择的方法是从原始特征数据集中选择出子集，是一种包含的关系，没有更改原始的特征空间。

PCA（Principal Component Analysis）

无监督学习，不考虑label，将高维数据降维，将其投影到可以分类的方向上（可以通过坐标旋转），数据在该方向上分布越分散越好

将样本点到投影线的距离表示成$J(\theta)$，$J(\theta)$越小表明从高维投影到低维损失的信息越少

因此对$J(\theta)$使用拉格朗日乘数法，最后发现要最大化的值就是特征值

描述：将数据的协方差矩阵（covariance matrix）进行特征分解，找到特征值最大的特征向量上，投影到该方向上即可在满足最少损失的条件下，将数据降维到n-1、n-2、…、2、1维

LDA（Linear Discriminant Analysis）

针对有标签数据，基本思路也是降维，但是要保留的是类的区分属性。LDA在投影时的思想类似于PCA，都是进行坐标旋转，并使得目标函数最大

目标：令$J$最大化

LDA和PCA例子

LDA的缺点

• $S_w$可能是奇异矩阵，即行数不等于列数时，逆矩阵不存在
• 当不同类的中心点重合时，目标函数$J(\theta)$为0，不work

从贝叶斯到决策树

课件下载

监督学习

一种从数据推测函数的技术，输入是一系列的特征，输出是一个bool值(二分类)或者整数(多分类)

贝叶斯分类(Naive Bayes Classifier)

一些贝叶斯应用实例

癌症：人群中检测出得癌症的概率是千分之八，人们往往容易产生恐慌

而从贝叶斯的角度分析，在得癌症的人群中假阳性的概率远大于真正癌症阳性的概率

这意味着即使体检报告上说得了癌症阳性，但其实上只有百分之20的概率是阳性。

头疼和流感：不同的先验概率得到的结果不同

$H=$“Having a headache” $F=$“Coming down with flu”

设$P(H)=1/10; P(F)=1/40; P(H|F)=1/2$，这意味着患流感人中有50%会头疼，这听起来不可思议。

但从另一个角度来看头疼的人中只有$1/8$的人患了流感，而现实人们往往将其混为一谈，误以为头疼有50%是得了流感

贝叶斯公式

​ $ P(A|B)=\frac{P(B|A)P(A)}{P(B)} $

朴素贝叶斯

在贝叶斯公式基础上assumpt各个事件是条件独立的

​ $ P (A,B|G) = P(A|G)P(B|G) \leftrightarrows P(A|G,B) = P(A|G)$

在实际中的例子

$P(Cancer│Male,Smoking)=P(Cancer|Smoking)$

即抽烟男性得肺癌得概率等于抽烟者得肺癌的概率，跟性别无关

肺癌

应用领域

文本分类，提取文本中的关键词，作为分类属性，使用贝叶斯分类器计算不同用户感兴趣的类别

在提取文本关键词时，并不是将文本简单分成词，随后将每一组词都参与运算，这样计算量很大并且效果也不明显，可以提取文章中出现最多的词语来为文章分类标签，那么就只需要统计每个词的频率，简化了公式，也就能够构建词袋模型，每个用户都会有自己的词袋，里面装满了用户的阅读喜好

决策树

决策树的优点是可解释性好，侯选属性在决策树中可以使用多次

决策树中建树的基本规则：信息增益大的属性应放在上层

当当前数据子集的标签一致、没有更多可用属性以及当前数据子集为空时必须停止树的增长

决策树剪支从叶节点开始

一些基本概念：

• 熵(Entropy)：最大值是1，熵越大表示越难分类，即分类更倾向于靠猜

  ​ $Entropy(S) = -\sum p_ilog(p_i)$

• 信息增益(Information Gain)：表示经过分类后对熵的优化程度，值越大表示效果越好，每次选取信息增益最大的分类属性作为根节点，以此类推。但当Information Gain接近于1时表明该属性将每个样本都分成一个类别，容易出现过拟合。

  ​ Gain(S,A)=Entropy(S)-\sum\frac{\vline S_V\vline}{\vline S\vline}Entropy(S_v)

• 奥卡姆的剃刀：如无必要，勿增实体，常用于两种或两种以上假说的取舍上，如果对于同一现象有两种或多种不同的假说，我们应该采取比较简单或可证伪的那一种，世界客观存在即是建立在客观实践之上，正所谓实践是检验真理的唯一标准

• 过拟合：训练集效果好，可是测试集效果差

ID3决策树

ID3是比较早期的一种决策树算法，分别对样本的所有属性计算信息增益， 找出信息增益最大的属性作为结点，并将该属性从候选属性中去除，以此类推最终得到一颗决策树。

但是ID3的缺点也比较明显，当Information Gain每次都接近于1时，很容易造成过拟合，即某个属性将单个样本分到一个个叶节点，这对新来的样本不能进行有效的预测。因此人们在此基础上进行了改进，出现了C4.5

C4.5决策树

C4.5算法不直接使用信息增益作为划分样本的主要依据，而是提出了另外一个概念————增益率，它在信息增益的基础上加入了惩罚项Penalized

$Gainratio(D,a) = \frac{Gain(D,a)}{IV(a)}$

IV(A)=-\sum_{v=1}^V\frac{\vline D^v\vline}{\vline D\vline}log_2\frac{\vline D^v\vline}{\vline D\vline}

但是同样的这个增益率对可取值数目较少的属性有所偏好，因此C4.5决策树先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择增益率最高的。

CART决策树

CART决策树的全称为Classification and Regression Tree,可以应用于分类和回归。采用基尼系数来划分属性

基尼值

Gini(D)=\sum_{k=1}^{\vline y\vline}\sum_{k'}p_kp_{k'}=1-\sum_{k=1}^{\vline y\vline}p_k^2

基尼系数

GiniIndex (D,a)=\sum_{v=1}^{V}\frac{\vline D^v\vline}{\vline D\vline}Gini(D^v)

因此在候选属性中选择基尼系数最小的属性作为最优划分属性。

剪支

树不能太复杂了，会过学习，当然也不能太简单了，否则不足以描述数据的分布

决策树数据集三个部分：训练集、训练集、验证集(validation set)

剪一点看一点盯着验证集的误差，在拐点的地方收手，不能再减了

连续型属性（Continuous Attributes）

取阈值进行离散化，阈值一般都出现在结果发生变化的地方

如何取阈值，还要用信息增益评估

扩展阅读https://blog.csdn.net/jiaoyangwm/article/details/79525237

神经网络

课件下载

感知机

无法解决线性不可分问题

梯度下降（Gradient Descent）

误差沿着每次梯度的方向移动，从而不断调整权重大小，最终能找到解决问题的最佳权重组合

图中学习率$\eta$限制权重调整的快慢，通常取0.001。$t_d$表期望输出，$O_d$表示实际输出。$E(w)$中的$\frac{1}{2}$则是为了便于平方求导消掉。$\Delta W_i<0$则是由于要减小误差，要使$w_i$不断向误差减小的方向调整

Delta Rule公式

$\Delta W_i = \eta \sum_{d\in D}(t_d - o_d)x_{id}$

当期望输出$t_d=1$时，假设$o_d$没有那么大，那么$t_d-o_d>0$，那么$\Delta W_i$和$x_{id}$同号，这意味着当输入一个正数$x$时，权重会增加，进而增大输出，进而使实际输出$o_d$接近$t_d$

batch learning

在batch learning模式下，权重调整出现在学习一批样本之后，即将每个样本的$\Delta w_i$累加起来，最终再修改$w_i$

stochastic learning

知错就改，每个样本都会更新$w_i$

多层感知机

可以解决线性不可分问题，如XOR，原理是将原始问题在隐含层映射成线性可分问题

Sigmoid函数

BP反向传播

对输出层权重的调整

BP算法在误差对输入求偏导的过程同感知机基本一致，唯一不同的是不在假设输出等于输入，而是更换了激活函数sigmoid。由于隐含层不知道期望输出$t_j$因此不能直接套。

输入对隐含层的误差分析

采用反向传播的方式，从输出层倒着向输入层过过渡

从图中可以看到，隐含层的第$j$个神经元的权重修改量$\Delta w_{ji}$是由它指向的各个输出的权重加权和

延伸

BP算法是一种更新权重的方法，容易掉到局部最优点，解决方案从不同的起始点出发。

在权重更新公式中引入冲量有助于摆脱平缓区域

Elman Network：第T时刻网络的输出取决于当前的网络输入和第T-1时刻网络的内部状态

Hopfield Network：在一定程度上模拟人脑的联想记忆功能，是基于内容的检索，含噪声的模式识别

支持向量机

资源下载

线性SVM

线性分类器

支持向量(support vector):确定了分界面可以平移范围的数据点，margin越大容错能力越强

超平面$w*x+b=0$的margin大小为\frac{2}{\vline w\vline}

Soft Margin:有些点$wx+b\not\geq1$，即噪声点使得无法优化margin，于是放宽条件，在求解时加入了惩罚量$\varepsilon$

但在实际推倒之后发现目标函数(objective function)并没有发生很大变化。

非线性SVM

映射到feature space，高维空间得特点是容易分类，可是问题在于计算量很大

kernel trick：利用向量的特性，将高维空间得计算与低维空间得计算等价，巧妙地绕开了高维空间的计算

String Kernel：专门处理字符串的和函数

发展过程

• VC Dimension

一个分类模型的Capacity是指不论怎么分配标签，都能将多少个点分开，也就是VC Dimension

拓展

聚类分析

一个好的聚类算法能够处理非球形的数据分布、能够处理噪点和离群点、对样本输入序列不敏感、对海量数据的可扩展性

分割聚类(Partitioning Methods)

K-means

Sequential Leader Cluster:处理流数据，迭代一次，不需要初始k

层次聚类(Hierarchial Methods)

EM算法：Model Para和latent Para，迭代收敛求模型参数

Density Based Methods

DBSCAN

Hierarchical Clustering

Agglomerative Methods

推荐算法

PageRank：在Googlez中用的比较多，评价网页重要性的指标

协同过滤(Collaborative Filtering)

Memory-Based CF：求不同用户或者商品的相似性来预测分数

Model-Based CF：将问题转化为分类问题，例如Naive classifier

三个经常遇到的问题

• Gray Shape：兴趣跟别人不一样，找不到类似的参考
• Shilling Attack：恶意好评或者坏评，水军
• Cold start：一个新用户或者新商品往往还没有数据难以打分

求不同用户的相关性系数，求出用户对某商品的评分，进而进行适当推荐

也可以从不同的商品的相关性考虑，进而得到不同商品之间的关系

TF-IDF的机理

集成学习

集成学习是按照一定策略的将不同的模型组合到一起，从而能更好的解决机器学习问题。

集成学习是一类算法的统称，包含Bagging和Boosting，这两类各自又包含了很多的算法。

集成学习主要解决两个问题：

1. 单个模型效果不佳
2. 解决多个模型的Model Selection问题

集成学习在机器学习中的位置

Divide and Conquer

集成学习可以将复杂问题简化为多个简单分类问题，来求的近似解，即分而治之。

Bagging

Majority Voting：统计不同分类器的投票结果，选出票数最多的结果作为最终answer

Weighted Majority Voting：按照权重投票，不同的分类器的效果不一样，选择加权最大的类别作为answer

Diversity：Bagging的前提是各个分类器都不同，不同主要包含三个方面

• 不同的训练算法：SVM、LinearRegression、DeepLearning等等

• 不同的训练过程：1.不同的初始参数 2.不同的训练集 3.不同的Feature Selection

Bootstrap Samples：随机抽样，有放回的随机抽取

Bagging的思想：Bootstrap Aggregation，对不同的分类器进行Majority Voting

Ramdom Forest

随机森林算法是Bagging的一种，这个森林是由多颗决策树构成的，并且这些决策树互不相同。为了保证生成不同的决策树，随机森林算法进行了以下的处理

• Bootstrap Samples：随机抽样，选取一部分数据集
• Ramdom Feature Selection：随机选区一定数量的特征

因此随机森林的优点也很明显

• 随机森林的Cross-Validation不再是传统的divide，而是将随机抽样中一次都没有被选中的样本Out of Bag（大概1/3）作为测试集
• 随机森林巧妙地化解了特征选择问题、过拟合问题
• 随机森林支持分类和回归问题，只有少量的参数，却有很高的Accuracy

Boosting

Stacking：bagging升级版，其工作过程如下图所示，在原有基础分类器上增加了权重，这些权重通过训练器C的训练进行调节，最终利用权重和来决策最终结果。

Boosting思想：串行训练分类器，对样本引入了权重。当前面的分类器总是将一个样本分错的时候，其权重就会越来越大，那么最新的分类器总是着重训练这些权重较大的样本，从而提高算法的accuracy。下面是boosting的一些特点

• 分类器串行生成
• 集中训练权重较大的数据点
• 输出结合权重进行投票
• 可以通过多个弱分类器（accuracy>50%）来训练出强分类器

boosting算法流程

AdaBoost

数据挖掘十大算法之一，运用了boosting的思想，每次分类后对样本权重进行调节，输出不同准确率加权和。
如下如是一个Demo演示训练过程，第一个分类器分出了两个，分错了四个，那么下一次就会在第一个分错的基础上进行二次分类，以此类推，最终得到黑色的不规则图形，完美的将数据分开。可以看出多个弱分类器是完全可以生成一个强分类器的。

公式推导过程：详见集成学习

优点：

• 简单容易使用
• 几乎没有需要调整的参数
• 训练集可证明误差边界
• 不会出现过拟合

缺点：

• 每次选则的不是最优的$\alpha$ ，只是采用贪心策略取的近似值
• 不能根据测试样本进行自适应调整
• 对噪声比较敏感

固定权重和动态权重：

在adaboost中各个样本的权重都是固定的，不会根据输入发生变化，但是实际上有些模型对样本的估计结果并不好。在ReginBoost中引入了动态权重，解决了这个问题

ReginBoost

在基础分类器之上添加置信度的预测器，该置信度预测器实际上采用了k近邻的方式评估置信度

对比RegionBoost和Adaboost的训练效果，如下图，左侧为训练误差，右侧为测试误差

很明显可以看到尽管Adaboost的训练误差比较小，最后甚至趋于0，但是其测试误差很大，也就是说它预测的并不可靠。而相反ReginBoost虽然训练误差最终趋于平缓，但是其测试误差越来越小，这才是我们需要的模型。

进化计算

全局优化

旅行商问题（tsp）

假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

关键概念

• 基于人口的随机优化算法
• 内在并行，不容易陷入局部最优点

经典算法

• GA：Genetic Algorithm

• GP：Genetic Proramming

• ES：Evolution Strategies

• EP：Evoluntionary Programming

• EDA：Estimation of Distribution Algorithm

• PSO：Particle Swarm Optimization

• ACO：Ant Colony Optimization

• DE：Differencial Evoluntion

并行搜索：

遗传算法(Genetic Algorithms)

每个问题的解决方案表示为染色体向量，初始随机生成多个染色体，然后一代代发生进化，基于自然进化的方式一代代进行改良。主要包含以下三方面的内容

1. 表示

   • Individual（chromesome）
   • Population：a set of individuals
   • Offspring：通过基因生成器生成的individuals
   • Encoding：Binary Or Gray

2. 生成基因

   • 杂交：在两个染色体之间交换遗传物质
   • 变异：随机修改选定位置的基因值

3. 选择

   • Roulette Wheel Selection：轮盘选择法，就是通过丢飞镖选择性状，值越大概率越大，缺点是没法处理负值或有单个值特别高就会漏选较好的变异体
   • Rank Selection：利用排名减小值的差距
   • Tournament Selection：两个或多个人相互PK，人数越多presure越大
   • Elitism Selection：精英选择，后代不一定比双亲好，可能由于变异或者杂交损失一些染色体，复制最好的性状到下一代。
   • Offspring Selection：用最老的染色体代替子孙染色体

选择VS杂交VS变异

• 选择
  • 可视为搜索资源分配的调节机制
  • 进化初期Selection Pressure过大易导致不成熟收敛
• 杂交
  • 从好的个体基因生成更好的个体
  • 是GA的主要搜索方式
  • 体现出对现有搜索结果的精细利用（Exploitation）
  • 不影响基因的多样性
• 变异
  • 增加基因多样性
  • 体现出对解空间的各个区域的探索（Exploration）
  • 通常独立作用于个体的某一位基因

上述过程总的来说是Exploration vs. Exploitation，前者意为探险，即探索不同的区域，主要从基因多样性角度考虑，后者Exploitation则指在某个区域进行更深层次的勘探（Choice）

GA 框架

遗传编程(Genetic Programming)

可进化硬件(Evolvable Things)