11、数据挖掘期末复习2015

1、数据挖掘期末复习 数据挖掘概论什么是数据挖掘？n数据挖掘 (从数据中发现知识) q从大量的数据大量的数据中挖掘出令人感兴趣的、有用的、隐含的、先前未知的和可能有用的模式或知识 n数据挖掘的替换词q数据库中的知识挖掘（KDD）q知识提炼、q数据/模式分析q数据考古q数据捕捞、信息收获等等。数据挖掘（KDD）的步骤1.数据清理: (这个可能要占全过程60的工作量)2.数据集成3.数据选择4.数据变换5.数据挖掘（选择适当的算法来找到感兴趣的模式）数据挖掘（选择适当的算法来找到感兴趣的模式）6.模式评估7.知识表示体系结构:典型数据挖掘系统数据仓库数据仓库数据清洗数据清洗过滤过滤数据库数据库数据库或

2、数据仓库服务器数据挖掘引擎模式评估图形用户界面知识库数据集成数据集成数据挖掘的主要功能n概念/类描述: 特性化和区分q n关联分析q n分类和预测 q n聚类分析q n孤立点分析q n趋势和演变分析q 数据仓库和OLAP技术什么是数据仓库?n“数据仓库是一个面向主题的、集成的、随时间而变化的、不容易丢失的数据集合，支持管理部门的决策过程.”W. H. Inmon（数据仓库构造方面的领头设计师）数据仓库与异种数据库集成n传统的异种数据库集成: q查询驱动方法数据仓库: 更新驱动从关系表和电子表格到数据立方体n数据仓库和数据仓库技术基于多维数据模型多维数据模型。这个模型把数据看作是数据立方体数据立

3、方体形式。n数据立方体数据立方体允许以多维数据建模和观察。它由维维和事实事实定义。n维维是关于一个组织想要记录的视角或观点。每个维都有一个表与之相关联，称为维表维表。n事实表事实表包括事实的名称或度量以及每个相关维表的关键字多维数据模型上的OLAP操作n上卷(roll-up):汇总数据q通过一个维的概念分层向上攀升或者通过维规约n下钻(drill-down)：上卷的逆操作q由不太详细的数据到更详细的数据，可以通过沿维的概念分层向下或引入新的维来实现n切片和切块(slice and dice)q投影和选择操作n转轴(pivot)q立方体的重定位，可视化，或将一个3维立方体转化维一个2维平面序列n

4、其他OLAP操作q钻过(drill_across)：执行涉及多个事实表的查询q钻透(drill_through)：使用关系SQL机制，钻到数据立方体的底层，到后端关系表数据仓库设计的四种视图n数据仓库设计的四种视图q自顶向下视图n q数据源视图n q数据仓库视图n q商务查询视图n 三种数据仓库模型n企业仓库q搜集关于跨越整个组织的主题的所有信息n数据集市q企业范围数据的一个子集，对于特定的客户是有用的。其范围限于选定的主题，比如一个商场的数据集市n虚拟仓库q操作数据库上的一系列视图q只有一些可能的汇总视图被物化OLAP服务器类型n n物理上，OLAP的底层数据存储实现可以有多种不同的方式q关

5、系OLAP服务器(ROLAP)n q多维OLAP服务器(MOLAP)n q混合OLAP服务器(HOLAP)n q特殊的SQL服务器n 数据仓库的概念模型n最流行的数据仓库概念模型是多维数据模型。这种模型可以以星型模式、雪花模式、或事实星座模式的形式存在。q星型模式（Star schema）: 事实表在中心，周围围绕地连接着维表（每维一个），事实表含有大量数据，没有冗余。q雪花模式（Snowflake schema）: 是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加表中。结果，模式图形成类似于雪花的形状。q事实星座（Fact constellations）: 多个事实表共享

6、维表, 这种模式可以看作星型模式集，因此称为星系模式（galaxy schema），或者事实星座（fact constellation） 数据预处理为什么要预处理数据？n现实世界的数据是“肮脏的”q不完整的：q含噪声的：q不一致的：数据预处理的主要任务n数据清理n数据集成n数据变换n数据归约噪声数据n噪声：一个测量变量中的随机错误或偏差如何处理噪声数据 n分箱(binning):n聚类：n计算机和人工检查结合n回归数据变换n平滑： n聚集： n数据概化： n规范化： q最小最大规范化qz-score规范化q小数定标规范化n属性构造q 数据归约策略n n数据归约q数据归约可以用来得到数据集的归约

7、表示，它小得多，但可以产生相同的（或几乎相同的）分析结果n数据归约策略q数据立方体聚集q维归约:通过删除不相干的属性或维 减少数据量q数据压缩q数值归约q离散化和概念分层产生n 在大型数据库中挖掘描述统计计量n对于数据挖掘任务，用户经常关心的数据特征包括数据的中心趋势和离散特征q中心趋势的度量包括：均值，加权平均，中位数，众数均值，加权平均，中位数，众数 q数据离散度量包括：极差，四分位数，方差，标准差极差，四分位数，方差，标准差 q n数据概化：数据概化：n数据库中的数据和对象通常包含原始概念层的细节信息，数据概化就是将数据库中的跟任务相关的数据集从较低的概念层抽象到较高的概念层的过程。n

8、关联规则挖掘什么是关联规则挖掘？n关联规则挖掘：q从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。n Apriori算法nApriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。nApriori性质：频繁项集的所有非空子集也必须是频繁的。qApriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。BAApriori算法示例Database TDB1st scanC1L1L2C2C22nd

9、 scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2多层关联一致支持度 VS. 递减支持度n一致支持度：对所有层都使用一致的最小支持度q优点：搜索时容易采用优化策略，即一个项如果不满足最小

10、支持度，它的所有子项都可以不用搜索q缺点：最小支持度值设置困难n太高：将丢掉出现在较低抽象层中有意义的关联规则n太低：会在较高层产生太多的无兴趣的规则n递减支持度：在较低层使用递减的最小支持度q抽象层越低，对应的最小支持度越小Computer support=10%Laptopsupport=6%Desktopsupport=4%min_sup = 5%min_sup = 5%min_sup = 3%关联规则的兴趣度度量n客观度量q两个流行的度量指标n支持度n置信度分类和预测数据分类一个两步过程n第一步，建立一个模型，描述预定数据类集和概念集n第二步，使用模型，对将来的或未知的对象进行分类有指

11、导的学习 VS. 无指导的学习n有指导的学习（用于分类）q模型的学习在被告知每个训练样本属于哪个类的“指导”下进行q新数据使用训练数据集中得到的规则进行分类n无指导的学习（用于聚类）q每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的q通过一系列的度量、观察来建立数据中的类编号或进行聚类用判定树归纳分类n判定树的生成由两个阶段组成q判定树构建n开始时，所有的训练样本都在根节点n递归的通过选定的属性，来划分样本 （必须是离散值）q树剪枝n许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝n防止应用判定树判定树分类中的数据过分适应的方法q先剪枝：通过提前停止树

12、的构造如果在一个节点划分样本将导致低于预定义临界值的分裂（e.g. 使用信息增益度量）n选择一个合适的临界值往往很困难q后剪枝：由“完全生长”的树剪去分枝对于树中的每个非树叶节点，计算该节点上的子树被剪枝可能出现的期望错误率n使用一个独立的测试集来评估每颗树的准确率，就能得到具有最小期望错误率的判定树n 后向传播分类n后向传播是一种神经网络学习算法模糊数学的基本思想基本思想基本思想用属于程度代替属于或不属于。某个人属于秃子的程度为0.8, 另一个人属于秃子的程度为0.3等.例三角形识别（用于识别染色体及白血球分类）180,| ),(CBACBACBAxX近似直角三角形:|90|9011),()

13、(ACBARxR近似等腰三角形:)(),min(6011)(CBBAxI近似等边三角形:)(18011),()(CACBAExE非典型三角形：cccEIRT)45,55,80(),(0CBAx81. 0)( ,83. 0)( ,87. 0)(00 xExIxR13. 0)(1 ()(1 ()(1 ()(0000 xExIxRxT直角三角形应为近似0 xn粗糙集理论是建立在不可分辨关系上的。 n在RS理论中，集合A的下近似为所有一定属于A的等价类所组成的集合 n集合A的上近似为所有与A相交非空的等价类组成的集合，即所有可能属于A的对象组成的最小集合n 聚类分析什么是聚类分析？n n聚类分析q将物

14、理或抽象对象的集合分组成为由类似的对象组成的多个类的过程n聚类是一种无指导的学习：没有预定义的类编号n 主要的聚类方法n聚类分析算法种类繁多，具体的算法选择取决于数据类型，聚类的应用和目的，常用的聚类算法包括：q划分方法q层次的方法q基于密度的方法q基于网格的方法q基于模型的方法基于密度的方法n基于距离的聚类方法的缺点：只能发现球状的簇，难以发现任意形状的簇。n基于密度的聚类：只要临近区域的密度（对象或数据点的数目）超过某个临界值，就继续聚类。q优点：可以过滤掉“噪声”和“孤立点”，发现任意形状的簇。二元变量的相异度示例P256 例 二元变量之间的相异度 （病人记录表）Name是对象标识gender是对称的二元