数据挖掘期末指南

数据挖掘复习指南

第一部分：概述与核心概念

1. 数据挖掘的定义与目标

基本定义

• 数据挖掘：从大量数据中发现潜在的、有用的模式、信息、知识、规律和模型的过程

与KDD的关系

• KDD是指从数据中发现有用知识的整个过程，而数据挖掘是特定算法的应用，用于从数据中提取模式。

• KDD（知识发现）：数据挖掘是KDD过程中的一个关键步骤

• KDD是更广泛的概念，包括：数据选择、预处理、变换、数据挖掘和评估等

核心任务

数据挖掘能做什么：

1. 预测 (Prediction)：通过分类或估值模型对未知变量进行预测

   • 分类 (Classification)：输出离散类别
   • 估值/回归 (Estimation/Regression)：输出连续值

2. 聚类 (Clustering)：无监督分类，将数据对象分组，组内相似度高，组间相似度低

3. 关联分析 (Association Analysis)：发现数据项之间的关联规则（如购物篮分析）

4. 异常分析 (Anomaly Detection)：识别数据中不寻常的模式或离群点

跨学科特性

• 相关领域：机器学习、统计学、OLAP、专家系统、模式识别、数据库技术、人工智能、可视化技术、并行计算等

数据挖掘流程

• 主要阶段：数据预处理 → 特征提取 → 选择模型（模型训练）→ 评估与优化 → 测试

第二部分：数据类型与属性

1. 属性与属性值

基本概念

• 属性 (Attribute)：指数据的特征或维度
  • 例如：身高、眼球颜色
• 属性值 (Attribute Value)：该属性具体可取的量
  • 例如：170cm、蓝色

重要区别

• 相同的属性可映射到不同值域
• 不同属性可映射到同一组值，但性质不同
  • 例如：ID无上限，年龄有最大最小值

2. 属性的类型 (Measurement Scale)

标称属性 (Nominal Attribute)

• 特点：值仅是不同名字，提供区分对象的信息（=, ≠），无序
• 例子：邮政编码、雇员ID号、眼球颜色、性别
• 可用操作：众数、熵、列联相关、χ² 检验

序数属性 (Ordinal Attribute)

• 特点：值提供确定对象顺序的信息（<, >）
• 例子：矿石硬度、{好，较好，最好}、成绩、街道号码
• 可用操作：中值、百分位、秩相关、游程检验、符号检验

区间属性 (Interval Attribute)

• 特点：值之间的差有意义，存在测量单位（+, -），无绝对零点
• 例子：日历日期、摄氏或华氏温度
• 可用操作：均值、标准差、皮尔逊相关、t和F检验

比率属性 (Ratio Attribute)

• 特点：差和比率都有意义（*, /），有绝对零点
• 例子：绝对温度、货币量、计数、年龄、质量、长度、电流
• 可用操作：几何平均、调和平均、百分比变差

属性分类总结

• 分类属性 (Qualitative)：标称和序数
• 数值属性 (Quantitative)：区间和比率
• 属性值的性质：相异性（=, ≠）、序（<, >）、加法（+, -）、乘法（*, /）

3. 离散与连续属性

离散属性 (Discrete Attribute)

• 特点：有限或无限可数个值，常表示为整数变量
• 特例：二元属性
• 例子：邮政编码、计数、文档集的词

连续属性 (Continuous Attribute)

• 特点：属性值为实数，一般用浮点变量表示
• 例子：温度、高度、重量

第三部分：数据集特性与类型

1. 数据集的重要特性

维度相关特性

• 维度 (Dimensionality)：数据集中对象具有的属性数目
• 维灾难 (Curse of Dimensionality)：
  • 随着数据维度增加，数据在空间中越来越稀疏
  • 许多数据分析变得困难
  • 导致分类准确率降低，聚类质量下降

其他重要特性

• 稀疏性 (Sparsity)：
  • 具有非对称特征的数据集
  • 一个对象的大部分属性上的值都为0
  • 只存储和处理非零值
• 分辨率 (Resolution)：模式依赖于度量尺度

2. 数据集类型

记录数据 (Record Data)

1. 数据矩阵 (Data Matrix)

   • 对象具有相同的固定数值属性集
   • 表示为 m×n 矩阵

2. 文档数据 (Document Data)

   • 每个文档视为一个向量
   • 值是对应术语出现次数

3. 事务数据 (Transaction Data)

   • 每条记录（事务）涉及一组项目
   • 例如：购物清单

有序数据 (Ordered Data)

1. 时间序列数据 (Time Series Data)

   • 一段时间的测量序列
   • 具有时间自相关性

2. 空间数据 (Spatial Data)

   • 具有空间属性
   • 具有空间自相关性

3. 序列数据 (Sequential Data)

   • 时间次序重要但具体时间不重要
   • 例如：基因序列

基于图的数据 (Graph-based Data)

• 特点：对象之间有联系或对象具有结构
• 例子：分子结构

第四部分：数据质量与预处理

1. 数据质量问题

常见数据质量问题

1. 离群点 (Outliers)

   • 与数据集中其他大部分数据对象特征不同的对象

2. 遗漏值 (Missing Values)

   • 信息未收集全或属性不适用
   • 处理策略：
     • 删除数据对象
     • 估计遗漏值
     • 分析时忽略
     • 用所有可能值替换

3. 不一致值

   • 矛盾或不匹配的值（如邮政编码与城市不符）
   • 纠正需附加信息

4. 重复数据 (Duplicate Data)

   • 冗余或几乎冗余的数据对象
   • 合并异构数据源时的主要问题

数据质量问题的根源

• 测量误差和数据收集错误：导致数据质量问题

数据清理 (Data Cleaning)

• 主要任务：
  • 格式标准化
  • 异常数据清除
  • 错误纠正
  • 重复数据清除

应用层面的问题

• 时效性 (Timeliness)：数据过时导致模型过时
• 相关性 (Relevance)：数据必须包含应用所需信息

2. 数据预处理方法

聚集 (Aggregation)

• 定义：组合属性或对象
• 目的：数据规约、范围转换、数据更稳定

抽样 (Sampling)

• 定义：选择数据对象子集，目的在于数据规约
• 基本原则：代表性（保留原数据集性质）
• 抽样方法：
  • 简单随机抽样（无放回、有放回）
  • 分层抽样（按个数或比例）
• 样本大小：足够大才能保留数据集结构
• 渐进抽样 (Progressive Sampling)：从小样本开始，逐渐增加容量直到模型准确率稳定

维归约 (Dimensionality Reduction)

• 定义：减少属性数目
• 目的：
  • 避免维度灾难
  • 降低算法开销
  • 便于可视化
  • 减少不相关特征或噪音
• 主要技术：
  • 主成分分析 (PCA)：找到原有属性线性组合，相互正交，捕获最大变差
  • 奇异值分解 (SVD)

特征子集选择 (Feature Subset Selection)

• 定义：识别并移除不相关或冗余特征
• 特征类型：
  • 冗余特征：重复信息
  • 不相关特征：对任务无用的信息
• 选择方法：
  • 嵌入方法：结合数据挖掘算法（如决策树）
  • 过滤方法：独立于算法
  • 包装方法：算法作为黑盒评估性能
  • 穷举方法

特征构造 (Feature Creation)

• 定义：创建更能体现对象本质的新特征
• 方法类型：
  • 特征提取：领域相关或映射到新空间（如傅里叶变换、小波变换）
  • 特征构造：一个或多个原始特征构造新特征（如密度=质量/体积）

离散化与二元化 (Discretization and Binarization)

• 目的：
  • 减少属性值个数
  • 便于挖掘
  • 产生概念分层结构
  • 适应算法要求
• 离散化类型：
  • 非监督离散化：不使用类信息
    • 等宽、等频、K-均值离散化
  • 监督离散化：使用类信息
    • 基于熵的方法：极大化区间纯度（最小化熵）
• 二元化方法：
  • 映射到整数再二进制化（不适合非对称属性）
  • 对每个值建立二元变量

属性变换 (Attribute Transformation)

• 定义：将属性值集映射到新值集
• 变换类型：
  • 简单变换：x^k, log(x), e^x, |x|, 1/x 等函数
  • 标准化/规范化：使值集具有特定性质（如均值0，标准差1）

第五部分：相似性和相异性的度量

1. 基本概念

核心定义

• 相似性 (Similarity)：数值度量相似程度，值越高越相似
• 相异性 (Dissimilarity)：数值度量差异程度，值越低越相似，最小为0
• 邻近性 (Proximity)：指相似或不同之处

2. 距离度量

欧氏距离 (Euclidean Distance)

• 定义：两点之间直线距离，最常见
• 公式：d(x,y) = √(Σ(xₖ - yₖ)²)

闵可夫斯基距离 (Minkowski Distance)

• 定义：欧氏距离的推广
• 特殊情况：
  • r=1：城市街区距离 (Manhattan, L1范数)，如汉明距离
  • r=2：欧氏距离
  • r→∞：上确界距离 (L∞范数)，最大差异

距离的性质 (度量 Metric)

1. 非负性：d(x,y) ≥ 0，且 d(x,y)=0 当且仅当 x=y
2. 对称性：d(x,y) = d(y,x)
3. 三角不等式：d(x,z) ≤ d(x,y) + d(y,z)

非度量的相异度

• 不满足一个或多个度量性质（如集合差、时间）

3. 数据对象间的相似度

常用相似度度量

1. 简单匹配系数 (SMC)

   • 匹配属性个数 / 总属性个数

2. Jaccard系数

   • 不涉及0-0匹配的属性个数

3. 余弦相似度 (Cosine Similarity)

   • 衡量向量方向的相似性
   • 公式：cos(x,y) = (x·y) / (||x|| × ||y||)

4. 相关性 (Correlation)

   • 对象属性之间线性联系的度量
   • 范围：-1到1

4. 邻近度计算的实际问题

主要挑战

1. 标准化和相关性

   • 属性值域不同时需变换到相同值域
   • 属性相关时使用Mahalanobis距离

2. 组合异种属性的相似度

   • 对不同类型属性分别计算并加权求和

3. 属性权重问题

   • 使用权值加权的相似度或闵可夫斯基距离

第六部分：分类算法

1. 分类模型评估基础

混淆矩阵 (Confusion Matrix)

• 定义：总结分类模型性能的表格
• 基本概念：
  • TP (True Positive)：真正例，实际为正预测为正
  • FN (False Negative)：假反例，实际为正预测为负
  • FP (False Positive)：假正例，实际为负预测为正
  • TN (True Negative)：真反例，实际为负预测为负

评估指标

1. 准确率 (Accuracy)

   • 公式：(TP + TN) / (TP + FN + FP + TN)
   • 局限性：类别不平衡时可能误导

2. 其他重要度量

   • 真正率 (TPR) / 灵敏度 (Sensitivity)
   • 真负率 (TNR) / 特异度 (Specificity)
   • 假正率 (FPR)
   • 假负率 (FNR)
   • 召回率 (Recall)
   • 精度 (Precision)
   • F1度量

3. ROC曲线

   • 定义：绘制TPR vs FPR
   • 用途：评估分类器性能
   • AUC：曲线下面积，重要指标

2. K-近邻分类 (K-Nearest Neighbors, KNN)

基本原理

• 定义：记录x的K近邻是与x距离最近的k个数据点
• 判断过程：
  1. 计算已知样本与未知样本的距离
  2. 找到k个最近样本
  3. 通过多数表决（或距离加权表决）确定类别

K值选择的影响

• K太小：
  • 对噪声敏感
  • 模型复杂
  • 易过拟合
• K太大：
  • 邻域可能包含其他类点
  • 模型简单

算法特点

• 优点：
  • 基于实例的学习（惰性学习）
  • 非参数估计
  • 生成任意形状的决策边界
• 缺点：
  • 需要邻近性度量
  • 分类开销大
  • 无显式学习过程
  • 需要数据预处理

3. 贝叶斯分类器

贝叶斯定理

• 公式：P(Y=yⱼ|X) = P(X|Y=yⱼ)P(Y=yⱼ) / P(X)
• MAP (最大后验假设)：将X指派到具有最大后验概率P(yⱼ|X)的类yⱼ
• 先验概率P(yⱼ)：由训练集中类yⱼ的样本数nⱼ与总样本数n的比值nⱼ/n估计

朴素贝叶斯分类器 (NBC)

• 核心假设：条件独立假设
  • 给定样本的类标号，假定属性值条件地相互独立
• 概率估计：
  • P(X|Y=yⱼ) = ∏P(xᵢ|yⱼ)
  • 离散属性：用频率估计
  • 连续属性：假设服从高斯分布

NBC的优缺点

• 优点：
  • 对孤立噪声点有鲁棒性
  • 能处理属性值缺失
  • 对无关属性有鲁棒性
• 缺点：
  • 条件独立假设可能不成立

贝叶斯信念网络 (BBN)

• 改进：允许在变量子集间定义类条件独立性
• 结构：因果关系图模型
  • 节点表示随机变量
  • 边表示依赖关系
  • 图中无环
• 特点：
  • 用图形模型捕获先验知识
  • 编码因果依赖关系
  • 构造费时但添加新变量容易
  • 适合处理不完整数据
  • 对过拟合鲁棒

4. 决策树分类器

基本原理

• 算法特性：贪心算法，自上而下分而治之，递归分割
• 属性选择：基于启发式或统计度量
• 停止条件：
  • 节点数据都属同一类别
  • 没有属性可再用于分割

不纯性度量 (Impurity Measure)

• 目的：衡量节点内数据类别分布的均匀性（越均匀越不纯）
• 主要度量：
  • 熵 (Entropy)：衡量系统无序程度，熵越大越无序
  • 基尼系数 (Gini Index)：衡量随机抽取两样本类别不一致的概率
  • 分类误差 (Classification Error)

划分增益

• 目的：衡量划分后不纯度的降低，增益越大越有利于分类
• 主要指标：
  • 信息增益 (Information Gain)：当不纯度用熵度量时的增益
  • 增益率 (Gain Ratio)：解决熵和基尼系数倾向于多值属性的问题

最佳划分策略

• 过程：
  1. 对每个属性确定最佳划分（不纯度最低）
  2. 选择增益最大的属性
• 连续属性处理：排序后取相邻不同类值中点作为划分点

决策树特点

• 基本性质：

  • 非参数方法
  • 贪心算法
  • NP完全问题
  • 决策边界是直线（平面），平行于坐标轴

• 优点：

  • 快速建立模型和分类
  • 分类准确率高
  • 适合固定属性记录数据
  • 相对容易解释
  • 对噪声鲁棒
  • 可避免过拟合
  • 自动选择最好属性

• 缺点：

  • 数据碎片问题
  • 子树可能重复
  • 平行于坐标轴的边界限制能力

5. 模型的过拟合与剪枝

误差类型

1. 训练误差 (Training Error)

   • 模型在训练集上的误分类比例

2. 泛化误差 (Generalization Error)

   • 模型在未知记录上的期望误差
   • 通常在检验集上估计

拟合问题

1. 欠拟合 (Underfitting)

   • 训练和检验误差都很大
   • 原因：模型假设空间太小或偏离

2. 过拟合 (Overfitting)

   • 训练误差小，但检验误差大
   • 原因：模型过度拟合训练数据，巨大的模型假设空间与稀疏数据矛盾
   • 具体原因：噪声、缺乏代表性样本

剪枝 (Pruning)

• 目的：降低决策树复杂度，解决过拟合

评估方法

1. 在训练集上估计

   • 训练误差结合模型复杂度
   • 悲观误差评估
   • 最小描述长度(MDL)

2. 使用确认集 (Validation Set)

   • 将训练数据分为训练子集和确认集
   • 确认集用于估计泛化误差

剪枝策略

1. 预剪枝 (Pre-pruning)

   • 提前停止树的构造

2. 后剪枝 (Post-pruning)

   • 先构造完整的树
   • 再剪掉不必要的分支

6. 分类模型评估方法

基本评估方法

1. 保持 (Holdout) 方法

   • 划分：2/3训练，1/3检验
   • 局限性：训练样本少，模型高度依赖数据集构成

2. 随机二次抽样 (Random Subsampling)

   • 重复保持方法k次，取平均准确率

3. 交叉验证 (Cross-validation)

   • K折交叉验证：
     • 数据集划分为k个不相交子集
     • k-1份训练，1份测试，重复k次
   • 留一法 (Leave-one-out)：
     • k=n，每个样本单独作为测试集

统计评估

1. 准确率的置信区间

   • 提供区间估计，衡量测量结果的可信程度

2. 模型性能比较

   • 通过比较误差率的差值是否统计显著
   • 使用t-分布计算置信区间

7. 集成学习 (Ensemble Learning)

基本思想

• 聚集多个分类器的预测以提高分类准确率

主要算法

1. Adaboost

   • 迭代训练基分类器
   • 每次调整训练样本权重
   • 对误分类样本赋予更高权重
   • 后续分类器更关注这些样本
   • 最终通过基分类器的加权投票产生预测

2. 随机森林 (Random Forest)

   • 多棵CART树的组合
   • 每棵树的训练集有放回采样
   • 训练节点时特征随机无放回抽取

3. Rotation Forest

   • 使用整个训练集建立多个基分类器
   • 通过不同特征变换将数据变换到不同新特征空间

特殊问题处理

1. 代价敏感学习 (Cost-sensitive Learning)

   • 考虑不同类型错误（如漏报、假警告）的代价

2. 不平衡数据问题 (Imbalanced Data)

   • 基于抽样：
     • 欠抽样 (Undersampling)：可能丢失有用样本
     • 过抽样 (Oversampling)：可能导致过拟合噪声样本
     • 组合方法：Undersampling + Oversampling
   • 两阶段学习：分阶段学习规则，如PN-Rules

第七部分：聚类分析 (无监督学习)

1. 聚类概述

学习类型对比

• 有监督学习：有标记，学习假设函数确定决策分界
• 无监督学习：无标记，算法对同一类的进行划分

基本概念

• 簇 (Cluster)：一个数据对象的集合，簇内对象相似性高，簇间相异性高
• 聚类分析：将给定数据对象集合分成不同的簇，是一种无监督分类法

好的聚类方法标准

• 高质量聚类结果（高簇内相似性、低簇间相似性）
• 能发现隐含模式

聚类算法要求

• 可伸缩性
• 发现任意形状簇
• 无需特定领域知识确定输入参数
• 处理噪声和异常
• 对输入数据顺序不敏感
• 处理高维数据
• 产生满足用户约束的可解释结果

聚类类型

1. 按结构分类：

   • 划分聚类 (Partitioning Clustering)：数据对象划分为不重叠的k个簇
   • 层次聚类 (Hierarchical Clustering)：簇具有子簇

2. 按覆盖方式分类：

   • 互斥、重叠与模糊
   • 完全聚类、部分聚类

2. 主要聚类方法分类

按算法原理分类

• 划分算法：构建数据的k个划分
• 层次算法：对数据对象集合进行层次分解
• 基于密度算法：基于连通性和密度函数聚类
• 基于网格算法：对象空间量化为网格，操作在网格中进行
• 基于模型算法：为每个簇假定一个模型

3. 划分聚类算法

K-均值 (K-means)

• 地位：最广泛使用的聚类算法

算法流程

1. 随机选择k个初始簇中心
2. 将每个对象赋给最近的簇
3. 重新计算每个簇的平均值
4. 重复直到准则函数收敛

优缺点分析

• 优点：

  • 简单、快速
  • 对大数据集可伸缩
  • 高效，当簇密集时效果好

• 缺点：

  • 需事先给定k
  • 对初值敏感
  • 不适合非凸面或大小差别很大的簇
  • 对噪声和孤立点敏感

算法变形

• 改进方向：
  • 初始K个平均值的选择
  • 相异度计算
  • 簇均值策略
• 处理分类属性：
  • K-modes
  • K-原型

K-中心点 (K-medoids) / PAM

• 特点：每个簇用接近聚类中心的一个中心点表示

4. 层次聚类方法

基本定义

• 对给定数据集进行层次分解

层次聚类类型

1. 凝聚的层次聚类 (AGNES)

   • 策略：自底向上，每个对象一个簇，逐步合并
   • 缺点：
     • 合并处理不能撤销，可能导致低质量聚类
     • 可伸缩性差，复杂度高O(n²)

2. 分裂的层次聚类 (DIANA)

   • 策略：自顶向下，所有对象一个簇，逐渐细分

簇间距离度量方法

• 最小距离 (Single Linkage)
• 最大距离 (Complete Linkage)
• 平均值距离 (Centroid Linkage)
• 平均距离 (Average Linkage)

5. 基于密度的方法 (DBSCAN)

核心概念

• 距离函数：度量样本点间关系
• Epsilon (ε)：距离阈值，定义邻域
• minPoints：邻域内的最小样本数

样本分类

1. 核心样本 (Core Point)

   • ε邻域内样本数 ≥ minPoints

2. 边界样本 (Border Points)

   • ε邻域内样本数 < minPoints
   • 且在某个核心样本的邻域内

3. 噪声样本 (Noise Points)

   • 不属于任何核心样本的邻域

密度连接概念

1. 密度直达：样本X在核心样本Y的邻域内
2. 密度可达：通过一系列核心样本的密度直达关系连接
3. 密度相连：两个样本X和Y都可以从同一个核心样本O密度可达

聚类过程

1. 随机寻找核心样本点
2. 推导其密度相连的点
3. 赋予簇编号
4. 重复直到所有核心样本点都有对应类别

DBSCAN优缺点

• 优点：

  • 能发现K-means不能发现的任意形状簇
  • 对噪声有鲁棒性

• 缺点：

  • 对高维数据处理能力不足
  • 簇密度变化较大时有问题

第八部分：关联分析

1. 基本概念

核心定义

• 关联规则 (Association Rules)：发现数据项之间有趣的关联关系，形如 X → Y
• 频繁项集 (Frequent Itemsets)：出现频率（支持度）高于最小支持度阈值的项集

重要度量

1. 支持度 (Support)

   • 项集在总事务中出现的百分比
   • 衡量项集的普遍性

2. 置信度 (Confidence)

   • 关联规则 X → Y 的置信度：P(Y|X) = Support(X∪Y) / Support(X)
   • 衡量规则的可靠性或强度

规则产生

• 从频繁项集中提取关联规则

2. Apriori算法

核心思想

1. 逐层算法

   • 从频繁1-项集到最长的频繁项集
   • 每次遍历项集格中的一层

2. 产生-测试策略

   • 产生新的候选项集
   • 对每个候选的支持度进行计数和比较

Apriori性质 (先验原理)

1. 正向性质：如果一个项集是频繁的，它的所有非空子集也必须是频繁的
2. 反单调性：如果一个项集是非频繁的，则它的所有超集也一定是非频繁的

算法步骤

1. 候选项集的产生与剪枝

   • 从频繁(k-1)-项集通过自连接产生k-项集
   • 利用Apriori性质剪掉非频繁候选项集

2. 支持度计数

   • 确定每个候选项集出现的频繁程度

3. 规则产生

   • 忽略前件或后件为空的规则
   • 每个频繁k-项集能产生多达 2^k-2 个关联规则
   • 利用置信度的反单调性进行剪枝：
     • 如果规则 X → Y-X 不满足置信度阈值
     • 则形如 X’ → Y-X’ 的规则（其中 X’ 是 X 的子集）也一定不满足置信度阈值

---

总结

本指南涵盖了数据挖掘的核心概念和主要算法，从数据预处理到具体的挖掘技术，为期末复习提供了系统性的知识框架。重点掌握各算法的原理、优缺点和适用场景，理解评估方法和实际应用中的问题处理策略。