清华大学大数据课程第4次课数据挖掘技术145

大数据分析和内存计算第4讲数据挖掘技术概述李国良清华大学计算机系提纲数据挖掘概览数据预处理分类（Classification）聚类（Cluster）关联规则（AssociationRule）回归（Regression）数据挖掘概览What?数据挖掘的定义Why?数据挖掘的动机How?哪些数据可以用来挖掘？数据挖掘的主要内容数据挖掘定义什么是数据挖掘（DataMining）？Extractionofinteresting(non-trivial,implicit,previouslyunknownandpotentiallyuseful)patternsorknowledgefromhugeamountofdata其他称谓：Knowledgediscovery(mining)indatabase(KDD),data/patternanalysis,businessintelligence,decision-supportsystem,knowledgeextraction,dataarcheology,datadredgingandinformationharvestingetc.DatapreprocessingDataminingpostprocessingknowledgerawdataFeatureselectionDimensionreductionNormalizationDatasubsettingFilteringpatternsVisuaralizationPatterninterpretationDataMiningProcess模式有效性度量SimplicityE.g.,(association)rulelength,(decision)treesizeCertaintyE.g.,confidence,P(A|B)=#(AandB)/#(B),classificationreliabilityoraccuracy,rulestrength,etc.UtilityPotentialusefulness,e.g.,support(association),noisethreshold(description)NoveltyNotpreviouslyknown,surprising(usedtoremoveredundantrules)为何需要数据挖掘？1.数据量大2.缺乏理论知识3.数据挖掘可以帮助产生新的假说或者使数据变得有意义为何需要数据挖掘？Wearedrowningindata,butstarvinginknowledgeDataexplosion:Automateddatacollectiontoolsandmaturedatabasetechnologyleadtotremendousamountsofdataaccumulatedand/ortobeanalyzedindatabases,datawarehouses,andotherinformationrepositories.苦恼:淹没在数据中;不能制定合适的决策!数据知识决策模式趋势事实关系模型关联规则序列目标市场资金分配贸易选择在哪儿做广告销售的地理位置金融经济政府人口统计生命周期数据挖掘的意义数据挖掘辅助社会管理促进民生改善支持商业决策推动科技进步股票趋势分析智能交通数据挖掘应用银行美国银行家协会(ABA)预测数据仓库和数据挖掘技术在美国商业银行的应用增长率是14.9％。分析客户使用分销渠道的情况和分销渠道的容量；建立利润评测模型；客户关系优化；风险控制等电子商务网上商品推荐；个性化网页；自适应网站…生物制药、基因研究DNA序列查询和匹配；识别基因序列的共发生性…电信欺诈甄别；客户流失…保险、零售数据挖掘应用Debt10%ofIncomeDebt=0%GoodCreditRisksBadCreditRisksGoodCreditRisksYesYesYesNONONOIncome$40KQQQQII123456factor1factor2factorn神经网络NeuralNetworks聚类分析ClusteringOpenAccn’tAddNewProductDecreaseUsage???Time序列分析SequenceAnalysis决策树DecisionTrees•倾向性分析•客户保留•客户生命周期管理•目标市场•价格弹性分析•客户细分•市场细分•倾向性分析•客户保留•目标市场•欺诈检测关联分析Association•市场组合分析•套装产品分析•目录设计•交叉销售数据挖掘步骤数据预处理数据清理（消除噪音或不一致数据，补缺）数据集成（多种数据源可以组合在一起）数据变换（规范化）数据规约（数据简化）数据挖掘算法（使用智能方法提取数据模式）分类、聚类、关联分析、回归预测、文本挖掘质量评估（识别提供知识的真正有趣模式）知识表示（可视化和知识表示技术）数据质量：为何需要数据预处理？数据质量衡量：准确度:correctorwrong,accurateornot完整度:notrecordedunavailable一致性:somemodifiedbutsomenot,dangling时效性:timelyupdate?可信度:howtrustablethedataarecorrect?可解释性:howeasilythedatacanbeunderstood?数据挖掘预处理的主要任务数据清理填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性数据集成集成多个数据库、数据立方体或文件数据变换规范化和聚集数据归约得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果数据离散化数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要数据清洗脏数据：例如设备错误，人或者机器错误，传输错误等不完整性：属性值缺失或者只有聚集数据例如：phone=“”;噪音：包含噪声、错误或者异常值例如：salary=-10不一致性:例如：age=42，birthday=03-07-2010假值：例如：使用某一值填补缺失属性缺失值（Incomplete/MissingData)数据并不总是完整的例如：数据库表中，很多条记录的对应字段没有相应值，比如销售表中的顾客收入引起空缺值的原因设备异常与其他已有数据不一致而被删除因为误解而没有被输入的数据在输入时，有些数据因为得不到重视而没有被输入对数据的改变没有进行日志记载空缺值要经过推断而补上如何补充缺失值忽略元组：当类标号缺少时通常这么做（假定挖掘任务设计分类或描述），当每个属性缺少值的百分比变化很大时，它的效果非常差。人工填写空缺值：工作量大，可行性低使用一个全局变量填充空缺值：比如使用unknown或-∞使用属性的平均值填充空缺值使用与给定元组属同一类的所有样本的平均值使用最可能的值填充空缺值：使用像Bayesian公式或判定树这样的基于推断的方法噪声数据噪声：一个测量变量中的随机错误或偏差引起不正确属性值的原因数据收集工具的问题数据输入错误数据传输错误技术限制命名规则的不一致其它需要数据清理的数据问题重复记录不完整的数据不一致的数据如何处理噪声数据分箱:firstsortdataandpartitioninto(equi-depth)binsthenonecansmoothbybinmeans,smoothbybinmedian,smoothbybinboundaries,etc.聚类detectandremoveoutliers人机融合detectsuspiciousvaluesandcheckbyhuman(e.g.,dealwithpossibleoutliers)回归smoothbyfittingthedataintoregressionfunctions分箱(Binning)等宽Equal-width(distance)partitioning:DividestherangeintoNintervalsofequalsize:uniformgridifAandBarethelowestandhighestvaluesoftheattribute,thewidthofintervalswillbe:W=(B–A)/N.Themoststraightforward,butoutliersmaydominatepresentationSkeweddataisnothandledwell.等深Equal-depth(frequency)partitioning:DividestherangeintoNintervals,eachcontainingapproximatelysamenumberofsamplesGooddatascalingManagingcategoricalattributescanbetricky.数据平滑的分箱方法price的排序后数据（单位：美元）：4，8，15，21，21，24，25，28，34划分为（等深的）箱：箱1：4，8，15箱2：21，21，24箱3：25，28，34用箱平均值平滑：箱1：9，9，9箱2：22，22，22箱3：29，29，29用箱边界平滑：箱1：4，4，15箱2：21，21，24箱3：25，25，34聚类：ClusterAnalysis每个簇中的数据用其中心值代替忽略孤立点先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。人工再审查这些孤立点Regression通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。线性回归多线性回归非线性回归XY2211XXY33221XXXYxyy=x+1X1Y1Y1’数据集成实体识别元数据可帮助避免错误知识图谱属性冗余相关分析数据重复（元组冗余）数据值冲突的检测与处理表示、比例或编码不同数据变换（规范化）平滑：去掉数据中的噪声。技术包括分箱、回归、聚类。聚集：对数据进行汇总或聚集。数据泛化（概化）：使用概念分层，用高层概念替换低层或“原始”数据。规范化：将属性数据按比例缩放，使之落入一个小的特定区间。最小-最大、Z-Score、按小数定标规范化。数据变换平滑，聚集数据概化，规范化属性构造(特征构造)有限区间的归一化：无限区间的归一化：模糊隶属度：minmaxminvv'vev11'数据规约海量数据代表性数据对海量数据进行复杂的数据分析和挖掘将需要很长时间，使得这种分析不现实或不可行。数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近保持原数据的完整性。对归约后的数据集挖掘将更有效，并产生相同（或几乎相同）的结果。数据规约数据归约策略：（1）数据立方体聚集：对数据立方体做聚集操作（2）属性子集选择：检测并删除不相关、弱相关或冗余的属性和维。（3）维度归约：删除不重要的属性（4）数值归约：用规模较小的数据表示、替换或估计原始数据（5）离散化和概念分层产生属性的原始数值用区间值或较高层的概念替换数据立方体据立方体存储多维聚集信息，提供对预计算的汇总数据进行快速访问。如：立方体内存储季度销售额，若对年销售额感兴趣，可对数据执行聚集操作，例如sum()等。属性子集选择通过删除不相关或冗余的属性（或维）减小数据集。其目标是找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性得到的原分布。通过穷举搜索找出有属性的最佳子集是不现实的。通常采用压缩搜索空间的启发式算法。如贪心算法：从局部最优到全局最优。逐步向前选择逐步向后删除向前选择和向后删除的结合决策树归纳维度规约维度归约使用数据编码或变