浙江大学计算机学院研究生课程《数据挖掘》考试重点内容的速成。

Data

关键的统计信息

  • Mean 平均值，进一步有加权平均值
  • Median 中位数
  • Mode 众数
  • Quartiles，Q1是排在第25%的数据，Q3是数据中排在75%处的数据
  • Inter-quartile range IQR=Q3-Q1
  • Variance 方差, Standard Deviation标准差

箱线图Boxplot

根据数据的五个特征：最小值，Q1，中位数，Q3和最大值进行作图，中间三个画成一个矩形区域，但是箱线图有一些缺点，比如下面这样两组不同的数据分布，他们的箱线图是一样的：

image-20221102224457863

Data Similarity and Dissimilarity

枚举特征

衡量枚举特征的相似度，可以直接计算数据中相同的属性个数，再除以属性值就可以。对于一些不是二元属性的枚举属性，可以讲数据转换成多个二元属性(Yes/No)，

数值特征

闵可夫斯基距离的计算方式如下：

  • 曼哈顿距离：h=1
  • 欧几里得距离：h=2
  • supremum距离：h=无穷大，计算的结果是里面最大的一个

Cosine相似度的计算公式：

Data Preprocessing

Major Task

数据预处理中的四个主要任务

  • Data Cleaning
  • Data Integration
  • Data Reduction
  • Data Transformation and Data discretization

Data Cleaning

主要是处理数据中的不完整输出、噪声数据、不一致数据和数据中的伪装缺失数据。如何处理缺失数据？可以用其他数据该属性的平均值作为缺失值的补充，可以设定一个新的unknown属性(对于一些nominal属性比如颜色)

可以用贝叶斯方法或者决策树来预测数据中缺失的值。

对于噪声数据可以通过binning、regression、clustering和人类验证等方式来进行清洗

Data Integration

卡方检验：检测变量的相关性，结果越大越好，计算公式为： 皮尔逊系数，计算变量之间的相关性，计算公式是： 如果r>0说明XY正相关，如果r<0说明XY负相关，r=0说明XY不相关

Data Reduction

Data Reduction的一类主要的做法是降维，常见的降维算法有这样几类：

  • 无监督的有PCA，ICA和CCA
  • 有监督的有LDA(线性判别分析)
  • 半监督的有SDA

其实数据降维的做法按照目的可以分成两类，一类是特征的选择，就是从给定的特征中选择一部分好的特征，一类是特征的抽取，就是从给定的特征中通过组合重新得到一些新的特征。

Data Reduction的另一类方法是数量规约，就是用较小的数据表示形式来替换原本的数据，比如说线性回归，聚类和采样。

还有一类方法是数据压缩，这个就没啥意思了

Data Transformation

数据转换主要有这样几种方法：

  • 平滑化Smoothing，从数据中移除噪音
  • 属性构建，从已有的属性中构建新的属性
  • 聚合
  • 标准化，将数据压缩到一个更小的范围里
  • 离散化，让连续的数据变成离散形式的数据

常见的数据标准化操作有这样几种：

  • min-max标准化，将数据按照最大值和最小值进行缩放
  • Z-score标准化，计算数据的平均值和标准差，然后进行标准化，实际上是把数据标准化成正态分布里采样的数据
  • Decimal Scaling，实际上就是同时约掉共同的0

Frequent Patterns

频繁项挖掘指的是挖掘出数据集中频繁出现的模式和组合，常见的应用场景就是超市购买商品的时候，我们可以根据顾客的消费记录来挖掘出一些比较普遍的客户喜好。我们可以把每一条购物数据看成一个商品集X，我们的目标就是从大量商品集中挖掘出频繁出现的商品组合。

频繁项集和关联规则

对于一个商品集X，它在数据中出现的频率称为absolute support，它在每条记录中出现过的次数(可以包含)称为relative support，如果X的频率不低于一个阈值，就可以认为它是频繁的。

我们可以用规则X->Y来表示X和Y之间的关联规则，我们的目标是需要找到拥有最小的support和最小的confidence的所有规则X->Y

  • support指的是一条记录同时包含XY的概率
  • confidence指的是一条有X的记录包含Y的条件概率

Apriori算法

频繁项集拥有一个被称为向下闭包的性质，意思就是，如果一个商品集是频繁项集，那么它的任何一个子集都是频繁项集合。

Apriori算法的原则就是，如果有任何一个商品集合是不频繁的，那么它的超集不应该是频繁项集，在频繁项挖掘的过程中就被剪枝了。Apriori算法的主要步骤有这样几步：

  • 首先扫描数据集，获得所有频繁的1项集
  • 通过长度为K的频繁项集生成长度为K+1的频繁项候选集(candidates)
  • 通过数据集来验证这些候选集是不是满足条件的，验证的主要依据包括min_support和min_confidence
  • 当没有频繁项候选集产生的时候，算法就结束了

Apriori算法有很多的改进，主要的改进方向是减少扫描数据集的次数和生成的候选集数量，来提高算法的效率

FPgrowth算法

太麻烦了，考试大概也不考，就不看了先。

Classification

机器学习任务可以分成监督学习和无监督学习两类，监督学习的目标实际上就是预测数据的某些属性，预测离散化的属性就是分类任务，预测数值信息就是回归任务。

分类任务可以分成两个步骤，一个是模型的构建，包括模型的设计和训练，第二个是模型的使用，就是用模型进行分类。下面介绍了几种经典的分类模型。

决策树

决策树是一种用树的形式来完成分类任务的算法，决策树是一种贪心算法，这棵树是通过自顶向下的分治法构建的，每一层都会选出一个属性，并根据这个属性来划分数据，当叶节点上的所有数据都属于同一个类别的时候，划分就停止了，所有的数据被分到了某一个具体的叶节点上，在推理阶段，就从树的根节点开始遍历，找到合适的叶子之后，用叶子里数据的标签作为推理的结果。

在这个过程中，最关键的实际上就是在决策树的每一层，根据一定的标准将数据进行合适的划分，常见的划分标准需要选择出最有区分度的属性，用这个属性作为当前节点划分的依据。

常见的划分依据有：

  • 信息熵，计算方式是 这里的是X的每一种可能的类别，信息熵越大代表信息的不确定性越高。一般要选信息熵低的属性。
  • 条件熵，计算方式是
  • 信息增益，计算方式是，其中 是D的信息熵，并且 ，这就是经典的ID3算法使用的分类标准，该算法的具体步骤可以描述为：
    • 每次选择信息增益最高的属性A作为当前节点的划分依据
    • 首先计算当前节点中全部数据D的信息熵，然后计算使用A将D分成v个部分所需要的信息，即，二者相减就可以得到使用A属性作为划分所得到的信息增益
    • 具体的做一道题就大概能了解了
    • 信息增益会导致模型更偏向于优先选择出现取值比较多的属性，信息增益率指标解决了这一问题，对应的决策树算法叫做C4.5
  • 除此之外，还有各种各样神奇的指标

决策树很容易在训练数据集上过拟合，可以用剪枝的方式来缓解这一问题，常见的剪枝方法有prepruning和postpruning两大类

贝叶斯方法

全概率公式： 贝叶斯公式实际上是在全概率公式的基础上推导得到的，它的具体形式是： 这里面X代表的是数据，而H代表了数据对应的类别，是类别H的先验概率，被叫做似然，就是所有标签为H的数据里，X出现的概率，而是数据X本身被观测到的概率，最终计算的结果就是后验概率。

用贝叶斯定理进行推断的时候最麻烦的事情在于如何计算似然，因为数据X的形式可能千奇百怪，一个很简单的做法是，假设X的各个属性之间都是互相独立的，这样一来就有： 似然就变得容易计算很多，如果不是枚举变量而是连续值，那么就可以假设服从高斯分布，然后计算其均值和方差，通过建立高斯分布模型来计算其似然。

这就是朴素贝叶斯算法，但是它要求计算过程中条件概率必须要是非0的，否则计算结果就会变成0，这里可以用拉普拉斯修正给每个类别添加一个实例来保证使用朴素贝叶斯进行计算的时候，条件概率都不会归零。

分类模型的选择和评估

分类任务模型的选择和评估主要依靠混淆矩阵，以二分类任务为例，根据数据原本的类别和分类得到的类别，可以将结果分成四类：

  • True Positive, TP正样本分类为正
  • False Negative, FN正样本分类为负
  • False Positive, FP负样本分类为正
  • True Negative, TN负样本分类为负

几个常见的分类指标的计算方式为：

  • 正确率= (TP+TN) / All
  • 错误率=1-正确率
  • 灵敏度 Sensitivity, TP的识别率=TP/(TP+FN)只考虑正样本数据的结果，实际上等于Recall
  • 特效度 Specificity, TN的识别率=TN/(TN+FP)只考虑负样本数据的结果
  • Precision 精确率 = TP / (TP+FP) 意思是模型分类成正样本的数据中原本就是正样本数据的占比
  • Recall 召回率， = TP / (TP + FN) 意思是模型对正样本的分类结果
  • F1-score，综合考虑Precision和Recall

Clustering

聚类是一种无监督学习的算法，目标是将没有标签的数据分成若干个簇，并且让簇内的数据尽可能相似，而让簇间的数据尽可能不相似(这也是聚类算法设计的基本原则)。聚类可以用于数据分析以及作为其他算法的预处理步骤。

聚类算法主要可以分成这样几类：

  • Partition方法，将数据进行划分并用某些指标来评估，然后学习到好的聚类
  • Hierachical方法，将数据进行层级化的分解，逐步学习到好的聚类
  • Density-based方法，基于数据的connectivity和density进行聚类
  • Grid-based方法，基于多级别的网格结构进行数据聚类

K-Means算法

K-Means算法是一类基于partition的算法，这类算法的主要特点是将数据集划分成K个簇，并且让簇类的平方距离最小化，总的学习目标可以表示为： 其中是划分的簇，而是每个簇的中心节点。K-Means算法中，我们用来表示一条数据是否属于第k个簇，然后用每个簇中所有数据的平均值来表示这个节点的中心，K-Means算法的总体流程可以概括成以下四个步骤：

  1. 将数据集随机划分到K个非空簇中
  2. 计算每个簇中的中心点(也叫做seed point)
  3. 将每个点重新分配到离自己最近的那个中心点对应的簇中
  4. 返回第2步，直到结果不再发生变化

看上去其实是一个很简单的算法，实际上K-Means算法是用EM算法进行求解的。当然K-Means算法是比较早期的聚类算法，它也存在一些问题，比如容易获得局部最优结果。对此，也有很多方法提出了对应的改进。

谱聚类

听说不考，先不学了。

Linear Regression