数据挖掘概论

第一章数据挖掘概论什么是数据挖掘？数据挖掘（DataMiningDM）从大量的数据中挖掘出令人感兴趣的、有用的、隐含的、先前未知的和可能有用的模式或知识数据挖掘的替换词数据库中的知识挖掘、知识发现（KDD）知识提炼、数据/模式分析数据考古数据捕捞、信息收获等等KDD的步骤数据清理:（这个可能要占全过程60%的工作量）数据集成数据选择数据变换数据挖掘（选择适当的算法来找到感兴趣的模式）模式评估知识表示体系结构:典型数据挖掘系统知识库过滤数据仓库知识库过滤数据仓库数据挖掘的主要功能概念/类描述：特性化和区分归纳，总结和对比数据的特性。关联分析发现数据之间的关联规则，这些规则展示属性一值频繁的在给定的数据中所一起出现的条件。分类和预测通过构造模型（或函数）用来描述和区别类或概念，用来预测类型标志未知的对象类。聚类分析将类似的数据归类到一起，形成一个新的类别进行分析。孤立点分析通常孤立点被作为“噪音”或异常被丢弃，但在欺骗检测中却可以通过对罕见事件进行孤立点分析而得到结论。趋势和演变分析描述行为随时间变化的对象的发展规律或趋势数据挖掘系统与DB或DW系统的集成方式不耦合松散耦合半紧密耦合紧密耦合概念P23第三章数据仓库和OLAP技术什么是数据仓库？数据仓库的定义很多，但却很难有一种严格的定义.“数据仓库是一个面向主题的、集成的、随时间而变化的、不容易丢失的数据集合，支持管理部门的决策过程.”一W.H.Inmon（数据仓库构造方面的领头设计师）数据仓库关键特征数据仓库关键特征一一一面向主题数据仓库关键特征二一一数据集成数据仓库关键特征三 随时间而变化数据仓库关键特征四一一数据不易丢失数据仓库与异种数据库集成传统的异种数据库集成：在多个异种数据库上建立包装程序和中介程序采用查询驱动方法一一当从客户端传过来一个查询时，首先使用元数据字典将查询转换成相应异种数据库上的查询；然后，将这些查询映射和发送到局部查询处理器缺点：复杂的信息过虑和集成处理，竞争资源数据仓库：采用更新驱动将来自多个异种源的信息预先集成，并存储在数据仓库中，供直接查询和分析高性能.从关系表和电子表格到数据立方体数据仓库和数据仓库技术基于多维数据模型。这个模型把数据看作是数据立方体形式。多维数据模型围绕中心主题组织，该主题用事实表表示。事实是数值度量的。数据立方体由维和事实定义。维：是关于一个组织想要记录的视角或观点。每个维都有一个表与之相关联，称为维表。事实表包括事实的名称或度量以及每个相关维表的关键字在最低抽象层建立的立方体是存放最底层汇总的方体叫做基本方体。0维方体存放最高层的汇总，也就是最高层抽象的立方体称作顶点方体。多维数据模型(数据立方体)使得从不同的角度对数据进行观察成为可能，而概念分层则提供了从不同层次对数据进行观察的能力。度量的分类一个数据立方体的度量是一个数值函数。度量可以根据其所用的聚集函数分为三类：分布的(distributive)：将函数用于n个聚集值得到的结果和将函数用于所有数据得到的结果一样。比如：count()，sum()，min()，max()等代数的(algebraic)：函数可以由一个带M个参数的代数函数计算(M为有界整数)，而每个参数值都可以有一个分布的聚集函数求得。比如：avg()，min_N()，standard_deviation()整体的(holistic)：比如：median。，mode()，rank()数据仓库的概念模型最流行的数据仓库概念模型是多维数据模型。这种模型可以以星型模式、雪花模式、或事实星座模式的形式存在。星型模式、雪花模式、或事实星座模式画图星型模式(Starschema):事实表在中心，周围围绕地连接着维表(每维一个)，事实表含有大量数据，没有冗余。雪花模式(Snowflakeschema):是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加表中。结果，模式图形成类似于雪花的形状。事实星座(Factconstellations):多个事实表共享维表，这种模式可以看作星型模式集，因此称为星系模式(galaxyschema)，或者事实星座(factconstellation)。星型模式实例雪花模式实例timetime_key ,dsyd3ftr_ofjhe_weekmonthquarteryearSalesFactTablebranchMeasuresbranch_keybranch_naniebranchtype事实星座模式实例.itemitem_keyitem_namebrandtype.supplier_keylocationlocation_keystreetcitvkey.supplier_supplierJ<eysupplier_rypecil^7_keydtystate_Q匚time_key ,dsyd3ftr_ofjhe_weekmonthquarteryearSalesFactTablebranchMeasuresbranch_keybranch_naniebranchtype事实星座模式实例.itemitem_keyitem_namebrandtype.supplier_keylocationlocation_keystreetcitvkey.supplier_supplierJ<eysupplier_rypecil^7_keydtystate_Q匚proviiicecountrytimetinie_keydayday_of_the_weekmanlthquarteryearitembranchkeylocation_keyunits_solddollars_soldlocation^k^streetcityprovinee_or_statecountry7\ShippingFactTabletime_k^ritem_keyshipper_key...fromJocationto_lcx:ationdollarsjcostunits_shippedavg_salesshipper/ 1——shippet^_keyshipper_nai]ielocation_ke：yshipperfype多维数据模型上的OLAP操作上卷(roll-up):汇总数据通过一个维的概念分层向上攀升或者通过维规约下钻(drill-down)：上卷的逆操作由不太详细的数据到更详细的数据，可以通过沿维的概念分层向下或引入新的维来实现切片和切块(sliceanddice)切片操作在给定的数据立方体的一个维上进行选择，导致一个子立方体切块操作通过对两个或多个维进行选择，定义子立方体转轴(pivot)立方体的重定位，可视化，或将一个3维立方体转化维一个2维平面序列其他OLAP操作钻过(drill_across)：执行涉及多个事实表的查询钻透(drill_through)：使用关系SQL机制，钻到数据立方体的底层，到后端关系表。典型的数据仓库设计过程选取待建模的商务过程选取商务过程的颗粒度比如：记录每条详细订单，或是开始于每日的汇总数据选取用于每个事实表记录的维常用的维有：时间、货物、客户、供应商等选取将安放在事实表中的度量常用的数字度量包括：售价、货物数量等三种数据仓库模型企业仓库数据集市虚拟仓库10.OLAP服务器类型逻辑上，OLAP服务器从数据仓库或数据集市中给商业用户提供多维数据物理上，OLAP的底层数据存储实现可以有多种不同的方式关系OLAP服务器多维OLAP服务器混合OLAP服务器特殊的SQL服务器在星型和雪花模型上支持SQL查询。第三章数据预处理为什么要预处理数据？现实世界的数据是“肮脏的”不完整的：有些感兴趣的属性缺少属性值，或仅包含聚集数据。含噪声的：包含错误或者“孤立点”。不一致的：在编码或者命名上存在差异。数据预处理的主要任务数据清理填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性数据集成集成多个数据库、数据立方体或文件数据变换规范化和聚集数据归约：得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果数据离散化数据归约的一部分通过概念分层和数据的离散化来规约数据对数字型数据特别重。如何处理空缺值忽略元组：。人工填写空缺值：工作量大，可行性低。使用一个全局变量填充空缺值：比如使用unknown或-8。使用属性的平均值填充空缺值。使用与给定元组属同一类的所有样本的平均值。使用最可能的值填充空缺值。P63页习题2.4(a~f)特征化和比较两种不同类别的数据挖掘从数据分析的角度看，数据挖掘可以分为描述性挖掘和预测性挖掘什么是概念描述？概念描述：为数据的特征化和比较产生描述(当所描述的概念所指的是一类对象时，也称为类描述)特征化：提供给定数据集的简洁汇总。区分：提供两个或多个数据集的比较描述。数据概化数据库中的数据和对象通常包含原始概念层的细节信息，数据概化就是将数据库中的跟任务相关的数据集从较低的概念层抽象到较高的概念层的过程。概念层第六章关联规则挖掘什么是关联规则挖掘？关联规则挖掘：从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。应用：购物篮分析、分类设计、捆绑销售和亏本销售分析由频繁项集产生关联规则同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算：confidence(AB)=P(A\B)= = support_countyA)每个关联规则可由如下过程产生：对于每个频繁项集1，产生l的所有非空子集；对于每个非空子集s，如果suppartcount(I) , 。 = >nnn_canf zj_x，则输出规则“-—J：—”。3Apriori算法 示例DatabaseTDBr',l：＞10A,C,D20B,C,E30A,B,C,E40B?E1stscanItemsetsup{A}2{B}3{C}3{□}1{E}3Itemsetsup{A}2担｝3{C}3{E}3l2Itemsetsup4c}20C}2但E}3(C,E}2Itemsetsup1{A,C}2{W}1但C}2{B.E}3{C,E}2?ndItemsetCmItemset◎C,E}|{A、B}佻C}{A、E}俱C}{B；E}{C,E}Itemsetsup|{B，E}|4.多层关 致支持度VS.递减支持度一致支持度：对所有层都使用一致的最小支持度递减支持度：在较低层使用递减的最小支持度第七章分类和预测分类：预测分类标号（或离散值）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据数据分类 个两步过程第一步，建立一个模型，描述预定数据类集和概念集假定每个元组属于一个预定义的类，由一个类标号属性确定。学习模型可以用分类规则、判定树或数学公式的形式提供。第二步，使用模型，对将来的或未知的对象进行分类首先评估模型的预测准确率。若预测准确率可接受，则用该模型对未知元组进行分类。用判定树归纳分类判定树的生成由两个阶段组成判定树构建树剪枝判定树的使用：对未知样本进行分类通过将样本的属性值与判定树相比较防止分类中的过分适应产生的判定树会出现过分适应数据的问题由于数据中的噪声和孤立点，许多分枝反应的是训练数据中的异常对新样本的判定很不精确防止过分适应的两种方法先剪枝：后剪枝：后向传播分类后向传播是一种神经网络学习算法。模糊分类Fuzzy基本思想：用属于程度即隶属度来代替属于或不属于个体识别(分类)最大隶属原则：阈值原则：群体识别贴近度1例三角形识别(用于识别染色体及白血球分类)M={工=\A>B>C,A+B^C=180}近似直角三角形：R(x)=R(A,B,C}=1—土M—90|近似等腰三角形：I(x)=1-—minO-B\(B-60近似等边三角形：E(x)=E(A^B^C)=1--(4-C)阈值原则：型三角形：r=RcnrnEc计算4](工。)4(也)〉——「4(0；给定阈值aw©1],若4(工。)>%J(x0)>«. £ ii称X。相对隶属于40广-,&.■L工 苗例如：在例2中，若气=(A.B.C)=(85,50,45)贝叶斯分类7?(t0)=0.95?7(x0)=0.91?£(t0)=0.87T(0=(1—R(x0))/\(l-J(x0))a(1-E(x0))=0.05取a二0.9,由阈值原则，办应为近似等腰直角三角形贝叶斯分类利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。朴素贝叶斯分类：假设每个属性之间都是相互独立的，并且每个属性对非类问题产生的影响都是一样的。第八章聚类分析什么是聚类分析？聚类分析将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。聚类是一种无指导的学习：没有预定义的类编号。聚类分析的数据挖掘功能作为一个独立的工具来获得数据分布的情况。作为其他算法(如：特征和分类)的预处理步骤。主要的聚类方法及特点聚类分析算法种类繁多，具体的算法选择取决于数据类型，聚类的应用和目的，常用的聚类算法包括：划分方法：一般按距离划分，适宜发现球形的簇。层次的方法，缺点：合并或分裂的步骤不能被撤销。基于密度的方法：可以过滤掉“噪声”和“孤立点”，发现任意形状的簇。基于网格的方法：处理速度快。基于模型的方法：为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。实际应用中的聚类算法，往往是上述聚类方法中多种方法的整合。相异度计算许多聚类算法都是以相异度矩阵为基础，如果数据是用数据矩阵形式表示，则往往要将其先转化为相异度矩阵。相异度d(ij)的具体计算会因所使用的数据类型不同而不同，常用的数据类型包括：区间标度变量二元变量标称型、序数型和比例标度型变量混合类型的变量二元变量(1)一个二元变量只有两种状态：0或1；e.g.smoker来表示是否吸烟一个对象可以包含多个二元变量。二元变量的可能性表：如何