数据仓库 第七章35670.pptx
第七章 概念描述7.1 概念描述基本知识7.2 数据概化与基于汇总的特征化7.3 解析特征化属性相关分析7.4 挖掘概念比较区分不同的类第七章 概念描述(续)DB中存放大量细节性数据，而用户通常希望以简洁的描述形式观察汇总的数据集。这种描述可提供某类数据的概貌以及与其他数据类的区别。此外，用户希望方便灵活地以不同的粒度和从不同的角度描述数据集。这种描述性数据挖掘称为概念描述，它是数据挖掘的一个重要部分。7.1 概念描述基本知识概念：通常指数据的汇集。概念描述：是描述式数据挖掘最基本形式，它以简洁汇总的形式描述给定数据集，提供数据的有趣的一般特性。7.1 概念描述基本知识（续）概念描述的组成：特征化：提供了一个有关数据整体的简洁清晰描述。（定性描述）比较：提供了基于多组不同类数据的对比概念描述。（对比定性描述）7.1 概念描述基本知识（续）概念描述与数据概化密切相关。给定存放在DB中的大量数据，能够以简洁的形式在更一般的抽象层描述数据是很有用的。允许数据集在多个抽象层概化，便于考察数据的一般行为。这种多维,多层数据概化类似于DW中的多维数据分析。而概念描述类似于DW的OLAP。7.1 概念描述基本知识（续）大型数据库的概念描述和数据仓库的OLAP有何差别？概念描述可处理复杂的数据类型和聚集。概念描述是自动处理数据挖掘过程。7.1 概念描述基本知识（续）概念描述的方法包括多层概化、汇总、特征化和比较。这些方法形成实现数据挖掘的两个主要功能模块的基础：多层特征化和比较。第七章 概念描述7.1 概念描述基本知识7.2 数据概化与基于汇总的特征化7.3 解析特征化属性相关分析7.4 挖掘概念比较区分不同的类7.2 数据概化与基于汇总的特征化 数据概化是一个分析过程，它将DB中与任务相关的大数据集从较低的概念层抽象到较高的概念层。对大量数据进行有效灵活的概化方法主要有两种：数据立方体方法基于属性的归纳方法1.数据立方体方法 利用数据立方体方法进行数据概化，被分析的数据存放在一个多维数据库中，通过对多维数据立方进行上卷或下钻操作，可完成数据概化和数据细化工作。1.数据立方体方法（续）数据立方体提供了一种有效的数据概化方法，且构成了描述性数据挖掘中一个重要功能。但由于OLAP的数据立方实现是将维的类型限制在简单非数值类型，且将处理限制在简单数据汇总方面，因此数据立方体并不能解决概念描述所能解决的一些重要问题。如：描述中应作用哪些维？概化过程应进行到哪个抽象层次上？这些问题均是由用户负责提供答案的。2.基于属性归纳方法基本思想：首先使用RDB查询收集任务相关的数据；然后通过考察任务相关数据中每个属性的不同值的个数，进行概化。数据概化是通过属性删除或属性概化操作来完成。通过合并相同行并累计它们相应的个数。这自然就减少了概化后数据集的大小，所获结果以图表、规则等多种不同形式提供给用户。2.基于属性归纳方法（续）例1：从一个大学数据库的学生数据中挖掘出研究生的一般特征。给定的属性有：姓名、性别、专业、出生地、出生日期、居住地、电话和GPA（平均等级分）。AOI方法的第一步：利用DB查询语言从大学DB中将学生数据抽取出来，然后指定一组与挖掘任务相关的属性集。2.基于属性归纳方法（续）由于数据挖掘查询通常只涉及DB的一部分，选择相关的数据集不仅使得挖掘更有效，而且与在整个DB挖掘相比，能产生更有意义的规则。对用户而言，指定挖掘的属性可能比较困难。有时，用户只能选择少量他感到可能重要的属性，而遗漏在描述中可能起作用的其他属性。2.基于属性归纳方法（续）如：出生地维由属性城市、省和国家定义。在这些属性中，用户或许只考虑了城市属性。为了对出生地进行概化处理，就必须将出生地概化所涉及到的其它属性包含进来。换句话说，系统自动地包括省和国家作为相关属性，使得城市可以在归纳过程中概化到较高的概念层。2.基于属性归纳方法（续）另一方面，用户可能引进过多的属性，如：指定所有的属性，这样大学DB的所有属性都将包含在分析中，而有些属性对有趣的描述是没有用的。姓名 性别 专业 出生地 出生日 居住地 电话GPA王东海 男 CS 合肥市 79.07.26合肥市金寨路65 号0551-36656783.67李哲 男 CS 合肥市 80.12.08合肥市芜湖路186 号0551-36560123.70汪燕 女 PH 上海市 80.09.03上海市高安路1250 号021-623819603.83初始工作关系：任务相关数据的集合2.基于属性归纳方法（续）对已经准备好的数据，如何进行基于属性归纳？AOI方法的第二步：进行数据概化操作，可用两种方法之一进行：属性删除，属性概化。2.基于属性归纳方法（续）属性删除基于如下规则：若一个属性有许多不同数值，且(a)该属性无法进行概化操作（如：没有定义相应的概念分层），或(b)它的更高层次概念是用其他属性描述的，则该属性应当从数据集中删除。2.基于属性归纳方法（续）属性概化基于如下规则：若一个属性有许多不同数值，且该属性存在一组概化操作，则可以选择一个概化操作对该属性进行处理。属性删除和属性概化两个规则都表明，如果某属性有大量的不同值，应当进行进一步概化。这就提出一个问题：多大才算“属性具有大量不同值”？2.基于属性归纳方法（续）这取决于属性或应用，有的用户愿意让属性留在较低的抽象层，而另一些用户愿意将它们概化到较高的抽象层。控制将属性概化到多高的抽象层通常是相当主观的。该过程的控制称为属性概化控制。2.基于属性归纳方法（续）若属性概化得“太高”，则导致过分概化，产生的规则可能没有多少信息。若属性概化没有达到“足够高的层次”，则“亚概化”也同样可能使得到的规则变得失去意义。因此在基于属性归纳时，掌握概化平衡非常重要。2.基于属性归纳方法（续）有许多控制概化过程的方法，下面是两种常用的方法：(1)属性概化阈值控制 该技术是对所有属性统一设置一个概化阈值（取值范围一般为2到8）。如果属性的不同值个数大于属性概化阈值，则应当进行进一步的属性删除或属性概化。2.基于属性归纳方法（续）(2)概化关系阈值控制 为概化关系设置一个阈值（通常取值范围为10到30）。如果概化关系中不同元组的个数超过该阈值，则应当进一步概化；否则，不再进一步概化。2.基于属性归纳方法（续）这两种技术可以顺序使用：首先使用属性概化阈值控制技术概化每个属性，然后使用概化关系阈值控制进一步减少概化关系的（规模）大小。无论使用哪种概化控制技术，都应当允许用户调整概化阈值，以便得到有趣的规则。2.基于属性归纳方法（续）例1（续）：对前面得到的初始工作关系的每个属性，概化过程如下：1）姓名：由于姓名存在大量不同值，并且其上没有定义概念分层，该属性被删除。2）性别：由于性别只有两个不同值，该属性保留，并不对其进行概化。2.基于属性归纳方法（续）3）专业：假设定义了一个概念分层，从而可以对专业属性进行概化。又假设属性概化阈值置为5，在初始数据集合中有25个不同取值。则通过对属性概化和属性概化控制，专业属性被概化到指定的概念（如：科学，工程，商学）。2.基于属性归纳方法（续）4）出生地：该属性有大量不同值，因此应当概化它。设出生地的概念分层为：城市省国家。如果初始关系中，国家取值超过了属性概化阈值，则出生地应当删除，因为尽管可以进行概化操作，概化阈值也不会满足。但如果假定国家的取值个数小于概化阈值，则出生地应当概化到出生国家。2.基于属性归纳方法（续）5）出生日期：假定存在概念分层，可以将出生日期概化到年龄，而年龄概化到年龄分类，并且年龄分类的区间数小于对应的属性概化阈值，则应当对出生日期进行概化。2.基于属性归纳方法（续）6）居住地：假定居住地被属性号码，街道，城市，省，国家定义。号码和街道的不同值一般很多，而且这些概念的层次相当低。因此，号码和街道应当删除，将居住地概化到居住城市。这样可包含较少的不同值。2.基于属性归纳方法（续）7）电话：与属性姓名一样，因包含太多不同值，应当在概化中删除。8）GPA：假定存在GPA的概念分层，将平均成绩分成若干区间，如：3.75-4.0，3.5-3.75，也可相应的描述为：优秀，良好，因此该属性可以被概化。2.基于属性归纳方法（续）概化过程会产生一系列内容相同的数据行，相同内容的数据行被合并成一个，并累计它们的计数值。最终结果如下表：性别 专业 出生国 年龄区间 出生城市GPA累计男 科学 中国2025合肥 良好16女 工程 中国2530上海 优秀22对初始关系的数据进行基于属性归纳得到的广义关系：3.基于属性归纳算法 算法：基于属性的归纳 输入：(1)关系DB；(2)数据挖掘命令DMQuery；(3)属性表a_list；(4)属性ai上的概念分层或概化操作符的集合Gen(a)；(5)每个属性ai概化阈值a_gen_thresh(a)3.基于属性归纳算法(续)输出：主概化关系P（包含基于a_list属性集的一个定性概念描述）方法：(1)Wget_task_relevant_data(DMQuery,DB)；/工作关系W存放任务相关的数据(2)prepare_for_generalization(W)/该步实现如下:3.基于属性归纳算法(续)(a)扫描W，收集每个ai属性取不同值的个数。(b)对每个属性ai，根据给定的或缺省的属性阈值，确定ai是否应当删除；如果不删除，则计算它的最小期望层次Li，并确定映射对(v,v)，基中v是W中ai的不同值，v是其在层Li对应的概化值。3.基于属性归纳算法(续)(3)Pgeneralization(W）通过用其在映射中对应的v替换W中每个值v，累计计数并计算所有聚集值，导出主概化关系P。这一步可用下面两种方法有效实现：(a)对每个概化元组，通过二分检索将它插入主关系P中。如果元组已在P中，则简单地增加它的计数值并相应处理其他聚集值；否则，将它插入P。3.基于属性归纳算法(续)(b)在大部分情况下，由于主关系层不同值的个数很少，可以将主关系编码，作为m_维数组，其中m 是P 中的属性数，而每个维包含对应的概化属性值。数组的每个元素存放对应的计数和其他聚集值。概化元组的插入通过对应的数组元素上的度量聚集进行。4.基于属性归纳结果的表示 基于属性归纳方法的挖掘结果可以有多种输出表示形式。地点 商品销售额(百万)个数累计(千)亚洲 电视15 300欧洲 电视12 250北美 电视28 450亚洲 电脑120 1000欧洲 电脑150 1200北美 电脑200 1800表格表示描述地点或商品电视 电脑电视+电脑销售额 累计 销售额 累计 销售额 累计亚洲15 300 120 1000 135 1300欧洲12 250 150 1200 162 1450北美28 450 200 1800 228 2250所有地区45 1000 470 4000 525 5000组合表表示描述棒图表示描述第七章 概念描述7.1 概念描述基本知识7.2 数据概化与基于汇总的特征化7.3 解析特征化属性相关分析7.4 挖掘概念比较区分不同的类7.3 解析特征化属性相关分析1.属性相关分析意义 在挖掘定性概念描述知识过程中，DW和OLAP工具中的多维数据分析有两个局限：一是无法处理复杂对象，二是缺乏自动概化过程。1.属性相关分析意义（续）通常，用户告诉数据挖掘系统每个维应当概化到多高层次并不困难，但确定数据集的定性描述应包含哪些属性是一件困难的事。我们引进一些方法进行属性（或维）相关分析，以过滤掉统计上不相关或弱相关的属性，而保留与挖掘任务最相关的属性。1.属性相关分析意义（续）包含属性（维）相关分析的类特征化称为解析特征化；包含属性（维）相关分析的类比较称为解析比较。直观上，若一个属性的取值可以帮助有效地区分不同类别的数据集，则这个属性就被认为是与相应类别数据集密切相关的。1.属性相关分析意义（续）例：一辆汽车的颜色不太可能用于区分贵贱汽车（类别），但汽车的型号、品牌、制造商、款式和气缸数可能是更相关的属性。此外，即使在同一个维内，对于区分一个类与其他类，在不同的概念层也可能有很不相同的能力。1.属性相关分析意义（续）例：在出生日维中，生日和生月都不太可能与雇员的工资相关；而只有年龄区间可能与雇员的工资高度相关。这意味着相关分析应当在多层次进行，并且只有那些最相关的维层次应当包含在分析中。1.属性相关分析意义（续）属性的相关性要根据属性区分一个类与其他类的能力来评估。在挖掘概念比较时，目标类和对比类要明显地在挖掘查询中给出。前面在挖掘概念特征时，只有一个被特征化的类，即没有说明对比类。哪些对比类应当用于相关分析并非是明显的。在这种情况下，除特征化的数据集外，DB中可比较的数据集都作为对比类。2.属性相关分析方法 属性相关分析的基本思想：计算某种度量，用于量化属性与给定类或概念的相关性。这些度量包括：信息增益，Gini索引，不确定性和相关系数。2.属性相关分析方法（续）下面介绍一种方法，它将信息增益分析技术和基于多维数据分析的方法集成在一起。该方法删除信息量较少的属性，收集信息较多的属性，用于概念描述分析。这里以ID3决策树归纳学习方法为例进行介绍。2.属性相关分析方法（续）设S 是训练样本的集合，其中每个样本的类标号已知，共有m个不同类别,则S 包含si个Ci类样本，i=1，m。任意一个样本属于类Ci的概率为si/s，其中s是集合S 所有样本总数。一个决策树可用于对数据对象进行分类,因此决策树可以看成是Ci的一个信息源,为产生相应信息需要的信息熵为：2.属性相关分析方法（续）(7.1)若属性A的取值为a1，a2，av，且该属性用作决策树的一个结点时，可将S 划分为子集S1，S2，Sv。其中Sj 包含属性A取同一值aj的数据行；Sj包含类Ci的sij个样本。2.属性相关分析方法（续）根据属性A的取值对当前数据集划分所获得的信息就称为属性A的熵。它的计算公式如下：(7.2)A上该划分得到的信息增益定义为:Gain(A)=I(s1,s2,sm)-E(A)(7.3)2.属性相关分析方法（续）ID3方法根据S集合中数据对象来计算每个属性Gain(A)值，并从中选择出值最大的作为决策树根结点，并根据该属性的取值个数将初始数据集划分为v份，即通过不断对每个新产生的数据子集循环进行上述操作，直到产生所有叶结点为止，至此就获得一个决策树。2.属性相关分析方法（续）概念描述的属性相关分析，执行步骤如下：(1)数据收集：通过查询处理，收集目标类和对比类的数据。(2)使用保守的AOI进行预相关分析：这里进行的AOI使用的属性分析阈值要合理的大，使得更多的属性在选定度量的进一步相关分析中被考虑。使用保守AOI得到的关系称作候选关系。2.属性相关分析方法（续）(3)使用选定的相关分析度量删除不相关和弱相关属性：使用选定的相关分析度量，评估候选关系中的每个属性。根据计算的属性与数据挖掘任务的相关性，对属性排序，然后删除不相关和弱相关属性。其结果为初始目标类（对比类）工作关系。(4)使用AOI产生概念描述:使用一组不太保守的属性概化阈值进行AOI。3.解析特征化实例例2：使用解析特征化挖掘大学数据库里研究生的一般特征描述。执行步骤为：（1）收集目标类数据，它由研究生的集合组成。对比类取本科生的集合。（2）用保守的属性概化阈值进行基于属性的归纳，通过属性删除和属性概化进行预相关分析（分析过程如例1）。得到下面两张表：性别 专业 出生国 年龄区间 GPA 累计计数男 科学 中国2125良16女 科学 外国2630优22男 工程 外国2630优18女 科学 外国2630优25男 科学 中国2125优21女 工程 中国2125优18由解析特征化得到的候选关系：目标类（研究生）由解析特征化得到的候选关系：对比类（本科生）性别 专业 出生国 年龄区间 GPA 累计计数男 科学 外国=20良18女 商学 中国=20及格20男 商学 中国=20及格22女 科学 中国2125及格24男 工程 外国2125良22女 工程 中国=20优243.解析特征化实例(续)（3）使用选定的相关分析度量(如信息增益),评估候选关系中的属性。设：C1对应于研究生类，有120个样本；C2对应于本科生类，有130个样本。为计算每个属性的信息增益，首先用公式(7.1)计算对给定的样本分类所需要的期望信息：3.解析特征化实例(续)3.解析特征化实例(续)下面计算每个属性的信息熵，以专业为例：专业=“科学”：S11=84 S21=42 I（S11，S21）=0.9183专业=“工程”：S12=36 S22=46 I（S12，S22）=0.9892专业=“商学”：S13=0 S23=42 I（S13，S23）=03.解析特征化实例(续)再利用公式(7.2)，如果样本根据专业划分，则对给定的样本进行分类所需的期望信息为：
