《数据挖掘导论》学习笔记（第1-2章）

本文的学习内容主要集中在对《数据挖掘导论（完整版）》这本书的学习笔记上。其目的是为了帮助整理思路，并没有太多深入的思考。不过我计划在后续阶段进行补充和完善。

第1章 绪论

1.1 什么是数据挖掘

KDD： K nowledge D iscovery in D atabase
过程如下：

Created with Raphaël 2.1.0 输入数据 数据预处理 数据挖掘 后处理 信息

其中，数据预处理 包括如下几部分：

• 特征选择
• 维归约
• 规范化
• 选择数据子集

后处理 包括如下及部分：

• 模式过滤
• 可视化
• 模式表达

1.2 数据挖掘要解决的问题

• 弹性：针对日益增长的数据量进行设计
• 高维度：对象具有大量属性
• 异构化与复杂化的数据：涵盖多种类型的数据格式（如XML、文本以及流式数据等）
• 所有权与分布问题：涉及分布式计算处理
• 现代分析方法：要求自动生成并评估假设，并且所涉及的数据集多为时机性样本，而非随机性样本

1.4 数据挖掘任务

数据挖掘主要有如下两大类任务：

• 预测目标：基于特定属性进行预测其可能的结果值。其中，在这一过程中所使用的用于推断的因素被称为 说明性因素 或者 自变量 ，而其结果则对应地被定义为目标指标或 因变量 。
• 模式挖掘任务：通过分析数据识别出隐藏的规律性特征和结构关系。具体而言，则包括以下几大核心任务：
  • 探索数据间的关联性和相互作用
  • 分析数据演变的趋势和发展方向
  • 检测数据中的群体结构和分布特征
  • 识别数据中的异常点和不寻常现象

该鸢尾花分类问题的数据集可在链接中下载：Iris_dataset

    %% 鸢尾花分类

    clear all; close all; clc;
    
    %% 载入数据
    % data各列分别为 花萼长度，花萼宽度，花瓣长度，花瓣宽度，种类
    load iris_dataset;
    
    %% 画图
    % 花瓣长度 花瓣宽度 与 种类
    type1 = data(data(:, 5) == 1, 3:4);
    type2 = data(data(:, 5) == 2, 3:4);
    type3 = data(data(:, 5) == 3, 3:4);
    plot(type1(:, 1), type1(:, 2), 'o', type2(:, 1), type2(:, 2), 'o', type3(:, 1), type3(:, 2), 'o');
    xlabel('花瓣长度(cm)');
    ylabel('花瓣宽度(cm)');
    legend(unique(classes), 'Location', 'NorthWest');

• 关联性分析(association analysis) ：该技术用于识别数据集中高度相关的关系模式
  • 聚类分析(cluster analysis) ：该方法通过统计学手段实现对象分组，并通过计算得出各簇之间的相似度
  • 异常检测(anomaly analysis) ：该技术能够识别出那些具有显著差异性的一组数据点，并将其标记为异常值或离群点

第2章 数据

2.1 数据类型

数据集 一般被视为一个包含多个数据对象的数据集体。此外还可以被称为条目样本点矢量模板事件实例案例描述观察结果等。每个数据对象都由一组表征对象核心特征的属性构成。这些属性也可被称为变量特性字段特征维等。

2.1.1 属性和度量

我们对以下术语作出如下定义：
- 属性（attribute）：描述了物体的性质或特征
- 测量标度（measurement scale）：通过规则（function）将数值或符号值与物体的属性相联系，并可应用于各种情境中以获取信息

属性的值往往有如下几种性质：
1. 相异性
2. 序
3. 加法
4. 乘法
根据这些性质，可将属性分为四种类型：标称(nominal) 、序数(ordinal) 、区间(interval) 和比率(ratio)

基于保持属性不变的原则进行描述允许的变换(permissible transformation)

此外，基于属性的各种取值情况，我们可以将属性区分为离散型的(discrete)和连续型的(continuous)。

在分析中涉及**非对称属性（asymmetric attribute）**时，在其数值不为零时具有意义。例如，在这个数据集中

2.1.2 数据集的类型

• 一般特性：维度属性中包含稀疏度和分辨能力
  • 记录类型：事务记录型数据或购物篮式数据；以及基于矩阵形式呈现的稀疏型矩阵
    • 数据表示形式：基于关联关系的对象空间中呈现的数据（借鉴自图论原理）
  • 序列特性和空间特征
    • 时间序列特性和空间分布特征
    • 序列模式识别与空间特征提取技术并存的有序数据分析方法
  • 非结构化记录形式

2.2 数据质量

数据挖掘所使用的大量数据往往是用于其他目的收集而来，在收集过程中缺乏明确使用目标的情况下较多存在。因此，在这种情况下，这些原始数据的质量通常不高。而针对这种情况的数据处理，则主要关注两个方面：（1）对这类低质量原始数据进行质量检测并加以修正；（2）采用能够容忍较低质量原始数据的算法进行后续分析

2.2.1 测量和数据收集问题

以下是对原文内容的同义改写版本

2.2.2 关于应用的问题

• 时效性
• 相关性：常见问题有 抽样偏倚2
• 关于数据的背景知识

2.3 数据预处理

数据预处理旨在优化数据挖掘效果的同时，缩短分析所需的时间，并降低运行成本并提升数据分析质量。常用的预处理技术可分为两类：（1）筛选所需的数据集；（2）修改或添加属性。

2.3.1 聚集

聚集(aggregation) 将多个对象合并为一个单一的对象。考虑到以下数据集：记录每年每日各地区商店的日销售额的情况，则可以使用单个商店事务取代该商店的所有交易。

2.3.2 抽样

在数据挖掘领域中，在处理海量数据时成本较高这一挑战促使我们采用抽样方法以减少样本数量

有效抽样的本质在于若样本具有代表性，则其效果几乎等同于基于完整数据集的分析

常见的随机采样方法主要包括简单随机采样、分层随机采样以及系统随机采样等技术。其中, 简单随机采样的特点是无需附加分组或排序即可直接实施

2.3.3 维归约

当数据集中包含大量特征（属性）时，在低维空间中就更能凸显其优势。其主要功能体现在：在低维空间中许多数据挖掘算法的效果会更加出色，并能有效规避因维度过高导致的"维度灾难"；同时还能使模型更容易被理解和解释。

降维技术的常见手段基于线性代数原理，通过将高维度的数据投影到低维度的空间中进行处理。具体而言，主成分分析(Principal Component Analysis, PCA)和奇异值分解(Singual Value Decomposition, SVD)是最常用的两种方法。

2.3.4 特征子集选择

基于属性集合中选取若干特征的方法能够有效降低数据维度

• 嵌入式方法(embedded approach)：特征选择被视为数据挖掘领域的重要组成部分
• 过滤策略(filter approach)：采用一种不依赖于数据分析阶段的方法来进行特征筛选
• 包装策略(wrapper approach)：将目标数据分析算法视为一个不可见的处理方式，并通过类似穷举的方式来评估各种组合的可能性。然而，这种方法通常并不会穷举所有可能性。

特征子集选择包含四个组成部分：度量评估机制、用于调节新生成特征子集的搜索路径、设定终止条件的标准以及验证机制。过滤方法与包装方法的主要区别在于它们所采用的子集评价标准。

此外，在讨论完上述三种方法后, 还可以采用 特征加权 方式来决定哪些特定的特征需要被保留或删除。

2.3.5 特征创建

通常可用原有属性生成新属性集，并有效提取数据中的关键信息。与之相关的具体方法包括以下几种：
- 特征识别技术（如从图片中识别面部特征）
- 时间域变量转换为频率域（例如傅里叶变换）
- 通过原始属性开发新特性（如根据密度区分木头与金块）

2.3.6 离散化和二元化

一些数据挖掘算法仅在处理分类属性时有效，在这种情况下，则需要采用分段编码（discretization）或二进制编码（binarization）。

2.3.7 变量变换

变量转换(variable transformation) 是指作用于所有变量值的一种转换方式；具体包括以下几种常见的类型：如简单函数转换、标准化处理（standardization）以及规范化处理（normalization）。

2.4 相似性和相异性的度量

我们基于邻近性(proximity) 表征相似性或差异性，在此框架下, 物体间的邻近性通常依赖于其属性所对应的邻近性函数。

简单属性的相似度和相异度可以通过下表刻画：

欧几里德距离：

设 是维数；\boldsymbol x = (x_1, x_2, \dots, x_n) 和 \boldsymbol y = (y_1, y_2, \dots, y_n) 分别表示向量 \boldsymbol x 和 \boldsymbol y 的各个分量。
闵可夫斯基距离：参数 被设定为实数值。

这种测度被称为_度量(metric)_ ，因为它同时具备三条基本属性：第一条是非负性的体现，第二条是对称性的表现，第三条是三角不等式的应用。然而，在实际应用中，相似度通常不具备三角不等式这一特性，并且同时具备前两条属性。

这种测度被称为_度量(metric)_ ，因为它同时具备三条基本属性：第一条是非负性的体现，第二条是对称性的表现，第三条是三角不等式的应用。然而，在实际应用中，相似度通常不具备三角不等式这一特性，并且同时具备前两条属性。

相异度相似度的具体说明：
对于两个实体A与B来说，在具有n个二元属性的情况下进行比较时会涉及以下四个指标：

据此可以定义如下距离

• 简单匹配系数(Simple Matching Coefficient, SMC)：SMC=\frac{f_{00} + f_{11}}{f_{00} + f_{01} + f_{10} + f_{11}}
• Jaccard系数(Jaccard Coefficient)：J=\frac{f_{11}}{f_{01}+f_{10}+f_{11}}
• 余弦相似度(Cosine Similarity)：sim(u,v)=\frac{\sum\limits_If_u(I)\cdot f_v(I)}{\sqrt{\sum\limits_If_u(I)^2}\cdot \sqrt{\sum\limits_If_v(I)^2}}
• 广义Jaccard系数：g_j = \frac{\sum\limits_If_u(I)\cap f_v(I)}{\sum\limits_If_u(I)\cup f_v(I)}
• 相关性：其中相关性表示两个变量之间线性关系的程度
• Bregman散度：给定一个严格凸函数\phi（连同一些通常满足的适度限制），由该函数生成的Bregman散度D(\boldsymbol x, \boldsymbol y)由如下公式给出：其中\nabla\phi(\boldsymbol y)是在\boldsymbol y点计算的梯度，

D(\boldsymbol x, \boldsymbol y)=\phi(\boldsymbol x)-\phi(\boldsymbol y)-\left<\nabla\phi(\boldsymbol y), (\boldsymbol x - \boldsymbol y)\right>

若采用基于不同尺度的距离度量，则应首先进行标准化处理。当遇到属性间存在一定相关性的情况时，则建议采用马氏距离作为度量工具。其中\sum^{-1}表示数据协方差矩阵的逆矩阵。当各属性的重要性程度不一时，则可引入加权系数进行调整。若遇到属性类型差异较大的情况，则具体处理方法可参考以下步骤说明：

Created with Raphaël 2.1.0

判定条件为：某对象在该属性上存在缺失值，或该属性为非对称属性且两对象在该属性上的取值均为0； 公式表示为

其中， \delta=0,1， w_k为权重

1. 时间序列数据是一种独特的时序数据类型，在其中每个条目都代表一个完整的时序过程（例如：北京地区从1982年到1994年各年的逐月平均温度）。
2. 抽象偏倚（sample bias）指的是样本中不同类别的实例与总体中的分布不均衡现象。
3. 确定合适的样本容量往往面临挑战，在这种情况下，则可能采用渐进抽样法（progressive sampling），即先采用小规模抽样作为基础，在此基础上逐步扩大样本规模直至达到所需容量。
4. 维灾难（curse of dimensionality）是指当数据维度不断增加时，许多数据分析任务变得愈发复杂和困难，并且随着维度的增长（d→∞），数据在它们所占据的空间中变得愈发稀疏。