华南理工大学《数据挖掘》复习资料

华南理工大学《数据挖掘》复习资料【英文缩写】BI(商务智能):BusinessIntelligenceOLAP(联机分析处理):OnlineAnalyticalProcessingOLTP(联机事务处理):OnlineTransactionProcessingETL(提取/变换/装入):Extraction/Transformation/LoadingKDD(数据中的知识发现):KnowledgeDiscoveryinDatabasesLecture1.【知识发现的主要过程】(1)数据清理（消除噪声和不一致的数据）(2)数据集成（多种数据源可以组合在一起）(3)数据选择（从数据库中提取与分析任务相关的数据）(4)数据变换（数据变换或同意成适合挖掘的形式，如通过汇总或聚集操作）(5)数据挖掘（基本步骤，使用只能方法提取数据模式）(6)模式评估（根据某种兴趣度度量，识别表示只是的真正有趣的模式）(7)知识表示（使用可视化和只是表示技术，向用户提供挖掘的知识）【挖掘的知识类型】(1)概念描述：特征划与区分(概化、摘要、以及对比数据特征)(2)关联（相关性或者因果关系）(3)分类与预测：对类或概念构造模型或函数以便对未来数据进行预测(4)聚类分析：类标识符是未知的，把数据分成不同的新类，使得同一个类中的元素具有极大的相似性，不同类元素的相似性极小。(5)趋势与偏差分析：序列模式挖掘(6)孤立点分析：孤立点，不符合该类数据的通用行为的数据，不是噪声或异常。【数据挖掘在互联网、移动互联网的应用】(1)Web用法挖掘（Web日志挖掘）：在分布式信息环境下捕获用户访问模式(2)权威Web页面分析：根据Web页面的重要性、影响和主题，帮助对Web页面定秩(3)自动Web页面聚类和分类：给予页面的内容，以多维的方式对Web页面分组和安排(4)Web社区分析：识别隐藏的Web社会网络和社团，并观察它们的演变Lecture2.【为什么需要数据预处理】现实世界中的数据很“脏”，具有以下特性：(1)不完整的:缺少属性值,感兴趣的属性缺少属性值,或仅包含聚集数据(2)含噪声的:包含错误或存在孤立点(3)不一致的:在名称或代码之间存在着差异数据预处理技术可以改进数据的质量，从而有助于提高其后的挖掘过程的精度和性能。【数据预处理的主要内容】(1)数据清洗（Datacleaning）填充遗失的数据,平滑噪声数据,辨识或删除孤立点,解决不一致性问题(2)数据集成（Dataintegration）对多个数据库，数据立方或文件进行集成(3)数据变换（Datatransformation）规范化与聚集（Normalizationandaggregation）(4)数据约简（Datareduction）得到数据集的压缩表示，它小的多，但能产生同样分析结果(5)数据离散化（Datadiscretization）特别对数字值而言非常重要【分箱平滑】是一种处理噪声数据的方法。先对数据进行排序，然后把它们划分到箱，然后通过箱平均值，箱中值等进行平滑。(1)等宽(距离)划分根据属性值的范围划分成N等宽的区间。很直接，但孤立点将会对此方法有很大的影响(2)等深(频率)划分划分成N个区间，每个区间含有大约相等地样本数。具有较好的数据扩展性【无监督离散化】分箱、直方图分析、聚类分析【有监督离散化】离散化过程使用类信息，基于熵的离散化：(1)给定样本集S，根据分解值T分为两部分，计算熵：(2)选择某一边界T使熵最大.(3)递归地用于所得到的划分，直到满足某个终止条件。【数据预处理（缺失数据）方法】数据清理缺失值的处理方法：(1)忽略元组：当缺失类标号时通常忽略元组。除非元组有多个属性缺失值，否则该方法不是很有效。当每个属性缺失值的百分比变化很大时，它的性能特别差。(2)人工填写缺失值：该方法很费时，当数据集很大，缺少很多值时，该方法不可行。(3)使用一个全局常量填充缺失值：将缺失的属性值用同一个常数（如unknow）替换。如果缺失值都用unknow替换，则挖掘程序则可能误以为它们行程了一个有趣的概念，因为它们都具有相同的值。因此，尽管该方法简单，但是并不十分可靠。(4)使用属性的均值填充缺失值(5)使用与给定元组属同一类的所有样本的属性均值(6)使用最可能的值填充缺失值：可以用回归、使用贝叶斯形式化的基于推理的工具或决策树归纳确定。（3）~（6）使数据偏置。填入的值可能不正确。方法6是最流行的策略，与其他方法相比，它使用已有的数据大部分信息来预测缺失值。缺失值不代表数据有错误（例如，信用卡中，有信息是驾照号码，如果没有驾照号码，该空则可以是缺失的）Lecture3.【数据仓库的特征】(1)面向主题的数据仓库围绕一些主题来组织的。(2)集成的数据仓库是将多个异构数据源集成在一起。(3)时变的数据存储从历史的角度提供信息。(4)非易失的数据仓库总是物理地分别存放数据【度量的分类】(1)分布式度量(distributivemeasure)是一种可以通过如下方法计算度量：可以将数据集划分成较小的子集，计算每个子集的度量，然后合并计算结果，得到原数据集的度量值(2)代数度量(algebraicmeasure)是可以通过应用一个代数函数于一个或多个分布度量计算的度量(3)整体度量(holisticmeasure)必须对整个数据集计算的度量。整体度量不能通过将给定的数据集划分成子集合并每个子集上度量得到的值来计算【数据仓库模型】(1)企业仓库（Enterprisewarehouse）搜集了关于主题的所有信息，跨越整个组织。(2)数据集市（DataMart）包含企业范围数据的一个子集，对于特定的用户是有用的，其范围限于选定的主题。(3)虚拟仓库（Virtualwarehouse）操作数据库上视图的一组集合。为了有效处理查询，只有一些可能的汇总视图被物化。【为什么需要构建单独隔离的数据仓库】(1)使得操作数据库与数据仓库都获得高性能DBMS—OLTP:访问方法,索引,并发控制,数据恢复。Warehouse—OLAP:复杂OLAP查询,多维视图,整理。(2)对数据与功能的要求不同:(a)丢失的数据:决策支持需要历史数据，而传统数据库并不一定维护历史数据。(b)数据整理:决策支持需对异构数据源进行数据整理。(c)数据质量:不同的数据源常常具有不一致的数据表示，编码结构与格式。【常见的OLAP操作】(1)上卷Rollup(上钻drill-up):通过一个维的概念分层向上攀升或通过维规约，在数据立方体上进行聚集。(2)下钻Drilldown(rolldown):上卷的逆操作，它由不太详细的数据得到更详细的数据。可以通过沿维的概念分层向下或引入新的维实现。(3)切片Slice与切块dice投影与选择。(4)转轴Pivot(rotate)是一种目视操作，它转动数据的视角，提供数据的替代表示(5)其它操作钻过drillacross：执行涉及多个事实表的查询。钻透drillthrough：使用SQL的机制，钻到数据立方的底层，到后端关系表。【数据仓库的设计模式】最流行的数据仓库数据模型是多维模型，以以下形式存在：(1)星型模式（Starschema）一个事实表以及一组与事实表连结的维表。(2)雪花模式（Snowflakeschema）雪花模式是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加的表中。(3)事实星座（Factconstellations）多个事实表分享共同的维表，这种模式可以看作星型模式的集合，因此称为星系模式（galaxyschema）或事实星座。【数据仓库的多层结构】通常，数据仓库采用三层结构：(1)底层是仓库数据服务器几乎总是关系数据库系统，使用后端工具和实用程序由操作数据库或者其他外部数据源提取数据(2)中间层是OLAP服务器直接实现多维数据和操作(3)顶层是前端客户层包括查询和报表工具、分析工具和/或数据挖掘工具【数据仓库的视图】(1)自顶向下视图可以选择数据仓库所需要的相关信息。这些信息能够满足当前和未来商务的需求。(2)数据源视图：解释操作数据库系统收集、存储和管理的信息。这些信息可能以不同的详细程度和精度建档，存放在由个别数据源表到集成的数据源表中。通常，数据源用传统的数据建模技术，如ER模型或者CASE工具建模。(3)数据仓库视图：包括事实表和维表。提供存放在数据仓库内部的信息。包括预计算的总和与计数，以及提供历史别进的关于源、原始日期和时间等信息。(4)商务视图：是从最终用户的角度透视数据仓库中的数据。？【数据立方的两种表】（维表、事实表）？立方体：立方格：立方体物化概念：实现把数据汇总算出来（不是临时提交时才计算）一个n维立方体（n-D）称为基本方体；0-D方体存放最高层的汇总，称为定点方体。方体的格称为数据立方体。·数据立方由维和度量组成【OLTP与OLAP的主要区别】(1)用户和系统的面向性：OLTP系统是面向顾客的，用于办事员、客户和信息技术专业人员的事务和查询处理。OLAP系统是面向市场的，用于知识工人的数据分析。(2)数据内容：OLTP系统管理当前数据。通常，这种数据太琐碎，难以用于决策。OLAP系统管理大量历史数据，提供汇总和聚集机制，并在不同粒度级别上存储和管理信息。这些特点使得数据更容易用于见多识广的决策。(3)数据库设计：通常，OLTP系统采用实体-联系（ER）数据模型和面向应用的数据库设计。而OLAP系统通常采用星形或雪花模型和面向主题的数据库设计。(4)视图：OLTP系统主要关注企业或部门的当前数据，不涉及历史数据或不同组织的数据。相比之下，由于组织的变化，OLAP系统尝尝跨越数据库模式的多个版本。OLAP系统还处理来自不同组织的信息，由多个数据存储集成的信息。由于数据量巨大，OLAP数据存放在多个存储介质上。(5)访问模式：OLTP系统的访问模式主要由短的原子事务组成。这种系统需要并发控制和恢复机制。然而，对OLAP系统的访问大部分是只读操作（大多是历史数据），尽管许多可能是复杂的查询。·OLTP和OLAP的其他区别包括数据库大小、操作的频繁程度、性能度量等。如下图Lecture4.【关联规则的确定性度量与实用性度量】确定性度量：支持度（Support），事务包含XY的概率，即support＝P(XY)实用性度量：置信度（Confidence），事务同时包含X与Y的条件概率，即confidence＝P(Y|X).Lecture5.【两种学习模型】有监督学习模型：提供了每个训练元组的类标号，称作监督学习，即分类器的学习在被告知每个训练元组属于哪个类的监督下进行。无监督学习（聚类）模型：每个训练元组的类标号都是未知的，并且要学习的类的个数或集合也可能事先不知道。【评估分类器准确率的方法】PPT版划分法：适用于大规模数据。把样本划分成2个独立的数据集合。交叉验证：适用于中型规模数据。把数据集划分成k个子样本集合，使用k-1个子样本集合作为训练集，另一个作为测试集，亦称k-折交叉验证。留一测试：适用于小规模数据。k=n(n-折交叉验证)。教材版保持方法和随机子抽样：保持方法把给定数据随机分成两个独立的集合：训练集和检验集，使用训练集导出模型，其准确率用检验集估计.随机子抽样是保持方法的变型，将保持方法重复k次，总准确率估计取每次迭代准确率的平均值交叉确认:把数据集划分成k个子样本集合，使用k-1个子样本集合作为训练集，另一个作为测试集，亦称k-折交叉验证。自助法：从给定训练元组中有放回均匀抽样【基于规则的分类器】内容：前件，后件，覆盖学习规则：分治法规则能够覆盖整个示例空间吗？：缺省规则如何学到最优规则？:NP－hard问题Lecture6.*【近似比】对于优化问题，算法A的近似比a(n)≥1最小化：a(n)=cost(A)/cost(opt)最大化：a(n)=cost(opt)/cost(A)*【问题的分类】*【P,NP,NPC,NP-Hard】P问题：在多项式时间内能解决的问题NP问题：在多项式时间内能验证的问题NPC问题：所有