1、数据挖掘与商务智能Data Mining&Business Intelligence第二章第二章 数据及数据预处理数据及数据预处理西安电子科技大学软件学院主讲人：黄健斌内容提纲2.1数据类型2.2数据质量2.3数据预处理2.4数据相似性和相异性度量2.5数据统计汇总2.6数据可视化n记录数据关系记录数据矩阵，例如，数值矩阵，交叉文档数据：文本文件：词频向量交易数据n图形和网络万维网社会或信息网络分子结构有序时间数据：时间序列顺序数据：交易序列基因序列数据n视频数据的图像序列空间，图像和多媒体：空间数据：地图TID Items 1 Bread,Coke,Milk 2 Beer,Bread 3 B
2、eer,Coke,Diaper,Milk 4 Beer,Bread,Diaper,Milk 5 Coke,Diaper,Milk 2.1数据类型数据对象n数据集由数据对象组成n一个数据对象代表一个实体n例子销售数据库：客户，商店物品，销售额医疗数据库：患者，治疗信息大学数据库：学生，教授，课程信息n称为样品，示例，实例，数据点，对象，元组（tuple）。n数据对象所描述的属性。数据库中的行-数据对象；列-“属性”。属性n属性（或尺寸，特征，变量）：一个数据字段，代表一个数据对象的特征或功能。例如，客户_ID，姓名，地址n类型：标称二进制数字：定量规模区间缩放比率属性类型n标称：类别，状态，或“
3、名字的东西”Hair_color=黑色，棕色，金色，红色，红褐色，灰色，白色婚姻状况，职业，身份证号码，邮政编码n二进制只有2个状态（0和1）的属性对称二进制两种结果重要n例如，性别不对称的二进制结果同样重要。n例如，医疗测试（正面与负面）公约：将1至最重要的成果（例如，HIV阳性）n序数词价值观有一个有意义的顺序（排名），但不知道连续值之间的大小。大小=小，中，大，等级，军队排名2.2数据质量n被广泛接受的数据质量测量标准准确性完整性一致性合时性可信度解释性2.3数据预处理n数据预处理：概述数据预处理主要任务n数据清洗n数据集成n数据缩减n数据转换和数据离散化n总结2.3数据预处理主要任务n
4、数据清理填写缺失值，平滑噪声数据，识别或删除离群，并解决不一致问题n数据集成整合多个数据库，多维数据集或文件n数据缩减降维Numerosity reduction数据压缩n数据转换和数据离散化正常化生成概念层次结构数据清洗n在现实世界中的数据是“脏”的：不完整的：缺少属性值，缺乏某些属性值，或只包含总数据n例如，职业=“”（丢失的数据）n含嘈杂的噪音，错误或离群例如，工资=“-10”（错误）n不一致的代码或不符的名称年龄=“42”生日=“03/07/1997”曾经评级“1,2,3”，现在评级“A，B，C”重复的记录之间的差异不完整（缺少）数据n数据并不总是可用的例如，许多元组没有属性，如客户收
5、入、销售数据的记录值n丢失的数据，可能是由于设备故障与其他记录的数据不一致，从而删除因误会而未读入在读入的时候，某些数据可能不会被认为是重要的不是历史或更改的数据注册n丢失的数据可能需要被推断如何处理丢失数据？n忽略元组：通常是类标签丢失时（这样做分类），每个属性的缺失值有很大的差别n手动填写遗漏值n自动填写全局常量属性含义属性意味着所有样本属于同一类最有可能的值：基于诸如贝叶斯公式或决策树推理噪声数据n噪声：一个测量变量中的随机错误或方差n原因收集工具故障数据录入问题数据传输问题技术限制命名约定不一致n其他数据问题需要数据清理如重复记录数据不完整不一致的数据如何处理噪声数据？n回归数据拟合n
6、聚类检测和删除离群n结合计算机和人工检查检测可疑的数据（例如人工处理可能的异常值）数据清洗n数据的误差检测使用元数据（例如，领域，范围，依赖，分销）检查是否溢出检查唯一性规则，连续统治和空的规则使用商业工具n数据清理：使用领域知识（例如，邮政编码，拼写检查），检测错误并改正n数据审计：通过分析数据检测违规者（例如，关联和聚类规则和关系，寻找离群）n数据迁移和整合数据迁移工具：允许指定的转换ETL（提取/转换/加载）工具：通过图形用户界面允许用户指定转换n两个过程的集成迭代和交互数据集成n数据集成将来自多个数据源的数据组合成一个连贯的数据源n模式集成：例如，A.cust-id B.cust-#整
7、合来自不同来源的元数据n实体识别问题：识别来自多个数据源的真实世界的实体，例如，Bill Clinton=William Clintonn数据冲突检测和解决对于同一个真实世界的实体，来自不同源的属性值可能的原因：不同的表述，不同的尺度，例如，公制与英制单位数据集成中的冗余信息的处理n整合多个数据库经常发生数据冗余Object identification：相同的属性或对象可能有不同的名字在不同的数据库中Derivable data：一个属性可能是“派生”的另一个表中的属性，例如，年收入n通过相关性分析和协方差分析可以检测到冗余的属性n仔细集成来自多个数据源，可能有助于减少/避免冗余和不一致的地
8、方，并提高读取速度和质量相关分析n2(chi-square)testn2值越大，越有可能变量是相关的nThe cells that contribute the most to the 2 value are those whose actual count is very different from the expected countn相关性并不意味着因果关系#of hospitals and#of car-theft in a city 是相关的两者都因果联系的第三个变量为人口ExpectedExpectedObserved22)(2(chi-square)test举例举例Play c
9、hessNot play chessSum(row)Like science fiction250(90)200(360)450Not like science fiction50(210)1000(840)1050Sum(col.)30012001500n2（卡方）计算（括号中的数字是预计计数基于两个类别中的数据分布计算）n这表明，组中的like_science_fiction和play_chess相关93.507840)8401000(360)360200(210)21050(90)90250(22222相关分析数据（数字数据）n相关系数（也称为皮尔逊积矩系数）n其中n是元组的数目，而p和
10、q是各自的具体值，p和q是各自的标准偏差，n如果R（p，q）0，p和q是正相关的（p的值增加为q的），较高的相关性。nR（p，q）=0：独立；R（p，q）0，则p和q都倾向于是大于它们的预期值。n负的协方差：如果在COV（p，q）0。数据缩减策略n数据还原：还原面积更小、体积减少的数据集，但尚未产生相同（或几乎相同）的分析结果n为什么数据缩减？-由于数据仓库可以存储TB的数据，因此在一个完整的数据集上运行时，复杂的数据分析可能需要一个很长的时间n数据缩减战略降维，例如，删除不重要的属性n小波变换n主成分分析（PCA）n特征选择，特征创建nNumerosity reduction回归和对数线性模
11、型直方图，聚类，取样数据立方体聚集n数据压缩降维n原因原因随着维数的增加，数据变得越来越稀疏对孤立点分析使得密度和距离变得意义不大子空间的可能的组合将成倍增长n降维作用避免维数灾难帮助消除无关紧要的属性，并降低噪音减少数据挖掘所需的时间和空间更容易的可视化n降维技术小波变换主成分分析监督和非线性技术（例如，特征选择）将数据映射到一个新的空间n傅里叶变换n小波变换Two Sine WavesTwo Sine Waves+NoiseFrequency小波变换是什么？n分解成不同的频率子带的信号适用于n维信号n转化的数据是在不同级别的分辨率中保存n用于图像压缩小波变换n离散小波变换（DWT）的线性信
12、号处理n压缩近似：只有一小部分的小波系数最强n离散傅里叶变换（DFT）类似，但在空间中有更好的压缩效果n方法：长度L，必须是2的整数次幂（0填充，必要时）每个变换具有2个功能：平滑，差异适用于双数据，在两个集得到的长度为L/2的数据施加两个递归函数，直到达到所需要的长度小波变换n小波：空间高效分解的数学工具n2，2，0，2，3，5，4，4可转化为S=S=23/4，-11/4，1/2，0，0，-1，0n压缩：许多小细节系数可以替换为0的，只有显示的系数被保留为什么小波变换？n使用hat-shape滤波器强调区域点聚集的地方在边界禁止较弱的信息n有效去除离群值对噪声不敏感n多分辨率在不同尺度检测任
13、意形状的集群n高效复杂度为O（N）n只适用于低维数据主成分分析（PCA）n原始数据投影到一个更小的空间，从而查找投影来捕获最大的变化量数据的，从而维数降低。n发现协方差矩阵的特征向量，用这些特征向量定义新的空间x2x1e主成分分析（步骤）n从n维向量中的N个数据中，求kN个正交向量（主成分）能用来表示数据归一输入数据：每个属性落在相同的范围内（单元）计算K：正交向量，即，主成分每个输入的数据（矢量）是k个主分量矢量的线性组合通过排序减少“意义”或强度的组成部分由于这些组件的排序方式，消除了弱的元件，即具有低方差（即，使用最强的主成分，也能够重建原始数据的一个很好的近似，可以减少数据的大小）属性
14、子集选择n通过属性子集选择以减少数据的维n多余的属性复制所有的信息中包含一个或多个其他属性例如，购买一个产品的价格和支付额两个属性相同，是多余的属性n不相关的属性不包含任何信息的属性例如，学生的ID往往在预测学生的GPA是不相关的启发式搜索属性选择nd的属性有可能是2d属性组合n典型的启发式属性选择方法：Best single attribute属性独立性假设：选择进行检验分步进行的功能选择：分步进行属性消除：n反复淘汰不需要的属性n最佳组合的属性选择和淘汰n优化分支和绑定：使用属性消除和回溯创建属性（特征生成）n创建新的属性（特征），可以更有效地比原来的数据捕捉重要的信息三个一般方法属性提取
15、n domain-specific将数据映射到新的空间（见：数据缩减）n例如，傅立叶变换，小波变换，歧管的方法（未覆盖）Attribute construction n数据离散化Numerosity Reductionn通过选择更小的数据来替代从而减少数据量n参数方法（例如，回归）假设数据适合一些模型，估计模型参数，只存储参数，并丢弃数据（可能的异常值除外）例如：对数线性模型在一个点在MD的空间作为产品上获得价值，适当的边际子空间n非参数方法不要假设模型主要方法：直方图，聚类，取样，.参数数据还原：回归和对数线性模型n线性回归：一次函数通常使用最小二乘法来拟合线n多元回归：允许多维特征向量的线
16、性函数建模为变量Yn对数线性模型：近似离散的多维概率分布回归分析n回归分析：组成的一个因变量（也称为响应变量）和一个或多个独立变量（亦称解释变量或预测变量的值的数值数据建模和分析技术的统称）n参数估计，以便使数据“最适合”n最常用的是通过使用最小二乘法来进行评估，但也被用于其他标准n用于时间序列数据预测等的预测，推断，假设检验，因果关系的建模xy=x+1X1Y1Y1回归分析和对数线性模型n线性回归：Y=W X+B两个回归系数，w和b，指定行，并且要使用手工的数据估计使用最小二乘准则已知的值，Y1，Y2，.，X1，X2，.n多元回归：Y=b0+b1 X1+b2 X2.。许多非线性函数，可转化为上
17、述n线性模型：多路表的联合概率近似为低阶表概率：p(a,b,c,d)=ab acad bcd直方图分析n将数据划分为buckets，然后存储buckets的均值n分区规则：等宽：等于buckets范围相等的频率（或等于深度0510152025303540100002000030000400005000060000700008000090000100000聚类n分区数据基于相似性进行存储，只能设置成集群（例如，质心和直径）n如果数据是集群 则非常有效，否则效果较差n可以在多维索引树结构有层次聚类和存储n聚类定义和聚类算法有很多选择n聚类分析在后续将进行深入研究采样n采样：获得一个小样本代表整个数
18、据Nn主要原则：选择有代表性的数据子集简单随机抽样开发的自适应采样方法，例如分层抽样n注：采样不得减少数据库I/O（第一次）采样类型n简单随机抽样相等的概率选择n不放回抽样一旦对象被选中，则将其删除n更换采样选择对象不会被删除n分层抽样对每个分区进行数据集的分区抽样（也就是说，大约相同比例的数据进行抽取样本）用于偏斜数据取样：用或不用更换SRSWOR(simple random sample without replacement)SRSWRRaw Data采样：群集或分层抽样Raw Data Cluster/Stratified Sample数据压缩n字符串压缩有丰富的理论和压缩算法通常无损
19、n音频/视频压缩通常有损压缩，需要逐步细化n时间序列压缩典型的短期和随时间变化缓慢数据压缩Original DataCompressed DatalosslessOriginal DataApproximated lossy数据转换n函数映射指给定的属性值更换了一个新的表示方法，每个旧值与新的值可以被识别n方法平滑：从数据中去除噪声属性/重新构造n从给定的构造的新的属性聚合：汇总数据计算规范化：指定范围内缩放属于较小的n最小-最大规范化nZ-得分正常化n小数定标规范化离散化：概念层次Discretization 离散n三种类型的属性从一个无序的设置，例如，颜色，专业的值从一个有序的集合，例如，
20、军事或学术排名次序值数字，真实的数字，例如，整数或实数n离散化：除以间隔连续属性的范围区间的标签可以被用来代替实际的数据值减少数据大小离散监督与无监督分割（自顶向下）与合并（自下而上）离散化，可以进行递归属性准备作进一步的分析，例如，分类数据离散化方法n典型的方法：所有的方法可应用于递归Binning n自顶向下的分割直方图分析n自顶向下的分割n其他方法聚类分析（无监督，自上而下裂开或自底向上的合并）决策树分析（监督，自上而下的分割）相关性分析（无监督，自下而上合并）离散不使用类标签（分级与集群）Equal frequency(binning)K-means clustering leads
21、to better results离散使用类标签n决策树方法（基于信息熵）3 categories for both x and y5 categories for both x and y概念层次生成n概念层次组织层次概念（即属性值）通常指数据仓库中的每个维度n概念层次通过滚动来查看数据在数据仓库中多粒度n形成概念层次：递归减少数据收集和更换低层次的概念（如年龄的数值）到更高层次的概念（如青年，成年，或高级）n由领域专家和/或数据仓库设计概念分层可以显式指定n概念层次可以自动形成数字和标称数据。对于数字数据，使用所示的离散化方法。总结n数据质量的准确性，完整性，一致性，时效性，可信性，解释性
22、n数据清洗：如缺少/高噪音值，离群值n来自多个来源的数据集成实体识别问题删除冗余检测不一致n数据缩减降维Numerosity reduction数据压缩n数据转换和数据离散化正常化生成概念层次2.4数据相似性和相异性度量n相似数值衡量两个数据对象值越高对象时更相似往往属于在区间0,1n相异（例如，距离）两个不同的数据对象的数值衡量值越低对象时更相异最低相异往往是0上限各不相同n接近指的相似性或不相似数据矩阵和相异矩阵n数据矩阵n个数据两种模式n相异矩阵n个数据点三角矩阵单模 npx.nfx.n1x.ipx.ifx.i1x.1px.1fx.11x 0.)2,()1,(:)2,3().ndnd0d
23、d(3,10d(2,1)0举例：数据矩阵和相异矩阵Dissimilarity Matrix(with Euclidean Distance)Data Matrix总结n数据属性类型：名义，二进制，顺序，间隔缩放比例，缩放n许多类型的数据集，例如，数值，文字，图形，网页，图像等。n洞察数据通过以下几种方式：基本的统计数据说明：集中趋势，分散，图形显示数据可视化：map data onto graphical primitives测量数据相似n上述步骤是数据预处理的开始。n许多方法已经开发，但现在其仍然是一个活跃的研究领域2.5数据统计汇总n动机为了更好地理解数据：集中趋势，变异和传播n数据的分散
24、特性最大值，最小值，中位数，位数，离群值，方差等。n尺寸数值对应排序的时间间隔数据分散性：多粒度的精确分析箱形图或位数排序的时间间隔分析测量集中趋势n平均（代数措施）（样品与人口）：注：n为样本大小和N是人口规模。加权算术平均值：n修剪意味着：去掉极端值中位数：中间值，如果值，奇数或平均中间的两个值，否则估计插补（分组数据）：n模式最频繁出现的值，该值在数据单峰，双峰，三峰经验公式：niixnx11niiniiiwxwx11Nx对称VS偏斜数据，n中位数，均值和对称模式，正面和负面的偏斜数据测量数据的分散性n四分位数，离群和盒状图四分位数（第25百分位）：Q1，Q3（第75百分位）四分位数间距
25、：IQR=Q3-Q1n箱形图：盒子的两端是四分位数明显;单独添加胡须，情节离群n离群：通常情况下，一个值高于/低于1.5IQR方差和标准差（样本：，人口：）方差：（代数，可扩展的计算）n标准差s（或）是方差的平方根2（或2）niniiiniixnxnxxns1122122)(111)(11niiniixNxN1221221)(1箱线图分析n五号码分布摘要最小，Q1，中位数，Q3，最大n箱形图数据表示与一个框框的端部上面的第一个和第三个四分位数，即，框的高度是四分位数间距方框内的中位数的带标记的线两线最小和最大扩展到外箱可视化数据分散：3-D箱图正态分布曲线的属性n正常分布曲线从-+：含有约68
26、的测量（：均值，：标准偏差）从-2+2：包含约95的从-3，+3：包含约99.7图形显示的基本统计描述n箱形图：图形显示n直方图：x轴值，y轴频率n位数：每个值xn位数-分位数（QQ）：一个单变量分布的分位数对相应位数的另一个图表n散点图：每个值对是一对坐标，其绘制在平面上相比盒形图直方图往往告诉更多n两个在右侧的直方图显示其可以具有相同的盒形图表示效果相同的values：最小，Q1，Q3，中位数，最大n但是他们有相当不同的数据分布位数图n显示的所有数据（允许用户评估整体行为和不寻常的事件）n位数信息对于数据x进行递增的顺序排序，FI表示，约一定比例的数据网络连接均低于或等于值xi散点图n二元
27、数据显示点的分布，离群点等n被视为一对坐标值的每对点在平面上绘制成正面和负面的相关数据n左半片段是正相关的n右半边是负相关不相关的数据2.6数据可视化n为什么数据可视化？将图元数据映射到信息空间提供大型数据集的定性浏览搜索数据之间的关系如模式，趋势，结构，规则，帮助进一步定量分析，通过合适的参数找到有趣的地区提供可视化的陈述n典型的可视化方法：几何技术基于图标的技术分层技术几何技术n几何变换和预测的数据可视化方法直接的数据可视化散点图矩阵Landscapes投影寻踪技术n寻找有意义的多维数据预测 Hyperslice平行坐标直接数据可视化n基于Vorticity的色带散点图矩阵Landscap
28、esn可视化的数据透视Landscapesn这些数据需要转化成一个（可能是人工的）二维空间表示，其中保存的数据的特征平行坐标n将一个轴划分为N等距离，每一个距离对应一个属性n轴缩放在最小，最大之间：对应属性范围n每一个数据项目（折线）对应的各轴相交的点表示相对应的属性值Attr.1Attr.2Attr.kAttr.3 平行坐标数据集基于图标的技术n将数据值作为可视化功能的图标n典型的可视化方法：Chernoff FacesStick Figuresn一般技术形状编码：使用形状来表示一定的信息编码彩色图标：使用彩色图标的信息编码TileBars：使用小图标代表文件检索的特征向量Chernoff
29、Facesn一种来显示二维表面上的变量的方法，例如，让x是眉毛倾斜，y是眼睛的大小，z是鼻子长度等n该组图显示了人脸部的10个特征-眼睛的大小，眼间距，偏心眼，瞳孔大小，眉毛倾斜，鼻子的大小，嘴的形状，嘴巴大小，张口等n参考文献：Gonick,L.and Smith,W.The Cartoon Guide to Statistics.New York:Harper Perennial,p.212,1993nWeisstein,Eric W.Chernoff Face.From MathWorld-A Wolfram Web R Stick Figuresn普查数据显示，年龄，收入，性别，教育等
30、等。分层技术n使用子空间分层分区的数据可视化。n方法Dimensional StackingWorlds-within-WorldsTree-Map Cone TreesInfoCubeDimensional Stackingn在2-D的子空间中分配的n维属性空间，堆叠相互转化n划分成类的属性值范围时，重要属性使用在the outer levels上。n低基数与序属性数据n超过九个维度难以显示n重要的地图尺寸适当attribute 1attribute 2attribute 3attribute 4Worlds-within-Worldsn指定两个最重要的参数n修复所有其他参数（1或2或3维世
31、界选择这些轴）n软件使用此范例，nNvision：通过data glove and stereo 立体显示，包括旋转，缩放（内环）和翻译（内/外动力相互作用）nAuto Visual:通过查询静态互动Tree-Mapn屏幕填充方法具体指根据属性值采用了分层方法将屏幕分割成区域nx和y维度的画面交替地进行分区的属性值（类）MSR NetScan的图片文件系统的Tree-MapThree-D Cone TreesnThree-D Cone Trees的可视化技术的工作原理首先建立一个二维的圆，安排节点在根节点上的同心圆，然后逐渐形成树预计到2D时无法避免重叠nG.Robertson,J.Macki
32、nlay,S.Card.“Cone Trees:Animated 3D Visualizations of Hierarchical Information”,ACM SIGCHI91InfoCuben3-D可视化技术，n分层信息显示嵌套的半透明立方体n最外层的多维数据集对应数据，里面的smmaller立方体表示的子节点或底层数据等参考文献nD.P.Ballou and G.K.Tayi.Enhancing data quality in data warehouse environments.Comm.of ACM,42:73-78,1999nT.Dasu and T.Johnson.Exp
33、loratory Data Mining and Data Cleaning.John Wiley,2003nT.Dasu,T.Johnson,S.Muthukrishnan,V.Shkapenyuk.Mining Database Structure;Or,How to Build a Data Quality Browser.SIGMOD02nH.V.Jagadish et al.,Special Issue on Data Reduction Techniques.Bulletin of the Technical Committee on Data Engineering,20(4),
34、Dec.1997nD.Pyle.Data Preparation for Data Mining.Morgan Kaufmann,1999nE.Rahm and H.H.Do.Data Cleaning:Problems and Current Approaches.IEEE Bulletin of the Technical Committee on Data Engineering.Vol.23,No.4nV.Raman and J.Hellerstein.Potters Wheel:An Interactive Framework for Data Cleaning and Transf
35、ormation,VLDB2001nT.Redman.Data Quality:Management and Technology.Bantam Books,1992nR.Wang,V.Storey,and C.Firth.A framework for analysis of data quality research.IEEE Trans.Knowledge and Data Engineering,7:623-640,1995D.P.Ballou and G.K.Tayi.Enhancing data quality in data warehouse environments.Comm.of ACM,42:73-78,1999Thank you
