数据的构成：对象(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} - 连续属性
是取实数值的属性
实践中实数值只能用有限的精度来测量和表示
例子：温度、身高、体重
数据集可以看作数据对象的集合，数据对象可以看作多维空间中的点，也称作数据点，其中每个维度代表对象的一个不同属性
数据集的类型
- 记录数据
定义：包含一系列记录的数据集，每个记录由一个固定的属性集合构成
数据矩阵：如果数据对象的所有属性都取数值，则该记录数据集是一个数据矩阵
文档数据:每个文档是一个词向量,每个词是词向量中的一个分量（即属性）,每个分量的值是对应词在文档中出现的次数。文档数据是典型的稀疏数据矩阵
事务数据：一种特殊类型的记录数据，一个记录代表一个事务，一个事务是项的集合(不同事务中项的个数可以不同)，例子：顾客一次购物所购买的商品的集合就构成一个事务，而购买的商品是项
- 基于图的数据
带有对象之间联系的数据
例子：带超链接的网页（图是隐性的）
具有图形对象的数据
例子：笨的分子结构C6H6（图是显性的）
- 有序数据
时序数据
序列数据
例子：基因序列数据，一个符号看作一个记录
空间数据
例子：全球温度数据
数据预处理
- 聚集（Aggregation）
聚集是指将两个或多个对象合并成单个对象
减少数据：减少属性或数据对象的个数；节省数据挖掘算法的运行时间和空间
尺度提升：城市聚集成区域、省、国家，等等；产生新的模式
更“稳定”的数据：聚集的数据会有较小的变异性；突出数据的趋势和轨迹 - 抽样（Sampling）
抽样是指选择数据对象子集，抽取的对象称作样本
抽样可以降低数据处理的费用和时间
只有有代表性的抽样样本才是有效的，一般具有与原数据集类似的性质（比如均值），使用有代表性的样本与使用整个数据集的效果几乎一样
抽样方法：随机抽样 （有放回和无放回），分层抽样 - 维归约（Dimensionality Reduction）
维归约是指降低数据的维度，即减少数据属性的个数
避免维灾难 (curse of dimensionality)
降低数据挖掘算法的时间和内存需求
使数据更容易可视化
可以删除不相关的属性并降低噪声
常用方法：主成份分析(PCA)
目标是找出新的属性（主成分），与原属性的线性组合，相互正交，捕获数据的最大变差。
随着维度增加，数据在它所占的空间中越来越稀疏。对于分类：没有足够的数据对象来创建模型；对于聚类和异常检测：点之间的密度和距离的定义变得不太有意义
- 特征子集选择（Feature subset selection）
特征子集选择是指选择一部分属性实施数据挖掘任务，目的是消除冗余特征和不相关特征
特征选择的常见方式和方法
嵌入方式：特征选择作为数据挖掘算法的一部分自然地出现（如构造决策树的算法）
过滤方式：在数据挖掘算法运行前进行特征选择
穷举方法：尝试所有可能的特征子集，然后选取产生最好结果的子集
前向/后向选择方法
前：从空集开始逐步添加特征，选取产生最好结果的子集
后：从全集开始逐步删除特征，选取产生最好结果的子集 - 特征创建（Feature creation）
特征创建是指由原来的属性创建新的属性集，可以更有效地捕获数据集中的重要信息，消除噪声的影响，同时新属性个数比原来的属性个数少，达到降维的效果
三种创建新属性的方法
特征提取：依赖于特定领域，比如人脸识别
映射数据到新空间：如傅立叶变换(Fourier transform)
特征构造：如密度=质量/体积 - 离散化（Discretization）和二元化（Binarization）
离散化是指将连续属性转变成离散属性。使数据能运用于不能处理连续属性的数据挖掘算法，同时降低离群点/异常点的影响
二元化是离散化的一种特例，将连续属性转变成二元属性
离散化的常用方法
监督（supervised）方法 ——使用类标
基于熵（entropy）的方法：找产生最小总熵的分界点，总熵是分区熵的加权平均
熵（信息）：数值区间内类分布的均匀程度；类分布越均匀，熵越高
非监督（unsupervised）方法——不使用类标 - 属性变换
变量变换是指变换变量的所有取值
简单函数: 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)
- 简单匹配系数和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
- 余弦相似度
如果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) - 皮尔森相关系数
一般用于度量数据对象属性之间的线性联系
皮尔森相关（Pearson’s correlation）系数的计算
正相关：0<corr(p,q)≤1
负相关：-1≤corr(p,q)<0
不相关：corr(p,q)=0
