《数据挖掘导论》读书笔记(二)—— 数据

书名:数据挖掘导论(Introduction to Data Mining)
作者: Pang-Ning Tan / Michael Steinbach / Vipin Kumar
出版社: 人民邮电出版社
译者: 范明 / 范宏建
出版年: 2010-12-10
ISBN: 9787115241009

第2章 数据

数据类型

属性与度量

相关定义

  • 属性(attribute):对象的性质或特性,它因对象而异,或随时间变化。
  • 测量标度(measurement scale):将数值或符号值与对象的属性相关联的规则(函数)。

注意

  • 形式上,测量过程是使用测量标度将一个值与一个特定对象的特定属性相关联。
  • 属性的性质不必与用来度量它的值的性质相同。如代表ID的数字,作为一系列数字,具有平均数等性质,但是这些性质与ID这个属性无关。

用值的个数描述属性

  • 离散(discrete):离散属性具有有限个值或无限可数个值。
  • 连续(continuous):连续属性是取实数值的属性。

非对称的属性

更关注部分属性值。如学生选修了对应某属性的课程,该属性记为1,否则记为0.由于学生只选修所有可选课程集合中的很小一部分,所以在这种情况,通过更加关注非零值。

数据集类型

数据集的一般特征

  • 维度(dimensionality)
    数据集的维度是数据集中的对象具有的属性数目。分析高维数据有时候会陷入所谓的维度灾难(curse of dimensionality),所以,数据预处理有的时候需要减少维度,称为维度归约(dimensionality reduction)。
  • 稀疏性(sparsity)
    数据集中大部分数据缺失或为0。这将节省大量的计算时间和存储空间,有些数据挖掘算法仅适合处理稀疏数据。
  • 分辨率(resolution)
    在不同的分辨率下数据的性质不同。如在几米的分辨率中,地球表面崎岖,但在几十公里的分辨率中,地球表面相对平坦。

常见的数据集类型

  • 记录数据
    事务数据(transaction data):其中每个记录(事务)涉及一系列的项。如顾客一次购买的商品集合。
    数据矩阵(data matrix):如果一个数据集族中的所有数据对象都具有相同的数值属性集,则数据对象可以看作多维空间中的向量,其中每个维代表对象的一个不同属性。
  • 基于图形的数据
    用图形表示对象之间的关系:如社交网络等。
    数据本身用图形表示:如化合物的分子结构图。
  • 有序数据
    时序数据(sequential data):每个记录包含一个与之相关联的时间。
    序列数据(sequence data):有序序列,考虑项的位置,如基因序列。
    时间序列数据(time series data):特殊的时序数据,一段时间以来的测量序列,如股票每日价格。
    空间数据:具有空间属性的数据,如全球温度。

数据质量

相关定义

  • 精度(percision):(同一个量的)重复测量值之间的接近程度。
  • 偏倚(bias):测量值与被测量值之间的系统变差。
  • 准确率(accuracy):被测量的测量值与实际值之间的接近程度。
    准确率依赖于精度和偏倚,而且是一个一般化的概念,因此没有用这两个量表达准确的具体公式。
  • 噪声:测量误差的随机部分。
  • 离群点(outlier):某种意义上具有不同于数据集中其他大部分数据对象的特征的数据对象,或是相对于该属性的典型值来说不同寻常的属性值。注意区别噪声和离群点,离群点也可以是合法的数据对象或值。
  • 遗漏值:一个对象遗漏一个或多个属性值。
    对于遗漏值,通常有三种应对措施:1. 删除数据对象或属性;2. 估计遗漏值;3. 在分析时忽略遗漏值(有些数据挖掘方法可以做到)。

关于应用

注意两个问题:

  • 数据的时效性
  • 数据的相关性:数据与模型必须相关,可用的数据必须包含应用功能所需要的信息。

数据预处理

聚集(aggregation)

定义:将两个或多个对象合并成单个对象。
动机:1. 减少数据规模,可以使用开销更大的数据挖掘算法。 2. 通过高层而不是低层的数据视图,起到了范围或标度转换的作用。 3. 对象或属性群的行为比单个对象或属性的行为更加稳定。
缺点:可能会丢失一些细节。

抽样

定义:选择数据对象子集进行分析。
要求:如果样本具有代表性,则使用样本与使用整个数据集的效果几乎一样。而样本具有代表性,要求样本近似地具有与原数据集相同的性质。
渐进抽样:需要自适应(adaptive)或渐进抽样(progressive sampling)来确定合适的样本容量。具体来说,从一个小样本开始,然后增加样本容量直至得到足够容量的样本。

维归约

定义:通过创建新属性,将一些旧属性合并在一起来降低数据集的维度。
好处:1. 删除不相关的属性并降低噪声; 2. 维归约使得模型更好理解,更容易让数据可视化。
维灾难:随着数据维度的增加,许多数据分析变得非常困难。
维归约的线性代数技术:主成分分析(Principal Components Analysis, PCA)。奇异值分解(Singular Value Decomposition, SVD)。

特征子集选择

定义:仅使用特征的子集来降低维度。
特征选择的理想方法:将所有可能的特征子集作为感兴趣的数据挖掘算法的输入,然后选取产生最好结果的子集。
特征选择的一般方法:

  • 嵌入方法(embedded approach):数据挖掘算法本身会进行特征选择。
  • 过滤方法(filter approach):使用某种独立于数据挖掘任务的方法,在数据挖掘算法运行前进行特征选择。
  • 包装方法(wrapper approach):这些方法将目标数据挖掘算法作为黑盒,使用类似于前面介绍的理想算法,但通常并不枚举所有可能的子集来找出最佳属性子集。
  • 特征子集选择体系
    可将过滤和包装方法放到一个共同的体系结构中,特征选择的过程可以看作由四部分组成:子集评估度量、控制新的特征子集产生的搜索策略、停止搜索判断和验证过程。过滤方法和包装方法的唯一不同是它们使用了不同的特征子集评估方法。对于包装方法,子集评估使用目标数据挖掘算法;对于过滤算法,子集评估技术不同于目标数据挖掘算法。流程如下图。
    特征子集选择过程流程图
  • 特征加权
    特征越重要,所赋予的权值越大;对不太重要的特征,赋予较小的权值。

特征创建

定义:由原来的属性创建新的属性集,更有效地捕捉数据集中的重要信息。
方法:特征创建的方法主要有以下三种:

  • 特征提取(feature extraction)
    最常用的特征提取技术都是高度针对具体领域的,对于特定领域,会开发新的特征和特征提取方法。
  • 映射数据到新的空间
    使用一种完全不同的视角挖掘数据可能揭示出重要和有趣的特征,如使用傅里叶变换(Fourier transform)、小波变换(wavelet transform)。
  • 特征构造
    由原特征构造新特征。如用质量和体积来构造密度。

离散化和二元化

定义:
离散化(discretization):将连续属性变换成分类属性。
二元化(binarization):连续和离散属性变换成一个或多个二元属性。

变量变换(variable transformation)

定义:用于变量值的变换,对于每个对象,变换都作用于该对象的变量值。
两种重要的变量变换类型:

  • 简单函数变换
    一个简单的数学函数(如平方根、倒数、对数)分别作用于每一个值。
  • 规范化
    使整个值的集合具有特定的性质。

相似性和相异性的度量

定义

两个对象的相似度(similarity)的非正式定义是这两个对象相似程度的数值度量。
两个对象的相异度(dissimilarity)的非正式定义是这两个对象差异程度的数值度量。

简单属性的相似度与相似度

x,y是两个对象,这两个对象都只有一个属性,d是两个对象之间的相异度,s是两个对象之间的相似度。

  • 对于标称属性:
    如果x=y, d=0, s=1;如果x!=y,d=1, s=0
  • 对于序数属性:
    d = |x-y|/(n-1) (值映射到整数0到n-1,其中n是值的个数)
    s = 1-d
  • 对于区间或比率属性:
    d = |x-y|
    s = -d, s = 1/(1+d), s = e^(-d), s = 1 – (d-min_d)/(max_d-min_d)

数据对象之间的相异度

  • 闵可夫斯基距离(Minkowski distance)
    $$d(x,y) = \sqrt[r]{\sum_{k=1}^{n} \left | x_{k}-y_{k} \right |^{r}} \tag{2-1}$$
    其中,r是参数,常见有以下三种例子。
    • r=1,城市街区(也称曼哈顿、出租车、\(L_1\)范数)距离,常见的是海明距离(Hamming distance)。
    • r=2,欧几里得距离(\(L_2\)范数)。
    • r=\(\infty\),上确界(\(L_{max}\)或\(L_\infty\)范数)。

邻近性度量

  • 二元数据的相似性度量
    简单匹配系数(Simple Matching Coefficient, SMC)
    $$SMC=(f_{11}+f_{00})/(f_{11}+f_{00}+f_{10}+f_{01}) \tag{2-2}$$
    其中,
    \(f_{11}\)是x取1并且y取1的属性个数
    \(f_{00}\)是x取0并且y取0的属性个数
    \(f_{10}\)是x取1并且y取0的属性个数
    \(f_{01}\)是x取0并且y取1的属性个数
    Jaccard系数(Jaccard Coefficient)
    $$SMC=f_{11}/(f_{11}+f_{10}+f_{01}) \tag{2-3}$$
    有些情况下,x取0,y取0的属性较多,但并不能说明这两个对象具有相似性。
  • 余弦相似度(cosine similarity)
    $$cos(x,y)=(x·y)/(\left \| x \right \| \left \| y \right \|)$$

选择正确的邻近性度量

对于许多稠密的、连续的数据,通常使用距离度量,连续属性之间的邻近度通常用属性值的差来表示。
对于稀疏数据,余弦、Jaccard和广义Jaccard度量对于这类数据是合适的。
如果时间序列的量值是重要的,可以使用欧几里得距离。