概念描述：特征化与比较(武汉大学-李春葆)

1、第第5章章 概念描述：特征化与比较概念描述：特征化与比较 n从数据分析的角度看，数据挖掘可以分为描述性挖掘和预从数据分析的角度看，数据挖掘可以分为描述性挖掘和预 测性挖掘。测性挖掘。 q描述性挖掘：描述性挖掘：以简洁概要的方式描述数据，并提供数据以简洁概要的方式描述数据，并提供数据 的有趣的一般性质。的有趣的一般性质。 q预测性数据挖掘：预测性数据挖掘：通过分析数据建立一个或一组模型，通过分析数据建立一个或一组模型， 并试图预测新数据集的行为。并试图预测新数据集的行为。 5.1 什么是概念描述？什么是概念描述？ n概念描述是以简洁的形式在更一般的（而不是在较低层的）概念描述是以简洁的形式在更一

2、般的（而不是在较低层的） 抽象层描述数据。抽象层描述数据。 q当所描述的概念所指的是一类对象时，也称为类描述。当所描述的概念所指的是一类对象时，也称为类描述。 n概念指的是一类数据的集合。概念指的是一类数据的集合。 qe.g. e.g. 研究生，大客户。研究生，大客户。 n概念描述产生特征化和比较描述。概念描述产生特征化和比较描述。 q特征化：提供给定数据集的简洁汇总。特征化：提供给定数据集的简洁汇总。 q区分：提供两个或多个数据集的比较描述。区分：提供两个或多个数据集的比较描述。 概念描述与概念描述与OLAP的区别的区别 n概念描述和数据仓库的联机分析处理（概念描述和数据仓库的联机分析处理（

3、OLAP）都跟数据）都跟数据 概化密切相关，即以简洁的形式在更一般的抽象层描述数概化密切相关，即以简洁的形式在更一般的抽象层描述数 据，允许数据在抽象层概化，便于考察数据的一般行为。据，允许数据在抽象层概化，便于考察数据的一般行为。 n两者的主要区别：两者的主要区别： q概念描述概念描述 n可以处理复杂数据类型的属性及其聚集。可以处理复杂数据类型的属性及其聚集。 n一个更加自动化的过程。一个更加自动化的过程。 qOLAP n实际使用的实际使用的OLAP系统中，维和度量的数据类型都非系统中，维和度量的数据类型都非 常有限（非数值型的维和数值型的数据），表现为常有限（非数值型的维和数值型的数据），

4、表现为 一种简单的数据分析模型。一种简单的数据分析模型。 n一个由用户控制的过程。一个由用户控制的过程。 5.2 数据概化数据概化 n数据概化数据概化 q数据库中的数据和对象通常包含原始概念层的细节信息，数数据库中的数据和对象通常包含原始概念层的细节信息，数 据概化就是将数据库中的跟任务相关的数据集从较低的概念据概化就是将数据库中的跟任务相关的数据集从较低的概念 层抽象到较高的概念层的过程。层抽象到较高的概念层的过程。 n主要方法：主要方法： q数据立方体（数据立方体（OLAP使用的方法）使用的方法） q面向属性的归纳方法面向属性的归纳方法 1 2 3 4 5 概念层概念层 5.2.1 数据概

5、化：数据立方体方法数据概化：数据立方体方法 n执行计算并将结果存储在数据立方体中。执行计算并将结果存储在数据立方体中。 n优点：优点： q数据概化的一种有效实现。数据概化的一种有效实现。 q可以计算各种不同的度量值。可以计算各种不同的度量值。 n比如：比如：count(), sum(), average(), max() q概化和特征分析通过一系列的数据立方体操作完成，比如上概化和特征分析通过一系列的数据立方体操作完成，比如上 卷、下钻等。卷、下钻等。 n缺点：缺点： q只能处理非数值类型的维和简单聚集数值类型的度量值（大只能处理非数值类型的维和简单聚集数值类型的度量值（大 部分现有商业系统中

6、，只能为非数值类型的维产生概念分部分现有商业系统中，只能为非数值类型的维产生概念分 层）。层）。 q缺乏智能分析，不能自动确定分析中该使用哪些维，应该概缺乏智能分析，不能自动确定分析中该使用哪些维，应该概 化到哪个层次。化到哪个层次。 5.2.2 面向属性的归纳面向属性的归纳 特点：特点： n一种面向关系数据查询的、基于汇总的在线数据分析技术。一种面向关系数据查询的、基于汇总的在线数据分析技术。 n受数据类型和度量类型的约束比较少。受数据类型和度量类型的约束比较少。 1. 面向属性的归纳的基本步骤面向属性的归纳的基本步骤 n数据收集。获得初始工作关系。数据收集。获得初始工作关系。 n进行面向属

7、性的归纳。进行面向属性的归纳。 q基本操作是数据概化，对有大量不同值的属性，进行进基本操作是数据概化，对有大量不同值的属性，进行进 一步概化。一步概化。 n属性删除属性删除 n属性概化属性概化 q属性概化控制：控制概化过程，确定有多少不同的值才属性概化控制：控制概化过程，确定有多少不同的值才 算是有大量不同值的属性。算是有大量不同值的属性。 n属性概化临界值控制属性概化临界值控制 n概化关系临界值控制概化关系临界值控制 （1） 数据收集数据收集 n目的：获得跟任务相关的数据集，包括属性或维，在目的：获得跟任务相关的数据集，包括属性或维，在DMQL中中 他们由他们由in relevance to

8、子句表示。子句表示。 n示例：示例： qDMQL: 描述描述Big-University数据库中研究生的一般特征数据库中研究生的一般特征: use Big_University_DB mine characteristics as “Science_Students” in relevance to name, gender, major, birth_place, birth_date, residence, phone#, gpa from student where status in “graduate” q将数据挖掘查询转换为关系查询：将数据挖掘查询转换为关系查询： Select n

9、ame, gender, major, birth_place, birth_date, residence, phone#, gpa from student where status in “Msc”, “MBA”, “PhD” 产生的结果表：产生的结果表： n数据收集时的困难数据收集时的困难 q用户在指定相关的数据集方面存在困难，遗漏在描用户在指定相关的数据集方面存在困难，遗漏在描 述中可能起作用的属性。述中可能起作用的属性。 q用户可能引进太多的属性。用户可能引进太多的属性。 （2）数据概化）数据概化 n数据概化的两种常用方法：属性删除和属性概化数据概化的两种常用方法：属性删除和属性概

10、化 q属性删除的适用规则：对初始工作关系中具有大量不同属性删除的适用规则：对初始工作关系中具有大量不同 值的属性，符合以下情况，应使用属性删除：值的属性，符合以下情况，应使用属性删除： n在此属性上没有概化操作符（比如该属性没有定义在此属性上没有概化操作符（比如该属性没有定义 相关的概念分层）。相关的概念分层）。 n该属性的较高层概念用其他属性表示。该属性的较高层概念用其他属性表示。 q属性概化的使用规则：如果初始工作关系中的某个属性属性概化的使用规则：如果初始工作关系中的某个属性 具有大量不同值，且该属性上存在概化操作符，则使用具有大量不同值，且该属性上存在概化操作符，则使用 该概化操作符对

11、该属性进行数据概化操作。该概化操作符对该属性进行数据概化操作。 属性概化控制属性概化控制 n确定什么是确定什么是“具有大量的不同值具有大量的不同值”，控制将属性概化到多，控制将属性概化到多 高的抽象层。高的抽象层。 n属性概化控制的两种常用方法：属性概化控制的两种常用方法： q属性概化临界值控制属性概化临界值控制 n对所有属性设置一个概化临界值或者是对每个属性都对所有属性设置一个概化临界值或者是对每个属性都 设置一个临界值（一般为设置一个临界值（一般为2到到8）。）。 q概化关系临界值控制概化关系临界值控制 n为概化关系设置一个临界值，确定概化关系中，不同为概化关系设置一个临界值，确定概化关系

12、中，不同 元组的个数的最大值。（通常为元组的个数的最大值。（通常为10到到30，应该允许在，应该允许在 实际应用中进行调整）。实际应用中进行调整）。 q两种技术的顺序使用：使用属性概化临界值控制来概化两种技术的顺序使用：使用属性概化临界值控制来概化 每个属性，然后使用关系临界值控制进一步压缩概化的每个属性，然后使用关系临界值控制进一步压缩概化的 关系。关系。 n相等元组的合并、累计计数和其他聚集值。相等元组的合并、累计计数和其他聚集值。 当属性不同值个数大于某阈值，删除或概化。当属性不同值个数大于某阈值，删除或概化。 当概化关系中不同元组个数超过阈值，当概化关系中不同元组个数超过阈值， 进一步

13、概化；否则不再概化。进一步概化；否则不再概化。 面向属性的归纳面向属性的归纳示例示例 n挖掘挖掘Big-University数据库中研究生的一般特征：数据库中研究生的一般特征： qname（姓名）：删除属性。（姓名）：删除属性。 qgender（性别）：只有两值，保留该属性，不概化。（性别）：只有两值，保留该属性，不概化。 qmajor（专业）：根据概念分层向上攀升（专业）：根据概念分层向上攀升文，理，工文，理，工。 qbirth_place（出生地）：根据概念分层（出生地）：根据概念分层location向上攀升。向上攀升。 qbirth_date（出生日期）：概化为（出生日期）：概化为age

14、，再概化为，再概化为age_range。 qresidence（住址）：根据概念分层（住址）：根据概念分层location向上攀升。向上攀升。 qphone#（电话）：删除属性。（电话）：删除属性。 qgpa（成绩）：根据（成绩）：根据GPA的分级作为概念分层。的分级作为概念分层。 通过面向属性归纳得到的主概化关系：通过面向属性归纳得到的主概化关系： gendermajorbirth_country age_range residence_city gpa count M Science Canada 20.25 Richmond very_good 16 F Science Foreign

15、25.30 Burnaby excellent 22 . 5.2.2 面向属性的归纳算法面向属性的归纳算法 n输入输入 q1. DB; 2. 数据挖掘查询数据挖掘查询DMQuery; 3. 属性列表属性列表; 4. 属性的概念分层属性的概念分层; 属性的概化临界值；属性的概化临界值； n输出输出 q主概化关系主概化关系P n算法描述：算法描述： 1.W get_task_relevant_data(DMQuery, DB) 2.prepare_for_generalization(W)/预处理预处理 1.扫描扫描W，收集每个属性，收集每个属性a的不同值。的不同值。 2.对每个属性对每个属性a，

16、根据临界值确定是否删除，如果不删除，则计算其最小，根据临界值确定是否删除，如果不删除，则计算其最小 期望层次期望层次L，并确定映射对，并确定映射对(v,v)。 3.P generalization(W) q通过使用通过使用v代替代替W中每个中每个v，累计计数并计算所有聚集值，导出，累计计数并计算所有聚集值，导出P。 1.每个概化元组的插入或累积计数。每个概化元组的插入或累积计数。 2.用数组表示用数组表示P。 主概化关系主概化关系 相关数据集合相关数据集合 学号学号性别性别分数分数 1男男85 2女女90 3男男76 4男男96 5男男62 6女女88 7女女93 all A 90 B 808

17、9 C 7079 D 6069 E 60 分数：概念分层分数：概念分层 性别性别分数分数个数个数 男男A1 男男B1 男男C1 女女A2 女女B1 5.2.3 导出概化的表示导出概化的表示 n概化关系概化关系 q一部分或者所有属性得到概化的关系，包含计数或其他一部分或者所有属性得到概化的关系，包含计数或其他 度量值的聚集。度量值的聚集。 locationitemsalescount 亚洲亚洲 TV 15 300 欧洲欧洲 TV 12 250 北美北美 TV 28 450 亚洲亚洲 计算机计算机15 300 欧洲欧洲 计算机计算机 12 250 北美北美 计算机计算机28 450 某年销售某年销

18、售 概化关系概化关系 n交叉表交叉表 q二维交叉表使用每行显示一个属性，使用每列显示二维交叉表使用每行显示一个属性，使用每列显示 另外一个属性将结果集映射到表中。另外一个属性将结果集映射到表中。 q可视化技巧：可视化技巧： n条形图、饼图、曲线和数据立方体浏览工具（用单元的大条形图、饼图、曲线和数据立方体浏览工具（用单元的大 小代表计数，用单元亮度代表另外的度量）。小代表计数，用单元亮度代表另外的度量）。 locationitemTV计算机两项和计算机两项和 salescountsalescountsalescount 亚洲亚洲15300 120 10001351300 欧洲欧洲 . 北美北美

19、 . 所有地区所有地区 . n量化规则量化规则 q使用使用t_weight表示主概化关系中每个元组的典型性表示主概化关系中每个元组的典型性 n量化特征规则量化特征规则 q将概化的结果映射到相应的量化特征规则中，比如：将概化的结果映射到相应的量化特征规则中，比如： n i ia qcountqcountweightt 1 )(/ )(_ : )(.: )()(_arg , mmll wtXconditionwtXconditionXclassettX %45: ) )( .%25: ) )( )( , tAmericanNorth XlocationtAsiaXlocationcomputerX

20、itemX 量化特征规则中每个条件的析取成为目标类的一个必要条件；亦即，量化特征规则中每个条件的析取成为目标类的一个必要条件；亦即， 如果如果X在目标类中，则在目标类中，则X满足满足conditioni的概率是的概率是wi： 兴趣度度量兴趣度度量 一个关于维一个关于维item、location和和cost的数据立方体，的数据立方体， 单元的单元的size表示对应单元的计数，单元的亮度表示另一表示对应单元的计数，单元的亮度表示另一 个度量，如个度量，如sum(sales)。可以进行旋转、上卷、下钻、。可以进行旋转、上卷、下钻、 切片和切块操作，在数据立方体浏览器中显示。切片和切块操作，在数据立方

21、体浏览器中显示。 5.3 解析特征化：属性相关分析解析特征化：属性相关分析 n特征化过程中的两大困难特征化过程中的两大困难 q复杂数据类型的处理。复杂数据类型的处理。 q缺乏一种自动概化的过程，用户必须告诉系统。缺乏一种自动概化的过程，用户必须告诉系统。 n哪些属性或维应该包括在类特征化中。哪些属性或维应该包括在类特征化中。 n每个维应该概化到多高的程度。每个维应该概化到多高的程度。 确定哪些维或属性是高度相关的确定哪些维或属性是高度相关的保留这样的属性或保留这样的属性或 维：其值可以用于区分该类与其他类。维：其值可以用于区分该类与其他类。 5.3.1 为什么进行属性相关分析？为什么进行属性相

22、关分析？ n数据仓库和数据仓库和OLAP系统中的多维数据分析缺乏一个自动概系统中的多维数据分析缺乏一个自动概 化过程，这使得这个过程中需要有很多用户干预。化过程，这使得这个过程中需要有很多用户干预。 q用户必须告诉系统哪些维或属性应当包含在类分析中用户必须告诉系统哪些维或属性应当包含在类分析中 （难）。（难）。 n属性太少，则造成挖掘的描述结果不正确属性太少，则造成挖掘的描述结果不正确 n属性太多，浪费计算、淹没知识属性太多，浪费计算、淹没知识 q告诉系统每个维应当概化到多高的层次告诉系统每个维应当概化到多高的层次 （易）。（易）。 n直接通过概化的临界值，说明给定维应当达到的概化程度直接通过

23、概化的临界值，说明给定维应当达到的概化程度 n对概化层次不满意，则可以指定需要上卷或下钻的维对概化层次不满意，则可以指定需要上卷或下钻的维 5.3.2属性相关分析的方法属性相关分析的方法 n属性相关分析的基本思想是计算某种度量，用于属性相关分析的基本思想是计算某种度量，用于量化属性量化属性 与给定类或概念的相关性与给定类或概念的相关性。 q可采用的度量包括：信息增益、可采用的度量包括：信息增益、Gini索引、不确定性和索引、不确定性和 相关系数。（涉及机器学习、统计、模糊和粗糙集理论相关系数。（涉及机器学习、统计、模糊和粗糙集理论 等方面的相关知识）等方面的相关知识） q比如：比如：信息增益信

24、息增益通过计算一个样本分类的期望信息和属通过计算一个样本分类的期望信息和属 性的熵来获得一个属性的信息增益，判定该属性与当前性的熵来获得一个属性的信息增益，判定该属性与当前 的特征化任务的相关性。的特征化任务的相关性。 信息增益方法信息增益方法 nS是一个训练样本的集合，该样本中已知每个集合的类编号。是一个训练样本的集合，该样本中已知每个集合的类编号。 每个样本为一个元组。有个属性用来判定某个训练样本的类每个样本为一个元组。有个属性用来判定某个训练样本的类 编号（类似于学生记录中的编号（类似于学生记录中的status属性）。属性）。 n假设假设S中有中有m个类，总共个类，总共s个训练样本，每个

25、类个训练样本，每个类ci有有Si个样本（个样本（i 1,2,3.m），那么任意一个样本属于类），那么任意一个样本属于类Ci的概率是的概率是si / s，那，那 么用来分类一个给定样本的么用来分类一个给定样本的期望信息期望信息是：是： s s s s sssI i m i i m2 1 21 log),.,( c1 c2 c3 cm s个样本分为个样本分为m个类个类 s1 s2 s3 sm n对于属性对于属性A，有，有v个值的个值的a1,a2,.,av，可以将，可以将S分成分成v个子集个子集 S1,S2,.,Sv，其中，其中Sj包含包含S中属性中属性A上的值为上的值为aj的样本。假的样本。假 设

26、设Sj包含类包含类Ci的的sij个样本。根据个样本。根据A的这种划分的期望信息的这种划分的期望信息 称为称为A的熵：的熵： ),.,( . )( 1 1 1 mjj v j mjj ssI s ss AE a1a2a3av S1S2S3 Sv 属性属性A： 类类Ci 1im si1si2si3 siv nA上该划分的获得的信息增益定义为：上该划分的获得的信息增益定义为： n具有高信息增益的属性，是给定集合中具有高区分度的属具有高信息增益的属性，是给定集合中具有高区分度的属 性。所以可以通过计算性。所以可以通过计算S中样本的每个属性的信息增益，中样本的每个属性的信息增益， 来得到一个属性的相关性

27、的排序。来得到一个属性的相关性的排序。 )(),.,()( 21 AEsssIAGain m 示例示例 n任务任务:使用解析特征化挖掘使用解析特征化挖掘BigUniversity的研究生的一的研究生的一 般特征描述。般特征描述。 n给定：给定： q属性属性name, gender, major, birth_place, birth_date, phone#和和gpa。 qUi = 属性分析阀值。属性分析阀值。 qTi = 属性概化阀值。属性概化阀值。 qR = 属性相关阀值。属性相关阀值。 n1. 数据收集数据收集 q目标类：研究生目标类：研究生 q对比类：本科生对比类：本科生 n2. 使用

28、保守的阀值使用保守的阀值Ui和和Ti进行进行AOI（面向属性的归纳）（面向属性的归纳） q属性删除属性删除 nname和和phone# q属性概化属性概化 n概化概化major, birth_place, birth_date 和和 gpa q进行累积计数进行累积计数 q候选关系：候选关系：gender, major, birth_country, age_range 和和gpa gendermajorbirth_countryage_rangegpacount MScienceCanada20-25Very_good16 FScienceForeign25-30Excellent22 MEn

29、gineeringForeign25-30Excellent18 FScienceForeign25-30Excellent25 MScienceCanada20-25Excellent21 FEngineeringCanada20-25Excellent18 目标类候选关系：目标类候选关系：研究生研究生( =120) gendermajorbirth_countryage_rangegpacount MScienceForeign20Very_good18 FBusinessCanada20Fair20 MBusinessCanada20Fair22 FScienceCanada20-25Fair24 MEngineering Foreign20-25Very_good22 FEngineering Canada20Excellent24 对比类候选关系：对比类候选关系：本科生本科生 ( =130) (可以在类比较时使用）可以在类比较时使用） n3. 相关性分析相关性分析 q计算给定的样本分类所需要的期望信息计算给定的样本分类所需要的期望信息 q计算每个属性的熵计算每个属性的熵: e.g. major（属性）（属性） 99880 250 130 250 130 250