第二章 数据预处理 2013年9月18日.

Presentation on theme: "第二章 数据预处理 2013年9月18日."— Presentation transcript:

1 第二章 数据预处理 2013年9月18日

2 第二章 数据预处理 Why Data Preprocessing Data Integration Missing Value
第二章 数据预处理 Why Data Preprocessing Data Integration Missing Value Noisy Data Data Reduction

3 2.1 Why Data Preprocessing?
高质量决策来自于高质量数据（Quality decisions come from quality data）. 数据质量的含义 正确性（Correctness） 一致性（Consistency） 完整性（Completeness） 可靠性（Reliability）

4 2.1 Why Data Preprocessing?
数据错误的不可避免性 数据输入和获得过程数据错误的不可避免性 数据集成所表现出来的错误 数据传输过程所引入的错误 据统计有错误的数据占总数据的5%左右 其他类型的数据质量问题: Data needs to be integrated from different sources Missing values Noisy and inconsistent values Data is not at the right level of aggregation

5 数据质量问题的分类 数据质量问题 单数据源问题 多数据源问题 模式相关 （缺乏完整性约束， 粗劣的模式设计） ——唯一值 ——参考完整性 …
实例相关 （数据输入错误） ——拼写错误 ——冗余/重复 ——矛盾的数据 （不同的数据模型 和模式设计） ——命名冲突 ——结构冲突 （矛盾的或不一致 的数据） ——不一致的聚集层次 ——不一致的时间点

6 包含数据清理过程的三个主要领域 数据仓库（data warehousing） 数据库中的知识发现(kdd) 总体数据质量管理(total data quality management,TDQM)

7 2.2 Data Integration Integrate data from multiple sources into a common format for data mining. Note: A good data warehouse has already taken care of this step. Data Warehouse Server OLTP DBMSs Extract, clean, transform, aggregate, load, update Other Data Sources Data Marts

8 Data Integration (Contd.)
Problem: Heterogeneous schema integration Different attribute names Different units: Sales in $, sales in Yen, sales in DM

9 Data Integration (Contd.)
Problem: Heterogeneous schema integration Different scales: Sales in dollars versus sales in pennies Derived attributes: Annual salary versus monthly salary

10 Data Integration (Contd.)
Problem: Inconsistency due to redundancy Customer with customer-id 150 has three children in relation1 and four children in relation2 Computation of annual salary from monthly salary in relation1 does not match “annual-salary” attribute in relation2

11 2.3 Missing Values 常常会有一些记录的某些属性值不知道的情况出现.出现缺失值的原因:
Attribute does not apply (e.g., maiden娘家姓 name) Inconsistency with other recorded data Equipment malfunction Human errors Attribute introduced recently (e.g., address)

12 Missing Values: Approaches
Ignore the record Complete the missing value: Manual completion: Tedious and likely to be infeasible Fill in a global constant, e.g., “NULL”, “unknown” Use the attribute mean Construct a data mining model that predicts the missing value

13 2.3 Noisy Data Examples: Faulty data collection instruments
Data entry problems, misspellings Data transmission problems Technology limitation Inconsistency in naming conventions（命名习惯） Duplicate records with different values for a common field

14 Noisy Data: Remove Outliers

15 Noisy Data: Smoothing y Y1 Y1’ X1 x

16 Noisy Data: Normalization
Scale data to fall within a small, specified range Leave out extreme order statistics Min-max normalization Z-score normalization Normalization by decimal scaling

17 2.4 Data Reduction Problem:
Data might not be at the right scale for analysis. Example: Individual phone calls versus monthly phone call usage Complex data mining tasks might run a very long time. Example: Multi-terabyte data warehouses One disk drive: About 20MB/s

18 Data Reduction: Attribute Selection
Select the “relevant” attributes for the data mining task If there are k attributes, there are 2k-1 different subsets Example: {salary, children, wyear}, {salary, children}, {salary, wyear}, {children, wyear}, {salary}, {children}, {wyear} Choice of the right subset depends on: Data mining task Underlying probability distribution

19 Attribute Selection (Contd.)
How to choose relevant attributes: Forward selection: Select greedily one attribute at a time Backward elimination: Start with all attributes, eliminate irrelevant attributes Combination of forward selection and backward elimination

20 Data Reduction: Parametric Models
Main idea: Fit a parametric model to the data (e.g., multivariate normal distribution) Store the model parameters, discard the data (except for outliers)

21 Parametric Models: Example
Instead of storing (x,y) pairs, store only the x-value. Then recompute the y-value using y = ax + b y x

22 Data Reduction: Sampling
Choose a representative subset of the data Simple random sampling may have very poor performance in the presence of skew

23 Data Reduction: Sampling (Contd.)
Stratified sampling(分层取样): Biased sampling Example: Keep population group ratios Example: Keep minority population group count

24 Data Reduction: Histograms(柱状图)
Divide data into buckets and store average (sum) for each bucket Can be constructed “optimally” for one attribute using dynamic programming Example: Dataset: 1,1,1,1,1,1,1,1,2,2,2,2,3,3,4,4,5,5,6,6, 7,7,8,8,9,9,10,10,11,11,12,12 Histogram: (range, count, sum) (1-2,12,16), (3-6,8,36), (7-9,6,48), (10-12,6,66)

25 Histograms (Contd.) Equal-width histogram Example:
Divides the domain of an attribute into k intervals of equal size Interval width = (Max – Min)/k Computationally easy Problems with data skew and outliers Example: Dataset: 1,1,1,1,1,1,1,1,2,2,2,2,3,3,4,4,5,5,6,6, 7,7,8,8,9,9,10,10,11,11,12,12 Histogram: (range, count, sum) (1-3,14,22), (4-6,6,30), (7-9,6,48), (10-12,6,66)

26 Histograms (Contd.) Equal-depth histogram Example:
Divides the domain of an attribute into k intervals, each containing the same number of records Variable interval width Computationally easy Example: Dataset: 1,1,1,1,1,1,1,1,2,2,2,2,3,3,4,4,5,5,6,6, 7,7,8,8,9,9,10,10,11,11,12,12 Histogram: (range, count, sum) (1,8,8), (2-4,8,22), (5-8,8,52), (9-12,8,84)

27 Data Reduction: Discretization
Same concept as histograms Divide domain of a numerical attribute into intervals. Replace attribute value with label for interval. Example: Dataset (age; salary): (25;30,000),(30;80,000),(27;50,000), (60;70,000),(50;55,000),(28;25,000) Discretized dataset (age, discretizedSalary): (25,low),(30,high),(27,medium),(60,high), (50,medium),(28,low)

28 Data Reduction: Natural Hierarchies
Natural hierarchies on attributes can be used to aggregate data along the hierarchy.Replace low-level concepts with high-level concepts Example replacements: Product Name by category City by state Year Industry Country Quarter Category State Month Week Product City Day

29 Aggregation: Example

30 Data Reduction: Other Methods
Principal component analysis Fourier transformation Wavelet transformation

31 主成分分析(Principal Component Analysis)
在许多领域的研究与应用中，往往需要对反映事物的多个变量进行大量的观测，收集大量数据以便进行分析寻找规律。 多变量大样本无疑会为研究和应用提供了丰富的信息，但也在一定程度上增加了数据采集的工作量，更重要的是在大多数情况下，许多变量之间可能存在相关性，从而增加了问题分析的复杂性，同时对分析带来不便。 如果分别对每个指标进行分析，分析往往是孤立的，而不是综合的。盲目减少指标会损失很多信息，容易产生错误的结论。

32 主成分分析 因此需要找到一个合理的方法，在减少需要分析的指标同时，尽量减少原指标包含信息的损失，以达到对所收集数据进行全面分析的目的。
由于各变量间存在一定的相关关系，因此有可能用较少的综合指标分别综合存在于各变量中的各类信息。主成分分析与因子分析就属于这类降维的方法。 主成分分析与因子分析是将多个实测变量转换为少数几个不相关的综合指标的多元统计分析方法。

33 主成分分析 例1：生产服装有很多指标，比如袖长、肩宽、身高等十几个指标，服装厂生产时，不可能按照这么多指标来做，怎么办？一般情况，生产者考虑几个综合的指标，象标准体形、特形等。 例2：企业经济效益的评价，它涉及到很多指标。例百元固定资产原值实现产值、百元固定资产原值实现利税，百元资金实现利税，百元工业总产值实现利税，百元销售收入实现利税，每吨标准煤实现工业产值，每千瓦时电力实现工业产值，全员劳动生产率，百元流动资金实现产值等，我们要找出综合指标，来评价企业的效益。

34 主成分分析 例3：假定你是一个公司的财务经理，掌握了公司的所有数据，比如固定资产、流动资金、每一笔借贷的数额和期限、各种税费、工资支出、原料消耗、产值、利润、折旧、职工人数、职工的分工和教育程度等等。 如果让你向上司介绍公司状况，你能原封不动地介绍所有指标和数字吗？ 当然不能。 你必须要对各个方面作出高度概括，用一两个指标简单明了地说清楚情况。

35 主成分分析 很多应用都会遇到有很多变量的数据，这些数据的共同特点是变量很多，在如此多的变量之中，有很多是相关的。
因此我们希望从中综合出一些少数主要的指标，这些指标所包含的信息量又很多。这些特点，使我们在研究复杂的问题时，容易抓住主要矛盾。 如何才能找出综合指标？

36 主成分分析 由于实测的变量间存在一定的相关关系，因此有可能用较少数的综合指标分别综合存在于各变量中的各类信息，而综合指标之间彼此不相关，即各指标代表的信息不重叠。综合指标称为主成分（提取几个主成分）。 若有一些指标 ，取综合指标即它们的线性组合F，当然有很多，我们希望线性组合F包含很多的信息，即var(F)最大，这样得到F记为 ，然后再找 ， 与 无关，以此类推，我们找到了一组综合变量 ，这组变量基本包含了原来变量的所有信息。

37 主成分分析

38 主成分分析 在数据挖掘领域，以及图像处理、通讯技术等信息处理领域，主成分分析是很常用的一种方法
通过对一组变量的几种线性组合来解释这组变量的方差和协方差结构，以达到数据的降维和数据的解释的目的。

39 成绩数据 学生的数学、物理、化学、语文、历史、英语的成绩如下表（部分）。

40 问 题 目前的问题是，能否将该数据的6个变量用一两个综合变量来表示？ 这一两个综合变量包含了多少原来的信息？ 能不能利用找到的综合变量来对学生排序？这一类数据所涉及的问题可以推广到对其他应用的分析、排序、判别和分类等问题。

41 主成分分析 例中的数据点是六维的，即每个观测值是6维空间中的一个点。我们希望将6维空间用低维空间表示。
先假定只有二维，即只有两个变量，它们由横坐标和纵坐标所代表；因此每个观测值都有相应于这两个坐标轴的两个坐标值；如果这些数据形成一个椭圆形状的点阵，那么这个椭圆有一个长轴和一个短轴。在短轴方向上，数据变化很少；在极端的情况，短轴如果退化成一点，那只有在长轴的方向才能够解释这些点的变化了；这样，由二维到一维的降维就自然完成了。

42 主成分分析 当坐标轴和椭圆的长短轴平行，那么代表长轴的变量就描述了数据的主要变化，而代表短轴的变量就描述了数据的次要变化。
但是，坐标轴通常并不和椭圆的长短轴平行。因此，需要寻找椭圆的长短轴，并进行变换，使得新变量和椭圆的长短轴平行。 如果长轴变量代表了数据包含的大部分信息，就用该变量代替原先的两个变量（舍去次要的一维），降维就完成了。 椭圆（球）的长短轴相差得越大，降维也越有道理。

43

44 主成分分析 对于多维变量的情况和二维类似，也有高维的椭球，只不过无法直观地看见罢了。
首先找出高维椭球的主轴，再用代表大部分数据信息的最长几个轴作为新变量；这样，就基本完成了主成分分析。 注意，和二维情况类似，高维椭球的主轴也是互相垂直的。这些互相正交的新变量是原先变量的线性组合，称为主成分(principal component)。

45 主成分分析 正如二维椭圆有两个主轴，三维椭球有三个主轴一样，有几个变量，就有几个主成分。
选择越少的主成分，降维幅度就越大。什么是降维标准呢？那就是这些被选的主成分所代表的主轴的长度之和占主轴长度总和的大部分。有些研究工作表明，所选的主轴总长度占所有主轴长度之和的大约85%即可，其实，这只是一个大体的说法；具体选多少个，要看实际情况而定。

46 对于上面的数据，主成分分析的结果 这里的Initial Eigenvalues就是这里的六个主轴长度，又称特征值（数据相关阵的特征值）。头两个成分特征值累积占了总方差的81.142%。后面的特征值的贡献越来越少。

47 特征值的贡献还可以从碎石图看出

48 怎么解释这两个主成分。前面说过主成分是原始六个变量的线性组合。是怎么样的组合呢？具体结果见下表。
这里每一列代表一个主成分作为原来变量线性组合的系数（比例）。比如第一主成分作为数学、物理、化学、语文、历史、英语这六个原先变量的线性组合，系数（比例）为-0.806, , , 0.893, 0.825, 0.836。

49 主成分分析 如用x1,x2,x3,x4,x5,x6分别表示原先的六个变量，而用y1,y2,y3,y4,y5,y6表示新的主成分，那么，第一和第二主成分y1,y2同原来6个变量x1,x2,x3,x4,x5,x6与的关系为： y1= x x x x x x6 y2= x x x x x x6 这些系数称为主成分载荷（loading），它表示主成分和相应的原先变量的相关系数。 比如y1表示式中x1的系数为-0.806，这就是说第一主成分和数学变量的相关系数为-0.806。 相关系数(绝对值）越大，主成分对该变量的代表性也越大。可以看出，第一主成分对各个变量解释得都很充分。而最后的几个主成分和原先的变量就不那么相关了。

50 主成分分析的一些注意事项 主成分分析从原理上是寻找椭球的所有主轴。因此，原先有几个变量，就有几个主成分。
主成分分析从原理上是寻找椭球的所有主轴。因此，原先有几个变量，就有几个主成分。  可以看出，主成分分析都依赖于原始变量，也只能反映原始变量的信息。所以原始变量的选择很重要。 另外，如果原始变量都本质上独立，那么降维就可能失败，这是因为很难把很多独立变量用少数综合的变量概括。数据越相关，降维效果就越好。 在得到分析的结果时，并不一定会都得到如我们例子那样清楚的结果。这与问题的性质，选取的原始变量以及数据的质量等都有关系

51 数学模型 X = =（X1，X2，…，XP） 其中，X i＝ , i = 1, …, p
设有n个数据样本，每个样本观测p个变量（指标）：X1，X2，…，XP，得到原始数据矩阵： X = =（X1，X2，…，XP） 其中，X i＝ , i = 1, …, p

52 数学模型 用数据矩阵X的p个向量（即p个指标向量）X1，X2，…，XP，作线性组合（即综合指标向量）为： 简写成
上述方程组要求： , i =1,…，p

53 数学模型 且系数aij由下列原则决定 ： Fi与Fj（i ≠j，i，j＝1，…，p）不相关；
F1 是X1，X2，…，X P ，的一切线性组合（系数满足上述方程组）中方差最大的，F2 是与 F1 不相关的X1，X2，…，X P ，一切线性组合中方差最大的，……, Fp 是与F1，F2，…，F P-1 ，都不相关的X1，X2，…，X P ，一切线性组合中方差最大的。 从代数学观点看主成分就是p个变量X1，X2，…，X P的一些特殊的线性组合，而在几何上这些线性组合正是把X1，X2，…，X P构成坐标系旋转产生的新坐标系，新坐标轴通过样本方差最大的方向（或说具有最大的样本方差）。

54 主成分的几何意义 设有n个样品，每个样品有两个观测变量 二维平面的散点图。n个样本点，无论沿着 轴方向还是 轴方向，都有较大的离散性，其离散程度可以用 或 的方差表示。 当只考虑一个时，原始数据中的信息将会有较大的损失。若将坐标轴旋转一下： 主元分析示意图

55 数学模型 若在椭圆长轴方向取坐标轴F1，在短轴方向取F2，这相当于在平面上作一个坐标变换，即按逆时针方向旋转θ角度，根据旋轴变换公式新老坐标之间有关系： F1 ，F2 是原变量X1 和X2 的线性组合，用矩阵表示是 ＝ = U ·X 显然 且是正交矩阵，即 U ＝ I 则n个样品在 轴的离散程度最大（方差最大），变量 代表了原始数据的绝大部分信息，即使不考虑 ，信息损失也不多。而且， 不相关。只考虑 时，二维降为一维。

56 主成分的推导 Var(a,X) = E (a’X – E (a’X) ) (a’X – E (a’X) )’ 达到最大值，且a’a=1。
设F＝a1X1 + a2X2 + … + apXp = ,其中 a＝(a1，a2，…，a P)’, X=( X1，X2，…，XP ) ’, 求主成分就是寻求X 的线性函数 使相应的方差尽可能地大，即 Var(a,X) = E (a’X – E (a’X) ) (a’X – E (a’X) )’ = a’ E (X – E (X) ) (X – E (X) )’a = a’∑a 达到最大值，且a’a=1。

57 主成分的推导 设协差阵∑的特征根为λ1≥λ2≥…λp >0，相应的单位特征向量为u1 ,…, up , 令U＝（u1，…，uP）＝
则UU’ = U’U=I ，且 ∑＝U U’ =

58 主成分的推导 因此 a’ ∑a= = = 所以 a’ ∑a≤ = = = = 而且，当a=u1时有 = = = =
= = 而且，当a=u1时有 = = = = 因此a= u1 使 Var(a’,X)= a’ ∑a达到最大值，且Var(u1’,X)= u1’ ∑u1=λ1。

59 主成分的推导 同理Var(ui’, X)=λi, 而且Cov(ui’X, uj’X) = ui’ ∑uj = ui’( )uj = ，i≠j
上述推导表明：X1，X2，…，XP 的主要成分就是以∑的特征向量为系数的线性组合，它们互不相关，其方差为∑的特征根。 由于∑的特征根λ1≥λ2≥…≥λp>0,所以Var(F1) ≥Var(F2) ≥…≥Var(Fp) >0。主要成分的名次是按特征根取值大小的顺序排列的。

60 主成分的推导 在解决实际问题时，一般不是取p个主成分，而是根据累计贡献率的大小取前k个。
定义：称第一主要成分的贡献率为λ1/ , 由于Var(F1)＝λ1，所以λi/ ＝ Var(F1)/ 。因此第一主成分的贡献率就是第一主成分的方差在全部方差中的比值。这个值越大，表明第一主成分综合X1，X2，…，XP信息的能力越强。 前k个主成分的累计贡献率定义为 / 。如果前k个主成分的贡献率达到85%，表明取前k个主成分基本包含了全部测量指标所具有的信息，这样既减少了变量的个数又方便于对实际问题的分析和研究。

61 主成分的推导 值得指出的是：当协差阵∑未知时，可用其估计值S（样本协差阵）来代替。 设原始数据矩阵为： 则S=（sij），其中
而相关系数阵 R=（rij） 其中 ，显然当原始变量X1，X2，…，XP标准化后，则 S=R=X’ X/n 标准化就是已知随机变量X的期望Q，方差为S的平方的话，令新变量为（X-Q）/S，新变量就是一个标准的方差 标准化就是已知随机变量X的期望Q，方差为S的平方的话，令新变量为（X-Q）/S，新变量就是一个标准的方差 标准方差（standard deviation)定义 就是方差的平方根：一组数据中的每一个数与这组数据的平均数的差的平方的和再除以数据的个数，取平方根即是。 即：标准方差={[∑（Xn-X)^2]/n}^(1/2)的平方根,(X表示这组数据的平均数。）

62 主成分的推导 实际应用时，往往指标的量纲不同，所以在计算之前先消除量纲的影响，而将原始数据标准化，这样一来S和R相同。因此一般求R的特征根和特征向量，并且不妨取R=X’X。因为此时的R和X’X/n只差一个系数，特征根差n倍，但特征向量不变，不影响求主成分。

63 计算步骤 设有n个样品，每个样品观测p个指标，将原始数据写成矩阵
1）将原始数据标准化(标准化就是已知随机变量X的期望Q，方差为S的平方的话，令新变量为（X-Q）/S，新变量就是一个标准的方差) 2）建立变量的相关系数阵R=X’X 3）R的特征根λ1≥λ2≥…≥λp>0及相应的单位特征向量：ai=[a1i ，a2i，…，api]’。 4）写出主成分Fi＝a1iX1 + a2iX2 + … + apiXp

64 Data Preprocessing: Summary
Problems during data integration: Different attribute names Different units Different scales Derived attributes Redundant data Missing values Imputation Prediction Noisy data: Outlier removal Smoothing Normalization Data Reduction: Attribute selection Fitting parametric models Sampling Histograms Discretization Aggregation