机器学习与计算智能Ι期末复习

frequent

a

关联规则：发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式。

可信度（最小可信度）：购买~的情况下购买的可能性，条件概率。

支持度（最小支持度）：同时购买~和的可能性。

频度：支持度的分子（大家的分母都相同）

频繁项目集：满足最小支持度的项目集。（频度大于最小频度）

公理：如果一个项目集是频繁的，那么的任意子集也是频繁的。

最大频繁集：任何超集都不是频繁集的集合。

Apriori算法：

第一次扫描数据，找出频度大于最小支持度的项目，组成集合。
第二次扫描数据，由规则生成，找出中频度大于最小支持度的候选对，组成集合。
第三次扫描数据，由规则生成，找出中频度大于最小支持度的候选三元组，组成集合。
一直进行到集合为空时为止，其中即为大小为的频繁项目集。

对于每个频繁项目集，对于的每个非空子集，

如果：的支持度/的支持度最小可信度

则有：关联规则

b

序列：不同项目集的有序排列

序列的包含：两个序列对应位置的项目集呈包含关系。若两个序列长度不同，那也应保证顺序性。

给定一个序列集合，如果序列不包含于任何一个其它的序列中，则称是最大的。

频繁序列：若一条序列在序列数据集中作为子序列的频率，则称序列是序列数据集的频繁序对。

支持数：序列数据库中包含序列的序列个数。

GSP算法：

预处理交易数据库：将交易数据库按照顾客号和交易时间进行排序
计算所有的频繁项目集：找到频度大于最小频度的频繁项集（可用Apriori算法，频度定义是包含它的购物序列的个数）
数据映射和转换：将频繁项集映射到一个整数集合
计算所有的频繁序列
计算最大的频繁序列

c

~~Apriori-based Sub-Graph Mining~~

d

FP-Growth算法：

第一次扫描数据库，找出频繁的1项目集，并将频繁项目按频度降序排列。
第二次扫描数据库，按频度从大到小构造fp-tree，按频度从小到大挖掘该树。

(数据库大时，fp-tree可能在内存中装不下，需要采取partition方法。)

构造fp-tree：

扫描数据库一遍，找到所有的频繁1的项目集
将频繁项目按照降序排列，生成一个f-list
再扫描数据库一遍，共享前缀的方式来构造条件模式基

挖掘fp-tree：

按照深度优先顺序生成投影数据库
每个需要生成投影的数据库集合都是频繁集，不频繁的在构造fp-tree时就过滤掉了
递归结束后，把所有的频繁集合并就是最后的所有频繁集

~~PrefixSpan算法~~

e

~~Mining various kinds of association rules~~

classification

a

决策树

叶子节点对应决策结果，其他节点对应一个属性测试
每个节点包含的样本集合根据属性测试的结果被划分到子节点中
根节点包含全部样本集
最大高度 = 决策属性的个数
树越矮越好
要把重要的好的属性放在树根
决策树建树算法就是选择树根的过程

决策树分类

开始时，所有的训练集样本都在树根
属性都是可分类的属性（如果是连续值，先要对其进行离散化）
停止划分的条件
1. 某个节点上的所有样本都属于相同类别
2. 所有属性都用到了——采用多数有效法对叶子结点分类
3. 没有样本了

选择属性作为树根：信息增益最大的属性被认为是最好的树根

计算信息增益

首先计算不考虑任何输入变量情况下，要确认样本集中任一样本所属类别需要的熵。
$表示中属于响应变量类别的样本个数$
计算引入每个输入变量后，要确定样本集中任一样本所属类别需要的熵
$每个划分子集占的比例划分子集在响应变量上的信息熵$
计算二者的差，，为变量X所能带来的信息增益

Overfitting：建树完全服从于训练集太循规蹈矩，可以用剪枝的方式来去掉一些特殊的、出现次数很少、不具有代表性的分支

先剪：建树过程中修剪

训练时间降低，测试时间降低
过拟合风险降低，欠拟合风险增加

后剪：整个树建后修剪

训练时间增加，测试时间降低
过拟合风险降低，欠拟合风险基本不变

泛化能力：后剪通常由于前剪

信息增益的缺点：偏向取值较多的特征

为了解决这个问题，改用增益比度量
$信息增益划分后总的信息熵$

b

函数逼近

回归：映射到数值型变量

线性回归： $Ŷ$
非线性回归： $Ŷ$
分段线性模型：把简单模型分段组合在一起构建起来的相对复杂的模型。
评分函数：误差平方和

分类：映射到范畴型变量

判别模型、概率模型
评分函数：误分类率

MSE：最小二乘

lasso回归：标准线性回归 + L1正则化

岭回归：标准线性回归 + L2正则化

L1会比L2让线性回归的权重更加稀疏，L1可以进行feature selection

c

贝叶斯分类

拼写纠正：用户输入，推测他想输入

由于是固定的，只需要考虑和

是先验概率，即猜测单词的出现概率

是似然性，即想打却打成的概率

最后取乘积最大的得到最可靠的猜测

垃圾邮件过滤器：对于邮件，推测他是垃圾邮件还是正常邮件

和这两个先验概率就是邮件库里垃圾邮件和正常邮件的比例

假设邮件中有个单词，不好求

朴素贝叶斯：条件独立假设，认为个单词之间是完全条件无关的

则

朴素贝叶斯分类器：

将未知样本分配给类，当且仅当。

最大化

其中可视为常数，则只需要最大化

就是响应变量每种类别的占比

由朴素贝叶斯假设，

对数似然，的极大似然估计为

若是分类属性，则是每种类别的占比

若是连续值属性，则是高斯分布的密度函数（在该处的概率）

优点：易于实现，多数情况下结果较满意
缺点：实际上，属性间存在依赖，假设独立会丢失准确性

拉普拉斯修正：

贝叶斯信念网络

有向图->贝叶斯网络
无向图->马尔科夫网

d

支持向量机（SVM）

目标：

e

神经网络

拓扑结构、连接方式、学习规则

通过迭代算法，对权值逐步修改优化

后向传播算法：

迭代地处理一组训练样本，将每个样本的网络预测与实际的类标号比较
每次迭代后，修改权值，使得网络预测和实际类之间的均方差最小
由输出层，经由每个隐藏层，到第一个隐藏层
算法终止条件：训练集中被正确分类的样本达到一定的比例，或者权系数趋近稳定

1、初始化权值：

权重通常设置为很小的随机数

每个单元都有一个偏置，也初始化为小随机数

2、向前传播输入：

输入层：输出输入样本的属性，

隐藏层和输出层：

输入前一层的输出的线性组合，
输出

3、向后传播误差：

计算各层每个单元的误差

输出层：，是单元的实际输出，是的真正输出。
隐藏单元层：，是由到下一层中单元的连接的权重，是单元的误差。

更新权和偏差

权：，，是学习率
偏置：，，是学习率

反向传播

利用梯度下降法优化损失函数，迭代修改参数

损失函数：预测结果和实际结果间的差异。预测结果越好，loss越小。

梯度下降（）：

对于每一个样本，进行一个网络权重的更新
更新的方向：使loss下降最快的方向->梯度的反方向->loss对权重求导
更新的步长：学习率->超参数

批量梯度下降法：更新参数时使用所有样本

随机梯度下降法：更新参数时仅选取一个样本

小批量梯度下降法：中庸的做法，Mini-batch，更新参数时选择10个样本

卷积神经网络CNN:

由卷积层、池化层、全连接层组成。卷积层与池化层配合，组成多个卷积组，逐层提取特征，最终通过若干个全连接层完成分类。
通过卷积来模拟特征区分，并且通过卷积的权值共享及池化，来降低网络参数的数量级，最后通过传统神经网络完成分类等任务。

卷积Convolution

卷积运算：用一个固定大小的卷积核扫过输入图，将输入特征图上对应位置和卷积核上进行内积运算

理解：使用一个过滤器（卷积核）来过滤图像的各个小区域，从而得到这些小区域的特征值，每个卷积核代表了一种图像模式。

卷积核大小kernel size：通常是奇数，越大效果越好，但参数个数会平方级增加
填充padding：不减小feature map。周边补0，向外对称
步长stride：降低feature maps的尺寸

池化Pooling

为了降低数据维度，进行采样

每一个区域选择一个值代表这个区域的特征：最大值采样、平均值采样

Dropout：随机去掉全连接层中的一些神经元，防止过拟合

Batch normalization：对输入数据进行减均值、除方差操作，加快训练速度

梯度消失或者爆炸：

求导算梯度时，前面层的梯度是来自后面层的项的乘积。

如果各项的值小于1，则在后向传播时会出现梯度随着层数减少越来越小的情况（消失）。

如果各项的值大于1，则会出现随着层数减少梯度越来越大的现象（爆炸）

f

k-NN分类

给定空间中的一点，从数据库中找出离q最近的点

每个训练样本都看作维空间中的一个点

给定未知类别的查询点，首先找到该点的个近邻，将这k个近邻按照类标号进行分组，查询点最终被分到组员最多的那个组。

准确性分析：

保持：给定数据分配到训练集，分配到测试集

-交叉确认：给定数据划分为个互不相交的子集~，每次选择个子集做训练集，个子集做测试集，准确率是次迭代中分类结果正确的样本样本总数

准确率P： $预测值为正值且真实值也为正值预测值为正值$

召回率R： $真实值为正值且预测值也为正值真实值为正值$

clustering

a

数据标准化：减平均值，除平均绝对偏差

距离：明考斯基距离（q=1：曼哈顿距离；q=2：欧几里得距离）

二元变量

对称：
不对称：（两个都取1的情况比两个都取0的情况更有意义）

标称变量

，是匹配的数目，是全部变量的数目

序数型变量

一共个有序的状态，将第个对象的值代替为

再将值域映射到上，，用代替第个对象的值

比例标度变量

聚类算法

基于划分的方法
- K-Means
- 将数据划分为个组
- 每个组至少包含一个对象
- 每个对象必须属于且只属于一个组
基于层次的方法
- 层次聚类树：不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。
- 聚合层次聚类：自下而上合并（两两合并）
- 划分层次聚类：自上而下分裂（一分为二）
- 弱点：选取的合并或分裂点
基于密度的方法
- 基于距离的划分只能发现凸状的蔟
- DBSCAN和OPTICS
- 临近区域的密度（数据点数目）大于某个阈值，就继续聚类；对给定类中的每个数据点，在一个给定范围的区域中必须包含至少某个数目的点。
- 过滤噪声，可以发现任意形状的蔟
基于方格的方法
- 把多维数据空间划分成一定数目的单元，然后在这种数据结构上进行聚类操作。
- 该类方法的特点是它的处理速度，其速度与数据对象的个数无关，而依赖于数据空间中每个维上单元的个数。
基于模型的方法
- 神经网络
- 统计

K-Means

给K个cluster选择最初的中心点，称为K个Means。
计算每个对象和每个中心点之间的距离。
把每个对象分配给距它最近的中心点做属的cluster。
重新计算每个cluster的中心点。
重复2，3，4步，直到算法收敛。

每次迭代：

选择的K个cluster的中心
计算每个点到每个中心的距离
将每个点分配给距离它最近的中心

优点：对大数据量具有可扩充性和高效率；局部最优化

缺点：K必须事先确定；初始K个中心点必须事先确定；不能处理噪声；不能处理凹形分布的数据

b

高斯混合模型GMM

GMM和k-Means的区别

k-Means聚类的最终结果是每个数据对象被指派到了某个蔟
GMM在算法结束时，除了将数据对象指派给某个蔟外，还给出了对象属于该蔟的概率（学习出一些概率密度函数来）

GMM假设数据服从高斯混合分布，数据可以看作是从k个高斯分布中生成出来的。

GMM的概率密度：

是一个数据对象，是由第个组件生成的概率，第个组件的概率密度函数，和是第个高斯分布的中心和协方差矩阵

GMM采用似然函数作为评分函数：

表示数据集D中数据对象的个数，表示采用GMM生成数据对象的概率。

在对数函数里面又有求和的操作，所以没有办法直接用求导后解方程的方式求得最大值。

为了解决这个问题，采取类似于k-Means的迭代求精的方法。

迭代步骤：

估计属于的概率

第一次迭代的、和都采用初始值
更新、和
将参数带入似然函数，如果值发生了变化，则重复迭代上面两步；否则认为值已收敛，停止迭代，算法结束。

EM(Expectation-Maximization)算法

最大似然

引入隐含变量，维向量，如果第个被选中了，那么将第个元素置，其余全置

Expectation步: 对应于求关于后验概率的期望，即

Maximization步: 则对应于接下来用最大似然的方法估计相关的参数亦即、和

c

话题检测

给定一个参数和个文档（文档、文档、……、文档）

首先找出个话题（话题、话题、…、话题）

然后计算出每篇文档对每个话题的覆盖概率（文档对话题的覆盖程度用概率值来表示，同一文档对不同话题的覆盖概率加起来的和为）

选择话题：

用作为评分函数
$某个词在文章中的出现次数文章的总词数语料库的文档总数包含该词的文章数$
单文档单话题：

停用词影响很大，使用2个模型的混合

一个用来生成背景词分布：

一个用来生成有意义的话题：

PLSA

d

DBSCAN方法

邻域：以为圆心，以为半径画圆，圆所在的区域

核心对象：若对象的邻域内至少包含个数据对象

边界对象：非核心对象

直接密度可达：如果是核心对象，在的邻域中，从直接密度可达

密度可达：如果从直接密度可达，则到密度可达

密度可达具有传递性，但不具有对称性

密度相连：存在到和都密度可达，则和密度相连

密度相连具有对称性，不具有传递性

如果一个数据对象和另一个数据对象是密度相连的，则和属于同一个蔟。

如果某个数据对象到任何一个其它数据对象都不密度相连，则认为该数据对象是一个噪音。

从任意一个数据对象开始
- 如果是一个核心对象，则根据输入的两个参数和，通过广度优先搜索提取所有从密度可达的数据对象，将它们标记为当前蔟，并从它们进一步扩展。
- 如果是一个边界对象，则将标记为噪声，再随机选取另外一个数据对象进行处理。
依次进行下去，直到找到一个完整的蔟。
然后再选择一个新的其它数据对象开始扩展，得到下一个蔟，算法一直进行到所有的数据对象都被标记过为止。

优点

不需要提前确定蔟数
速度快
对噪声不敏感
能发现任意形状的蔟

缺点

参数和比较难确定
密度不均匀时，用相同的参数可能得不到好的结果
可能会产生链条现象
R树在高维空间不够有效，导致性能下降

OPTICS方法

解决DBSCAN方法密度不均匀时容易出现聚类差的缺点

为每个数据对象计算出一个顺序值，位于同一个蔟的数据对象具有相近的顺序值。

核心距离：使得能成为核心对象的最小半径（满足邻域内刚好有个对象的）（不是核心对象的没有核心距离）

可达距离：的核心距离和与的欧几里得距离中的较大值

离很近的对象，二者之间的可达距离用的核心距离表示

计算每个对象的核心距离和可达距离，生成蔟序
- 如果是一个核心对象，则根据输入的两个参数和，通过广度优先搜索提取所有从直接密度可达的数据对象，计算它们的核心距离和可达距离，并放入队列
- 从中选取一个最小可达距离的对象，对其进行扩展。（对扩展时，需要更新中数据对象的可达距离进行更新，保证储存的是到最近的核心对象的距离）
  - 如果是核心对象，则计算直接密度可达的对象的核心距离和可达距离
  - 如果不是，则什么都不做
用蔟序信息进行聚类
- 如果的可达距离小于等于，直接将标记为当前蔟
- 如果的可达距离大于，则说明在之前处理的对象没有一个到是可达的
  - 如果的核心距离小于，说明是一个核心对象，创建一个新的蔟
  - 否则标记为噪声

评价指标

a：在C中和C*中都属于相同聚类的样本对个数

b：在C中属于相同聚类、但在C*中属于不同聚类的样本对个数

c：在C中属于不同聚类、但在C*中属于相同聚类的样本对个数

d：在C中和C*中都属于不同聚类的样本对个数

e

基于层次的聚类

不适合非球形或者大小不均匀的蔟结构

层次聚类树，逐步将距离最近的两两合并，或距离最远的一分为二

两蔟间的最小距离是两蔟对象间的最小距离

两蔟间的最大距离是两蔟对象间的最大距离

平均距离是所有两蔟对象间距离的平均值

蔟的半径：蔟中所有对象到中心点距离的平均值

Recommendation Systems

a

基于协同过滤的推荐

用最近邻的用户集合，预测该用户的喜好

计算用户相似度

对物品的打分预测

用户打分的平均值加减邻居的偏见值

计算物品相似度

n个人的评分组成n维向量

向量夹角余弦

改进后类似计算用户相似度

打分不用加平均值，直接计算

问题

数据稀疏：递归协同、图扩展

冷启动

概率模型

基于内容的推荐

物品内容、特征提取、匹配度、用户偏好

不需要借助用户群体信息

推荐太多类似的物品了