DataMining

本文最后更新于 2024年11月18日上午

数据挖掘

前言

学科地位：

主讲教师	学分配额	学科类别
郑智超	3+1	专业课

成绩组成：

理论课		实验课
考勤	5%	考勤	10%
作业 (书面)	20%	作业 (编程)	30%
期末 (闭卷)	75%	大作业	60%

教材情况：

课程名称	选用教材	版次	作者	出版社	ISBN 号
数据挖掘	《数据挖掘：原理与应用》	1	丁兆云，周鋆，杜振国	机械工业出版社	978-7-111-69630-8

为什么要学这门课？

数据量在进入信息化时代后指数级增长，显然这些数据一定具有某种价值。之前看到过这样的说法 “你能想到和做到的，前人都已经想到和做到了”。虽然这样的说法不具有绝对性，但是个人认为对于大多数人都是适用的。也就是说，人类的行为甚至是万物的变迁都是符合统计学规律的，而这些规律都藏在浩瀚的数据之中，因此个人认为这门课对于研究统计学规律会有一些入门的帮助。

会收获什么？

数据预处理的基本策略和一些无监督学习算法。

1 绪论

科学发展范式。实验 (经验) 科学 $\to$ 理论科学 $\to$ 计算科学 $\to$ 数据科学。

属性分类。定性、定量。其中定性属性可以分为三类（二元属性、标称属性、序数属性）；定量属性即数值属性，可以用合适的 统计量 进行描述。

统计量。分中心趋势度量和离散度度：

中心趋势度量。用来描述数据集中心位置的统计量，它反映了数据的平均水平或典型值。例如：
1. 算术平均数（受计算数据的影响大）
2. 调和平均数（特定场景）
3. 中位数（适用于序数申诉信，表示位置信息，不受极差影响）
4. 众数（不受极差影响）
离散度度量。用来描述数据分布的广泛程度，即数据值偏离其中心趋势的程度。例如：
1. 极差（适用于数据极端值较少且分布不复杂的场景）
2. 标准差（解释性比方差更好，反应数据与均值之间的关系，对极端值敏感）
3. 四分位数间距（反应数据内部的离散程度，容易忽略极端数据）

可视化策略。按照数据类型有以下三种策略：

箱型图、五数概括、直方图。有助于可视化单个属性的分布情况
饼图。有助于表示单个属性的数据分布占比情况。
散点图。有助于可视化两个属性的相关关系。

邻近性度量。当我们在对「两个数据对象」进行邻近性度量计算时，是将所有同一个类别的属性联合起来计算的，例如当我们在计算二院属性的相异性或者相似性时，是将所有的二元属性联合起来一起计算的。下面讲一下不同属性类别的邻近性度量方法：

标称属性。我们在实际计算两个对象的标称属性的相似或相异性时，一般为了便于计算，需要进行编码。然后再比较两个数据对象的所有标称属性中相同或相异的编码个数占总标称属性数量的大小。
二元属性。与标称属性类似，相同性的计算就是计算 0,0 和 1,1 的二元属性取值数量；相异性计算是，如果对称属性，则为 1,0 和 0,1 的数量，如果是非对称属性，则为 1,0 或 0,1 的数量。
数值属性。闵可夫斯基距离（h = 1 为曼哈顿距离，h = 2 为欧氏距离，h = $\infty$ 为切比雪夫距离）、余弦距离（偏向于语言上描述两个对象的相似性，并不具备三角不等式关系）。
序数属性。使用排名法对属性的每一个可能的取值进行编码，然后归一化到 $[0,1]$ 范围内，最后就可以使用上面的数值属性的方法进行两个数据对象的邻近性度量。
混合属性。如果出现了不止一种上述类别的属性，可以采用加权平均的方式进行邻近性度量。

2 数据预处理

数据决定上限，模型和算法只是尽可能逼近这个上限，因此数据的质量是核心所在。数据的质量可以被描述为这几个方面：准确性、完整性、一致性、合时性、可信度、解释性。

接下来我们主要介绍数据预处理的几个主要任务，将数据处理成模型可接受的形式并且提升数据的质量。

2.1 数据清理

大约需要处理两类问题：缺失值处理、噪声处理。

关于缺失值处理。

显然我们可以直接删除含有缺失属性的元组。
也可以进行缺失值填充。填充策略比较多，简单点可以用平均数、众数等策略进行填充，也可以用前推法、后推法、插值法、滑窗均值法等策略进行填充，还可以用贝叶斯等概率策略进行填充。

关于噪声处理。

可以用箱型图去掉离群点。
也可以对数据做平滑处理。平滑策略有很多，例如：函数拟合平滑、近邻局部平滑、指数平滑。函数拟合平滑比较显然，就是利用线性回归拟合一个函数即可，下面展开后两者策略的简介：
- 近邻局部平滑（分箱法）。我们将原始数据排序后，通过「等深分箱（按元素数量）」或「等宽分箱（按元素值域）」或「自定义分箱」等策略划分为不同的子集，然后对每一个子集进行平滑处理，子集可以用均值、中位数、边界、窗口均值等策略做平滑处理。
- 指数平滑（递推法）。定义权重参数 $\alpha \in (0,1)$ ，原始数据记作 $x_1,x_2,...,x_n$ ，平滑后数据记作 $s_1,s_2,...,s_n$ ，则有：
  $s_i = \alpha x_i + (1 - \alpha) s_{i-1}$

2.2 数据集成

借鉴数据库的逻辑，将多源数据通过外键集成到一个完整的数据集合中。可以理解为升维。

2.3 数据规约

所谓数据规约就是降低数据集的规模。大约有三种策略分别为：降维、降数据、数据压缩。其中：

降维可以采用对应的机器学习策略。参考之前的笔记 https://blog.dwj601.cn/GPA/4th-term/MachineLearning/#第10章-降维与度量学习
降数据可以采用简单随机抽样或者分层抽样。
数据压缩就是从编码角度进行数据编码和数据压缩。

2.4 数据规范化 | 离散化

数据规范化就是所谓的「归一化」方法，从而避免不同属性的量纲之间的影响。常用的有：

最大最小规范化。规范公式为 $\displaystyle x'= \frac{x - x_{\min}}{x_{\max} - x_{\min}}(r - l) + l$ 。缺点是容易受离群点的影响，且测试数据可能会超过阈值 $[l,r]$ 。
均值标准差规范化。规范公式为 $\displaystyle x'=\frac{x - \overline{x}}{\sigma_x}$ 。缺点是计算量相对更大。
零均值规范化。规范公式为 $\displaystyle x'=\frac{x}{10^j}$ ，其中 $j$ 为使得 $\displaystyle \frac{\max{|x|}}{10^j}<1$ 的最小取值。

数据离散化就是对连续属性值的属性进行离散化操作。从而适用于只能处理离散属性的场景。

3 关联分析

本章我们学习一种无监督学习方法：关联分析。

3.1 基本概念

关联向量数据集

基本的定义。首先定义每一列的字段为项 Item，项的集合就叫做项集 Itemset。每一行表示一个事物 tuple，显然事物是一个项集的实例。如果我们定义项集 $X$ ，所有事物中包含 $X$ 的个数就叫做 $X$ 的 支持度 $\sigma (X)$ ，若 $\sigma (X)$ 超过了某个阈值，则称 $X$ 为 频繁项集。

规则的定义。为了知道两个不相交的项集 $X,Y\quad(X \bigcup Y=\empty)$ 之间的关联性，引入 规则 $X\to Y$ 的支持度 $s$ 和置信度 $c$ 的概念。其中 $s(X\to Y)=\frac{\sigma(X\bigcup Y)}{N},\quad c(X\to Y)=\frac{\sigma(X\bigcup Y)}{\sigma(X)}$ 。从概率上来看不难发现， $s(X\to Y)=P(X\bigcup Y),\quad c(X\to Y)=P(Y|X)$ 。若 $X$ 和 $Y$ 的支持度和置信度同时超过了对应的阈值，则称 $X$ 和 $Y$ 之间的关联是 强规则 的。

而关联分析的任务就是在给定事物集、支持度阈值、置信度阈值的情况下，找到所有的强规则。

3.2 支持度检测算法

显然可以直接枚举 $X\to Y$ 的所有项集然后进行支持度检测和置信度检测，但是这样的时间复杂度过高。常规的优化算法就是支持度检测和置信度检测分模块串行计算。先用支持度检测算法寻找出所有的频繁项集，然后再进行支持度检测。下面介绍两个经典的支持度检测算法来寻找出所有的频繁项集。

3.2.1 Apriori 算法

项集的搜索空间如下示例所示：

项集的搜索空间 - 示例

为了降低枚举出来的项集的个数以及重复性，Apriori 算法的核心思路就是「非频繁项集的超集一定也是非频繁项集」，对应的有两个优化步骤：

自连接。在 利用 $k$ 项集构造 $k+1$ 项集 时。用所有的 $k$ 频繁项集自连接来构造 $k+1$ 项集。两个 $k$ 频繁项集可以连接的前提是它们有 $k-1$ 项是相同的
剪枝。在 降低搜索空间 时。如果当前项集是不频繁的，那么搜索空间中当前项集的超集都直接被减掉。

当然，在进行支持度计算时，涉及到了向量匹配算法，可以用字典树进行常数优化。这里被称为哈希树。

需要注意的是，由于计算置信度时需要使用之前计算过的支持度信息，当频繁项集很多时，这会造成很大的存储消耗，为了减少这种存储消耗，我们需要减少频繁项集的数量，为此引入「极大频繁项集」和「闭频繁项集」来压缩频繁项集的数量从而在保留重要信息的前提下减少存储消耗。其中极大频繁项集定义为「某个频繁项集的直接超集都不是频繁项集」，而闭频繁项集定义为「某个频繁项集的直接超集与它的支持度计数都不一样」。

这里再补充一个 Apriori 算法的变种，叫做 Eclat 算法。其算法逻辑是将项集编号和项集进行「反拉链」存储，后续在统计频繁项集时只需要取交集即可，如下图所示：

Eclat 算法示例假设最小支持度阈值为 2

但是即使上面这么折腾进行优化，Apriori 的计算复杂度仍然很高。因为连接步产生的候选项集仍然可能有有很多，并且对于每一个候选项集，即使使用哈希树也几乎需要遍历一遍事务集。下面介绍 FP-Growth 算法。

3.2.2 FP-Growth 算法

这其实就是 trie 树的弱化版。显然 trie 可以拆项并计数，由于事务集的每一个事务中的项的顺序是无关的，因此在构造 trie 树之前可以自定义项的顺序，常规方法就是对每一个事务中的项按照其出现的频率降序排序（这里借鉴了哈夫曼树的构造策略，但也不一定会简化树的结构）。接下来构造一个 trie 树即可。当然，在一开始对项的出现频率排序时，可以提前删除不符合的候选一项集。

从上面的算法描述可以看出，我们需要对事务集扫描两边来维护出必要的信息。举例说明：假设最小支持度阈值为 22.2%。

一）首先扫描一遍事务集并将项集按照某种规则排序（一般是按照频率降序排序）

按照频率降序排序

二）接着扫描一遍事务集构造 FP 树

构造 FP 树

构造完 FP 树后，如何寻找频繁项集呢？从候选一项集（叶子结点）开始向上搜索合适的路径，将合适的结点排列组合即可得到频繁项集。示例代码如下：

▶

FP-Growth 实现

上述事务集对应输入：

Member_number,itemDescription
1,b
1,a
1,e
2,b
2,d
3,b
3,c
4,b
4,a
4,d
5,a
5,c
6,b
6,c
7,a
7,c
8,b
8,a
8,c
8,e
9,b
9,a
9,c

代码：

ori_data = pd.read_csv('./ppt_demo_data.txt')

d: {tuple, list} = {}
for _, row in ori_data.iterrows():
    key = row['Member_number']
    value = row['itemDescription']
    if key in d:
        d[key].append(value)
    else:
        d[key] = [value]

data = []
for key, value in sorted(d.items()):
    data.append(value)

te = TransactionEncoder()
te_ary = te.fit(data).transform(data)
df = pd.DataFrame(te_ary, columns=te.columns_)
print(df.shape)
print(df)

frequent_itemsets: pd.DataFrame = fpgrowth(df, min_support=2/9, use_colnames=True)
print(frequent_itemsets)

事务集 one-hot 矩阵：

满足 2/9 最小支持度阈值的频繁项集：

当然，如果第一步中的排序规则不合理很容易导致建树的开销很大（几乎是指数级别），这也就会导致在一些情况下 FP-Growth 算法甚至不如 Apriori 算法。

3.3 置信度检测算法

有了频繁项集，接下来就是在其中寻找符合置信度的项集从而得到强关联规则。显然的，对于每一个频繁项集 V，假设 $|V|=k$ ，那么就可以 $2^k-2$ 次枚举所有可能的关联规则进行置信度检测。但是指数级别的时间复杂度是不被允许的，尝试优化。

不难发现，根据置信度 $c$ 的定义式 $c(X\to Y)=\frac{\sigma(X\bigcup Y)}{\sigma(X)}$ ，如果一个频繁项集被划分为 $\{X,Y\}$ 后不满足置信度阈值，则 $X$ 的子集对应的划分方法一定都不满足置信度阈值，以此可以对搜索空间进行剪枝来降低时间复杂度。

3.4 度量评估

在得到所有的强关联规则后，如何进行评估呢？下面给出一些度量评估方法。

提升度： $\displaystyle\text{lift}(X,Y)=\frac{P(X\cup Y)}{P(X)P(Y)}$
全置信度： $\displaystyle \text{all\_conf}(X, Y) = \min\{P(X|Y), P(Y|X)\}$
最大置信度： $\displaystyle \text{max\_conf}(X, Y) = \max\{P(X|Y), P(Y|X)\}$
Kluc 度量： $\displaystyle \text{Kluc}(X, Y) = \frac{P(X|Y)+P(Y|X)}{2}$
余弦度量： $\displaystyle \text{Cosine}(X, Y) = \sqrt{P(X|Y)P(Y|X)}$

提升度的解释。对于两个项集 $X$ 和 $Y$ ，如果 $\frac{P(X\bigcup Y) }{P(X)P(Y)} >1$ 则说明 $X$ 和 $Y$ 是正相关的，这也是我们进行关联分析所感兴趣的；如果 $\frac{P(X\bigcup Y) }{P(X)P(Y)} = 1$ 则说明 $X$ 和 $Y$ 是相互独立的，没有研究意义；如果 $\frac{P(X\bigcup Y) }{P(X)P(Y)} < 1$ 则说明 $X$ 和 $Y$ 是负相关的，其中一项的出现会抑制另一项的出现，也没有研究意义。

3.5 扩展研究

当待分析的内容不是项集时，例如连续数值属性时，有必要进行连续数值离散化。

更进一步的，如果我们希望分析项集的先后时序关系，可以将频繁项集拓展为频繁序列，例如频繁时序序列分析。

4 聚类问题

本章再学一种无监督学习方法。不重复造轮子，详见《机器学习》课程的聚类笔记：https://blog.dwj601.cn/GPA/4th-term/MachineLearning/#9-聚类。

分类问题

异常检测

GPA > 5th-term

DataMining

https://blog.dwj601.cn/GPA/5th-term/DataMining/

作者

Mr_Dwj

发布于

2024年8月27日

更新于

2024年11月18日

许可协议

MachineLearningClassDesign 上一篇

DigitalImageProcessing 下一篇