数据挖掘导论 第二章：数据
本章重点介绍了数据及其基本概念、数据质量问题与处理方法，以及数据预处理技术和衡量数据对象之间相似性与相异性的度量方法。
2.1 数据类型
- 数据：数据集是数据对象的集合。
- 数据对象 (Data Object)：用一组刻画其基本特性（如物体质量或事件发生时间）的属性描述。
- 其他名称：记录、点、向量、模式、事件、案例、样本、观测或实体。
- 属性 (Attribute)：对象的性质或特性。
- 其他名称：变量、特性、字段、特征或维。
- 例：眼球的颜色、温度。
- 测量标度 (Measurement Scale)：将数值或符号值与对象的属性相关联的规则（函数）。
- 属性 vs. 属性值
- 同样的属性可以映射到不同的值域中，例如身高可以用cm或m做单位。
- 不同属性可以映射到同一组值的集合，例如ID和年龄，但属性值的性质不同（ID没有上限，年龄有最大最小值）。
- 属性可以用一种不描述属性全部性质的方式测量。
- 属性的类型
- 属性可以通过数值的如下性质来描述：相异性 (= ≠), 序 (< >), 加法 (+ -), 乘法 (* /)。
- 标称属性 (Nominal)：
- 值仅仅只是不同的名字，只提供足够的信息以区分对象。
- 性质：相异性。
- 允许的变换：任何一对一变换（例如值的排列）。
- 例：邮政编码、雇员ID号、眼球颜色、性别。
- 允许的操作：众数、熵、列联相关、χ²检验。
- 序数属性 (Ordinal)：
- 值提供足够的信息确定对象的序。
- 性质：相异性、序。
- 允许的变换：值的保序变换（新值 = f(旧值), 其中f是单调函数）。
- 例：矿石硬度、{好，较好，最好}、成绩、街道号码。
- 允许的操作：中值、百分位、秩相关、游程检验、符号检验.
- 区间属性 (Interval)：
- 值之间的差是有意义的，存在测量单位。
- 性质：相异性、序、加法.
- 允许的变换：新值 = a × 旧值 + b, 其中a、b是常数.
- 例：日历日期、摄氏或华氏温度.
- 允许的操作：均值、标准差、皮尔逊相关、t和F检验.
- 比率属性 (Ratio)：
- 差和比率都是有意义的。
- 性质：相异性、序、加法、乘法.
- 允许的变换：新值 = a × 旧值.
- 例：绝对温度、货币量、计数、年龄、质量、长度、电流.
- 允许的操作：几何平均、调和平均、百分比变差.
- 上述属性类型可以分为分类的(定性的)和数值的(定量的).
- 离散 vs. 连续属性
- 离散属性 (Discrete Attribute)：
- 有限或无限可数个值。
- 常表示为整数变量。
- 例：邮政编码, 计数, 文档集的词。
- 注意：二元属性是离散属性的特例。
- 连续属性 (Continuous Attribute)：
- 属性值为实数。
- 实践中，实数只能用有限位数字的数度量和表示。
- 一般用浮点变量表示。
- 例：温度, 高度, 重量。
- 离散属性 (Discrete Attribute)：
- 数据集的重要特性
- 维度 (Dimensionality)：数据集中对象具有的属性数目。
- 维灾难 (Curse of Dimensionality)。
- 维归约 (Dimensionality Reduction)。
- 稀疏性 (Sparsity)：具有非对称特征的数据集，一个对象的大部分属性上的值都为0。只存储和处理非零值。
- 分辨率 (Resolution)：模式依赖于度量尺度 (scale)。不同尺度下观察到的模式不同。
- 维度 (Dimensionality)：数据集中对象具有的属性数目。
2.2 数据集类型
- 记录数据 (Record Data)：
- 典型情况。
- 数据矩阵 (Data Matrix)：对象具有相同的固定数值属性集，视为多维空间中的点，可用m*n矩阵表示。
- 文档数据 (Document Data)：每个文档是一个向量，分量为术语在文档中出现的次数。
- 事务数据 (Transaction Data)：每条记录（事务）涉及一组项目。例：杂货店购物记录。
- 基于图 (Graph) 的数据：
- 带有对象之间联系的数据。例：HTML链接。
- 具有图对象的数据：对象有结构，包含有联系的子对象。例：分子结构。
- 有序 (Ordered) 数据：
- 常常涉及时间或空间序。
- 时序数据 (Sequential Data)，也称时间数据 (Temporal Data)：时间次序重要，具体时间不重要。例：事务序列。
- 序列数据 (Sequence Data)：个体项的序列。例：基因组序列数据（如DNA序列），重要的是在序列中的位置.
- 时间序列数据 (Time Series Data)：特殊的时序数据，每个记录是时间序列（一段时间的测量序列）。具有时间自相关（临近测量值相似）。
- 空间数据 (Spatial Data)：具有空间属性，如位置或区域。例：地理位置的气象数据。具有空间自相关性（物理上靠近的对象趋向于在其他方面也相似）。
- 空间-时间数据 (Spatial-Temporal Data)：结合空间和时间序。
2.3 数据质量
- 数据质量问题：离群点、遗漏值、不一致值、重复数据。
- 测量误差 (Measurement Error) 和数据收集错误 (Data Collection Error)：
- 测量误差：测量过程导致的问题。
- 数据收集错误：遗漏数据对象或属性值，或不正确包含对象等。
- 都可能是系统的或随机的。
- 噪声 (Noise)：测量误差的随机部分。可能扭曲值或附加谬误对象。
- 离群点 (Outliers)：在某种意义上不同于数据集中其他大部分数据对象的特征。也称为异常对象。
- 噪声与离群点区别：噪声是随机测量误差，离群点是观测量中与大部分观测量明显不同的值，它既可能由真实数据产生，也可能由噪声带来。
- 遗漏值 (Missing Values)：
- 原因：信息未收集全、属性不适用于所有样例。
- 处理策略：删除数据对象、估计遗漏值、分析时忽略遗漏值、用所有可能值替换（按概率加权）。
- 不一致值 (Inconsistent Values)：数据可能包含互相矛盾的值。纠正需要附加或冗余信息。时序数据中的不一致可能是使用了不同的测量手段。
- 重复数据 (Duplicate Data)：数据集可能包括互为冗余或几乎互为冗余的数据对象。是合并异构数据源时的主要问题。
- 数据清理 (Data Cleaning)：包括格式标准化、异常数据清除、错误纠正、重复数据清除。
- 应用问题 (Application Issues)：
- 时效性 (Timeliness)：数据的快照只代表有限时间内的真实情况，过时数据上的模型也可能过时。
- 相关性 (Relevance)：可用数据必须包含应用需要的信息，否则模型精度受限。
2.4 数据预处理
- 数据预处理方法：聚集、抽样、维归约、特征子集选择、特征构造、离散化与二元化、属性变换。
- 聚集 (Aggregation)：
- 定义：将两个或多个属性（或对象）组合成单个属性（或对象）。
- 目的：
- 数据规约 (Data Reduction)：减少属性或对象数量。
- 范围转换 (Change of Scale)：将细粒度数据聚集成粗粒度（如城市聚集成区域、州、国家）。
- 数据更稳定 (More “Stable” Data)：聚集数据变异性更小。
- 举例：澳大利亚降水变化的标准差在按地区聚集后变小.
- 抽样 (Sampling)：
- 定义：选择数据对象子集的常用方法。
- 目的：用于数据初步调查和最终分析。在数据挖掘中使用抽样是因为处理整个数据集太昂贵或耗时。
- 有效抽样原则：
- 代表性 (Representativeness)：如果样本具有代表性，使用样本几乎和使用整个数据集一样有效。
- 保留原数据集的性质：如果样本与原始数据集大致具有相同的属性，则样本具有代表性。
- 抽样方法：
- 简单抽样 (Simple Random Sampling)：选择任何特定项目的概率相等。
- 简单无放回抽样 (Sampling without replacement)。
- 简单有放回抽样 (Sampling with replacement)：同一对象可以被多次提取。
- 分层抽样 (Stratified Sampling)：将数据分成几个分区，然后从每个分区抽取随机样本。可以按相同个数或按比例抽取。
- 简单抽样 (Simple Random Sampling)：选择任何特定项目的概率相等。
- 样本大小：示例展示了不同样本大小对保留原数据集结构的影响（2000点保留大部分结构，500点丢失结构）。对于容量相等的组，需从每组至少找出一个代表点。
- 渐进抽样 (Progressive Sampling) 或 自适应抽样 (Adaptive Sampling)：
- 原因：有时难以预先确定样本集大小。
- 方法：从小样本开始，逐渐增加样本容量直到足够大。需要评估样本是否足够大（例如，预测模型准确率随样本容量增加趋于稳定时停止）。
- 维归约 (Dimensionality Reduction)：
- 问题：数据集包含大量特征（如文档数据集数万词），导致维灾难。高维数据越来越稀疏，许多算法（分类、聚类）效果下降。
- 目的：避免维灾难；降低数据挖掘算法空间和时间损耗；易于数据可视化；减少不相关特征或噪音。
- 方法：
- 线性代数技术：主成分分析 (PCA)、奇异值分解 (SVD)。
- 主成分分析 (PCA)：目标是找到新的属性（主成分），是原有属性的线性组合，相互正交，能捕获数据最大变差。通过求协方差矩阵的特征向量定义新空间。关键在于选择“特征明显的、重要的信息”：同一维度内方差大（有个性，易分开），不同维度间关联度小（表征共同信息少，理想情况不相关，协方差为0，线性空间内正交）。
- 特征子集选择 (Feature Subset Selection)：
- 降低维度的另一种方法。
- 原因：特征并非越多越好。
- 需避免的特征：
- 冗余特征 (Redundant features)：重复一个或多个其他属性中的大部分信息。例：产品购买价格和支付的销售税。
- 不相关特征 (Irrelevant features)：对数据挖掘任务无用。例：学生ID对预测GPA通常不相关。
- 技术：
- 穷举方法 (Exhaustive methods)：尝试所有可能的特征子集作为算法输入。
- 嵌入方法 (Embedded methods)：特征选择作为数据挖掘算法的一部分（如决策树算法本身决定哪些特征有用）。
- 过滤方法 (Filter methods)：在运行数据挖掘算法之前选择特征。
- 包装方法 (Wrapper methods)：使用数据挖掘算法作为黑箱来寻找最佳属性子集。
- 特征创建 (Feature Creation)：
- 目标：创建出比原始特征更能体现对象本质的新特征。
- 三种一般方法：
- 特征提取 (Feature Extraction)：领域相关（domain-specific）。映射数据到新空间（如傅里叶变换、小波变换）。更好的特征可以揭示数据重要性质。
- 特征构造 (Feature Construction)：由一个或多个原始特征构造新特征。例：密度=质量/体积。原始特征形式不适合算法时，构造新特征可能更有用。
- 离散化与二元化 (Discretization and Binarization)：
- 目的：减少属性值个数（便于挖掘，结果更简洁、易理解使用）；产生概念分层结构；满足某些算法（需要离散或二元属性）的要求。
- 非监督 vs. 监督：差别在于是否使用类信息。
- 离散属性二元化：
- 方法1：属性有m个值，每个值映射到[0, m-1]整数（保序），再将m个整数变换为二进制，用n=⌈log₂m⌉个二元属性表示。缺点：建立了属性值之间的联系，不适合非对称属性（1比0更重要）。
- 方法2：对m个属性值建立m个二元变量，每个对应于一个原属性值。适合非对称属性。
- 连续属性离散化：
- 基本思想：将排序后的连续属性值通过n-1个分割点分成n个区间。将一个区间中的值映射到相同分类值。问题是决定分割点数目和位置。分割点数目一般由用户确定。
- 分割点位置确定方法：
- 非监督方法：等宽离散化、等频离散化、K-均值离散化。
- 监督方法：假定数据属于不同类。原则是极大化区间纯度（区间中数据都属于一个类最纯，等比例属于各类最不纯）。有多种度量纯度的方法。
- 基于熵的离散化：熵是一种不纯度度量。基本思想是初始切分成两部分使得结果区间产生最小熵，重复分割直到满足条件（区间数或终止条件）。
- 具有过多值的离散属性：
- 序数属性：用类似于连续属性的方法。
- 标称属性：一般需要领域知识。例：系名（合并成工程学、社会科学等），城市（合并成省、国家）。
- 属性变换 (Attribute Transformation)：
- 定义：将给定属性的整个值集映射到一组新的替换值的函数。
- 简单变换：xk, log(x), ex, |x|, 1/x 等简单函数。注意：可能改变数据特性。
- 标准化 (Standardization) / 规范化 (Normalization)：在数据挖掘中不区分，统计学有不同含义。目标是使值集具有特定性质（如均值0、标准差1）。可使用均值/中位数，标准差/绝对标准差。公式例：x’ = (x - 均值) / 标准差。
2.5 相似性和相异性的度量 (Similarity and Dissimilarity Measures)
相似性 (Similarity)：两个数据对象相似程度的数值度量。对象越相似，值越高。通常在范围内。
相异性 (Dissimilarity)：两个数据对象之间差异的数值度量。对象越相似，值越低。最小不相似度通常为0。
邻近性 (Proximity)：指相似或不同之处。
数据对象的相异度：
欧氏距离 (Euclidean Distance)：衡量n维空间中两点间的直线距离。公式：d(x, y) = √Σ(xk - yk)²。
闵可夫斯基距离 (Minkowski Distance)
：欧氏距离的推广。公式：d(x, y) = (Σ|xk - yk|^r)^(1/r)。
- r = 1：城市街区距离 (Manhattan, taxicab, L1范数)。汉明距离是二元向量城市街区距离的常见例子。
- r = 2：欧几里得距离。
- r → ∞：上确界距离 (Lmax norm, L∞ norm)，是向量任意分量间最大差值。
距离的性质：
- 非负性：d(x, y) ≥ 0，仅当x = y时d(x, y) = 0。
- 对称性：d(x, y) = d(y, x)。
- 三角不等式：d(x, z) ≤ d(x, y) + d(y, z)。
- 满足这三个性质的测度称为度量 (metric)。
非度量的相异度 (Non-metric Dissimilarity)：有些相异度不满足一个或多个度量性质。例：集合差 (size(A-B))，时间计算方式。
数据对象之间的相似度：
- 通常s(x, y) ∈。s(x, y)=1 (或最大相似度) 仅当x = y。s(x, y) = s(y, x) (对称性)。
- 三角不等式（或类似性质）通常不成立。
- 有时可将相似度变换成一种度量距离（如余弦相似性、Jaccard相似性）。
衡量相似度的方法：
简单匹配系数 (Simple Matching Coefficient, SMC)：用于二元属性。衡量两个对象之间匹配的属性个数占总属性个数的比例。公式：SMC = (f₁₁+f₀₀) / (f₀₁+f₁₀+f₁₁+f₀₀)。例：对于x=(1,0,…,0), y=(0,0,…,1) (10维)，SMC=0.7。
Jaccard系数 (Jaccard Coefficient)：用于二元属性。衡量匹配个数（1-1匹配）占不涉及0-0匹配的属性个数的比例。更适合非对称二元属性（关注1-1匹配）。公式：J = f₁₁ / (f₀₁+f₁₀+f₁₁)。例：对于x=(1,0,…,0), y=(0,0,…,1) (10维)，J=0.0。
余弦相似度 (Cosine Similarity)：设x和y是两个向量。公式：cos(x, y) = (x · y) / (||x|| ||y||)。几何解释为向量夹角的余弦。例：对于x=(3,2,0,5,0,0,0,2,0,0), y=(1,0,0,0,0,0,0,1,0,2)，cos(x, y) ≈ 0.31.
广义Jaccard系数 (Generalized Jaccard Coefficient) 或 Tanimoto系数：用于向量。公式：EJ(x, y) = (x · y) / (||x||² + ||y||² - x · y)。
相关性 (Correlation)
：对象属性之间线性联系的度量。
- 皮尔森相关系数 (Pearson’s Correlation)。公式涉及协方差和标准差。范围[-1, 1]。corr(x, y)=0 表示不相关；corr(x, y)=1 (-1) 表示正(负)相关。散点图可可视化相关度。
邻近度计算问题 (Proximity Calculation Issues)：
- 标准化：当属性值域不同时，距离可能被值域大的属性左右。处理方法是变换到相同值域。
- 相关性：当属性之间相关时，使用马氏距离 (Mahalanobis distance)。公式：mahalanobis(x, y) = (x - y)Σ⁻¹(x - y)ᵀ，其中Σ⁻¹是数据协方差矩阵的逆。协方差矩阵Σ的第ij个元素是第i和第j个属性的协方差。例：对于相关属性，马氏距离更能反映实际差异。
- 组合异种属性：当属性类型不同但需要计算总相似度时。算法2.1提供了一种方法：对每个属性计算的相似度sk(x,y)，定义指示变量δk（非对称属性且都为0或有遗漏值时δk=0，否则为1），使用加权公式计算总相似度：similarity(x, y) = (Σ δk sk(x, y)) / (Σ δk)。
- 加权：如果不希望所有属性同等对待，可以使用权重wk（0~1之间，累加和为1）计算加权的相似度或加权的闵可夫斯基距离。