数据仓库数据挖掘期末复习题（2024-2025第2学期限选版）
前言
1 数据分析的基本步骤有哪些？每个步骤的主要工作
1.明确分析目的
- 梳理分析思路，并搭建分析框架，把分析目的分解成若干个不同的分析要点，即如何具体开展数据分析，需要从哪几个角度进行分析，采用哪些分析指标。
2.数据收集
- 基于物联网的采集方法
- 系统日志采集方法
- 网络数据采集方法
- 其他数据采集方法
3.数据处理
4.数据挖掘
- 数据源包括：数据库、数据仓库、Web、其他信息存储库或动态地流入系统的数据。
- 关系数据库：由表组成，每个表有一个唯一的表名。
- 数据仓库：指存储大量历史数据的数据库；一般情况下将被长期保留，也就是数据仓库中一般有大量的查询操作，但修改和删除操作很少，通常只需要定期的加载、刷新
- 特点：数据仓库是集成的，可以把来自不同数据源（如关系数据库、文件数据、在线事务记录等 ）的信息以同一模式保存在同一个物理地点。
5.数据展现
- 一般情况下，数据是通过表格和图形的方式来呈现的。
- 饼图、柱形图、条形图、折线图、气泡图、散点图、雷达图等。关系图，热图，词云，地图，三维图，动态图等
6.报告撰写
2 关于大数据的4V理论是什么？
3 四种基本度量尺度适用的集中趋势和离散度量方法有哪些？
属性类别
- 标称属性（名词属性）：名词属性的值是事物的符号或者名称。
- 例：：发色和婚姻状态。发色可以是黑色，棕色，红色，灰色，白色。婚姻状态可以是单身、已婚、离异或者丧偶。
- 二进制属性：二进制属性是只有两个类别或状态：0和1。
- 次序属性：次序属性具有次序或者级别的意义。但是相邻值的级别未知。
- 例：例如饮料尺寸，可以是“小杯”，“中杯”，“大杯”。值有顺序的意义，但是不能分辨中杯比大杯大多少。再比如，成绩等级A+, A,A-,B+职称：助理，副教授，教授
- 数值型属性：数值型属性是定量的，是可测量的数值，为整数或实数。分为间隔尺度（Interval）和比例尺度（Ratio）
- 间隔尺度：间隔尺度使用同等大小的单元来衡量。除了能对属性值排序，还可以比较和衡量不同值的差值大小。
- 例：温度属性是间隔尺度。20摄氏度高于15摄氏度。日历也是间隔尺度，以及年份。
- 比例尺度：比例尺度属性是具有零点的数值属性。如果一个测量是比例尺度，则可以以比率来衡量两个值，也可以计算值的差值，以及中值，均数和众数。
- Kelvin温度有一个真正的0点。另外，计数属性，经验年数，单词个数，体重，身高，速度，货币都是比例尺度。
数据的计量尺度
定类尺度(Nominal Level)：标称属性
- 按照事物的某种属性对其进行平行的分类或分组。
- 定类尺度只测度了事物之间的类别差，而对各类之间的其他差别却无法从中得知，因此各类地位相同，顺序可以任意改变。
- 对定类尺度的计量结果，可以且只能计算每一类别中各元素个体出现的频数 (frequency)。
- 对事物进行分类时，必须符合穷尽(exhaustive)和互斥(mutually exclusive)要求。
定序尺度(Ordinal Level)：次序属性
- 是对事物之间等级或顺序差别的一种测度。
- 不仅可以测度类别差（分类），还可以测度次序差（比较优劣或排序）
- 数据表现为“类别”，但有序
定距尺度(Interval Level)：数值型间隔尺度属性
- 是对事物类别或次序之间间距的测度。
- 不仅能将事物区分为不同类型并进行排序，而且可准确指出类别之间的差距是多少
- 没有绝对零点；“0”是测量尺度上的一个测量点，并不代表“没有”
定比尺度(Ratio Level)：数值型定比尺度属性
- 是能够测算两个测度值之间比值的一种计量尺度。
- 除了具有其他三种计量尺度的全部特点外，还具有可计算两个测度值之间比值的特点；
- “0”表示“没有”，即它有一固定的绝对“零点”，因此它可进行加、减、乘、除运算（而定距尺度只可进行加减运算）
练习
集中趋势的测度
- 定类数据：众数
- 定序数据：中位数
- 定距和定比数据：平均数（均值）
- 众数、中位数和均值的比较
离散程度
定类数据：异众比率（非众数组的频数占总频数的比例）
定序数据：四分位差（上四分位数与下四分位数之差）
定距和定比数据：极差、平均差、方差和标准差
- 平均差：各变量值与其平均数离差绝对值的平均数（应该不重要）
- 方差
$$
\sigma^2 = \frac{1}{N} \sum_{i=1}^N (x_i - \mu)^2
$$
$$
\sigma^2 = \frac{\sum_{i=1}^N x_i^2}{N} - \mu^2
$$
$$
s^2 = \frac{\sum_{i=1}^k f_i (M_i - \bar{x})^2}{n - 1}
$$
$$
M_i : 组中值，f_i : 频数
$$
标准分数：相对位置的度量, 对某一个值在一组数据中相对位置的度量
$$
z = \frac{x_i - \mu}{\sigma}
$$
相对离散程度：离散系数
$$
V_s = \frac{\sigma}{\mu}
$$
$$
V_s：离散系数，\sigma：方差，\mu：均值
$$
4 数据对象的相似性（单属性，多同种属性，混合属性）有哪些方法，jaccard,闵可夫斯基
数据矩阵与相异性矩阵
单属性的相似性
标称属性
- 由于标称属性只携带了对象的相异性信息，因此我们只能说两个对象有相同的值，或者没有。
- 如果属性值匹配，则相似度定义为1，否则为0；相异度用相反的方法定义：如果属性值匹配，相异度为0，否则为1。
序数属性
- 在标度{poor, fair, OK, good, wonderful}上测量产品（例如，糖块）质量的属性。
- P1:wonderful;P2:good;P3:OK
- 相异度：d(P1,P2) 与 d(P1,P3)
- 序数属性的值常常映射到从0或1开始的相继整数，例如，{poor = 0, fair =1, OK = 2, good = 3, wonderful = 4}。
- d(P1, P2) = |4-3| = 1
- 如果我们希望相异度在0和1之间取值，d(P1, P2) = |4-3|/4 = 0.25；序数属性的相似度可以定义为s = 1-d。
- 规格化：将值映射到0~1，假设排位为：x∈{1,2,…,n}
$$
d(x, y) = \frac{|x - y|}{\max(x) - \min(x)}
$$
数值（区间或比率属性）
- 对于区间或比率属性，两个对象之间的相异性的自然度量是它们的值之差的绝对值。
小结
多个同种类型属性的临近性度量
距离
闵可夫斯基距离
$$
d(x, y) = \left( \sum_{i=1}^n |x_i - y_i|^p \right)^{\frac{1}{p}}
$$
$$
i= (x_{i1}, x_{i2}, …, x_{ip}) \space, j = (x_{j1}, x_{j2}, …, x_{jp})
$$
- p=1时，曼哈顿距离
- p=2时，欧几里得距离
- p->∞时，切比雪夫距离，等于两个对象的属性中的最大距离
- 闵可夫斯基距离在面对离散数据集的时候不适用，对于有序数列数据集可用
- 缺点:1.将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。2. 没有考虑各个分量的分布（期望，方差等）可能是不同的。
标准化欧式距离
- 标准化，使分量与单位无关，使各维度分别满足标准正态分布
$$
z_i = \frac{x_i - \mu_i}{\sigma_i}
$$
马氏距离
$$
d_M(x, y) = \sqrt{(x - y)^T S^{-1} (x - y)} \
(x - y): \text{两个数据点的差向量} \
S^{-1}: \text{协方差矩阵的逆矩阵} \
$$
标称属性
二元属性的邻近性度量
Jaccard相似系数
$$
J(A, B) = \frac{|A \cap B|}{|A \cup B|}
$$
余弦相似度
$$
\text{Cosine Similarity} = \cos(\theta) = \frac{\vec{A} \cdot \vec{B}}{|\vec{A}| |\vec{B}|}
$$
文章相似性求法
- 使用TF-IDF(词频”（TF）和”逆文档频率idf)算法，找出两篇文章的关键词；
- 每篇文章各取出若干个关键词（比如20个），合并成一个集合，计算每篇文章对于这个集合中的词的词频（为了避免文章长度的差异，可以使用相对词频）；
- 生成两篇文章各自的词频向量；
- 计算两个向量的余弦相似度，值越大就表示越相似。
- 词频 (TF) 是一词语出现的次数除以该文件的总词语数。假如一篇文件的总词语数是100个，而词语“母牛”出现了3次，那么“母牛”一词在该文件中的词频就是3/100=0.03。
- 一个计算文件频率 (IDF) 的方法是文件集里包含的文件总数除以测定有多少份文件出现过“母牛”一词。所以，如果“母牛”一词在1,000份文件出现过，而文件总数是10,000,000份的话，其逆向文件频率就是 lg(10,000,000 / 1,000)=4。
- TF-IDF的分数为0.03 * 4=0.12。
混合类型属性的相异性
方法
- 方法1：将各种类型的属性分为一组，然后利用前面介绍的方法计算两个数据对象在每种类型的相似度，最后将不同类型的相似度综合成总的相似度
- 方法2：把所有属性类型一起处理，把不同的属性组合到单个相异性矩阵中，把所有有意义的属性转换到相同的区间 [0.0, 1.0] 上
5 数据属性的相关性有哪些方法（斯皮尔曼等级相关系数，皮尔森）
斯皮尔曼等级相关系数
$$
r_s = 1 - \frac{6 \sum d_i^2}{n(n^2 - 1)} \
d_i: \text{每对数据的等级差，即 } d_i = R(x_i) - R(y_i) \
n: \text{数据对的数量} \
$$
- 出现相同等级时的排序方法：
- 将所有的数（包括相同的数）都按顺序排列
- 按顺序为每一个数据排序
- 当两个（或多个）数据相同时，计算这些数据顺序的平均数，然后将平均数作为最终的顺序分配到每个数值中
皮尔逊积矩相关系数
- 协方差
$$
\text{Cov}(X, Y) = \sum_{i=1}^n (X_i - \bar{X})(Y_i - \bar{Y})
$$
- 皮尔逊相关系数
$$
r = \frac{\text{Cov}(X, Y)}{\sigma_X \sigma_Y} \
$$
$$
r = \frac{\sum_{i=1}^n (X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum_{i=1}^n (X_i - \bar{X})^2} \cdot \sqrt{\sum_{i=1}^n (Y_i - \bar{Y})^2}}
$$
$$
r = \frac{n \sum X Y - \sum X \sum Y }{\sqrt{n \sum X^2 - \left(\sum X \right)^2} \cdot \sqrt{n \sum Y^2 - \left(\sum Y \right)^2}}
$$
6 数据预处理的主要任务有哪些？每个任务要解决的问题主要有哪些？
- 数据清理
- 填充缺失值, 识别/去除离群点, 光滑噪音, 并纠正数据中的不一致
- 数据集成
- 数据变换
- 数据规模
7 脏数据主要有哪几种？产生的主要原因是什么？
- 不完全数据源于
- 数据收集时未包含
- 数据收集和数据分析时的不同考虑.
- 人/硬件/软件问题
- 噪音数据源于
- 不一致数据源于
8 缺失值的处理方法有哪些？
- 忽略元组: 缺少类别标签时常用(假定涉及分类)—不是很有效，当每个属性的缺失百分比变化大时
- 手工填写缺失数据: 乏味+费时+不可行
- 自动填充
- 一个全局常量 : e.g., “unknown”, a new class?!
- 使用属性均值
- 与目标元组同一类的所有样本的属性均值: 更巧妙
- 最可能的值: 基于推理的方法，如贝叶斯公式或决策树
热卡填充法
- 对于一个包含缺失值的变量，热卡填充法的做法是：在数据库中找到一个与它最相似的对象，然后用这个相似对象的值来进行填充。
自动处理缺失数据的机制
- 在缺失率少且属性重要程度低的情况下，若属性为数值型数据则根据数据分布情况简单的填充即可，例如：若数据分布均匀，则使用均值对数据进行填充即可；若数据分布倾斜，使用中位数填充即可。
- 当缺失率高(>95%)且属性重要程度低时，直接删除该属性即可。然而在缺失率高且属性程度较高时，直接删除该属性对于算法的结果会造成很不好的影响
- 缺失率高，属性重要程度高：主要使用的方法有插补法与建模法
- 插补法主要有随机插补法，多重插补法，热平台插补法，以及拉格朗日插值法与牛顿插值法
- 可以用回归、贝叶斯、随机森林、决策树等模型对缺失数据进行预测。例如：利用数据集中其他数据的属性，可以构造一棵判定树，来预测缺失值的值。
9 什么是噪声数据？产生的原因有哪些？
- 噪声：在测量一个变量时可能出现的测量值相对于真实值的偏差或者错误。
- 原因
- 错误的数据收集工具
- 数据录入问题 data entry problems
- 数据传输问题data transmission problems
- 技术限制 technology limitation
- 不一致的命名惯例 inconsistency in naming convention
10 噪声数据的检测和处理方法有哪些？
检测
简单统计分析
- 对属性值进行一个描述性的统计（规定范围），从而查看哪些值是不合理的（范围以外的值）。
3σ原则
- 若数据服从正态分布：根据正态分布的定义可知，距离平均值3δ之外的概率为 P(|x-μ|>3δ) <= 0.003 ，这属于极小概率事件，在默认情况下我们可以认定，距离超过平均值3δ的样本是不存在的。因此，当样本距离平均值大于3δ，认为该样本为异常值
使用距离检测多元离群点
- 当数据不服从正态分布时，可以通过远离平均距离多少倍的标准差来判定，多少倍的取值需要根据经验和实际情况来决定。
基于模型检测
- 首先建立一个数据模型，异常是那些同模型不能完美拟合的对象；如果模型是簇的集合，则异常是不显著属于任何簇的对象；在使用回归模型时，异常是相对远离预测值的对象
基于密度
- 当一个点的局部密度显著低于它的大部分近邻时才将其分类为离群点。适合非均匀分布的数据。
- 优点：给出了对象是离群点的定量度量，并且即使数据具有不同的区域也能够很好的处理
- 缺点：时间复杂度O(m^2)；参数选择困难，虽然算法通过观察不同的k值，取得最大离群点得分来处理该问题，但是，仍然需要选择这些值的上下界。
处理
方法
- 删除含有异常值的记录
- 将异常值视为缺失值，使用缺失值处理方法来处理
- 数据平滑
- 不处理
回归
- 回归：发现两个相关的变量之间的变化模式，通过使数据适合一个函数来平滑数据，即利用拟合函数对数据进行平滑及除去噪声。
- 通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。
聚类
- 簇：一组数据对象集合。同一簇内的所有对象具有相似性，不同簇间对象具有较大差异性。
- 聚类：将物理的或抽象对象的集合分组为由不同簇，找出并清除那些落在簇之外的值（孤立点），这些孤立点被视为噪声。
- 通过聚类分析发现异常数据：相似或相邻近的数据聚合在一起形成了各个聚类集合，而那些位于这些聚类集合之外的数据对象，自然而然就被认为是异常数据。
- 特点：直接形成簇并对簇进行描述，不需要任何先验知识。
- 每个簇中的数据用其中心值代替
- 先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。
- 人工再审查这些孤立点
数据平滑————分箱
- 分箱：把待处理的数据按照一定的规则放进一些箱子中，考察每一个箱子中的数据，采用某种方法分别对各个箱子中的数据进行处理。
- 箱子：按照属性值划分的子区间，如果一个属性值处于某个子区间范围内，就称把该属性值放进这个子区间代表的“箱子”里。
- 分箱技术需要确定的主要问题：
- 分箱方法，即如何分箱
- 数据平滑方法，即如何对每个箱子中的数据进行平滑处理
11 什么叫数据集成？集成的框架结构？分类？数据集成解决的主要问题有哪些？例子
数据集成
- 数据集成是指将互相关联的分布式异构数据源集成到一起，使用户能够以透明的方式访问这些数据源。
- 集成是指维护数据源整体上的数据一致性、提高信息共享利用的效率；
- 透明的方式是指用户无需关心如何实现对异构数据源数据的访问，只关心以何种方式访问何种数据。
集成的框架结构
数据集成解决的主要问题
异构性
- 主要表现在数据语义、相同语义数据的表现形式、数据源的使用环境等；主要原因是数据源通常独立开发，数据模型异构；
- 语法异构
- 一般指源数据与目的数据之间命名规则及数据类型存在不同。对数据库而言，命名规则指表名和字段名；
- 语法异构相对简单，只要实现字段对字段、记录对记录的映射，解决其中的名字冲突和数据类型冲突；
- 语法异构无需关心数据的内容和含义，只要知道数据结构信息，完成源和目的之间的映射就可以了。
- 语义异构
- 语义异构涉及数据的内容和含义；
- 语义异构比语法异构复杂得多，往往需要破坏字段的原子性，需要直接处理数据的内容；
- 语义异构的形式：字段拆分、字段合并、字段数据格式变换、记录间字段转移等。
- 语法异构与语义异构的形成可以追溯到数据源建模时的差异
- 当数据源的实体关系模型相同时，只是命名规则不同时，造成的只是数据源之间的语法异构；
- 当数据源构建实体模型时，若采用不同的颗粒划分、不同的实体间关系以及不同的字段数据语义表示，必然会造成源数据的语义异构。
分步性
- 数据源是异地分布的，依赖网络传播数据，集成需要考虑传输性能和信息安全问题；
- 数据库是数据集成过程中最重要的操作对象；
- 绝大多数的源数据都存贮在分布不同地点（系统）的数据库中；
- 数据集成最终是集成存贮于数据库中的数据。
- 因此，数据集成的方法必须围绕数据在数据库中的存贮方式、数据库体系结构特点、数据库应用架构进行设计和选择；
12 什么叫数据归约？主要有哪几类归约问题？简要说明每种问题
为什么要数据规约
- 在现实场景中，数据集是很庞大的，数据是海量的，在整个数据集上进行复杂的数据分析和挖掘需要花费很长的时间。
种类
维归约
- 维归约也称为特征规约，是指通过减少属性特征的方式压缩数据量，通过移除不相关的属性，可以提高模型效率。
数量规约
- 用较小的数据表示数据，或采用较短的数据单位，或者用数据模型代表数据，减少数据量。
- 从数据集中选出一个有代表性的样本的子集。子集大小的确定要考虑计算成本、存储要求、估计量的精度以及其它一些与算法和数据特性有关的因素。
特征值规约
全面规约
- 通过减少数据记录的数量来实现数据归约的技术。其目标是通过数据抽样或聚合等方法，减少数据规模，同时保留数据的整体分布和主要特征。
13 维度归约有哪两类技术？有什么区别？
特征选择
- 删除不相关/冗余属性，减少数据集
- 找出最小属性集，类别的数据分布尽可能接近使用全部属性值的原分布
- 减少了发现的模式数目, 容易理解
特征提取
- 产生新的属性，其可以比始属性更有效地表示数据的重要信息。
14 什么是数据离散化和概念分层？
离散化
- 通过将属性（连续取值）域值范围分为若干区间，来帮助消减一个连续（取值）属性的取值个数。
概念分层
15 数据增长有那些方面？具体可采用什么技术及每个技术要点（新）
维度增长
特征衍生/构造
- 特征衍生/构造： 在数据分析中，原始数据往往并不直接包含有用的信息，而是通过特征之间的组合或转换才能得到。因此，特征衍生技术被用来创建新的特征，以提取更多的信息
数量增长
数据平衡
过采样
- 通过增加少数类样本的数量来平衡数据集
- 常用的过采样方法包括随机过采样、SMOTE（Synthetic Minority OverSampling Technique）和 ADASYN（Adaptive Synthetic Sampling Approach）等。
- 这些方法通过合成新的少数类样本，使得少数类样本的数量与多数类样本相当，从而达到数据平衡的效果。
- 然而，过采样也可能导致过拟合的问题，因此在应用过采样方法时需要谨慎选择合适的参数和方法。
欠采样
- 通过减少多数类样本的数量来平衡数据集。
- 常用的欠采样方法包括随机欠采样和聚类欠采样等。
- 欠采样的优点是能够减少模型训练的时间和计算成本，但是也可能导致丢失重要信息的问题。因此，在应用欠采样方法时需要充分考虑样本的分布和特征。
集成学习
- 将多个基分类器集成为一个强分类器的方法
- 常见的集成学习方法包括Bagging、Boosting和Stacking等。
- 这些方法可以有效地提高模型的泛化能力和预测性能，同时也能够解决数据不平衡的问题。
- 在实际应用中，集成学习方法往往能够取得较好的效果，成为解决数据不平衡问题的重要方法之一。
数据扩充
数据增强
- 数据增强是最常用的数据集扩充方法之一。它是通过对原始数据进行一系列变换操作，生成新的数据，从而增加数据集的大小。
- 常见的数据增强方法包括：旋转、平移、缩放、翻转、加噪声等。
- 这些操作可以使得数据更加丰富多样，有助于提高模型的泛化能力。
- 但是，数据增强也存在一些问题，比如增强后的数据可能会出现噪声或者失真，这会影响模型的训练效果。
数据合成
- 通过将不同的数据组合起来，生成新的数据。
- 常见的数据合成方法包括：图像叠加、图像融合、图像拼接等。
- 这些操作可以使得数据更加多样化，有助于提高模型的鲁棒性。
- 但是，数据合成也存在一些问题，比如可能会出现过拟合的情况，导致模型的泛化能力下降。
GAN
VAE
数据迁移
16 数据规范化/标准化的方法有哪些？形式，有什么作用？
概念
零-均值规范化
- 将样本数据化为均值为0，标准差为1的标准正态分布
$$
z_i = \frac{x_i - \mu_i}{\sigma_i}
$$
最小-最大规范化
- 将一列数据变化到某个固定区间(范围)中。这种方法的一个缺陷是当有新的数据加入时，可能导致max,min值的变化，需要重新定义。
$$
x’ = \frac{x - \text{old_min}}{\text{old_max} - \text{old_min}} \cdot (\text{new_max} - \text{new_min}) + \text{new_min}
$$
小数定标规范化
- 通过移动属性A值的小数位置，将属性A的值映射到[0，1]之间，用小数的科学表示法来达到规格化的目的。
- 移动的小数位数取决于属性A绝对值的最大值。
17 数据编码技术有哪些？具体实现要点（新）
标签编码（LABEL ENCODING）
内容
- 替换类别名称为一个唯一的整数来进行类别转换。每一个类别被分配一个从0开始的唯一整数。
- 将类别标签转换为连续的整数值。例如，如果有一个标签列表[‘cat’, ‘dog’, ‘bird’]，LabelEncoder可能会将其转换为[0, 1, 2]。
优点
- 简单、快速，并且转换后的数据可以直接用于许多机器学习算法。
缺点
- 首先，它假设类别之间存在某种顺序关系，这种假设可能并不总是成立。例如，在上述例子中，我们不能假定“dog”在“cat”之后就有某种内在的意义。
- 如果新的、未知的类别出现在测试集中，LabelEncoder将无法处理，这可能导致模型性能下降
- 在大多数模型中，这种有序关系的引入可能会导致模型学习错误的关系，从而影响模型性能。
独热编码（ONE-HOT ENCODING）
内容
- 独热编码即One-Hot编码，又称一位有效编码，是处理类型数据较好的方法，主要是使用N位状态寄存器来对N个状态进行编码，每个状态都有它独立的寄存器位，并且在任意时候都只有一个编码位有效。
- 对于每一个特征，如果它有m个可能值，那么经过独热编码后，就变成了m个二元特征，并且这些特征之间是互斥的，每一次都只有一个被激活，这时原来的数据经过独热编码后会变成稀疏矩阵。对于性别男和女，利用独热编码后可以表示为10和01。
优点
- 对离散型特征使用独热编码，可以让特征之间的距离计算更为合理
- 避免了LabelEncoder的假设，即类别之间不存在顺序关系。
- 可很好地处理未知类别的问题，可以简单地将未知的类别编码为一个全零向量
缺点
- 当类别数量很多时，OneHot编码可能会引入大量的特征，这可能会增加模型的复杂性。
- 由于OneHot编码是二进制的，它无法处理类别之间的相似性。例如，如果我们知道’cat’和’tiger’在某种程度上是相似的，OneHot编码无法体现这种相似性。
二值化编码（BINARY ENCODING）
- 二进制编码是标签编码与独热编码的结合。
- 由于独热编码存在过多的零，因此可以通过二值化编码减少部分零位。
- 这种方法相比于纯独热编码可以大幅度减少新特征的数量，同时避免了标签编码的问题。
- 减少了特征的维度。
- 保持了类别之间的某种程度的独立性。
18 数据仓库的主要特征是什么，对每一特征给予简要解释
面向主题（Subject-Oriented）
- 主题：主题是企业中需要重点关注和分析的业务领域。
- 每个主题通常对应一个分析目标，例如“销售”主题可能包含销售额、销售时间、销售地区等信息。
- 数据仓库以主题为中心组织数据，而不是以业务流程为中心。
- 每个主题（如客户、销售、产品）反映了企业的关键业务领域，便于分析和决策支持。
- 与传统数据库的区别：
- 传统数据库：以业务流程为中心，数据分散在不同的业务系统中（如订单管理系统、库存管理系统）。
- 数据仓库：以主题为中心，将分散在不同业务系统中的相关数据整合到一起，形成一个完整的主题视图。
集成性（Integrated）
- 数据仓库中的数据是在对原有分散的数据库数据抽取、清理的基础上经过系统加工、汇总和整理得到的
- 解决数据格式、命名规则、单位等不一致问题，确保数据的一致性和统一性。
非易失性（Non-Volatile）
- 数据一旦进入数据仓库后，通常不会被修改或删除。
- 数据仓库中的数据是历史数据的累积，支持长期的趋势分析和决策。
时变性（Time-Variant）
- 数据仓库中的数据包含时间戳或时间维度，反映数据在不同时间点的变化。
- 支持历史数据的存储和分析，便于进行趋势分析和预测。
19 数据仓库的作用
- 数据仓库提供用户用于决策支持的当前和历史数据，这些数据在传统的操作型数据库中很难或不能得到。
- 数据仓库技术是为了有效的把操作形数据集成到统一的环境中以提供决策型数据访问的各种技术和模块的总称。
- 所做的一切都是为了让用户更快更方便查询所需要的信息，提供决策支持
20 典型的数据仓库体系结构，各层简要说明
- 底层: 数据仓库服务器, 几乎总是一个关系型数据库系统;
- DW服务器从操作型数据库或外部数据源(如:咨询机构提供的客户背景)提取数据，并进行清洗、转换、集成等,装入到数据仓库中。
- 中间层: OLAP服务器,提供对多维数据的存储和操作。
- ROLAP: 将多维数据上的操作映射为标准的关系操作
- MOLAP: 直接在多维模型上实现多维数据操作
- 顶层: 前端工具, 包括查询和报表、分析、数据挖掘工具等。
21 数据库与数据仓库系统在设计上的差别
系统设计的目标不同
- 数据库是面向事务型处理的，所以事务型处理性能是系统设计的一个主要目标。
- 而数据仓库是为了支持决策分析而建立的一种数据存储集合。在系统设计时，更关心的是建立起一个全局一致的分析型处理环境来支持企业的决策分析。
面向的需求不同
- 数据库系统是面向应用的，所以在系统设计时应以此为出发点和基础。
- 而在决策分析时，决策者分析问题的角度多种多样，所以数据处理流和信息流不固定，甚至决策者对所要进行的分析处理都不太明了，数据的分析处理的需求更灵活。这就决定了在数据仓库系统设计时，不可能从用户需求出发来进行设计。
数据来源不同
- 数据库系统中数据是从企业外部通过输入得到的，所以系统设计时就是设计如何与外部对话得到数据，如何存储这些数据，它关心的是数据的安全性和完整性等。
- 数据仓库中的数据大部分是从企业内部的数据库系统得到的，还有一部分是企业外部的非结构化数据，这些数据都是安全可靠且正确有效的，所以在系统设计时它关心的不是数据的安全性和完整性，而是数据的一致性。
数据的处理类型不同
- 数据库系统支持的是事务型处理，主要指数据的增、删、改、查等等，系统设计时都是针对某一具体应用。
- 数据仓库是面向分析的，它的数据处理大都是对数据的复杂查询，所以在设计时考虑的是如何更好的面向主题，如何提高查询的效率等。
22 数据仓库设计的过程有哪些
自顶向下
- 从总体设计和规划开始
- 优点: 系统的解决方法，能最大限度地减少集成问题。
- 缺点: 费用高、费时长，缺乏灵活性, 因为整个企业的共同数据仓库模型要达到一致很困难。
- 首先建造企业数据仓库
- 再从企业数据仓库中建造数据集市
自底向上
- 由实验和原型开始
- 特点: 花费少、灵活性高、能快速回报投资; 但将分散的数据集市集成为一个一致的企业仓库可能很困难。
- 先建立部门数据集市
- 逐步扩展到企业数据仓库
23 模型设计（概念——逻辑；星型模型；粒度选择）
含义
概念模型设计
- 这一阶段之前的首要工作是通过需求分析，明确需求所涵盖的业务范围。然后再对需求范围内的业务及其间关系进行高度概括性的描述，把密切相关业务对象进行归类，即划分主题域。
- 概念模型的设计是为逻辑模型的设计做准备，它没有统一的标准，主要根据设计者的经验。
逻辑模型设计
- 分别对概念模型的各个主题域进行细化，根据业务定义、分类和规则，定义其中的实体并描述实体之间的关系，并产生实体关系图（ERD），然后遵照规范化思想在实体关系的基础上明确各个实体的属性。实体产生于中国移动开展的业务、服务及其涉及的对象（如客户、帐户、员工、机构、资源），实体间的对应、约束关系则来自于各业务过程中的规则。可以说，这一阶段面对的是业务。
概念模型——E-R图
逻辑模型
要做的工作
- 主题域进行概念模型(E-R图)到逻辑模型(星型模型)的转换
- 粒度层次划分
- 关系模式定义
- 定义数据血缘关系
关系模型
维度/多维数据模型
- 将数据看作数据立方体 (data cube)形式，允许以多维对数据建模和观察。
星型模型
- 星形模式通过使用一个包含主题的事实表和多个维度表来支持各种决策查询。
- 星形模型可以采用关系型数据库结构，模型的核心是事实表，围绕事实表的是维度表。通过事实表将各种不同的维度表连接起来，各个维度表都连接到中央事实表。
粒度
粒度选择
- 粗略估算数据量，确定合适的粒度级的起点。即粗略估算数据仓库中将来的数据行数和所需的数据存储空间。
- 例如：预估一年及5年内表中的最少行数和最多行数，并对每张表确定键码的长度和原始表中每条数据是否存在键码。
- 确定粒度的级别。在数据仓库中确定粒度的级别时，需要考虑如下因素：分析需求类型、数据最低粒度和存储数据量。
- 对于业务量大，分析要求比较高的情况下，最佳解决办法则是采用多重粒度的形式。
- 双重粒度
- 在数据仓库的细节级上创建两种粒度
- 短期储存的低粒度（真实档案），满足细节查询
- 具有综合的高粒度（轻度综合），做分析
24 ETL的含义
含义
- E（Extract）抽取、T（Transform）转换、L（Load）加载
- ETL是数据从业务系统抽取转化到数据仓库的过程，包括4个子过程：数据抽取、数据转换、数据清洗、数据装载
- 用户从数据源抽取出所需数据，经过数据清洗，按照预先定义好的数据仓库模型，将数据装载到数据仓库中去
内容
- 数据抽取：数据抽取是数据源接口，从业务系统中抽取数据，为数据仓库输入数据
- 数据转换：根据数据仓库系统模型的要求，进行数据的转换、清洗、拆分、汇总等处理，保证来自不同系统、不同格式的数据具有一致性和完整性，并按要求装入数据仓库
- 数据清洗：过滤不符合要求的数据，将过滤的结果交给业务主管部门，确认是否过滤掉还是由业务单位修正之后再进行抽取
- 数据装载：将从数据源系统中抽取、转换、清洗后的数据装载到数据仓库系统中。
25 五种OLAP的操作，并说明每种的具体内容
OLAP含义（OnLine Analytical Processing）
- 数据仓库创建之后，需要进行各种复杂的数据查询操作。这些查询具有多角度/多视图模式、旋转、上钻、下卷等要求。
- 仅拥有数据仓库，要完成这样的复杂查询是不可能的，必须依靠一种强有力的工具。OLAP就是可完成上述任务的一种强有力工具。
- 在线分析处理或联机分析处理 (OLAP ) 是一个应用广泛的数据仓库使用技术。
- 定义：是针对特定决策问题的联机数据访问和分析。通过对信息(维数据)的多种可能的观察形式进行快速、稳定一致和交互性的存取，允许决策人员对数据进行深入观察。
操作
上卷(drill-up，roll up): 概括数据
- 通过沿一个维的概念分层向上攀升或者通过维归约，对数据立方进行聚集
下钻(Drill down ，roll down): 上卷的逆操作
- 从高层概括到底层概括，从不太详细到更加详细的数据
- 给数据添加更多细节，添加新的维到立方体来实现
切片和切块（Slice and dice）:投影和选择 ：
- 在多维数据结构中,固定一个维度的某个特定成员进行切片,在多个维度上定义范围或条件进行切块,可得到所需要的数据。如在“城市、产品、时间”三维立方体中进行切块和切片,可得到各城市、各产品的销售情况
转轴或旋转（Pivot or rotate）:
- 转换立方体的视角, 可视化, 从3D 到 2D 平面序列
26 MOLAP和ROLAP的体系结构，工作原理
RelationaI OLAP (ROLAP):
- 利用关系数据库来存储和管理基本数据和聚合数据，并利用一些中间件来支持缺失数据的处理
- 具有良好的可扩展性
Multidimensional OLAP(MOLAP)
- 利用多维数组来存放和管理基本数据和聚合数据，其中需要对稀疏矩阵处理技术
- 对预综合的数据进行快速索引
体系结构
MOLAP
ROLAP
工作原理
MOLAP
- 基于多维数组存储数据立方体，并进行联机分析处理操作
- 事先将汇总数据计算好，存放在自己特定的多维数据库中，用户的OLAP操作可以直接映射到多维数据库的访问，不通过SQL访问。
ROLAP
- 采用关系表存储数据，可以有效地处理海量数据，但因对多维数据处理涉及大量连接运算，导致查询速度较慢。
- 不做Cube计算，直接使用关系数据库，采用基于事实表和维表的星型模型或者更为复杂的雪花型模型，组织数据。
- 在ROLAP过程中，能够将Cube上的各种操作转换为数据库上SQL查询分析语句执行。
27 什么叫数据立方体的预计算？为什么要进行预计算？面临的问题有哪些？有哪些策略？
预计算
- 多维分析中需要对具有不同综合程度的数据进行查询，因而需要对细节数据进行综合。综合的过程称为预计算
面临的问题
- 海量数据，有限的内存和时间。海量数据运算对大量计算时间和存储空间的要求
策略
以空间换时间策略
- 在存储空间充足的情况下，可以采取将一个完整的数据立方体全部预计算出来，并进行存储的方法。
28 完整数据立方体的预计算方法
- 尽量一次同时计算多个数据立方体；
- 对每个数据立方体，计算时尽量选择在数据立方格结构中离自己最近的数据立方体进行聚集计算；
- 多个数据立方体同时计算时尽量共享排序结果、扫描结果、缓存结果、划分结果等。
（补充）数据立方体
结构
- 多维数据模型一般用数据立方体表示，一个数据立方体由多个维度和度量组成。
- 由不同维或维上的不同层可以组合出多个综合数据立方体。
- 举例：如果有三个维度A、B、C，每个维只有一个层，可以组合8个数据立方体。分别是：ABC、AB、AC、BC、A、B、C、ALL
- 一般来讲，对于一个n维数据集，如果不考虑层次，它的数据立方体个数为：2^n。
- 不包含任何维的数据立方体称之为总数据立方体，一般用ALL表示
导出关系定义
- 如果数据立方体A是由数据立方体B通过减少维的个数得到，则称数据立方体A可以由数据立方体B导出。
数据立方格
- 数据立方格结构是一个有向图，图中的每一个节点表示一个数据立方体，图中的每一条边表示节点之间的导出关系。
冰山立方体
- 冰山立方体指的是只存储和计算满足某个阈值（如计数、和等度量值大于等于某个最小支持度）的立方体单元（cell），而忽略那些度量值很小、不重要的单元。
- 换句话说，冰山立方体只保留“山峰”部分，过滤掉“冰山水面下”的大量无用数据，从而大大减少存储和计算量。
完全立方体计算的多路数组聚集方法
- 一般情况下，一般先从基数小的维开始聚集。在本例中设A=40，B=400，C=4000，则先聚集A，计算2-D面BC.然后是AC,最后是AB.
- 因为计算刚开始的四个块1,2,3,4就可以得到BC面的第一块，并且之后每连续的四个块一组得到下一个BC面的块，则在计算BC面时只需要缓冲BC面一个块的大小100*1000就可以，之后计算的16次均重复利用此内存块。
- 因为只有在调入块13的时候才可以计算得AC面的一块，则前面的12块都应该得到缓存，所以在计算AC面的时候，缓存的结果大小为AC面的一行，即40*1000；
- 因为只有调入第49块的时候才可以计算AB面，则前面计算结果均需保存，所需内存应为AB整个平面的面积，即40*400.
- 所以在此次计算中所需的内存为：100*1000+40*1000+40*400。
BUC算法
流程
例子（AI）
假设有如下销售数据，维度为A、B、C，度量为“数量”，最小支持度为3：
| A |
B |
C |
数量 |
| x |
p |
m |
2 |
| x |
p |
n |
2 |
| x |
q |
m |
1 |
| y |
p |
m |
3 |
| y |
p |
n |
1 |
| y |
q |
m |
2 |
| y |
q |
n |
1 |
步骤1：统计各维度的单独计数（1维立方体）
- A维度：x=5，y=7（都≥3，保留）
- B维度：p=8，q=4（都≥3，保留）
- C维度：m=8，n=4（都≥3，保留）
步骤2：统计二维组合（2维立方体）
- (x, p)：2+2=4（保留）
- (x, q)：1（不保留）
- (y, p)：3+1=4（保留）
- (y, q)：2+1=3（保留）
- (x, m)：2+1=3（保留）
- (x, n)：2（不保留）
- (y, m)：3+2=5（保留）
- (y, n)：1+1=2（不保留）
- (p, m)：2+3=5（保留）
- (p, n)：2+1=3（保留）
- (q, m)：1+2=3（保留）
- (q, n)：1（不保留）
步骤3：统计三维组合（3维立方体）
- (x, p, m)：2（不保留）
- (x, p, n)：2（不保留）
- (x, q, m)：1（不保留）
- (y, p, m)：3（保留）
- (y, p, n)：1（不保留）
- (y, q, m)：2（不保留）
- (y, q, n)：1（不保留）
步骤4：统计全体（，，*）
步骤5：输出所有满足条件的单元
- (x, *, *)：5
- (y, *, *)：7
- (*, p, *)：8
- (*, q, *)：4
- (*, *, m)：8
- (*, *, n)：4
- (x, p, *)：4
- (y, p, *)：4
- (y, q, *)：3
- (x, *, m)：3
- (y, *, m)：5
- (p, m)：5
- (p, n)：3
- (q, m)：3
- (*, *, *)：12
- (y, p, m)：3
说明：
- BUC算法只输出“数量”大于等于3的组合，极大减少了无用单元的计算和存储。
29 什么叫数据泛化
- 数据库中的数据和对象通常包含原始概念层的细节信息，数据泛化就是将数据库中的跟任务相关的大型数据集从相对较低的概念层抽象到较高的概念层的过程。
- 通过将相对层次较低的值（如属性age的数值）用较高层次的概念（如青年、中年、老年）置换来汇总数据
30 面向属性的泛化方法有哪两种实现及规则
属性删除
- 对初始工作关系中具有大量不同值的属性，符合以下情况，可使用属性删除：
- 在此属性上没有泛化操作符（比如该属性没有定义相关的概念分层）
- 该属性的较高层概念用其他属性表示,如street，其高层次概念用属性（city,province,country）等描述，可删除
属性泛化
- 如果初始工作关系中的某个属性具有大量不同值，且该属性上存在泛化操作符，则使用该泛化操作符对该属性进行数据泛化操作
31 频繁模式挖掘相关概念（关联规则，支持度，置信度）
定义
频繁模式挖掘
- 频繁模式挖掘：从大量数据中发现经常一起出现的项、事件或对象的集合（即“模式”）。
- 频繁模式：频繁的出现在数据集中的模式，如项集、子序或者子结构
- 频繁项集：频繁项集是指在数据集中出现次数（支持度）大于或等于用户设定的最小支持度阈值的项集。
关联规则
- 关联规则：是从频繁项集中提取的模式，它可以发现不同项之间的关联关系
- 关联规则挖掘：用来发现大量数据中项集之间有趣的关联联系。如果两项或多项属性之间存在关联，那么其中一项的属性就可以依据其他属性值进行预测。
- 关联规则表示项集之间的关系或关联，一般用形如 $X \Rightarrow Y$ 的蕴含式表达，其中， $ X \subset I，Y \subset I，X \cap Y= \varnothing $，I是项目集合，X称为规则前提，Y称为规则结果
支持度
- 支持度：项集在所有事务中出现的频率。
- 是事务集中同时包含X和Y的事务数与所有事务数之比，它反映了X和Y中所含的项在事务集中同时出现的概率。
$$
support(X \Rightarrow Y) = support(X \cup Y ) = P(XY)
$$
置信度（confidence）
- 置信度是事务集中，同时包含X和Y的事务数与包含X的事务数（不考虑是否包含Y）之比，反映了包含X的事务中出现Y的条件概率，记为 $confidence(X \Rightarrow Y)$，即：
$$
confidence(X \Rightarrow Y) = P(Y|X) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}
$$
- 置信度高说明X发生引起Y发生的可能性高，也就是说，规则Y依赖X的可能性比较高。
注：上述公式有的地方用交集有的地方用并集（我觉得应该是交集，但PPT并集），只需记住意思是同时出现，也就是韦恩图中间的部分
32 关联规则挖掘的步骤
找出所有频繁项集
由频繁项集产生强关联规则
33 Apriori方法（原理，例子）
思想
- 频繁项目集的子集仍是频繁项目集；非频繁项目集的超集是非频繁项目集。
原理
第一步：发现频繁项集
- 根据用户给定的最小支持度min_ sup，寻找出所有的频繁项集，即满足支持度Support不低于min_ sup的所有项集。由于这些频繁项集之间有可能存在包含关系，因此，我们可以只关心所有的最大频繁项集，即那些不被其它频繁项集所包含的所有频繁项集。
第二步：生成关联规则
- 根据用户给定的最小置信度min_ conf，在每个最大频繁项集中，寻找置信度Confidence不小于min_ conf的关联规则。
伪代码
- 令L1是频繁1项集
- 从2开始，对于所有频繁k-1项集
- 令Ck为用Apriori算法生成的候选k项集
- 对于所有数据库中的事务t
- 找出Ck中所有是t的子集的集合Ct
- 对于所有Ct中的集合c，c的计数+1
- Lk为大于给定支持度的项目集合
- 结果为Lk的并集
关联规则生成
34 FP-TREE（原理，例子）
构造FP-Tree
- 扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项，而将频繁项按照支持度的递减排序
- 创建树的根节点，用null标记；
- 将每个事务中的项按递减支持度计数排列，并对每个事务创建一个分枝；
- 比如为事务{f, c, a, m, p}构建一个分枝
- 当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数加1，为跟随前缀后的项创建节点并连接
- 比如将事务{f, c, a, b, m}加到树上时，将fca计数分别+1
- 创建一个项头表，以方便遍历，每个项通过一个节点链指向它在树中的出现。
挖掘FP-Tree
- 构造FP-Tree时是按照1-项集频度的降序进行的，对构造后的FP-Ｔree进行挖掘时，需要按照1-项集频度的升序进行。
- 对于每一个1-项集，首先构造它的条件模式基。
- 条件模式基：由FP-Tree中与该1-项集一起出现的前缀路径组成。即以要挖掘的节点作为叶子节点所对应的FP子树
- 具体实现：
- 从数据项头表中首先找到该1-项集，然后顺着链表找到它在树中出现的位置，每找到一个位置，则得到从树根到该位置的一条路径，该路径就构成了条件模式基中的一部分。
- 构造该初始后缀模式的条件FP树，重复1,2
- 直到结果FP-tree为空，或只含唯一的一个路径（此路径的每个子路径对应的项目集都是频繁集）
例子
step1：建立模式频繁树
- 我们首先需要建立一颗模式频繁树，做法很简单，也就是直接建立一颗字典树。在建立之前，我们需要先对每一个项进行统计，并去除出现次数小于support count的项，然后排序。对于上表，这么做后的结果如下：此处我们选择的support count为2，所以所有的项都被保留了下来。
| item |
count |
| I2 |
7 |
| I1 |
6 |
| I3 |
6 |
| I4 |
2 |
| I5 |
2 |
- 然后我们需要对保留下来的项压缩成一个字典树，为了保证这颗字典树尽可能小，我们需要对事务集中的每一个项集进行排序，结果如下：
| TID |
itemset list |
| T100 |
I2, I1, I5 |
| T200 |
I2, I4 |
| T300 |
I2, I3 |
| T400 |
I2, I1, I4 |
| T500 |
I1, I3 |
| T600 |
I2, I3 |
| T700 |
I1, I3 |
| T800 |
I2, I1, I3, I5 |
| T900 |
I2, I1, I3 |
- 字典树的根节点设为null，然后我们可以开始从第一条数据开始建立字典树，需要说明的是，这颗字典树的每个节点还需要维护一个count，这个count的含义是当前该节点被“经过”了多少次。下面的图中，每个结点被我标注为Ik : n的样子，代表当前节点名为Ik，count为n。我们先加入T100：
- 然后加入T200：
- 在频繁模式树建立完后，我们需要按照第一步中获取的表的逆顺序来遍历每一个项，先从I5开始，因为最少
step2：获取当前项的条件模式基
- 定义：Ik在建立的频繁模式树中对应的条件模式基定义为所有节点为Ik的前缀集合
- 以I5为例，获取I5的条件模式基
- 首先，找到频繁模式树中所有为I5的节点，如下图红色箭头所指：
- 很明显，每一个节点只会有一个前缀（也就是根节点到节点的父节点的路径上的节点集合），这两个I5节点对应的两个前缀就是I5在频繁模式树中的条件模式基。第一个I5节点的前缀为{I2, I1}，由于我们要考虑I5本身的count，所以第一个I5节点的前缀的count为1（所以前缀的count就定义为前缀中所有节点和挖掘的节点在树中的所有count中最小值），我们用{I2, I1 : 1}表示一个count为1的前缀。很显然，I5的条件模式基为{I2, I1 : 1}和{I2, I1, I3 : 1}
- 以此类推，获取其余节点的条件模式基：
| item |
conditional pattern base |
| I5 |
{I2, I1 : 1}, {I2, I1, I3 : 1} |
| I4 |
{I2, I1 : 1}, {I2 : 1} |
| I3 |
{I2, I1 : 2}, {I2 : 2}, {I1 : 2} |
| I1 |
{I2 : 4} |
由于I2不存在叶子节点上，所以I2不存在条件模式基
step3：从条件模式基中获取频繁项集
- 我们之前使用了字典树来压缩表征原事务集，那么对于我们的子事务集，我们也完全可以采用相同的步骤。
- 建立子事务集的频繁模式树之前，需要进行统计和基于support count的项的裁剪。
- 对于I5的子事务集（也就是条件模式基），我们需要先统计，得到{I2 : 2, I1 : 2, I3 : 1}。
- 由于我们的support count为2，所以我们需要去除count只为1的I3，然后排序得到I2, I1，剩下的事务集重构为{I2, I1 : 1}, {I2, I1 : 1}，很明显这两个前缀可以合并为{I2, I1 : 2}，然后我们画出这个裁剪后的子事务集的频繁模式树：
- 然后找出这棵频繁模式树的所有路径，可以看到上面的这棵频繁模式树只有一条路径，然后我们找出这条路径上节点所有可能的组合，也就是{I2, I1}, {I2}, {I1}，这也就是{I2, I1}的幂集。然后对于每一个组合类型，我们再加上I5，于是就得到了这条路径上得到的频繁项集：{I2, I1, I5}, {I2, I5}, {I1, I5}。所有路径上的频繁项集合并起来就是I5对应的频繁项集。
- 由于I5对应的FP-tree只有一条路径，所以这个例子不是很好，我们再举一个例子，就举I3吧。首先统计项得到{I2 : 4, I1 : 4}，都大于2，不需要裁剪，排序后得到的子事务集不变，还是{I2, I1 : 2}, {I2 : 2}, {I1 : 2}，构建该子数据集的频繁模式树：
- 然后找出FP-tree的所有路径：{I2, I1}和{I1}。对于路径{I2, I1}在，找出所有的组合{I2, I1}, {I2}和{I1}，加上I3得到 $ {I2, I1, I3}, {I2, I3}, {I1, I3} $ ；对于路径{I1}，找出所有的组合{I1}，加上I3得到 {I1, I3}。
- 遍历完所有路径后，将得到的频繁项集集合取并集，得到{I2, I1, I3}, {I2, I3}, {I1, I3}。所以I3对应的频繁项集就是{I2, I1, I3}, {I2, I3}, {I1, I3}。
step4：整合每个项的频繁项集，就是答案啦
- 其余的两个项也是同样的操作过程，最终的每个项对应的频繁项集如下表所示：
| item |
frequent itemsets |
| I5 |
{I2, I1, I5}, {I2, I5}, {I1, I5} |
| I4 |
{I2, I4} |
| I3 |
{I2, I3}, {I1, I3}, {I2, I1} |
| I1 |
{I2, I1} |
例子2
35 为什么进行关联规则的主观性测试？有哪些指标及其特点（提升度）
背景
- 最终，只有用户才能确定一个规则是否有趣的，而且这种判断是主观的，因不同的用户而异；通常认为一个规则（模式）是有趣的，如果：
- 它是出人意料的
- 可行动的（用户可以使用该规则做某些事情）
- 支持度和置信度度量不足以过滤掉无趣的关联规则。
指标————提升度
$$
\text{lift}(A, B) = \frac{\text{support}(A \cup B)}{\text{support}(A) \times \text{support}(B)} = \frac{P(A \cup B)}{P(A)P(B)}
$$
- 当项集A的出现独立于项集B时，$P(A∪B)=P(A)P(B)$，即 $lift(A,B)＝1$ ，表明A与B无关，$lift(A,B) >1$ 表明A与B正相关，$lift(A,B) <1$ 表明A与B负相关
- $\text{lift}(A, B) = 1$：A和B独立，无关联
- $\text{lift}(A, B) > 1$：A和B正相关，A的出现增加了B出现的概率（有趣）
- $\text{lift}(A, B) < 1$：A和B负相关，A的出现反而减少了B出现的概率
指标————χ²（chi-square）指标
$$
\chi^2 = \sum_{i=1}^n \frac{(Observed_i - Expected_i)^2}{Expected_i}
$$
- χ²值越大，说明观测值与期望值的偏离越大，A和B之间的关联越强，规则越有趣。
- χ²值越小，说明A和B接近独立，规则不显著、不有趣。
- 可以查χ²分布表，根据自由度和显著性水平判断是否显著（如p < 0.05）。
36 提升度的内涵（新）
- 衡量两个项集之间关联强度和相关性的指标。它反映了在已知A发生的情况下，B发生的概率与A和B独立时B发生概率的比值。
- $\text{lift}(A, B) = 1$：A和B独立，无关联
- $\text{lift}(A, B) > 1$：A和B正相关，A的出现增加了B出现的概率（有趣）
- $\text{lift}(A, B) < 1$：A和B负相关，A的出现反而减少了B出现的概率
37 序列挖掘的相关概念
序列挖掘
- 序列挖掘或称序列模式挖掘，是指从序列数据库中发现蕴涵的序列模式。
- 序列挖掘一般是指相对时间或者其他顺序出现的序列的高频率子序列的发现，典型的应用还是限于离散型的序列。
- 序列模式分析旨在寻找事件间在顺序上的相关性。
例子
- 凡是买了喷墨打印机的顾客中，80%的人在三个月之后又买了墨盒 。
- 两年前购买了Ford 牌轿车的顾客，很可能在今年采取贴旧换新的购车行动。
- 购买了自行车的客户中，70%的客户会在两个月后购买打气筒。
序列模式挖掘概述
项集
- 设 $ I={i_1，i_2，…，i_n} $ 是所有项的集合，在购物篮例子中，每种商品就是一个项。项集是由项组成的一个非空集合。
事件
- 事件（events）是一个项集，在购物篮例子中，一个事件表示一个客户在特定商店的一次购物，一次购物可以购买多种商品，所以事件表示为（x1，x2，…，xq），其中xk（1≤k≤q）是I中的一个项，一个事件中所有项均不相同，每个事件可以有一个事件时间标识TID，也可以表示事件的顺序。
序列
- 序列（sequence）是事件的有序列表，序列s记作 $<e_1，e_2，…，e_l>$，其中ej（1≤j≤l）表示事件，也称为s的元素。
- 通常一个序列中的事件有时间先后关系，也就是说，ej（1≤j≤l）出现在ej+1之前。序列中的事件个数称为序列的长度，长度为k的序列称为k-序列。在有些算法中，将含有k个项的序列称为k-序列。
序列数据库
- 是元组 $<SID，s>$ 的集合，其中SID是序列编号，s是一个序列，每个序列由若干事件构成。
子序列
- 对于序列t和s，如果t中每个有序元素都是s中一个有序元素的子集，则称t是s的子序列。
- 形式化表述为，序列 $t=<t_1，t_2，…，t_m>$ 是序列 $s=<s_1，s_2，…，s_n>$ 的子序列，如果存在整数 $1≤j_1<j_2<…<j_m≤n$，使得 $t_1 \subset S_{j_1}, t_2 \subset S_{j_2},…,t_m \subset S_{j_m}$
最大序列
- 两个序列 $A= <a_1,a_2…a_n>$ 和 $B= <b_1,b_2…b_m>$ ，如果存在整数 $i_1<i_2<…<i_n$ 且 $a_1$ 包含于 $b_{i_1}，a_2$ 包含于 $b_{i_2}，…，a_n$ 包含于 $b_{i_n}$ ，则称序列a包含于序列b。在一个序列集中如果序列s不包含于任何其它序列中，则称序列s为最大的。
- 如果一个序列s不包含在序列数据库S中的任何其他序列中，则称序列s为最大序列。
支持度
- 一个序列α的支持度计数是指在整个序列数据库S中包含α的序列个数。即：
$$
supportS(\alpha)=| {(SID,S)|(SID,s)∈S且\alpha 是s的子序列}|
$$
- 其中|α|表示α出现的次数，若序列α的支持度计数不小于最小支持度阈值min_sup，则称之为频繁序列，频繁序列也称为序列模式。
- 长度为k的频繁序列称为频繁k-序列。
序列模式挖掘
- 给定一个序列数据库D以及最小支持度阈值min_sup，从中找出所有支持度计数不小于min_sup的序列，这些频繁序列也称为序列模式。
序列模式挖掘算法AprioriAll算法
步骤
- 排序阶段。数据库D以客户号为主键，交易时间为次键进行排序。这个阶段将原来的事务数据库转换成由客户的序列组成的数据库。
- 频繁项集阶段。找出所有频繁项集组成的集合L。也同步得到所有频繁1-序列组成的集合。
- 转换阶段。在找序列模式的过程中，要不断地进行检测一个给定的频繁集是否包含于一个客户序列中。
- 序列阶段。利用已知的频繁集的集合来找到所需的序列。类似于关联的Apriori算法。
- 最大化阶段。在频繁序列模式集合中找出最大频繁序列模式集合
例子
- 排序阶段
- 频繁项集阶段
- 转换阶段
- 每个事件被包含于该事件中所有频繁项集替换。
- 如果一个事件不包含任何频繁项集，则将其删除。
- 如果一个客户序列不包含任何频繁项集，则将该序列删除。
- 产生频繁序列阶段
- 最大化阶段
38 apriori-all算法（原理，例子）
//39 GSP算法（原理，例子）（不考了，明确说了）
40 决策树算法（原理，例子）（新）
ID3算法
信息熵
|
类别1 |
类别2 |
… |
类别n |
| 类别概率 |
$p_1$ |
$p_2$ |
… |
$p_n$ |
| 信息量 |
$-log(p_1)$ |
$-log(p_2)$ |
… |
$-log(p_n)$ |
- 在一个样本集合 $X$ 中，其可以划分为 $n$ 类样本，而且每一类所占的比例为 $p(x_i)$ ，则 $X$ 的信息熵定义为：
$$
H(X) = -\sum_{i=1}^n p(i) \log_2 p(i)
$$
条件熵
$$
H(X|Y) = -\sum_{j=1}^m p(y_j) \sum_{i=1}^n p(x_i|y_j) \log_2 p(x_i|y_j)
$$
信息增益
- 信息增益=划分前的信息熵-划分后的信息熵
ID3算法基本思想
- 在每一步选择信息增益最大的特征进行划分，递归地构建决策树，直到所有样本被正确分类或没有可用特征为止。
ID3步骤
- 计算信息熵：计算当前样本集合的熵，衡量集合的不确定性。
- 计算信息增益：对每个特征，计算用该特征划分数据后信息熵的减少量（即信息增益）。
- 选择最优特征：选择信息增益最大的特征作为当前节点的划分特征。
- 递归构建子树：对每个分支上的子集，重复上述过程，直到满足停止条件（如样本全属于同一类别或特征用尽）。
- 生成决策树：最终得到一棵以信息增益为划分标准的决策树。
朴素贝叶斯分类
贝叶斯公式
$$
P(Y|X_1,X_2,…,X_n)=\frac{P(X_1,X_2,…,X_n|Y)*P(Y)}{P(X_1,X_2,…,X_n)}=\frac{P(X_1|Y)P(X_2|Y)…*P(X_n|Y)*P(Y)}{P(X_1,X_2,…,X_n)}
$$
例子
41 关于基于混淆矩阵的几个主要指标及其作用；特别是召回率和精度（新）
混淆矩阵
指标
例子
42 划分聚类基本思想和原理，k-means, K-medoid算法（原理，例子）
k-means算法
思想
- k平均算法以k-为参数，把n个对象分为k个簇，以使簇内具有较高的相似度。相似度的计算根据一个簇中对象的平均值来进行
- 算法首先随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇，然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。
$$
E = \sum_{j=1}^k \sum_{x∈C_i} | x - \bar{x_i} |^2
$$
- 其中x是空间中的点，表示给定的数据对象， $\bar{x_i}$ 是簇Ci的平均值。这个准则可以保证生成的簇尽可能的紧凑和独立。
伪代码
例子
k-medoid算法
思想
- 为每个簇随机选择一个代表对象(中心点)；
- 剩余的对象根据其与代表对象的距离分配给与其最近的一个簇；
- 反复地用非代表对象来替换代表对象，以提高聚类的质量，直至找到最合适的中心点。
- 聚类结果的质量用一个代价函数来估算, 该函数评估了对象与其参照对象之间的平均相异度
43 层次聚类基本思想和原理，AGNES, DIANA算法（原理，例子）
AGNES算法
过程
- 首先，将数据集中的每个样本作为一个簇；
- 然后，根据某些准则将这些簇逐步合并；
- 合并的过程反复进行，直至不能再合并或者达到结束条件为止。
- 合并准则：每次找到距离最近的两个簇进行合并
- 两个簇之间的距离由这两个簇中距离最近的样本点之间的距离来表示。
伪代码
- 算法 AGNES（自底向上凝聚算法）
- 输入：包含n个对象的数据库，终止条件簇的数目k。
- 输出：k个簇，达到终止条件规定簇数目。
- (1) 将每个对象当成一个初始簇；
- (2) REPEAT
- (3) 根据两个簇中最近的数据点找到最近的两个簇；
- (4) 合并两个簇，生成新的簇的集合；
- (5) UNTIL 达到定义的簇的数目；
连接方法
- 单连接：两个簇中离得最近的点的距离
- 完全链接：两个簇中最远的两个点的距离
- 组平均：所有点距离的平均值
例子
DIANA算法
伪代码
- 算法 DIANA（自顶向下分裂算法）
- 输入：包含n个对象的数据库，终止条件簇的数目k。
- 输出：k个簇，达到终止条件规定簇数目。
- （1）将所有对象整个当成一个初始簇；
- （2） FOR(i=1;i≠k;i++)DOBEGIN
- （3） 在所有簇中挑出具有最大直径的簇C；
- （4） 找出C中与其它点平均相异度最大的一个点p并把p放入splinter group，剩余的放在oldparty中；
- （5）. REPEAT
- （6） 在old party里找出到最近的splinter group中的点的距离不大于到old party中最近点的距离的点，并将该点加入splinter group。
- （7） UNTIL没有新的oldparty的点被分配给splintergroup；
- （8） splinter group和old party为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。
- （9） END.
例子
44 BIRCH算法相关概念，基本思想，例子
聚类特征CF
- N：簇中有多少个点
- LS：线性和
$$
\vec{LS} = \sum_{i=1}^N \vec{x_i}
$$
- SS：平方和
$$
SS = \sum_{i=1}^N |\vec{x_i}|^2 = \sum_{i=1}^N \sum_{j=1}^d (x_{ij})^2
$$
几个量
- 质心
$$
\text{Centroid} = \frac{\vec{LS}}{N}
$$
- 半径
$$
R = \sqrt{\frac{1}{N} \sum_{i=1}^N |\vec{x_i} - \vec{C}|^2} = \sqrt{\frac{SS}{N} - |\frac{\vec{LS}}{N}|^2} = \sqrt{\frac{SS}{N} - |\vec{C}|^2}
$$
- 直径
$$
D = \sqrt{\frac{1}{N(N-1)} \sum_{i=1}^N \sum_{j=1}^N |\vec{x_i} - \vec{x_j}|^2}= \sqrt{\frac{2N \cdot SS - 2|\vec{LS}|^2}{N(N-1)}}
$$
例子
- $x_1=0.5,x_2=0.25,x_3=0,x_4=0.65,x_5=1,x_6=1.4,x_7=0.1$
- 阈值T=0.15：叶子节点的半径不超过0.15
- 叶子节点 L=2 中的条目数
- 分支因子 B=2:每个非叶子节点的子节点的最大数目
45 Chameleon基本思想和步骤
思想
- 当合并后的结果簇类似于原来的两个簇时，这两个簇才应当合并。
伪代码
46 密度聚类相关概念（邻域，密度可达等）
47 DB-SCAN算法，例子
思想
- 任意两个足够靠近(相互之间的距离在ε之内)的核心点将放在同一个簇中。类似地，任何与核心点足够靠近的边界点也放到与核心点相同的簇中(如果一个边界点靠近不同簇的核心点，则可能需要解决平局问题)，噪声点被丢弃。
描述
- DBSCAN算法描述
- 算法5-5 DBSCAN
- 输入：包含n个对象的数据库，半径ε，最少数目MinPts。
- 输出：所有生成的簇，达到密度要求。
- 1.任意选取一个点 p
- 2.repeat
- 得到所有从p关于 Eps和 MinPts密度可达的点.
- 如果p是一个核心点, 则找到一个聚类.
- 如果 p是一个边界点, 没有从p密度可达的点, DBSCAN 将访问数据库中的下一个点.
- 3.until 数据库中的所有点都被处理.
例子
48 OPTICS算法如何由结果图进行聚类
49 什么是离群点？离群点挖掘有什么意义？主要有哪几类方法
离群点
- 在样本空间中，与其他样本点的一般行为或特征不一致的点
意义
- 发现与大部分其他对象显著不同的对象，大部分数据挖掘方法都将这种差异信息视为噪声而丢弃，但在一些应用中，罕见的数据可能蕴含更大的研究价值。此外还可以分析数据并及时发现异常。
方法
- 基于统计的方法
- 基于距离的方法
- 基于密度的方法
- 基于聚类的方法
- 基于偏差的方法
- 基于深度的方法
- 基于小波变换的方法
- 基于神经网络的方法…
50 基于距离和密度的离群点发现方法（相关概念，K最邻近距离，原理，例子）
K-近邻邻域
- 采用给定邻域半径，依据点的邻域中包含的对象多少来判定离群点
- 如果一个点的邻域内包含的对象少于整个数据集的一定比例则标识它为离群点，也就是将没有足够邻居的对象看成是基于距离的离群点。
K-最近邻距离
- 一个对象的离群点得分由到它的k-最近邻的距离给定。
- 离群点得分的最低值为0，最高值是距离函数的可能最大值—-如无穷大
51 基于聚类的离群点发现方法（原理，例子）
原理
