数挖——数据

数据的构成：对象(object)及其属性(attribute)

• 属性是对象的性质或特性
  属性也称作变量(variable)、字段(field)、特性(characteristic)或特征(feature)
• 对象是一组属性描述
  对象也称作记录(record)、元组(tuple)、点(point)、事例(case)、样本(sample)、实体(entity)或实例(instance)
• 属性值是赋给属性的一个数字或符号

第一种属性类型的划分——根据属性对应数值的性质

• 分类属性/定性属性
   标称（Nominal）：仅仅只是不同名字，只提供足够信息区分对象
  例子：证件号、肤色、邮政编码
  操作：众数，熵，列联相关，卡方检验
   序数（Ordinal）：提供足够信息确定对象的序
  例子：等级{高,中,低}、成绩{A,B,C,D}、身高 {高,中,矮}
  操作：中值，百分位，轶相关，游程检验，符号检验
• 数值属性/定量属性
   区间（Interval）：区间属性的值之间的差是有意义的，即存在测量单位
  例子：日历日期、摄氏或华氏温度
  操作：均值，标准差，皮尔斯系数，t和F检验
   比率（Ratio）：差和比率都是有意义的
  例子：绝对温度、长度、计数
  操作：几何平均，调和平均，百分比变差

每种属性类型拥有其上方属性类型所有性质和操作，属性类型的定义是累加的。

第二种属性类型的划分——根据属性对应值的个数

• 离散属性
  在有限符号集合或在无限可数集合中取值，无限可数集合包括自然数集和有理数集
  例子：邮政编码（分类属性）、计数（数值属性）
  典型的子类：二元属性 － 值域是二值集合的属性，如{0,1}和{false,true}
• 连续属性
  是取实数值的属性
  实践中实数值只能用有限的精度来测量和表示
  例子：温度、身高、体重

数据集可以看作数据对象的集合，数据对象可以看作多维空间中的点，也称作数据点，其中每个维度代表对象的一个不同属性

数据集的类型

1. 记录数据
   定义：包含一系列记录的数据集，每个记录由一个固定的属性集合构成
    数据矩阵：如果数据对象的所有属性都取数值，则该记录数据集是一个数据矩阵
    文档数据:每个文档是一个词向量,每个词是词向量中的一个分量（即属性）,每个分量的值是对应词在文档中出现的次数。文档数据是典型的稀疏数据矩阵
    事务数据：一种特殊类型的记录数据，一个记录代表一个事务，一个事务是项的集合(不同事务中项的个数可以不同)，例子：顾客一次购物所购买的商品的集合就构成一个事务，而购买的商品是项

数据矩阵 文档数据 事务数据

2. 基于图的数据
    带有对象之间联系的数据
   例子：带超链接的网页（图是隐性的）
    具有图形对象的数据
   例子：笨的分子结构C6H6（图是显性的）

3. 有序数据
    时序数据
    序列数据
   例子：基因序列数据，一个符号看作一个记录
    空间数据
   例子：全球温度数据

数据预处理

1. 聚集（Aggregation）
   聚集是指将两个或多个对象合并成单个对象
    减少数据：减少属性或数据对象的个数；节省数据挖掘算法的运行时间和空间
    尺度提升：城市聚集成区域、省、国家，等等；产生新的模式
    更“稳定”的数据：聚集的数据会有较小的变异性；突出数据的趋势和轨迹
2. 抽样（Sampling）
   抽样是指选择数据对象子集，抽取的对象称作样本
    抽样可以降低数据处理的费用和时间
    只有有代表性的抽样样本才是有效的，一般具有与原数据集类似的性质（比如均值），使用有代表性的样本与使用整个数据集的效果几乎一样
    抽样方法：随机抽样 （有放回和无放回），分层抽样
3. 维归约（Dimensionality Reduction）
   维归约是指降低数据的维度，即减少数据属性的个数
    避免维灾难 (curse of dimensionality)
    降低数据挖掘算法的时间和内存需求
    使数据更容易可视化
    可以删除不相关的属性并降低噪声
    常用方法：主成份分析(PCA)
   目标是找出新的属性（主成分），与原属性的线性组合，相互正交，捕获数据的最大变差。

随着维度增加，数据在它所占的空间中越来越稀疏。对于分类：没有足够的数据对象来创建模型；对于聚类和异常检测：点之间的密度和距离的定义变得不太有意义

4. 特征子集选择（Feature subset selection）
   特征子集选择是指选择一部分属性实施数据挖掘任务，目的是消除冗余特征和不相关特征
   特征选择的常见方式和方法
    嵌入方式：特征选择作为数据挖掘算法的一部分自然地出现（如构造决策树的算法）
    过滤方式：在数据挖掘算法运行前进行特征选择
    穷举方法：尝试所有可能的特征子集，然后选取产生最好结果的子集
    前向/后向选择方法
   前：从空集开始逐步添加特征，选取产生最好结果的子集
   后：从全集开始逐步删除特征，选取产生最好结果的子集
5. 特征创建（Feature creation）
   特征创建是指由原来的属性创建新的属性集，可以更有效地捕获数据集中的重要信息，消除噪声的影响，同时新属性个数比原来的属性个数少，达到降维的效果
   三种创建新属性的方法
    特征提取：依赖于特定领域，比如人脸识别
    映射数据到新空间：如傅立叶变换(Fourier transform)
    特征构造：如密度=质量/体积
6. 离散化（Discretization）和二元化（Binarization）
   离散化是指将连续属性转变成离散属性。使数据能运用于不能处理连续属性的数据挖掘算法，同时降低离群点/异常点的影响
   二元化是离散化的一种特例，将连续属性转变成二元属性
   离散化的常用方法
    监督（supervised）方法 ——使用类标
   基于熵（entropy）的方法：找产生最小总熵的分界点，总熵是分区熵的加权平均
   熵（信息）：数值区间内类分布的均匀程度；类分布越均匀，熵越高
    非监督（unsupervised）方法——不使用类标
7. 属性变换
   变量变换是指变换变量的所有取值
    简单函数: xⁿ, log(x), |x|
    标准化或规范化
   例子：将一个变量标准化成一个具有均值0和标准差1的新变量: x’=(x-mean(x))/std(x)
    目的：将数据转换成特定分布（如正态分布）的数据；压缩数据；相似度/相异度计算时统一属性的尺度

相似度和相异度

• 相似度（similarity）：两个对象相似程度的数值度量
  对象越相似，相似度越高
  通常在区间[0,1]中取值
• 相异度（dissimilarity）：两个对象差异程度的数值度量
  对象越相似，相异度越低
  有时在区间[0,1]中，有时在[0,+∞]中取值（如用距离表示相异度）
• 邻近度（proximity）指相似度或相异度

属性值之间的相似度/相异度

举例：序数属性相异度的例子：{低,中,高} = {0,1,2}，则d(低,高)=2/2=1，
d(低,中)＝ d(中,高)＝1/2=0.5

数据对象之间的相异度

欧几里德（Euclidean）距离：

其中n 是属性个数， pk和qk分别是数据对象p和q的第k个属性的取值
注意：属性的尺度不同时，需要标准化，变量标准化 x’=(x-mean(x))/std(x)

欧几里德距离的拓广—— 闵可夫斯基（Minkowski）距离

其中r是参数，n 是属性个数， pk和qk分别是数据对象p和q的第k个属性的取值

r = 1. 城市块距离（曼哈顿距离/L1范数距离）
一个常见的特例是汉明（Hamming）距离，它是两个具有二元属性的对象之间不同的二进位个数
r = 2. 欧几里德距离（L2范数距离）
r → ∞. 上确界距离（切比雪夫距离/L∞范数距离）
等于属性之间的最大距离

数据对象之间的相似度

相似度具有如下典型性质
 全等最相似：对于所有的点p和q，仅当p = q时s(p, q) = 1
 对称性：对于所有的点p和q，s(p, q) = s(q, p)

1. 简单匹配系数和Jaccard系数
   数据对象p和q仅包含二元属性，p和q也称作二元向量
    p和q的相似度的计算一般使用下面四个量：
   M01 = 在p中取0但在其q中取1的属性个数
   M10 = 在p中取1但在其q中取0的属性个数
   M00 = 在p中取0但在其q中取0的属性个数
   M11 = 在p中取1但在其q中取1的属性个数
    简单匹配系数（Simple Matching Coefficient, SMC）和Jaccard系数
   SMC = 值匹配的属性个数 / 属性个数 = (M11 + M00) / (M01 + M10 + M11 + M00)
   J = 1-1匹配的属性个数 / 不涉及0-0匹配的属性个数 = (M11) / (M01 + M10 + M11)

SMC系数 vs Jaccard系数
p = 1 0 0 0 0 0 0 0 0 0
q = 0 0 0 0 0 0 1 0 0 1
则
M01 = 2 (在p中取0但在其q中取1的属性个数)
M10 = 1 (在p中取1但在其q中取0的属性个数)
M00 = 7 (在p中取0但在其q中取0的属性个数)
M11 = 0 (在p中取1但在其q中取1的属性个数)
求
SMC = (M11 + M00 )/(M01 + M10 + M11 + M00) = (0+7) / (2+1+0+7) = 0.7
J = (M11) / (M01 + M10 + M11) = 0 / (2 + 1 + 0) = 0

2. 余弦相似度
    如果d1和d2 是两个文档向量，则 cos( d1, d2 ) = (d1 ● d2) / ||d1|| ||d2|| ,
   其中 ● 表示向量点积（即各个对应分量的乘积和），|| d ||表示向量d的长度，即
   || d || = (d ● d)^0.5
    例子:
   d1 = 3 2 0 5 0 0 0 2 0 0
   d2 = 1 0 0 0 0 0 0 1 0 2
   d1 ● d2= 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5
   ||d1||=(3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)^0.5 =(42)^0.5 = 6.481
   ||d2||= (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2)^0.5 =(6)^0.5 = 2.245
   cos( d1, d2 ) =5/(6.481*2.245)= 0.3150
    应用场合：文档聚类、信息检索
   实际应用中，一般使用TF-IDF文档向量，调用余弦相似度计算两个文档之间的相似程度
   每个分量的权重代表对应词的重要程度
   在长文档中出现的词相对不重要；在大量文档中的词是不重要的
   怎样考虑权重？以加权词频替代词的出现次数 （TF-IDF方法）计算第i个词（分量）在第j个文档中的出现的加权词频 = 词频(TF)*反文档频率(IDF)
3. 皮尔森相关系数
   一般用于度量数据对象属性之间的线性联系
   皮尔森相关（Pearson’s correlation）系数的计算

正相关：0<corr(p,q)≤1
负相关：-1≤corr(p,q)<0
不相关：corr(p,q)=0