数据挖掘课件汇总

DataMining:ConceptsandTechniques数据挖掘

DataMining

DataMining:ConceptsandTechniques第1章.引言什么是数据挖掘？数据挖掘的功能数据挖掘系统的分类有关的几个问题总结DataMining:ConceptsandTechniques什么是数据挖掘?数据挖掘(数据库中的知识发现KDD):从存放在数据库、数据仓库或其它类型信息库中的大量数据中提取或挖掘有趣知识的过程。(重要的,暗含的,预先未知的以及潜在有用的）其它相关术语Datamining:用词不当?Knowledgediscovery(mining)indatabases(KDD),知识提取（knowledgeextraction）,模式分析（data/patternanalysis）,数据考古（dataarcheology）,数据捕捞（datadredging）,信息收割（informationharvesting）,商业智能（businessintelligence）,等等DataMining:ConceptsandTechniques为什么进行数据挖掘?—

潜在的应用数据库分析以及决策支持市场分析和管理目标市场,客户关系管理（customerrelationmanagement）,菜篮子分析，交叉销售，市场划分风险分析和管理预测，客户保持，改善保险业务，质量控制，竞争分析欺诈行为探查及管理，异常监测其它应用文本挖掘(新闻组,email,documents)andWeb分析.智能查询应答DataMining:ConceptsandTechniques市场分析和管理

(1)哪些数据需要分析?信用卡事务，优惠券，客户投诉，生活方式研究等等目标市场发现具有相同特征（兴趣，收入水平，消费习惯等）的客户群。.确定客户购买模式随时间变化情况交叉市场分析不同产品销售间的关联基于关联信息的预测DataMining:ConceptsandTechniques市场分析和管理(2)客户分析数据挖掘能指出哪种类型的客户灰购买什么产品（分类，聚类）确定客户需求为不同客户确定最好产品利用预测技术发现能够吸引新客户的因素。提供概要信息各种多维综合报告统计汇总信息（主要的数据的趋势和变化）DataMining:ConceptsandTechniques风险分析和管理财政计划和资产评估现金流分析和预测时间序列分析

(financial-ratio,trendanalysis,etc.)资源计划:资源与耗费汇总及比较竞争:竞争监控和市场方向各户分类及基于类别的定价在高竞争力市场设置价格策略DataMining:ConceptsandTechniques欺诈检测与管理(1)应用广泛应用于医疗保险,零售业,信用卡服务,电信领域(phonecardfraud),etc.方法利用历史数据建立欺诈行为模型，使用datamining技术来确定相关实例。例子汽车保险:detectagroupofpeoplewhostage（策划）accidentstocollectoninsurance（骗保）洗钱:监测可疑现金交易医疗保险:detectprofessionalpatientsandringofdoctorsandringofreferencesDataMining:ConceptsandTechniques欺诈检测与管理(2)监测不适当医学检查电话欺诈Telephonecallmodel:接受方,持续时间,每周或天的次数.分析与期望标准相偏离的模式.BritishTelecomidentifieddiscretegroupsofcallerswithfrequentintra-groupcalls,特别是移动电话，经常有打破数百万美元的欺诈。零售估计有38%的零售亏损来自不诚实的雇员.DataMining:ConceptsandTechniquesOtherApplications运动IBMAdvancedScoutanalyzedNBAgamestatistics(shotsblocked,assists,andfouls)togaincompetitiveadvantageforNewYorkKnicksandMiamiHeat天文学类星体Web应用通过分析web访问日志，发现客户的偏好和行为模式，分析网上市场的效果，改进网站的组织。DataMining:ConceptsandTechniques一些具体例子DataMining:ConceptsandTechniques一些具体例子例1：医生给一个病人看病（模式识别的完整过程）。测量病人的体温和血压，化验血沉，询问临床表现；通过综合分析，抓住主要病症；医生运用自己的知识，根据主要病症，作出正确的诊断。DataMining:ConceptsandTechniques一些具体例子选取做家具的松木。

怎样区分它的类型？观察：颜色、花纹、亮度、密度（样本测量值），得到样本模式综合分析：提取、选择主要特征根据主要区别：区分各单一样本（松木、桦木）DataMining:ConceptsandTechniques具体过程DataMining:ConceptsandTechniques常见的模式识别系统

DataMining:ConceptsandTechniques知识发现的步骤：

学习应用领域:相关先验知识和应用目标创建目标数据集:数据选择数据清理和预处理:(maytake60%ofeffort!)数据约简和转化:发现有用特征,维和变量约简.转化成适合挖掘的形式数据挖掘功能选择

摘要,分类,regression(回归）,关联,聚类.选择挖掘算法数据挖掘:查找感兴趣的模式模式评估及知识表达可视化,转化,删除冗余模式等等发现知识的使用DataMining:ConceptsandTechniques有些人将数据挖掘视为数据库中知识发现的一个基本步骤，如图Datamining:知识发现过程的核心过程.DataCleaningDataIntegrationDatabasesDataWarehouseKnowledgeTask-relevantDataSelectionDataMiningPatternEvaluationDataMining:ConceptsandTechniques典型数据挖掘系统的结构DataWarehouseDatacleaning&dataintegrationFilteringDatabasesDatabaseordatawarehouseserverDataminingenginePatternevaluationGraphicaluserinterfaceKnowledge-baseDataMining:ConceptsandTechniques1.预处理模式空间里，针对具体的研究对象，往往需要进行适当的预处理。去噪声，提取有用信息，并对输入测量仪器或其它因素所造成的退化现象进行复原具体地说，预处理的功能包括：清除或减少模式采集中的噪声及其它干扰，提高信噪比。消除或减少数据图像的模糊及几何失真，提高清晰度。转变模式的结构，以便后续处理（如非线性模式转为线性模式）。预处理的方法：滤波、变换、编码、标准化等。（这些内容在“数字信号处理”、“数字图像处理”等课程中学过）为了便于计算机处理，往往需要将模拟量转化为数字量，也就是进行A/D转换。在此过程中必须考虑2个问题，采样间隔与量化等级。采样间隔（采样频率），表示单位时间内（秒），要求多少个采样值。量化级，表示每个采样值要有多少个量化级，才能满足要求。2.特征提取/选择特征提取/选择的必要性和原则。一般的情况，人们对客观世界里的具体物体或事件进行模式采集时，总是尽可能多的采集测量数据，造成样本在模式空间里的维数很大。模式维数很大首先带来的问题是处理的困难，处理时间很长，费用很高，有时甚至直接用于分类是不可能的，即所谓“维数灾难”。另外，在过多的数据坐标中，有些对刻划事物的本质贡献不大，甚至很小。因此，特征提取/选择十分必要。特征提取/选择的目的目标：就是要压缩模式的维数，使之便于处理，减少消耗。特征提取往往以在分类中使用的某种判决规则为准则，所提取的特征使在某种准则下的分类错误最小。为此，必须考虑特征之间的统计关系，选用适当的正交变换，才能提取最有效的特征。特征提取的分类准则：在该准则下，选择对分类贡献较大的特征，删除贡献甚微的特征。3.分类分类目标：把特征空间划分成类型空间。把未知类别属性的样本确定为类型空间的某一个类型。在给定条件下，可以否定样本属于某种类型。实际分类过程中，对于预先给定的条件，分类中出现错误是不可避免的。因此，分类过程只能以某种错误率来完成。显然，错误率越小越好。但是，分类错误率又受很多条件的制约：分类方法、分类器设计、选用的样本及提取的特征等。因此，分类错误率不能任意小。此外，分类错误率的分析、计算也很困难，只有在较简单的情况下才能有解析的解。分类错误率是分类过程中的重要问题。DataMining:ConceptsandTechniques数据挖掘和商务智能IncreasingpotentialtosupportbusinessdecisionsEndUserBusinessAnalyst

DataAnalystDBA

MakingDecisionsDataPresentationVisualizationTechniquesDataMiningInformationDiscoveryDataExplorationOLAP,MDAStatisticalAnalysis,QueryingandReportingDataWarehouses/DataMartsDataSourcesPaper,Files,InformationProviders,DatabaseSystems,OLTPDataMining:ConceptsandTechniques数据挖掘功能(1)概念描述:特征化和区分

特征化：汇总相应概念的数据，描述这些数据的特征例如：研究上一年销售增加10%的软件产品的特征。产生一年内在AllElectronics花费$1000以上顾客特征描述。结果可能是：年龄在40-50，有工作，有很好的信用等级。

数据区分：将目标概念数据的特征与其它概念数据的特征进行比较。例如：上年销售增加10%的软件与同时期销售至少下降30%的软件进行比较。比较两组AllElectronics顾客，如定期购买计算机产品的顾客和偶（每年少于3次）购买这种产品的顾客。可能结果是常购买者80%在20-40岁之间，受过大学教育。偶尔购买者60%太老或太年轻，没有大学学位。DataMining:ConceptsandTechniques数据挖掘功能(1)关联

(相关和因果关系)关联规则：形如X=>Y,满足X中条件的记录多半也满足Y中条件。多维和单维关联age(X,“20..29”)^income(X,“20..29K”)=>buys(X,“PC”)[support=2%,confidence=60%]

所有顾客的2%在20-29岁，年收入20K-29K，并且在AllElectronics购买PC。而这个年龄和收入组的顾客购买PC的可能性为60%contains(T,“computer”)=>contains(x,“software”)[1%,75%]DataMining:ConceptsandTechniques数据挖掘功能

(2)分类和预测

找出描述并区分数据类或概念的模型，以便能够使用模型预测类标记未知的对象。例如：按气候分类国家，按油耗分类汽车。分类模式的表示方法:决策树,分类规则,神经网络预测:预测某些未知或空缺数据值。聚类分析类标记未知:产生类标记。聚类原则：最大化类内相似性，最小化类间相似性。例1.8P17DataMining:ConceptsandTechniques数据挖掘功能(3)孤立点分析孤立点:数据库中可能包含一些对象，它们与数据的一般行为或模型不一致，这些数据对象是孤立点。孤立点经常被作为噪声或异常丢弃，但在欺诈检测、罕见事件分析中却是十分有用的。趋势分析趋势分析描述随时间变化的对象的规律或趋势衰退分析序列模式挖掘，周期分析基于相似性的分析例如：股票市场数据DataMining:ConceptsandTechniques所有模式都是有趣的吗?数据挖掘系统可能产生数以千计的模式或规则。而并不是所有模式和规则都是有趣的。Suggestedapproach:Human-centered,query-based,focusedmining兴趣度度量:Apatternisinterestingifitiseasilyunderstoodbyhumans,validonnewortestdatawithsomedegreeofcertainty,potentiallyuseful,novel,orvalidatessomehypothesisthatauserseekstoconfirm客观兴趣度与主观兴趣度客观:基于模式的统计和结构

-------仅与数据本身有关

例：support,confidence,etc.主观:

基于用户对数据的确信。-------往往因人而异

例：意外性，新颖性，可操作性，有用性etc.DataMining:ConceptsandTechniques能发现所有有趣模式吗？能够仅产生有趣模式吗？发现所有有趣模式:挖掘算法的完全性Canadataminingsystemfindalltheinterestingpatterns?Associationvs.classificationvs.clustering是完全的。仅产生有趣模式:挖掘算法的优化问题Canadataminingsystemfindonlytheinterestingpatterns?方法Firstgeneralallthepatternsandthenfilterouttheuninterestingones.Generateonlytheinterestingpatterns—miningqueryoptimizationDataMining:ConceptsandTechniquesDataMining:多学科交叉DataMiningDatabaseTechnologyStatisticsOtherDisciplinesInformationScienceMachineLearningVisualizationDataMining:ConceptsandTechniquesDataMining分类Differentviews,differentclassifications挖掘各种类型数据库：关系，文本，多媒体，空间…所挖掘的知识类型不同：特征化，区分，关联，分类聚类。孤立点分析，趋势分析，偏差分析，…所使用的技术不同：如数据库技术，机器学习方法，统计学，可视化技术，模式识别所应用的场合：如金融，电信，DNA,股票市场，e-mail，…DataMining:ConceptsandTechniques在何种数据库上进行挖掘？关系数据库数据仓库事务数据库高级数据库系统面向对象和对象-关系数据库空间数据库时间序列数据库和临时数据文本数据库和多媒体数据库异类及遗产数据库WWWDataMining:ConceptsandTechniques关系数据库：是关系表的集合。每个表含有一组属性（字段），大量元组（记录）组成。

例1.1AllElectronics公司数据库由以下关系表组成：customer,item,employee,branchPP7常用操作：增删改查。数据库查询

例如：“显示上季度销售的商品列表”统计汇总

“汇总上季度总销售额”数据挖掘用于关系数据库：（1）分析customer表，根据客户收入、年龄和以前客户的信用信息预测新客户的信用等级。（2）检测偏差，与以前年分相比哪种商品销售出人意料。DataMining:ConceptsandTechniques数据仓库

AllElectronics有许多分公司，每个分公司有自己的数据库，要获得整个公司的销售情况该如何做呢？从各分公司数据库获得数据，整理汇总，一致化，去除重复，得到结果。若经常需要这种操作---重复，费时建立数据仓库---将这些数据整理、汇总后集中存放。见图1-7P9例1.2P9汇总销售的数据立方返回DataMining:ConceptsandTechniques事务数据库

由一个文件组成，文件中每个记录代表一个事务。一个事务包含一个唯一的事务ID,和组成事务的项的列表。例如：Sales事务表

trans_IDlistofitem_IDs

T100I1，I2，I5，I6T200I2，I3，I4，I7T300I5，I6T400I2，I6，I8数据挖掘问题：哪些商品适合一起销售？返回

DataMining:ConceptsandTechniques空间数据库：

数据挖掘问题：

“坐落在特定类型地点（如公园）的房屋特征。”

“根据城市离主要公路的距离描述都市贫困率的变化趋势”

返回DataMining:ConceptsandTechniquesWWW：

数据挖掘问题：挖掘用户访问模式网页特征和网页间关联挖掘特定主题的权威网页对网页进行分类

返回DataMining:ConceptsandTechniques总结Datamining:discoveringinterestingpatternsfromlargeamountsofdataAKDDprocessincludesdatacleaning,dataintegration,dataselection,transformation,datamining,patternevaluation,andknowledgepresentationDataminingfunctionalities:characterization,discrimination,association,classification,clustering,outlierandtrendanalysis,etc.ClassificationofdataminingsystemsDataMining:ConceptsandTechniquesABriefHistoryofDataMiningSociety1989IJCAIWorkshoponKnowledgeDiscoveryinDatabases(Piatetsky-Shapiro)KnowledgeDiscoveryinDatabases(G.Piatetsky-ShapiroandW.Frawley,1991)1991-1994WorkshopsonKnowledgeDiscoveryinDatabasesAdvancesinKnowledgeDiscoveryandDataMining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusamy,1996)1995-1998InternationalConferencesonKnowledgeDiscoveryinDatabasesandDataMining(KDD’95-98)JournalofDataMiningandKnowledgeDiscovery(1997)1998ACMSIGKDD,SIGKDD’1999-2001conferences,andSIGKDDExplorationsMoreconferencesondataminingPAKDD,PKDD,SIAM-DataMining,(IEEE)ICDM,etc.DataMining:ConceptsandTechniquesWheretoFindReferences?DataminingandKDD(SIGKDDmemberCDROM):Conferenceproceedings:KDD,andothers,suchasPKDD,PAKDD,etc.Journal:DataMiningandKnowledgeDiscoveryDatabasefield(SIGMODmemberCDROM):Conferenceproceedings:ACM-SIGMOD,ACM-PODS,VLDB,ICDE,EDBT,DASFAAJournals:ACM-TODS,J.ACM,IEEE-TKDE,JIIS,etc.AIandMachineLearning:Conferenceproceedings:Machinelearning,AAAI,IJCAI,etc.Journals:MachineLearning,ArtificialIntelligence,etc.Statistics:Conferenceproceedings:JointStat.Meeting,etc.Journals:Annalsofstatistics,etc.Visualization:Conferenceproceedings:CHI,etc.Journals:IEEETrans.visualizationandcomputergraphics,etc.第一节数据挖掘概念（应用举例，功能认识）数据挖掘过程介绍（举例，医生看病，木材识别，还是数据挖掘的概念）数据挖掘系统，机器学习过程数据挖掘功能分类第二节数据预处理（数据平滑）DataMining:ConceptsandTechniques数计学院陈晓云DataMining:ConceptsandTechniques39Chapter3:数据预处理目的?数据清洁数据集成和转换数据约减离散化和概念分层小结数计学院陈晓云DataMining:ConceptsandTechniques40WhyDataPreprocessing?实际数据经常含有”脏”数据不完全:缺少属性值，其少某些该兴趣的属性，或仅包含聚集数据。噪声:包含错误或存在孤立点不一致:编码或命名的矛盾没有高质量的数据，就没有高质量的挖掘结果。高质量决策必须有高质量数据数据仓库需要一致的高质量的集成数据。数计学院陈晓云DataMining:ConceptsandTechniques41数据质量的多维度量多维视图好坏的评价标准:Accuracy准确性Completeness完整性Consistency一致性Timeliness线性时间Believability可信的Valueadded附加值的Interpretability可判断的Accessibility可访问的Broadcategories:本质的,内容相关的,代表性的,可访问的数计学院陈晓云DataMining:ConceptsandTechniques42数据预处理的主要任务数据清洁填写缺失值，平滑噪声数据，识别、删除孤立点，解决不一致来”清理”数据。数据集成多个数据库，数据立方或文件的集成数据转化标准化和聚合如年龄和薪金属性取值范围差距很大。数据归约压缩数据集，而又不损害数据挖掘结果提高挖掘过程的速度数据聚集、维规约（去掉不相关属性）、数据压缩（最短编码）、概化（较高概念替换较低概念）数据离散化数据离散化是数据归约的一种，但特别重要。尤其对数值数据数计学院陈晓云DataMining:ConceptsandTechniques43数据预处理的形式数计学院陈晓云DataMining:ConceptsandTechniques44Chapter3:数据预处理目的?数据清洁数据集成和转换数据约减离散化和概念分层小结数计学院陈晓云DataMining:ConceptsandTechniques45数据清洁数据清洁任务填写缺失值识别和删除孤立点平滑噪声数据纠正不一致数据数计学院陈晓云DataMining:ConceptsandTechniques46缺失数据数据并非总是有用的例如在许多记录中有些属性值因为不重要而被忽略，如customerincomeinsalesdata（忽略元组）缺失数据是因为设备故障与其它数据不一致，被删除因为不能理解数据导致数据未被选中（加载时认为是不重要的）记录历史或修改的数据可能被忽空缺数据的补充需要推导数计学院陈晓云DataMining:ConceptsandTechniques47如何处理缺失数据?忽略元组:当类标号缺少时这样处理。(假设挖掘任务涉及分类或描述)—不是很有效，每个属性缺少值得百分比变化很大时，它的性能差。手工输入缺失数据:费时+不可靠?使用全局常量填充空缺值:例如，“unknown”,anewclass?!会误认为形成一个新概念使用属性的平均值填充缺失值:例如，假定客户的平均收入为28000元，则使用该值替换income中的空缺值。使用与给定元组属于同一类的所有样本的平均值。（好），同一类元组属性平均值使用最可能的值填充空缺值:基于统计方法预测Bayesian公式或决策树数计学院陈晓云DataMining:ConceptsandTechniques48噪声数据噪声:测量变量中的随机错误或偏差噪声数据产生的原因错误的数据集收集手段数据登陆问题数据传输问题技术局限命名约定时的不一致其他需要数据清洁的数据问题重复记录不完全数据不一致数据数计学院陈晓云DataMining:ConceptsandTechniques49如何处理噪声数据?分箱法:通过考查邻居局部平滑数据首先排序数据并将其存入等深的箱中。然后可以分别按箱均值、箱中值和箱边界平滑数据。

例P73数计学院陈晓云DataMining:ConceptsandTechniques50数据平滑的分箱方法*Price排序后的数据(indollars):4,8,9,15,21,21,24,25,26,28,29,34*划分为等深的箱:-Bin1:4,8,9,15-Bin2:21,21,24,25-Bin3:26,28,29,34*用箱平均值平滑:-Bin1:9,9,9,9-Bin2:23,23,23,23-Bin3:29,29,29,29*用箱边界平滑:-Bin1:4,4,4,15-Bin2:21,21,25,25-Bin3:26,26,26,34数计学院陈晓云DataMining:ConceptsandTechniques51聚类检测并移去孤立点P74图计算机+人工检测计算机检测出可疑值并且由人工检测是否噪声数据。回归让数据适合一个函数（回归函数)来平滑数据如何处理噪声数据?数计学院陈晓云DataMining:ConceptsandTechniques52聚类分析数计学院陈晓云DataMining:ConceptsandTechniques53回归xyy=x+1X1Y1Y1’数计学院陈晓云DataMining:ConceptsandTechniques54简单的离散方法:分箱等宽(距离)划分:将数据划分成N个等距离的区间。如果A

和B是属性最小和最大值，那么区间宽度为W=(B-A)/N.最直接简单孤立点容易占优势倾斜数据不易处理等深(频率)划分:将数据划分成N个区间，每个包含大致相等样本数量。数据缩放比例好.易于管理分类属性.数计学院陈晓云DataMining:ConceptsandTechniques55作业：实现等深分箱、等宽分箱的箱均值、箱中值、箱边界数据平滑。数计学院陈晓云DataMining:ConceptsandTechniques56Chapter3:数据预处理目的?数据清洁数据集成和转换数据约减离散化和概念分层小结数计学院陈晓云DataMining:ConceptsandTechniques57数据集成数据集成:将多个数据源中数据结合起来存放在一个一致的数据存储中集成计划从不同的源集成源数据实体识别:识别来自多数据源的现实实体，例如A.cust-idB.cust-number探测和解决数据值冲突现实世界的同一实体其来自不同源的属性值可能不同可能原因:表达不同,比例不同或编码不同，e.g.,公制单位vs.英制单位数计学院陈晓云DataMining:ConceptsandTechniques58处理冗余数据数据冗余问题属性能由另一表导出则是冗余的。如年薪属性或维命名不一致导致冗余相关分析检测冗余。P573.1将多个数据源中数据集成起来可以减少/避免冗余和矛盾，能够提高挖掘速度和质量。数计学院陈晓云DataMining:ConceptsandTechniques59卡方检验卡方检验由统计学家皮尔逊推导。理论证明，实际观察次数（fo）与理论次数（fe），又称期望次数）之差的平方再除以理论次数所得的统计量，近似服从卡方分布，可表示为：这是卡方检验的原始公式，其中当fe越大（fe≥5）,近似得越好。显然fo与fe相差越大，卡方值就越大；fo与fe相差越小，卡方值就越小；因此它能够用来表示fo与fe相差的程度。根据这个公式，可认为卡方检验的一般问题是要检验名义型变量的实际观测次数和理论次数分布之间是否存在显著差异（假设检验）。数计学院陈晓云DataMining:ConceptsandTechniques60CorrelationAnalysis(CategoricalData)Χ2(chi-square)test

Χ2

值越大,变量之间的相关性越强。实际计数与期望值相差最大的，对Χ2

值的贡献越大。相关并不意味着因果关系#ofhospitalsand#ofcar-theftinacityarecorrelatedBotharecausallylinkedtothethirdvariable:population设属性A有c个不同值，B有r个不同值。A和B描述的数据元组可以用一个相依表显示，其中A的c个值构成列，B的r个值构成行。令（Ai,Bj)表示属性A取值ai,B取值bj,.每个可能的(Ai,Bj)联合事件都在表中有自己的单元。值可以用下式计算其中期望观测次数可以用下式计算卡方统计检验假设A和B是统计独立的。检验基于显著水平，具有（r-1)*(c-1)自由度。数计学院陈晓云DataMining:ConceptsandTechniques61数计学院陈晓云DataMining:ConceptsandTechniques62Chi-SquareCalculation:AnExampleΧ2(chi-square)calculation(numbersinparenthesisareexpectedcountscalculatedbasedonthedatadistributioninthetwocategories)Itshowsthatlike_science_fictionandplay_chessarecorrelatedinthegroupPlaychessNotplaychessSum(row)Likesciencefiction250(90)200(360)450Notlikesciencefiction50(210)1000(840)1050Sum(col.)30012001500皮尔逊定理当（p1,p2,…,pr)是母体的真实概率分布时，由

式（1）定义的统计量的渐进分布是自由度为r-1的-分布。当我们要检验某个假设H0:pi=pi0,i=1,…r时，只要将pi0带入式（1），根据字样观察值计算出统计量的观察值并对给定的水平a,查x2-分布表，求出临界值，比较与，如果则做出拒绝H0的决定，认为实验结果与假设有显著差异。数计学院陈晓云DataMining:ConceptsandTechniques63数计学院陈晓云DataMining:ConceptsandTechniques64数计学院陈晓云DataMining:ConceptsandTechniques65【练习】某校对学生课外活动内容进行调查，结果整理成下表，表中彩色格子里的数是原始数据的汇总数，括号内的数是理论次数（是按下面将要介绍的原理计算得来的），此外的是原始数据。

性别(因素2)课外活动内容(因素1)小计和(fx)体体育

文娱阅读男生21112355女生

672942小计和(fy)27185297数计学院陈晓云DataMining:ConceptsandTechniques66【练习】某校对学生课外活动内容进行调查，结果整理成下表，表中彩色格子里的数是原始数据的汇总数，括号内的数是理论次数（是按下面将要介绍的原理计算得来的），此外的是原始数据。

性别(因素2)课外活动内容(因素1)小计和(fx)体体育

文娱阅读男生21(15.3)11(10.2)23(29.5)55女生

6(11.7)

7(7.8)29(22.5)42小计和(fy)27185297数计学院陈晓云DataMining:ConceptsandTechniques67df=(3-1)(2-1)=2，而x22,0.05=5.99，所以在0.05的显著性水平下，拒绝独立性假设，即可以认为性别与课外活动内容有关联，或者说男女生在选择课外活动上存在显著的差异。数计学院陈晓云DataMining:ConceptsandTechniques68数据变换平滑:removenoisefromdata聚集:summarization,datacubeconstruction数据概化:concepthierarchyclimbing规范化:scaledtofallwithinasmall,specifiedrangemin-maxnormalizationz-scorenormalizationnormalizationbydecimalscaling（小数定标规范化）属性构造Newattributesconstructedfromthegivenones数计学院陈晓云DataMining:ConceptsandTechniques69DataTransformation:Normalizationmin-maxnormalization例3.1P76z-scorenormalizationP77例3.2normalizationbydecimalscaling通过移动小数点位置规范化例P773.2WherejisthesmallestintegersuchthatMax(||)<1数计学院陈晓云DataMining:ConceptsandTechniques70Chapter3:数据预处理目的?数据清洁数据集成和转换数据归约离散化和概念分层小结数计学院陈晓云DataMining:ConceptsandTechniques71数据归约数据仓库可以存储TB级数据

:在大规模数据上进行复杂的数据分析和挖掘将花费大量的时间什么是数据归约数据归约可以得到数据集的规约表示，它小得多，但仍接近于保持原数据的完整性。数据归约策略数据立方的聚集操作维归约：检测并删除不相关、弱相关或冗余的属性或维。数据压缩：使用编码机制压缩数据集数值压缩：用替代的较小的数据表示替换或估计数据。离散化和概念分层产生：属性的原始值用区间值或较高层概念替换。数计学院陈晓云DataMining:ConceptsandTechniques72数据立方体聚集数据立方的最低层称基本方体，最高层抽象的数据立方称为顶点方体。为得到感兴趣的实体集成数据。例

P78-3.4.1.在数据立方中的多层聚集方体格较高层抽象可进一步减少数据基本方体应当对应于感兴趣的实体。使用与给定任务相关的最小方体。查询聚集信息时，应尽可能用数据立方回答。数计学院陈晓云DataMining:ConceptsandTechniques73维归约通过删除不相关属性减少数据量。特征选择

(例如属性子集选择):找出最小属性集，使数据类的概率分布尽可能接近使用所有属性的原分布。例：根据广告后是否愿买CD将顾客分类，与属性age,music_taste不同,电话号码等属性是不相关的。减少发现模式中的属性数目，易于理解。属性选择的启发式方法—贪心算法

因为当属性数增加时，组合爆炸，d个属性有2d个子集:逐步前向选择逐步后向删除组合前向选择和后项删除决策树归纳ID3，C4.5数计学院陈晓云DataMining:ConceptsandTechniques74决策树归纳的例子原始属性集

:{A1,A2,A3,A4,A5,A6}A4?A1?A6?Class1Class2Class1Class2>约简属性集:{A1,A4,A6}数计学院陈晓云DataMining:ConceptsandTechniques75属性选择的贪心算法d

个特征有

2d个可能的子集集中启发式特征选择方法:在特征独立性假设下最优的单特征：通过重要性测试选择特征.每步选取特征:最初选择最优的单个特征然后下一个最好的特征被选择,...每步特征的删除:重复删除最糟的特征最优的特征选择和删除:最佳的分支和边界:使用特征删除和回溯数计学院陈晓云DataMining:ConceptsandTechniques76数据压缩数据压缩应用数据编码或变换，以便得到原数据的归约或压缩。典型的无损压缩，压缩数据重新构造而不损失任何信息。一些很好的串压缩算法仅允许有限操作音频/声频压缩典型的有损压缩只能重新构造原数据的近似表示。时间序列不是音频速度慢数计学院陈晓云DataMining:ConceptsandTechniques77数据压缩原始数据压缩后数据无损原始数据估计有损数计学院陈晓云DataMining:ConceptsandTechniques78维度规约---小波变换离散小波变换DWT:线性信号处理技术压缩近似:仅保存小波系数最强的较小片断与离散Fourier变换相似(DFT),但是更好的有损压缩。

给定的数据向量，如果DWT和DFT保留相同数目的系数，DWT将提供原数据更精确的近似。

Haar2Daubechie4数计学院陈晓云DataMining:ConceptsandTechniques79假定待压缩的数据由N个元组或数据向量组成，取自k-维。找出c个最能代表数据的k-维正交向量。原始数据投影到一个较小空间,导致数据压缩。每个数据向量是c个主成分向量的线性组合仅对数值数据有效当维数较大时使用维度规约---主成分分析数计学院陈晓云DataMining:ConceptsandTechniques80X1X2Y1Y2主成分分析数计学院陈晓云DataMining:ConceptsandTechniques81数值归约参数法假定数据是某些模型，评估适合数据的模型参数，并只存储参数而删去数据（可能是孤立点）对数线性模型:近似离散的多维概率分布无参数法不能假设模型主要方法:直方图,聚类,取样数计学院陈晓云DataMining:ConceptsandTechniques82回归及对数线性模型线性回归:对数据建模，使之适合一条直线。经常使用最小平方法拟合直线多元回归:响应变量是多维特征向量的线性函数。对数线性模型:近似离散的多维概率分布数计学院陈晓云DataMining:ConceptsandTechniques83线性回归:Y=+X两个参数,and确定一条直线并用以估计数据.对Y1,Y2,…,X1,X2,….利用最小平方准则

多元回归:Y=b0+b1X1+b2X2.许多非线性函数能转化成上式.对数线性模型:Themulti-waytableofjointprobabilitiesisapproximatedbyaproductoflower-ordertables.概率:p(a,b,c,d)=abacadbcd回归分析及对数线性模型数计学院陈晓云DataMining:ConceptsandTechniques84直方图流行的数据约减方法（用分箱法）将数据分成若干桶并存储每个桶的平均值(和)在一维情况下可以使用动态规划。例：P83数计学院陈晓云DataMining:ConceptsandTechniques85例3.4商品单价排序：1,1,5,5,5,5,5,8,8,10,10,10,10,12,14,14,14,15,15,15,15,15,15,18,18,18,18,18,18,18,18,20,20,20,20,20,20,20,21,21,21,21,25,25,25,25,25,28,28,30,30,30

单桶：属性值/频率对频率2524136874523属性值15810121415182021252830

桶等宽直方图

132514

1-1011-2021-30数计学院陈晓云DataMining:ConceptsandTechniques86聚类将数据对象划分为群或聚类，使得在一个聚类中的对象“类似”，但与其他聚类中的对象不类似。类似性用距离描述。例P85图3-11归约时用数据聚类表示实际数据。层次聚类并存储在多维索引树结构中。P85图3-12有多种聚类定义和聚类算法，详见第8章。数计学院陈晓云DataMining:ConceptsandTechniques87取样用较小的数据子集表示大的数据集。花费正比于样本大小n，而不是数据大小。其它归约方法要扫描整个数据集Choosearepresentativesubsetofthedata简单随机选样：从N个元组中随机抽取n个（n<N)样本分为回放不回放简单取样当数据倾斜严重时性能较差自适应取样方法分层选样:D被分为不相交的部分，通过对每层的简单随机选样可以得到D的分层选样。当数据倾斜时，可保证选样的数据具有代表性聚类选样图3-113-12例：图3-13数计学院陈晓云DataMining:ConceptsandTechniques88SamplingSRSWOR(simplerandomsamplewithoutreplacement)SRSWRRawData数计学院陈晓云DataMining:ConceptsandTechniques89SamplingRawDataCluster/StratifiedSample数计学院陈晓云DataMining:ConceptsandTechniques90层次归约Usemulti-resolutionstructurewithdifferentdegreesofreductionHierarchicalclusteringisoftenperformedbuttendstodefinepartitionsofdatasetsratherthan“clusters”ParametricmethodsareusuallynotamenabletohierarchicalrepresentationHierarchicalaggregationAnindextreehierarchicallydividesadatasetintopartitionsbyvaluerangeofsomeattributesEachpartitioncanbeconsideredasabucketThusanindextreewithaggregatesstoredateachnodeisahierarchicalhistogram数计学院陈晓云DataMining:ConceptsandTechniques91Chapter3:数据预处理目的?数据清洁数据集成和转换数据约减离散化和概念分层小结数计学院陈晓云DataMining:ConceptsandTechniques92离散化三种属性类型:名词性的—如:颜色，职业序数—来自于有序的数据值,如：军衔，学术职称连续的—如：整数，实数好处：通过将连续属性值域划分为区间，可以减少给定连续属性值的个数。区间标号可以代替实际的数据值。某些分类算法仅允许分类属性数计学院陈晓云DataMining:ConceptsandTechniques93离散化和概念分层离散化：通过将属性范围划分成若干区间，减少属性取值个数。区间标号可以替代实际的数据值。有监督和无监督的离散化分裂的（自顶向下的）与合并的（自底向上的）概念分层离散化：递归的减少数据bycollectingandreplacinglowerlevelconcepts(suchasnumericvaluesfortheattributeage)byhigherlevelconcepts(suchasyoung,middle-aged,orsenior).如P87-图3-14数计学院陈晓云DataMining:ConceptsandTechniques94数值数据的离散化和概念分层的产生分箱(seesectionsbefore)直方图分析(seesectionsbefore)聚类分析(seesectionsbefore)基于熵的离散化基于2分析的区间合并自然划分分段数计学院陈晓云DataMining:ConceptsandTechniques95基于熵的离散化已知样本集S,如果S用边界T被划分成两个区间S1和S2,划分后的熵为阀值T是使划分得到信息增益最大。该过程直到条件满足才停止,e.g.,试验显示该方法可以降低数据规模并改善分类精度。数计学院陈晓云DataMining:ConceptsandTechniques96IntervalMergeby2AnalysisMerging-based(bottom-up)vs.splitting-basedmethodsMerge:FindthebestneighboringintervalsandmergethemtoformlargerintervalsrecursivelyChiMerge[KerberAAAI1992,SeealsoLiuetal.DMKD2002]Initially,eachdistinctvalueofanumericalattr.Aisconsideredtobeoneinterval2testsareperformedforeverypairofadjacentintervalsAdjacentintervalswiththeleast2valuesaremergedtogether,sincelow2valuesforapairindicatesimilarclassdistributionsThismergeprocessproceedsrecursivelyuntilapredefinedstoppingcriterionismet(suchassignificancelevel,max-interval,maxinconsistency,etc.)数计学院陈晓云DataMining:ConceptsandTechniques97通过自然划分分段3-4-5规则可以将数值数据划分成相对一致和自然的区间.*Ifanintervalcovers3,6,7or9distinctvaluesatthemostsignificantdigit,partitiontherangeinto3equi-widthintervals*Ifitcovers2,4,or8distinctvaluesatthemostsignificantdigit,partitiontherangeinto4intervals*Ifitcovers1,5,or10distinctvaluesatthemostsignificantdigit,partitiontherangeinto5intervals数计学院陈晓云DataMining:ConceptsandTechniques98Exampleof3-4-5rule(-$4000-$5,000)(-$400-0)(-$400--$300)(-$300--$200)(-$200--$100)(-$100-0)(0-$1,000)(0-$200)($200-$400)($400-$600)($600-$800)($800-$1,000)($2,000-$5,000)($2,000-$3,000)($3,000-$4,000)($4,000-$5,000)($1,000-$2,000)($1,000-$1,200)($1,200-$1,400)($1,400-$1,600)($1,600-$1,800)($1,800-$2,000)

msd=1,000 Low=-$1,000 High=$2,000Step2:Step4:Step1:

-$351 -$159 profit $1,838 $4,700

MinLow(i.e,5%-tile) High(i.e,95%-0tile)Maxcount(-$1,000-$2,000)(-$1,000-0)(0-$1,000)Step3:($1,000-$2,000)数计学院陈晓云DataMining:ConceptsandTechniques99分类数据的概念分层生成由用户或专家在模式级显示说明分类属性的部分序.如location维：street,city,provinec_or_state和country通过显示数据分组说明分层结构的一部分。例如：province,country型成分层后，可能想人工添加某些中间层。如{albert,saskatchewan,manitoba}属于prairies_canada说明属性集，但不说明其偏序。根据给定属性集中每个属性的不同值个数，由系统自动产生偏序例3.6只说明部分属性集。例如3.7location概念，数据库系统将number,street,city,province_or_state和country捆绑在一起。如用户定义分层结构时，只说明属性city,系统可自动拖进另外几个相关属性，形成分层结构。并去掉分层结构的任何属性。数计学院陈晓云DataMining:ConceptsandTechniques100属性集的说明概念分曾可以根据每个属性的不同值得数量自动产生。具有最多不同值的属性位于最低层。countryprovince_or_statecitystreet15distinctvalues65distinctvalues3567distinctvalues674,339distinctvalues数计学院陈晓云DataMining:ConceptsandTechniques101Thankyou!!!Chapter5:概念描述:CharacterizationandComparison什么是概念描述?

Datageneralizationandsummarization-basedcharacterization数据概化和基于汇总的特征化Analyticalcharacterization:AnalysisofattributerelevanceMiningclasscomparisons:区分不同的类Miningdescriptivestatisticalmeasuresinlargedatabases

挖掘描述统计度量DiscussionSummaryWhatisConceptDescription?Descriptivevs.predictivedatamining描述性数据挖掘:以简洁概要的方式描述数据，并提供数据的有趣的一般性质。预测挖掘:分析数据，建立一个或一组模型，并试图高效能新数据集的行为。Conceptdescription:产生数据的特征化和比较描述Characterization（特征化）:提供给定数据集的简洁汇总Comparison（比较）:提供两个或多个数据汇集的比较描述。ConceptDescriptionvs.OLAP概念描述与数据概化相关，类似于OLAP。Conceptdescription:能够处理属性的复杂数据类型，如数值的、非数值的、空间的、文本的或图像的。amoreautomatedprocessOLAP:维和度量的数据类型有限。少量维和度量类型，如维一般是非数值型数据，度量(count,sum,avg)用于数值数据。user-controlledprocess：下钻、上卷、切块和切片Chapter5:ConceptDescription:CharacterizationandComparisonWhatisconceptdescription?Datageneralizationandsummarization-basedcharacterizationAnalyticalcharacterization:AnalysisofattributerelevanceMiningclasscomparisons:DiscriminatingbetweendifferentclassesMiningdescriptivestatisticalmeasuresinlargedatabasesDiscussionSummaryDataGeneralizationandSummarization-basedCharacterizationDatage