1、2022-6-10史忠植 高级人工智能1高级人工智能高级人工智能第十四章第十四章 知识发现知识发现（二）（二） 史忠植史忠植 中国科学院计算技术研究所2022-6-10史忠植 高级人工智能2主要内容主要内容n研究背景nWeka nMSMiner体系结构n元数据n数据仓库平台n数据采掘集成工具2022-6-10史忠植 高级人工智能3典型的知识发现系统典型的知识发现系统 SAS公司的SAS Enterprise Miner IBM公司的Intelligent Miner Solution公司的Clementine 加拿大Simon Fraser Univ.的DBMiner 中科院计算技术研究所的M
2、SMiner 等2022-6-10史忠植 高级人工智能4 知识发现工具知识发现工具SASSAS SAS公司的SAS Enterprise Miner是一种通用的数据挖掘工具。通过收集分析各种统计资料和客户购买模式，SAS Enterprise Miner可以帮助您发现业务的趋势，解释已知的事实，预测未来的结果，并识别出完成任务所需的关键因素，以实现增加收入、降低成本。2022-6-10史忠植 高级人工智能5 知识发现工具知识发现工具SASSAS SAS Enterprise Miner提供抽样-探索-转换-建模-评估(SEMMA)的处理流程。数据挖掘算法有： 聚类分析，SOM/KOHONEN神
3、经网络分类算法 关联模式/序列模式分析 多元回归模型 决策树模型(C45, CHAID, CART) 神经网络模型(MLP, RBF) SAS/STAT，SAS/ETS等模块提供的统计分析模型和时间序列分析模型也可嵌入其中。2022-6-10史忠植 高级人工智能6 知识发现工具知识发现工具Intelligent MinerIntelligent Miner IBM公司的Intelligent Miner具有典型数据集自动生成、关联发现、序列规律发现、概念性分类和可视化显示等功能。它可以自动实现数据选择、数据转换、数据发掘和结果显示。若有必要，对结果数据集还可以重复这一过程，直至得到满意结果为止
4、。2022-6-10史忠植 高级人工智能7 知识发现工具知识发现工具Clementine Solution公司的Clementine 提供了一个可视化的快速建立模型的环境。它由数据获取（Data Access）、探查（Investigate）、整理（Manipulation）、建模（Modeling）和报告（Reporting）等部分组成。都使用一些有效、易用的按钮表示，用户只需用鼠标将这些组件连接起来建立一个数据流，可视化的界面使得数据挖掘更加直观交互，从而可以将用户的商业知识在每一步中更好的利用。2022-6-10史忠植 高级人工智能8数据挖掘工具数据挖掘工具: : 公用系统公用系统nML
5、C+nMatlabnWeka6/10/2022University of Waikato9作者: Ian H. Witten / Eibe Frank副标题: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems)页数: 525出版社: Morgan Kaufmann出版年: 2005-06-08Weka关于关于WEKAWEKA的简介的简介WEKA的全名是怀卡托智能分析环境（Waikato Environment for
6、 Knowledge Analysis），是一款免费的，非商业化（与之对应的是SPSS公司商业数据挖掘产品-Clementine ）的，基于JAVA环境下开源的机器学习（machine learning）以及数据挖掘（data minining）软件。它和它的源代码可在其官方网站下载。非常有趣的是，该软件的缩写WEKA也是New Zealand独有的一种鸟名，而Weka的主要开发者同时恰好来自New Zealand的the University of Waikato。6/10/2022University of Waikato106/10/2022University of Waikato11
7、WEKA: the bird（译：秧鸡）Copyright: Martin Kramer (mkramerwxs.nl) 关于关于WEKAWEKA的简介的简介nWEKA作为一个公开的数据挖掘工作平台，集合了大量能承担数据挖掘任务的机器学习算法，包括对数据进行预处理，分类，回归、聚类、关联规则以及在新的交互式界面上的可视化。而开发者则可使用Java语言，利用WEKA的架构上开发出更多的数据挖掘算法。用户如果想自己实现数据挖掘算法的话，可以查看WEKA的接口文档。在WEKA中集成自己的算法甚至借鉴它的方法自己实现可视化工具并不是件很困难的事情。6/10/2022University of Waik
8、ato12WEKAWEKA开发历史的介绍开发历史的介绍nWEKA自1993年由位于 New Zealand的 the University of Waikato 进行开发，最初的软件基于C语言实现。1997年，开发小组用JAVA语言重新编写了该软件，并且对相关的数据挖掘算法进行了大量的改进。2005年8月，在第11届ACM SIGKDD国际会议上，the University of Waikato 的Weka小组荣获了数据挖掘和知识探索领域的最高服务奖，Weka系统得到了广泛的认可，被誉为数据挖掘和机器学习历史上的里程碑，是现今最完备的数据挖掘工具之一.6/10/2022University
9、of Waikato136/10/2022University of Waikato14WEKA: versionsnThere are several versions of WEKA:nWEKA 3.4: “book version” compatible with description in data mining booknWEKA 3.6: “GUI version” adds graphical user interfacesnWEKA 3.7: “development version” with lots of improvementsnThis talk is based
10、on the snapshot of WEKA 3.3WEKA：Format of the Datan使用这个系统前，首先需要将用户的数据转变成为WEKA所需要的数据格式（ARFF格式）。大多数ARFF数据文件是一个包括所有事例的列表，还有每个事例的属性值，这些属性值用逗号分开。当事例存在EXCEL或数据库中的时候，只需要将他们提出，转成数据间用逗号分割的形式，然后加上数据集的名字relation，属性信息attribute，值data，然后再将该文件保存成ARFF格式即可。n需要注意的是WEKA中的分类方案缺省假定ARFF文件中的最后一个属性是分类属性。6/10/2022University
11、 of Waikato156/10/2022University of Waikato16relation heart-disease-simplifiedattribute age numericattribute sex female, maleattribute chest_pain_type typ_angina, asympt, non_anginal, atyp_anginaattribute cholesterol numericattribute exercise_induced_angina no, yesattribute class present, not_presen
12、tdata63,male,typ_angina,233,no,not_present67,male,asympt,286,yes,present67,male,asympt,229,yes,present38,female,non_anginal,?,no,not_present.WEKA only deals with “flat” files6/10/2022University of Waikato17relation heart-disease-simplifiedattribute age numericattribute sex female, maleattribute ches
13、t_pain_type typ_angina, asympt, non_anginal, atyp_anginaattribute cholesterol numericattribute exercise_induced_angina no, yesattribute class present, not_presentdata63,male,typ_angina,233,no,not_present67,male,asympt,286,yes,present67,male,asympt,229,yes,present38,female,non_anginal,?,no,not_presen
14、t.WEKA only deals with “flat” files6/10/2022University of Waikato186/10/2022University of Waikato196/10/2022University of Waikato206/10/2022University of Waikato21Explorer: pre-processing the datanData can be imported from a file in various formats: ARFF, CSV, C4.5, binarynData can also be read from
15、 a URL or from an SQL database (using JDBC)nPre-processing tools in WEKA are called “filters”nWEKA contains filters for:nDiscretization, normalization, resampling, attribute selection, transforming and combining attributes, 6/10/2022University of Waikato226/10/2022University of Waikato236/10/2022Uni
16、versity of Waikato246/10/2022University of Waikato256/10/2022University of Waikato266/10/2022University of Waikato276/10/2022University of Waikato282022-6-10史忠植 高级人工智能29 知识发现工具知识发现工具MSMiner 中科院计算技术研究所智能信息处理开放实验室开发的MSMiner是一种多策略知识发现平台，能够提供快捷有效的数据挖掘解决方案，提供多种知识发现方法。 MSMiner具有下列特点： .基于数据仓库和新型的元数据管理按照主题创
17、建数据仓库，并通过元数据进行管理和维护。 .数据的抽取、转换、装载等预处理方便，支持OLAP查询。 2022-6-10史忠植 高级人工智能30MSMinerMSMiner的特点的特点n提供决策树、支持向量机、粗糙集、模糊聚类、基于范例推理、统计方法、神经计算等多种数据挖掘算法，支持特征抽取、分类、聚类、预测、关联规则发现、统计分析等数据挖掘功能，并支持高层次的决策分析功能。n实现了可视化的任务编辑环境，以及功能强大的任务处理引擎，能够快捷有效地实现各种数据转换和数据挖掘任务。 n可扩展性好。转换规则和挖掘算法是封装的、模块化的，系统提供了一个开放的、灵活通用的接口，使用户能够加入新的规则和算法
18、。 n容易进行二次开发。 2022-6-10史忠植 高级人工智能31数据仓库数据仓库: : 特征特征n面向主题n集成性n稳定性n随时间变化2022-6-10史忠植 高级人工智能32数据仓库数据仓库: : OLAPOLAPnROLAP: Relational OLAPnMOLAP: Multidimensional OLAPnHOLAP: Hybrid OLAP2022-6-10史忠植 高级人工智能33数据挖掘和数据仓库的结合数据挖掘和数据仓库的结合n数据仓库为数据挖掘提供经良好处理的数据源n数据挖掘为数据仓库提供深层数据分析手段2022-6-10史忠植 高级人工智能34MSMiner体系结构体
19、系结构设计目标：提供快捷有效的数据挖掘解决方案。设计要求：n开放性n可扩展性n效率n易用性2022-6-10史忠植 高级人工智能35MSMiner体系结构体系结构MSMiner体系结构示意图客户端服务器端元数据模块执行数据挖掘任务编辑数据挖掘任务数据采掘集成工具数据抽取和集成主题组织OLAP可视化数据仓库管理器数据仓库OLE DB for ODBC2022-6-10史忠植 高级人工智能36元数据的内容元数据的内容关于外部数据源的关于内部数据的（包括数据库、表、字段的信息）关于数据仓库的（包括事实表、维表、立方以及其它的中间表）关于用户信息的数据采掘算法（包括算法的参数信息）关于采掘任务的（包括
20、采掘步骤、每个步骤的所用的参数）2022-6-10史忠植 高级人工智能37元数据：元数据库元数据：元数据库2022-6-10史忠植 高级人工智能38元数据：元数据对象模型元数据：元数据对象模型设计思路n一致性n完备性n易维护性2022-6-10史忠植 高级人工智能39元数据是层次的嵌套的封装的互相联系的采用面向对象的方法共有60多个类元数据的结构元数据的结构2022-6-10史忠植 高级人工智能40数据仓库平台：结构数据仓库平台：结构MSMiner数据仓库结构示意图外部数据数据仓库元 数 据数据抽取、清洗、聚集、转换主题2主题1主题nOLAP及可视化工具数据采掘集成工具.2022-6-10史忠
21、植 高级人工智能41数据仓库平台：数据抽取和集成数据仓库平台：数据抽取和集成n数据的简单抽取和集成n数据的复杂处理n面向数据挖掘的数据预处理2022-6-10史忠植 高级人工智能42数据抽取和集成数据抽取和集成: : MSETLMSETL nMSETL系统作为MSMiner数据挖掘平台的一个重要组成部分，主要完成从业务数据源到分析数据源的转换功能。具体包括从异质业务数据源中抽取需要的数据，对这些数据进行多种预处理，把经过处理后的数据装载入指定数据仓库/数据库2022-6-10史忠植 高级人工智能43数据抽取和集成数据抽取和集成: MSETL 用户界面（ETL转换函数和ETL任务）逻辑处理元数据
22、管理数据库服务器2022-6-10史忠植 高级人工智能44数据抽取和集成数据抽取和集成: : MSETLMSETLn支持多种数据源和目的数据库n良好的可扩充性n高效率的调度执行功能n增量更新功能2022-6-10史忠植 高级人工智能45数据抽取和集成数据抽取和集成: : MSETLMSETL2022-6-10史忠植 高级人工智能46数据抽取和集成数据抽取和集成: : MSETLMSETL2022-6-10史忠植 高级人工智能47数据仓库平台：数据仓库建模数据仓库平台：数据仓库建模产品号产品名称产品目录产品维表订单号订货日期订货维表客户号客户名称客户地址客户维表产品号客户号订单号时间标识地区名称
23、产品数量总价事实表时间标识月季度年时间维表地区名称省别地区维表星型模型2022-6-10史忠植 高级人工智能48OLAPMOLAP, ROLAP, HOLAPOLAP 的操作Slice （切片）Dice （切块）Roll up （上卷）Drill down （下钻）Pivot （旋转）OLAP方案采用了自主开发的 OLAP Server2022-6-10史忠植 高级人工智能49数据立方体数据立方体2022-6-10史忠植 高级人工智能50数据仓库平台：数据仓库平台：OLAPOLAP的实现的实现2022-6-10史忠植 高级人工智能51数据挖掘集成工具：结构数据挖掘集成工具：结构数据挖掘集成工具
24、结构示意图数据仓库平台任务编辑任务规划和执行算法库算法管理元数据任务模型库、算法描述2022-6-10史忠植 高级人工智能52数据挖掘集成工具：数据挖掘集成工具：数据挖掘任务模型数据挖掘任务模型Step1Step2Step4Step3Step5DMTask = (V, R)V = x | x StepObjectsR = | P(x, y) x, yV2022-6-10史忠植 高级人工智能53数据挖掘集成工具：数据挖掘集成工具：数据挖掘任务模型数据挖掘任务模型步骤对象BNF语法定义： := ; := |; := , := |; := , := | := | := *2022-6-10史忠植 高
25、级人工智能54数据挖掘集成工具：编辑任务模型数据挖掘集成工具：编辑任务模型n任务向导2022-6-10史忠植 高级人工智能55数据挖掘集成工具：数据挖掘集成工具：编辑任务模型编辑任务模型n任务编辑图板2022-6-10史忠植 高级人工智能56数据挖掘集成工具：数据挖掘集成工具：处理任务模型处理任务模型人机界面主控模块规划器解释器缓存函数库黑板任务模型库数据采掘任务处理引擎的结构2022-6-10史忠植 高级人工智能57数据挖掘集成工具：数据挖掘集成工具：处理任务模型处理任务模型任务规划和解释执行S1S3S2S4S5S1 - S2 - S3 - S4 - S52022-6-10史忠植 高级人工智
26、能58数据挖掘集成工具：数据挖掘集成工具：DMLDML语言语言DML函数n人机交互和控制台输入/输出n数值计算n字符串处理n图形、图表展示n文件操作n数据库访问n网络通讯n对象访问n消息处理和流程控制n黑板操作n外部功能调用n其它辅助功能2022-6-10史忠植 高级人工智能59数据挖掘集成工具：内嵌数据挖掘集成工具：内嵌n决策树nSOM神经网络n粗糙集n关联规则2022-6-10史忠植 高级人工智能60决策树决策树2022-6-10史忠植 高级人工智能61知识约简知识约简知识约简在保持知识库的分类或决策能力不变的条件下，删除其中不相关或不重要知识冗余知识资源的浪费；干扰人们作出正确而简洁的决
27、策Rough Set把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集（Z.Pawlak ） 知识约简是粗糙集的核心内容之一 2022-6-10史忠植 高级人工智能62Rough Set约简约简2022-6-10史忠植 高级人工智能63数据挖掘集成工具：外联数据挖掘集成工具：外联nBP神经网络n统计分析n模糊聚类n超曲面分类nSVMn贝叶斯网络n基于范例推理(CBR)n隐马尔科夫模型(HMM)2022-6-10史忠植 高级人工智能64BP用于预测用于预测2022-6-10史忠植 高级人工智能65统计工具统计工具线性回归模型一元线性回归、多元线性回归、逐步回
28、归 非线性回归模型二次曲线、三次曲线、指数曲线、幂指数曲线、生产函数等模型 确定型时间序列模型指数平滑法、趋势移动平均法（水平趋势、线性趋势和二次曲线趋势）、成长曲线模型（Compertz曲线、Logistic曲线和修正指数曲线 ）、季节指数法随机型时间序列模型（自回归移动平均模型ARMA）相关分析 2022-6-10史忠植 高级人工智能66自回归移动平均自回归移动平均( ARMA)2022-6-10史忠植 高级人工智能67模糊聚类模糊聚类基于传递闭包的模糊聚类计算模糊相似矩阵的传递闭包，从而获得传递闭包法的模糊聚类基于摄动的模糊聚类参数系相似矩阵的最优模糊等价阵及其等价标准型获得失真最小的模
29、糊聚类2022-6-10史忠植 高级人工智能68数据挖掘集成工具：数据挖掘集成工具：可扩展算法库可扩展算法库n算法注册2022-6-10史忠植 高级人工智能69MSMiner的应用的应用：计算机选案计算机选案决策树选案执行选案选案结果分析定义样本模板训练样本数据选案规则样本数据表数据汇总表税务稽查计算机选案系统功能结构2022-6-10史忠植 高级人工智能70MSMiner的应用的应用：计算机选案：计算机选案挖掘结果：n云计算时代的分布并行编程技术n分布并行数据处理技术nGoogle Map/ReducenHadoop Map/Reduce n分布式文件系统nGoogle File Syste
30、mnHadoop Distributed File Systemn分布式数据库nGoogle BigTablenHadoop HBase云计算时代的分布并行编程技术云计算时代的分布并行编程技术分布并行数据处理分布并行数据处理72软件工程国家重点实验室v Map/Reduce 用于大规模数据并行处理数据量大（超过1TB） 在成百上千个CPU上并行处理 用户只需实现下面接口map (in_key, in_value) - (out_key, intermediate_value) listreduce (out_key, intermediate_value list) - out_value l
31、ist分布并行数据处理分布并行数据处理73软件工程国家重点实验室v Map/Reduce架构分布并行数据处理分布并行数据处理MapReduce实现原理分布式文件系统分布式文件系统75nGoogle File System（GFS）n需求：在廉价、相对不可靠的计算机上对巨量数据进行冗余存储。 n为什么不用现有的文件系统？-Google面对特殊的挑战文件较大，每个都在100M以上，通常为几个GB文件通常需要频繁的追加用流方式读取高吞吐量低延迟n针对上述问题，GFS在文件系统性能和可伸缩性方面进行了优化设计。nGFS的设计理念n文件用块存储n每个块固定为64MBn通过冗余解决可靠性问题n每个块同时拷
32、贝在3个块服务器上n主服务器负责协调访问和保存元数据n简单化的集中管理n定制化的APIn无数据缓存n较大文件块和流式读取使得缓存效果不佳76分布式文件系统分布式文件系统GFS架构分布式文件系统分布式文件系统nGFS集群n一个 GFS 集群有一个主服务器和多个块服务器n文件被分割成固定尺寸的块。n块服务器把块作为 linux 文件保存在本地硬盘上，并根据指定的块句柄和字节范围来读写块数据。n主服务器管理文件系统所有的元数据，包括名字空间、访问控制信息和文件到块的映射信息，以及块当前所在的位置。n客户端与主服务器交互，处理元数据n客户端与块服务器交互，存取数据本身分布式文件系统分布式文件系统分布式
33、数据库系统nGoogle BigTablen为了处理Google内部大量的格式化以及半格式化数据而构建的大规模分布式数据存储系统n 特点n面向大规模处理、容错性强的自我管理系统，拥有TB级的内存和PB级的存储能力，每秒可以处理数百万的读写操作n能够保存记录的不同时段的版本n构建于GFS和Map/Reduce基础之上软件工程国家重点实验室79nBigTable的设计理念n面向网页数据的发布、搜索和浏览等特定处理的需要，简化数据管理系统的设计，并提高性能n不支持关联n不支持SQL查询n简化数据的一致性管理n网页数据的管理对一致性要求不高n简化事务管理n网页数据的处理（搜索、发布）对事务管理要求不高
34、n面向海量数据管理要求n设计分割和合并管理机制（基于元数据）n设计自动伸缩功能（根据数据量调整资源用量）软件工程国家重点实验室80分布式数据库系统分布式数据库系统nBigTable的实现nGFS为表文件、元数据和日志提供存储服务nChubby 提供分布式并行处理功能n一个Table按照行被分割为多个tabletn每一个tablet在物理层被存为SSTable文件n通过维护keydisk block索引， SSTable 文件管理系统提供 keyvalue的索引功能分布式数据库系统分布式数据库系统nBigTable架构82分布式数据库系统分布式数据库系统2022-6-10史忠植 高级人工智能83进一步的工作进一步的工作n与用户合作开发应用实例n进一步完善工作流n完善和丰富数据挖掘算法库n算法评测功能。2022-6-10史忠植 高级人工智能
