第2个回答 2006-10-16
一种基于数据立方体的数据泛化算法
[日期：2006-08-21] 来源： 作者： [字体：大 中 小]
黄建国
（合肥幼儿师范 现代教育技术中心 安徽 合肥 230011 ）
摘要 为了更有效的进行在线分类挖掘，提出了一种泛化算法。该算法结合了数据立方体技术和面向属性归纳方法中的泛化策略，有效降低了聚合运算的运算量，提高了运算效率，将数据库中的原始数据泛化成用户感兴趣的概念层次上的、聚合的、具有统计意义的元数据,为在线分类提供了良好的数据环境。
关键词 数据挖掘 数据泛化 数据立方体
1 引言
数据准备是KDD过程中一个很重要的过程，良好的数据准备过程能够为数据挖掘提供清洁、可靠、稳定的数据环境，以保证挖掘算法的有效实施。在线分类理想的数据环境应具备以下几个特点： （1）数据应包含丰富的属性信息，应具备可靠性和稳定性；
（2）数据的属性应具有对于分类任务的相关性。大多数的分类任务只与数据库中部分属性有关，多余的、无关的属性介入分类，常会减慢甚至错误引导分类过程，应此必须去掉无关属性。
（3）数据应具有高层数据信息，以发现清晰的、高层的、具有统计意义的分类规则。在本文的研究中，为了使数据环境达到上述要求，在数据准备阶段采用了数据泛化的策略，这个策略用概念层次作为背景，结合了OLAP技术与Jiawei Han等人的面向属性归纳的方法，明显提高了工作效率。
2 面向属性归纳中的基本泛化策略和算法
随着KDD研究的逐步深入， Jiawei Han等人提出了一种基于归纳的知识发现方法——面向属性的归纳方法[1][2][3]，这方法的特点是能够根据概念层次将低概念层的数据泛化到相应的高层次的概念层，以发现多层的或高层的规则。面向属性归纳方法是一种有效的、完整的知识发现算法，该算法将机器学习中示例学习方法与数据库的操作技术相结合[1]。算法的一个关键就是攀升属性所对应的概念层次树以泛化原始数据集的数据到用户感兴趣的概念层上，减少数据集的大小，从而降低知识发现过程的计算复杂度。面向属性归纳方法的进行，必须有两个前提：
（1）必须由用户提出明确的知识发现任务。在Jiawei Han等人的研究中，采用了一种类似SQL语句的知识发现语句DMQL[4]用来让用户定义发现任务，下面便是一个分类任务的语句描述：
要说明的是在本文的研究中采用了一个可视化的向导来引导用户定义发现任务，但为了文章描述方便，在本文的描述中，借用了DMQL来描述发现任务
（2）与发现任务相关的属性应有概念层次，如上文所述，数值型的概念层次可以自动提取，给定的概念层次可以用户的兴趣和发现任务的不同而进行动态调整。
在具备以上两个前提时，面向属性归纳采用了以下一些泛化策略。
● 泛化策略
策略1 在最小分解单位上泛化
一般而言，泛化都是在数据集的单个属性上进行的。因为单个属性常常是数据集中的最小分解单位。在最小分解单位上进行泛化，更能确定泛化过程中的细微变化，从而达到适度泛化的目的，避免过度泛化。
策略2 属性去除
如果一个属性在相关数据集中有大量不同的值，但是在其对应的概念层次树上，没有比该属性更高的概念层，则该属性将被从发现任务中去除。因为这样的属性是不可能被泛化到更高的概念层的，这是符合示例学习理论的。
策略3 概念树攀升
如果一个属性在概念层次树上有更高层次的概念，那么在泛化后的数据集中将所有记录的该属性值以高层次的属性值替代。
策略4 增加属性CNT
作为策略3的执行结果，必然会有许多不同的纪录由于属性值完全相同而合并成一条纪录。为了反应这一变化，引入属性CNT来纪录最初的表中不同纪录被概括成泛化表中相同纪录的个数。属性CNT在泛化的过程中保存了最初的计数，该值在知识发现的过程中起到了重要作用。
策略5 设立阈值
利用策略2中的CNT可以定义规则的正确率P，P=（符合规则的CNT值）/（符合规则左边属性条件的CNT值）。这样可以定义一阈值L用于取舍规则，若P>L则规则有效，否则丢弃该规则。另外，对一个属性A而言，为了将数据集概括到一定层次，必须沿着A的概念层次向上爬行几次。为了控制这个过程，有必要设置一归纳阈值，若A的取值个数达到这一阈值，则无需进一步概括，否则必须进行进一步的概括。除此之外，我们还可以对泛化表设置一个归纳阈值，如果泛化表的记录树大于该归纳阈值，则进行进一步的泛化直到满足这个归纳阈值为止。以上策略可以总结成算法如下：
算法1 (基本泛化算法)
输入条件：1.一个关系数据集，2 一个学习任务，3 一套相关属性的概念层次，4 每个属性归纳阈值t[i](i=1 to n，于属性相对应)、一个泛化表归纳阈值t2。
输出：一个用户期望的泛化后的数据集。
步骤：本算法可以分为两大步：
Step1. 根据用户提交的学习任务，从原始的关系数据集中收集与任务相关的属性与数据。生成初始泛化集GR；
Step2. 运行基本的泛化算法产生泛化数据集。
注意，step2可以细化成如下算法：
begin
for GR中的每一个属性Ai do
begin
while Ai的不同值的数目>t[i] do
begin
if Ai在概念层次中有高层次的概念 THEN
将Ai的所有值以高层次的概念值取代
else
在GR中移去Ai;
合并同样的记录；
end;
end；
while GR中的记录数>t2 do
begin
选择泛化属性进一步泛化；
合并相同的记录。
end;
end.
3 基于数据立方体的泛化算法
上述泛化算法是针对关系表的，其生成的结果也是关系数据表。对泛化后关系数据表进行分类规则挖掘时仍要进行大量的聚合运算，如计数、求和等。有没有办法降低聚合运算的运算量呢？有，那就是数据立方体。我们知道数据立方体的方格内存放的就是一些聚合值，而且对数据立方体进行聚合运算，其效率远高于对关系数据库进行聚合运算。基于此，本文提出了一种基于数据立方体的算法。
● 基于数据立方体的泛化算法
本算法共分为四步：第一步，初始化。首先，根据用户提出的发现任务，收集相关数据。（这里需说明的一点是此处用户提出的发现任务的相关属性实际上是一个维的概念，它可能对应于数据库中一个或几个有层次关系的实际属性。在下面的例子中我们将看到这一点。）然后确定每维的概念层次（自动提取数值型概念层次或动态调整已有概念层次）。第二步，构造基本立方体（Basecube）。这一步中首先根据数据库的数据分布特性（对于离散属性确定不同值的个数，连续值则确定数值间的最小间隔）确定每维的最初泛化层次，然后进行聚合计算来构造基本立方体。第三步，按照基本泛化策略对每维进行泛化造作，以确定每维理想的泛化层次。第四步，在新的泛化层次上对Basecube进行再计算，以构造最终的泛化立方体Primecube。这一步中将大量使用数据立方体的操作。该算法的形式描述如下：
算法2 基于数据立方体的泛化算法
输入：
1 一个待挖掘的关系数据集；
2 一个学习任务；
3 一个概念层次集合Gen(Ai)，Ai是任意维；
4 Ti，任意维Ai的泛化阈值。
输出：一个最终泛化的数据立方体。
方法：
⑴ 始化：
① 根据用户的学习任务，确定每一维对应的属性，并从初始关系数据集中收集相关的数据。
② for 每一维Ai do
begin
if Ai是数值型 and Ai没有概念层次 then 自动生成概念层次（算法2.1）
else 动态调整概念层次以适应当前学习任务；
end;
⑵ 造Basecube：
① 对于每一维的属性计算其在数据库中对应的不同值的个数，如果是数值型则计算数值间的最小间隔，根据不同值的个数或最小间隔确定每一维的最初泛化层次。
② 按最初泛化层次确定每维的维成员，并进行COUNT，SUM等聚合运算。用文[26]中算法构造基本立方体。
⑶ 确定每维的泛化层次。
① 根据每一维的泛化阈值，进行基本泛化（算法2.5）找到最终理想的层次Li。
② 找出每一维Ai的映射<v,v’>，其中v是维成员值，v’是v在泛化层上对应的概念值。
⑷ 构造Primecube。
① 将Basecube的维成员v替换成v’;
② 对Basecube进行数据立方体操作，构造Primecube。
本算法中，第一步的时间复杂度主要依赖于特定数据库的操作和提取或调整概念层次的算法的效率。第二步的主要操作在于立方体的构造上，复杂度为 。第三步和第四步都只对基本立方体进行一次扫描，加上计算量，复杂度也为 。所以本算法中二到四步总的时间复杂度应为 。
下面以一个例子来进一步描述该算法。
例1：从网上下了一个数据库CITYDATA，该数据库记录了美国地区城市的情况。其中有三个表，如下：
表1 CityLocation 记录城市所在地
表2 LaborIncome 记录城市人员的收入
表3 记录犯罪率与教育程度
我们有一个初始概念层次US_LOCATION：
{USA} {ANY}
{North_East,North_Central,South,West} {USA}
{New_England,Middle_Atlantic} {North_East}
{Mountain,Pacific_East, Pacific_West} {West}
…
现在我们要对数据库进行如下任务的发现：
CLASSIFY CITYDATA
ACCORDING TO UNEMPLOYMENT_RATE
IN RELEVANCE TO US_LOCATION，FAMILY_INCOME，POVERTY_PCT，
CRIME_RATE，BACHELOR_PCT
FROM LABORINCOME，CRIMEEDUCATION
注意到该发现任务中的维US_LOCATION对应着几个有层次关系的数据库属性：area-name→county→state→region→big region→country，这些属性在概念层次Us location中都对应着相应的层次。每一维的阈值为5。
根据算法，我们首先作初始化，对family income，poverty pct，crime_rate，bachelor_pct由于它们是数值型的属性，所以概念层次可以自动提取出来，下面便是自动提取出来的概念层次：
运行算法二、三、四步，得到六维的基本立方体和泛化立方体，为方便起见本文给出其中三维的立方体图。
最后的泛化结果放在了表4。注意到cityid的属性已被移去。
表4 最后的泛化结果
4 结束语
数据泛化在线分类研究中占有重要地位，它是在线分类规则挖掘算法的基础。在线分类任务的一个重要特征就是数据量庞大，且数据中含有一定量的异常信息，这样的数据是不适合直接分类的。通过数据泛化，可以将数据整理、清洁，为分类提供较好的数据环境。另外数据泛化采用了概念层次技术，可以发现高层的分类规则，从而使分类结果更易理解。
本文结合基本的面向属性归纳技术，提出了一种数据立方体的数据泛化算法，给在线分类提供了较好的数据预处理技术。
参考文献
[1] Han J, Fu Y. Exploration of the power of attribute-oriented induction in data mining. In: Fayyad U M et al eds. Advances in Knowledge Discover and Data Mining. Cambridge: AAAI/MIT Press, 1996. 399～421
[2] J. Han, Y. Cai, and N. Cercone. Knowledge discovery in databases: An attribute_Oriented approach. In Proc. 18th Int. Conf. Very Large Data Bases, pages 547--559, Vancouver, Canada, August 1992.
[3] Cheung D W, Fu A W C, Han J. Knowledge discovery in databases: a rule based attribute oriented approach. In: Zbigniew R ed. Methodologies for Intelligent systems: 8th International Symposium. Berlin: Springer-Verlag, 1994. 164～173
[4] Han, J., Chiang, J., Chee, S., Chen, J., Chen, Q., Cheng, S., Gong, W., Kamber, M., Liu, G., Koperski, K., Lu, Y., Stefanovic, N., Winstone, L., Xia, B., Zaiane, O. R., Zhang, S. & Zhu, H. (1997), DBMiner: A system for data mining in relational databases and data warehouses, in `Proc. CASCON'97: Meeting of Minds', Toronto, Canada, pp. 249--260.
作者简介：
黄建国(1974年10月-- ) ，男，安徽省合肥市人，合肥幼儿师范学校讲师，中国科技大学计算机应用工程硕士。本回答被提问者采纳