第３４卷 第２Ｏ期 计算机工程 ２００８年１Ｏ月 Ｖｏ１．３４ Ｎｏ．２ｏ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ Ｏｃｔｏｂｅｒ ２００８ ・软件技术与数据库・ 文章编号；ｌ００ ＿３４２８（２００８）２ｏ ｌｏ４矗＿＿０３ 文献标识码：Ａ 中圈分类号；ＴＰ３１１ 基于数据立方体的属性核计算方法 刘亚渡 ，刘大有 ，高滢 ，齐红 （１．吉林大学计算机科学与技术学院，长春１３００１２；２．吉林大学符号计算与知识工程教育部重点实验室，长春１３００１２） 擅要：商业智能系统应用联机分析处理技术将数据组织为数据立方体。该文建立了数据立方体中非空单元与决策表中等价类的一一 映射关系。通过复用数据立方体中的聚合结果，提出一种基于数据立方体计算相容决策表属性核的方法，并证明了该方法的正确性。利用 ＵＣＩ数据集进行实验，结果表明在大数据量下该方法具有较好的时间效率。 关健诃：数据立方体；联机分析处理；粗集；属性核 Ｄａｔａ Ｃｕｂｅ—ｂａｓｅｄ Ｆｅａｔｕｒｅ Ｃｏｒｅ Ｃｏｍｐｕｔｉｎｇ Ａｐｐｒｏａｃｈ ＬＩＵ Ｙａ－ｂｏ ，ＬＩＵ Ｄａ．ｙｏｕ ，２ＧＡＯ Ｙｉｎｇ ０，，ＱＩ Ｈｏｎｇ ０ （１．Ｄｅｐａｒｔｍｅｎｔ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｊｉｌｉｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ １３００１２； ２．Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｓｙｍｂｏｌｉｃ Ｃｏｍｐｕｔａｔｉｏｎ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｍｉｎｉｓｔｒｙ ｏｆ Ｅｄｕｃａｔｉｏｎ，Ｊｉｌｉｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ １３００１２） ［Ａｂｓｔｒａｃｔ］ＩｎＢＩ ｓｙｓｔｅｍ，ｄａｔａ ａｌｅｆｏｒｍｅｄ ａｓ ａｍｕｌｉｔｄｉｍｅｎｓｉｏｎａｌＯＬＡＰｃｕｂｅ．Ｔｈｉｓ ｐａｐｅｒｆｏｃｕｓｅｓｏｎ ｃｏｍｐｕｔｉｎｇｔｈｅｆｅａｔｕｒｅ ｃｏｒｅｏｆｔｈｅｄｅｃｉｓｉｏｎｔａｂｌｅ ｂｙ ｒｅｕｓｉｎｇ ｔｈｅ ａｇｇｒｅｇａｔｉｏｎ ｉｎ ｃｕｂｅ．Ａｆｔｅｒ ｈｔｅ ｒｅｌａｔｉｏｎ ｉｓ ｅｓｔａｂｌｉｓｈｅｄ ｂｅｔｗｅｅｎ ｎｏｎｅｍｐｔｙ ｃｅｌｌｓ ｉｎ ａ ｄａｔａ ｃｕｂｅ ａｎｄ ｅｑｕａｌ ｃｌａｓｓｅｓ ｆｒｏｍ ａ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ，ａ ｎｅｗ ｃｕｂｅ—ｂａｓｅｄ ａｐｐｒｏａｃｈ ｏｆ ｃｏｍｐｕｔｉｎｇ ｔｈｅ ｆｅａｔｕｒｅ ｃｏｒｅ ｏｆ ａ ｃｏｎｓｉｓｔｅｎｔ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ ｉｓ ｐｕｔ ｆｏｒｗａｒｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ａｎｄ ｔｈｅ ｃｏｒｒｅｃｔｎｅｓｓ ｏｆ ｈｔｅ ｎｅｗ ａｐｐｒｏａｃｈ ｉｓ ｐｒｏｖｅｄ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｗｉｈｔ ＵＣＩ ｄａｔａ ｓｅｔ ｓｈｏｗ ｈｔａｔ ｈｔｅ ｎｅｗ ａｐｐｒｏａｃｈ ｈａｓ ｈｉｇｈ ｔｉｍｅ ｐｅｒｆｏｒｍａｎｃｅ． ［Ｋｅｙ ｗｏｒｄｓ］ｄａｔａ ｃｕｂｅ；ｏｎｌｉｎｅ ａｎａｌｙｓｉｓ ｐｒｏｃｅｓｓｉｎｇ；ｒｏｕｇｈ ｓｅｔ；ｆｅａｔｕｒｅ ｃｏｒｅ 基于粗集的属性约简算法通常建立在属性核基础上…， 员，可确定Ｃｕｂｅ（Ｓ）中唯一单元，设为Ｐ，记ｐｅ Ｃｕｂｅ（Ｓ）表示 多数求属性核的方法基于区分矩阵 。Ｊ。根据区分矩阵确定属 Ｐ是Ｃｕｂｅ（Ｓ）中单元。对Ｃｕｂｅ（Ｓ）中单元Ｐ给出以下描述方法： 性核的方法易于理解，但计算量大。文献【３】给出了不需建立 （１）ｋ／ａｆ∈Ａ（１≤ ≤ＩＡＩ），令ａｉ（ｐ）表示Ｐ的维ａｆ成员，记ｐ＝ 区分矩阵的属性核计算方法，但对数据量较大的决策表，仍 【ａ】 ），ａ２ ），…， 川 ），Ｃｏｕｎｔ￣）］，Ｃｏｕｎｔ（ｐ）是Ｐ的度量值。 无法避免计算量大的问题。商业智能系统运用数据仓库、联 （２）Ｄｉｍｓ ）＝｛口 ）￣ａｎｙ，ａＥ Ｃ Ｕ Ｄ｝ 机分析处理（ＯＬＡＰ）和数据挖掘等技术来处理和分析数据。 （３）Ｄａｔａ ）＝｛ｘｌＶａ￣Ｄｉｍｓ ），ｄ ）＝ａ ），ＸＥ Ｕｌ ＯＬＡＰ技术将数据组织为数据立方体（ｄａｔａ ｃｕｂｅ），用维和 例１由表ｌ决策表Ｓ生成４维数据立方体Ｃｕｂｅ（Ｓ），包 度量来描述数据。在商业智能系统中进行数据挖掘时，若能 含单元ｐ＝［ｈｉｇｈ，ａｎｙ，ｙｅｓ，ａｎｙ，２】，Ｄｉｍｓ（ｐ）＝ｆＣ１，Ｃ３｝，Ｄａｔａ ）＝｛ ｌ， 复用已有数据立方体中的聚合结果及下钻等ＯＬＡＰ操作，可 Ｘ２｝，Ｃｏｕｎｔ￣）＝ｌＤａｔａ（ ）Ｉ＝２。 提高挖掘效率Ｈ】，本文基于数据立方体及ＯＬＡＰ操作计算相 表１决策表Ｓ 容决策表属性核。 ｌ相关概念和理论 定义１决策表 ＝（ ，Ａ，ｖＪ）。其中，Ｕ为论域；Ａ＝ＣＵ Ｄ且ＣｆｌＤ＝ ，Ｃ是条件属性集，Ｄ是决策属性集； ， 是ａ的属性值集；厂：ＵｘＡ 是函数，它指定Ｕ中每个对 象在不同属性上的取值。若Ｕ中存在 和Ｙ使得ｆ（ｘ，ｃ）－厂（），，Ｃ）， 但ｆ（ｘ，Ｄ）≠，（），，Ｄ），则称Ｓ为不相容决策表，否则为相容决策表。 ２．１等价类与非空单元的映射关系 定义２决策表 ＝（ｕ，ＣＵ Ｄ，ｖｏ９，称Ｃ中所有必要属性的 为证明决策表中等价类与数据立方体中非空单元问的一 一集合为Ｃ的属性核，记为Ｃｏｒｅ（Ｃ）。 对应关系，给出定义４、定义５、定义６及引理１。定义７ 定义３相容决策表 ＝（ ，ＣＵＤ， ｔ厂）。条件属性ｃ∈Ｃ是Ｓ 给出了具体的对应方法。 的关键属性，当且仅当 （ｕ，Ｃ一｛Ｃ｝ｕ Ｄ， ）不相容。 基金项目：国家自然科学基金资助重大项目（６０４９６３２１）；国家自然科 定理１若决策表 ＝（ｕ，Ｃｕ Ｄ，ｖＪ）相容，则Ｓ的所有关键 学基金资助项目（６０３７３０９８，６０５７３０７３）；国家“８６３”计划基金资助项 属性构成的集合为Ｃ的属性核。 目（２００３ＡＡ１１８０２０） ２基于数据立方体计算属性核的方法 作者倚介：刘亚波（１９７５－－），女，博士后，主研方向：粗集，数据挖 决策表 ＝（ ，Ａ， ，），Ａ＝ＣｕＤ，将Ｕ作为事实表， 作为 掘，数据仓库；刘大有，教授、博士生导师；高滢，硕士；齐红， 数据立方体的维集，维ｎ ∈Ａ）的成员集为 Ｕ｛ａｎｙ｝，可构 博士 造ｌ Ａｌ维数据立方体，记为Ｃｕｂｅ（Ｓ）。若Ａ中每维都取一个成 收藕日期：２００８—０６—１２ Ｅ－ｍａｉｌ：ｙａｂｏ＠ｊｌｕ．ｅｄｕ，ｃｎ ——４６—— 定义４决策表 ＝（ｕ，Ｃ Ｕ Ｄ，ｙ ，Ｐｌ，ｐ２Ｅ Ｃｕｂｅ（Ｓ），若Ｖａｅ 故Ｕ／Ｒ＝｛Ｄａｔａ（ｑ）ＩＤｉｍｓ（ｑ）＝Ｒ，ｑｅ Ｃｅｌｌｓ（Ｓ）｝。证毕。 Ｃ ｕ Ｄ，ａ（ｐ１）＝口（ｐ２），则ｐｌ＝ ２，否则Ｐｌ ２。 根据推论１，若决策表 ＝（ｕ，ＣＵ｛ｄｌ，ｙ ，则 定义５决策表 ＝（ｕ，ＣｕＤ，Ｖｄ），定义 Ｕ／Ｃ＝｛Ｄａｔａ（ｑ）ｌＤｉｍｓ（ｑ）＝Ｃ，ｑｅ Ｃｅｌｌｓ（Ｓ）｝ Ｐａｉｒｓ（Ｓ）＝｛＜ ，Ｅ＞ＩＥｅ Ｕ／Ｒ，Ｒｃ＿Ｃ ｕ Ｄ｝ Ｕ／｛ｄ｝＝｛Ｄａｔａ（ｑ）ｌＤｉｍｓ（ｑ）＝｛ｄ｝，目∈Ｃｅｌｌｓ（Ｓ）｝ 若＜Ｒ１，Ｅｌ＞，＜尺２，Ｅ２＞∈Ｐａｉｒｓ（Ｓ），且ＲＩ＝Ｒ２，Ｅｌ＝Ｅ２，则＜ １， ｌ＞＝ ２．２基于数据立方体的属性核计算算法 ＜Ｒ２，Ｅ２＞，否则＜ＲＩ，ＥＩ＞￣＜Ｒ２，Ｅ２＞． 以下设决策表 ＝（ ，Ｃｕ｛ｄ｝， ，且 是相容决策表。根 定义６决策表 ＝（ ，Ｃ ｕ Ｄ， ，若ｐ∈Ｃｕｂｅ（Ｓ）且Ｃｏｕｎｔ 据决策表中等价类与Ｃｕｂｅ（Ｓ）中非空单元的一一对应关系，通 （ ）＞０，则称ｐ为非空单元，定义非空单元集Ｃｅｌｌｓ（Ｓ）＝｛ｑｌＣｏｕｎｔ 过在部分非空单元上沿维ｄ下钻，计算出关键属性。 （口）＞０，ｑ∈Ｃｕｂｅ（Ｓ））。 定义８决策表 ＝（ ，Ｃｕ｛ｄ Ｊ，ＶＪ），设Ｐ，ｑ∈Ｃｅｌｌｓ（Ｓ），若 引理１决策表ｓ＝（ ，ＣｕＤ， ，对ＶｐＥＣｅｌｌｓ（Ｓ）都有＜Ｄｉｍｓ Ｖｃｅ Ｃ，ｃ（ｑ）＝ｃ ）且ｄ（ｐ）＝ａｎｙ，ｄ（ｑ）￣ａｎｙ，则称ｑ是Ｐ沿维ｄ的 ），Ｄａｔａ ）＞∈Ｐａｉｒｓ（Ｓ）成立。 下钻单元。称Ｐ的所有沿维ｄ的下钻单元构成的集合为Ｐ沿 证明：任取Ｐ∈Ｃｅｌｌｓ（Ｓ），则Ｄｉｍｓ ） ｃｕＤ是Ｕ上等价 维ｄ的下钻集，记为ｐ ｄ。 关系，Ｄａｔａ ）是Ｕ／Ｄｉｍｓ ）中等价类。由定义５，＜Ｄｉｍｓ ）， 例２取例１ Ｃｕｂｅ（Ｓ）中单元ｐ＝［ｈｉｇｈ，ｇｏｏｄ，ａｎｙ，ａｎｙ，１］， Ｄａｔａ ）＞∈Ｐａｉｒｓ（Ｓ）。证毕。 ｑｌ＝［ｈｉｇｈ，ｇｏｏｄ，ａｎｙ，ｌｏｓｓ，０】，ｑ２＝［ｈｉｇｈ，ｇｏｏｄ，ａｎｙ，ｐｒｏｆｉｔ，１】。 定义７决策表 ＝（ ，Ｃ ｕ Ｄ，ｙ ，＜ ，Ｅ＞ｅ Ｐａｉｒｓ（Ｓ），ｐ∈ 因Ｃｏｕｎｔ（ｑ１）＝Ｏ，Ｃｏｕｎｔ（ｑ２）＝１，故ｐ ｛ｑ２｝。 Ｃｅｌｌｓ（Ｓ），若Ｄｉｍｓ ） ，Ｄａｔａ ）＝Ｅ，则ａ（Ｒ，Ｅ） 。 定理３决策表 ＝（ｕ，ＣＵ ｆ ｝， ｔ厂）不相容，当且仅当存在 引理２决策表 ＝（ ，Ｃ ｕ Ｄ， ，Ｖ＜Ｒ，Ｅ＞ｅ Ｐａｉｒｓ（Ｓ），存在 单元ｐ∈Ｃｅｌｌｓ（Ｓ），且Ｐ满足Ｄｉｍｓ ）＝Ｃ ＩｐＳｄｌ＞ｌ。 唯一单元Ｐ∈Ｃｅｌｌｓ（Ｓ）满足ａ（Ｒ， ） 。 证明：Ｓ不相容，当且仅当存在 ，ｙｅ Ｕ，满足Ｖｃｅ Ｃ，ｃ ）＝ 证明： ｃ ０，），ｄ ）≠ｄ（ｙ）。当且仅当ｘ，）Ｉ∈【ｘｌｃ， ∈【Ｘ］ｃｕ㈨，ｙｅ［），］ｃｕＩｄ｝且 （１）存在性。取 ，Ｅ＞ｅＰａｉｒｓ（Ｓ），设 ＝ｆ口ｌ，ａ２，…，ａ ｝ＧＣＵ Ｉｘ］ｃｕ ≠ ｃｕ 。根据定理２，有 Ｄ，Ｅ＝｛ｘｌａｌ（ ）＝ｖ１，ａ２（ｘ）＝ｖ２，…，ａｓ ）＝ｖ ，ｘ∈Ｕ｝，若ａ 维取ｖ 成 当且仅当存在Ｐ，ｑｌ，ｑ２ＥＣｅｌｌｓ（Ｓ），满足 员 （１≤ ≤ｓ），其他维取ａｎｙ成员，可确定Ｃｕｂｅ（Ｓ）中唯一单 （Ｃ，ｉｘ】ｃ）＝ （３） 元，设为Ｐ，易见ＤａｔａＣｏ）＝Ｅ，Ｄｉｍｓ（ｐ）＝Ｒ，因Ｃｏｕｎｔ（ｐ）＝ＩＥＩ＞０， 口（Ｃ ｕ｛ｄ｝，［ｘｌｃｏ｛ｄ｝）＝鼋ｌ （４） 故Ｐ∈Ｃｅｌｌｓ（Ｓ），则 （ ，Ｅ）＝ 。 口（Ｃ Ｕ｛ｄ｝，［ＹＪｃｕ ｆｄ１）＝ｑ２ （５） （２）唯一性。假设存在Ｐ’ ’印）∈Ｃｅｌｌｓ（Ｓ）满足ａ（Ｒ，Ｅ） ’。 由式（３）有ｃ ）＝ｃ（ ），ｄ（ｐ）＝ａｎｙ； 由ａ（Ｒ，Ｅ）－ｐ’，可得 由式（４）有ｃ（ｑ１）＝ｃ（ ），ｄ（ｑ１）＝ｄ（ ）≠口ｎｙ； Ｄｉｍｓ ’）＝Ｄｉｍｓ（ｐ）＝Ｒ，Ｄａｔａ ’）＝Ｄａｔａ ）－Ｅ （１）、 由式（５）有ｃ（ｑ２）＝Ｃ（ｙ），ｄ（ｑ２）＝ｄ（ｙ）＊ａｎｙ。 由Ｐ’印，可得 当且仅当对Ｖｃｅ Ｃ，Ｃ（ｑ１）＝ｃ（ｑ２）＝ｃ（ｐ），且ｄ（ｐ）＝ａｎｙ， ｑ１）≠ 或Ｄａｔａ ’）＝Ｄａｔａ ）＝ ，或Ｄａｔａ ’）￣Ｄａｔａ ） （２） ａｎｙ，ｄ（ｑ２）ｃ－ａｎｙ，ｄ（ｑ１）＃ｄ（ｑ２），故 显然式（１）、式（２）矛盾，故假设不成立。引理２证毕。 当且仅当ｑｌ∈ｐ ，ｑ２ｅｐＳｄ，且ｑｌ≠鼋２，当且仅￣ｌｐｉｄｌ＞ｌ。 弓ｊ理２表明可以把Ｐａｉｒｓ（Ｓ）中任意元素映射到Ｃｅｌｌｓ（Ｓ）中 证毕。 唯一单元。下面证明该映射是一一映射。 定理４相容决策表 ＝（ ，ＣＵ｛ｄ｝，ＶＪ），条件属性ｃＥ Ｃ是 定理２ 决策表 ：（ ，Ｃ Ｕ Ｄ， ｌ／），ｔ７是从Ｐａｉｒｓ（Ｓ）到Ｃｅｌｌｓ（Ｓ） 的关键属性，当且仅当存在至少一个单元ｐｅＣｅｌｌｓ（Ｓ）， 的一一映射。 Ｄｉｍｓ ）＝Ｃ一｛ｃ｝，Ｉｐ，Ｌｄｌ＞ｌ。 证明： 证明：令决策表 ’＝（ ，Ｃ一｛ｃ Ｊ ｕ｛ｄ｝，ＶＪ），若ｃ∈Ｃ是Ｓ的 （１）任取＜ ｌ，Ｅｌ＞，＜Ｒｅ，Ｅ２＞ＥＰａｉｒｓ（Ｓ），＜ １，Ｅｌ＞≠＜Ｒ２，Ｅ２＞，往证 关键属性，当且仅当 ’不相容，根据定理３，当且仅当Ｃｅｌｌｓ（Ｓ’） （Ｒ１，Ｅ１）Ｖ：ａ（Ｒ２，Ｅ２），用反证法。 存在至少一个非空单元Ｐ’满足Ｄｉｍｓ（ｐ’）＝ｃ一｛ｃ１且Ｉｐ’．ｉ．ｄｌ＞ｌ，设 设ａ（Ｒｌ，Ｅ１）＝ｐ１，故Ｄｉｍｓ（ｐ１）＝ １，Ｄａｔａ １）＝￡１； ｑ’ｅｐＳｄ，当且仅当存在ｐｅ Ｃｅｌｌｓ（Ｓ），其中，Ｖ口∈Ｃ．｛ｃ｝Ｕ｛ｄ Ｊ， 设ａ（Ｒ２，Ｅ２） ２，故Ｄｉｍｓ ２）＝ ２，Ｄａｔａ ２）＝Ｅ２。 ａ（ｐ）＝口 ’），且ｃ（ｐ）＝ａｎｙ，Ｃｏｕｎｔ（ｐ）＝Ｃｏｕｎｔ￣’）＞０。 假设ａ（ＲＩ’Ｅ１）： （ ２，Ｅ２），则Ｐｌ ２。故Ｒｌ＝Ｒ２，Ｅｌ＝Ｅ２，＜Ｒｌ， 存在ｇ∈Ｃｅｌｌｓ（Ｓ），其中，Ｖｎ∈Ｃ－ｆｃ｝Ｕ｛ｄ｝，ａ（ｑ）＝口（ｑ’），且 Ｅ１＞＝＜ ２，Ｅ２＞，与已知＜Ｒ１，Ｅｌ＞≠＜ ２，Ｅ２＞矛盾。因此， Ｒｌ，Ｅ１）≠ ｃ（ｑ）＝ａｎｙ，Ｃｏｕｎｔ（ｑ）＝Ｃｏｕｎｔ（ｑ’）＞０。因Ｄｉｍｓ（ｐ’）＝Ｃ一｛ｃ｝，故Ｖａｅ Ｃ， ａ（Ｒ２，Ｅ２），口是单射。 ａ（ｐ）＝ｄ（ｑ），且ｄ（ｐ）＝ｄ（ｐ’）＝ａｎｙ， （日）＝ｄ（ｑ’）￣ａｎｙ，即ｑ￣ｐ＋ｄ。由 （２）Ｖｐｅ Ｃｅｌｌｓ（Ｓ），令Ｒ＝Ｄｉｍｓ ），Ｅ＝Ｄａｔａ（ｐ），由引理１， ｑ’的任意性，得当且仅当任意ｑ’∈ｐ’ ｄ，都存在单元ｑ∈ｐ ， ＜见Ｅ＞ｅＰａｉｒｓ（Ｓ）且 Ｒ，Ｅ） ，因此口是满射。 因Ｉｐ’￣ｄｌ＞ｌ，当且仅当Ｉｐ，Ｌｄｌ＝ｌ Ｐ’，Ｉ．ｄｌ＞１。证毕。 既是单射，也是满射，故 是一一映射，使决策表中 例３取例１中非空单元Ｐｌ＝［ａｎｙ，ｇｏｏｄ，ｙｅｓ，ａｎｙ，２】， 等价类与数据立方体中非空单元一一对应。证毕。 Ｄｉｍｓ（ｐ１）＝ｃ一｛Ｃ１｝，ｐｌ ｛ｑｌ，ｑ２）。其中，ｑｌ＝［ａｎｙ，ｇｏｏｄ，ｙｅｓ，ｐｒｏｉｆｔ， 推论１决策表 ＝（ｕ，ＣｕＤ， ，ＲＧＣＵＤ，则Ｕ／Ｒ＝ １】，ｑ２＝［ａｎｙ，ｇｏｏｄ，ｙｅｓ，ｌｏｓｓ，１】。故Ｉｐ１ ＞１，属性ｃｌ是关键属性。 ｛Ｄａｔａ（ｑ）ｌＤｉｍｓ（ｑ）＝Ｒ，ｑｅ Ｃｅｌｌｓ（Ｓ）｝。 取例１中非空单元ｐ２＝［ｈｉｇｈ，ａｎｙ，ｙｅｓ，ａｎｙ，２】，Ｄｉｍｓ（ｐ２）＝ 证明： Ｃ一｛ｃ２｝，ｐｚｉｄ＝｛ｑ３，ｑ４｝。其中，ｑ３＝【ｈｉｇｈ，ａｎｙ，ｙｅｓ，ｐ ｆ，１１，ｑ４＝ （１）设Ｅ∈Ｕ／Ｒ，则＜ ，Ｅ＞∈Ｐａｉｒｓ（Ｓ）。再设ｇ（Ｒ， ） ，故 【ｈｉｇｈ，ａｎｙ，ｙｅｓ，ｌｏｓｓ，１】。故Ｉｐ２．．Ｉｄｌ＞ｌ，属性ｃ２是关键属性。 Ｄｉｍｓ（ｐ）＝Ｒ，则ｐ∈｛ｑｌＤｉｍｓ（ｑ）＝Ｒ，ｑｅ Ｃｅｌｌｓ（Ｓ）｝，Ｅｅ｛Ｄａｔａ（ｑ）ｌ 因｛ｑｌＤｉｍｓ（ｑ）＝Ｃ一｛ｃ３｝，Ｃｏｕｎｔ（ｑ）＞ｌ｝中每一单元的下钻集 Ｄｉｍｓ（ｑ）＝Ｒ，ｑｅ Ｃｅｌｌｓ（Ｓ）｝。 大小均为１，故ｃ３不是关键属性。 （２）设ｐｅ｛ｑｌＤｉｍｓ（ｑ）＝Ｒ，ｑ∈Ｃｅｌｌｓ（Ｓ）｝， 则Ｄｉｍｓ ）＝ ， 例３的结论与其他方法得到的属性核一致。下面给出了 Ｄａｔａ（ｐ）∈Ｕ／Ｒ。 基于数据立方体的属性核求取算法Ｃｏｒｅ＊。 算法Ｃｏｒｅ （ｃ，ｄ，ＣＵＢＥ．ｃｏｒｅ） ，丰Ｃ＝（ｃｌ，ｃ２，…，Ｃ ），输出属性核ｃｏｒｅ＊／ Ｃ１［初始化］ ｃｏｒｅ＝｛） ｃ２［逐个判断每个属性是否为关键属性】 Ｆｏｒ ｅａｃｈ Ｃｌ∈ＣＤｏ Ｌｔ：ｆ ｓｅｔ ＝｛ｑ ＩＤｉｍｓ（ｑ）＝Ｃ一（ｃ ｝，Ｃｏｕｎｔ（ｑ）＞０｝ ／／对Ｐ∈ｓｅｔｉ，若Ｉｐ－１．ｄｌ＞１，则ｃ是关键属性 Ｆｏｒ ｅａｃｈ Ｐ∈ｓｅｔｉ Ｄｏ （Ｉｆ（Ｃｏｕｎｔ（ｐ）＞１）Ｔｈｅｎ Ｌ２：ｆ ｄｒｉｌｌｓｅｔ＝ｐ Ｊ，ｄ ＩｆＩ ｄｒｉｌｌｓｅｔ ｌ＞ｌ Ｔｈｅｎ ｛ｃｏｒｅ＝ｃｏｒｅｕ｛Ｃｉ｝，Ｂｒｅａｋ） 】 ｝ 】 ２．３算法分析 算法Ｃｏｒｅ＊的时间复杂度主要和扫描数据立方体的语句 Ｌ。和Ｌ２的执行次数有关。Ｌｌ共执行ｍ次。因度量为１的单 元其下钻单元只有一个，故算法Ｃｏｒｅ＊不计算度量为１的单 元的下钻集。若在计算ｓｅｔ 中第ｎｆ（１≤ｎｉ≤Ｉｓｅｔ 个度量大于１ 的单元的下钻集时，发现其下钻集大小大于１，即可判定Ｃ 为关键属性。故算法Ｃｏｒｅ＊扫描数据立方体次数为ｍ＋∑ ， ｉ＝ｌ 取决于实际计算了下钻集的单元数兰 ， ≤至 ≤∑ｍＩ ｓｅ Ｉ。 ｉ＝１ ｉ＝１ ｉ＝１ ３实验 笔者在ＵＣＩ数据集Ｍｕｓｈｒｏｏｍ数据上进行了测试，使用 ＳＱＬ Ｓｅｒｖｅｒ ２００５ Ａｎａｌｙｓｉｓ Ｓｅｒｖｉｃｅｓ生成数据立方体，通过 ＡＤＯＭＤ．ｎｅｔ和ＭＤＸ查询访问数据立方体。Ｍｕｓｈｒｏｏｍ共 ８ １２４条相容记录，分别选择了５个、７个和９个条件属性， 在不同数据量下对Ｃｏｒｅ＊和文献【４冲的算法（记为Ｃｏｒｅ）进行 了测试和比较。表２给出了运行时间比较的结果。 表２算法Ｃｏｒｅ＊和算法Ｃｏｒｅ妁运行时间比较 由表２可见，当有５个条件属性时，算法Ｃｏｒｅ 的时问 效率明显好于算法Ｃｏｒｅ。当有７个或９个条件属性时，在小 数据量情况下算法Ｃｏｒｅ＊ｌｇＪ时问效率不具有明显优势，但当 数据量超过４ ０００条或６ ０００条，且逐步增加时，算法Ｃｏｒｅ 的时间效率明显好于算法Ｃｏｒｅ。为验证算法Ｃｏｒｅ 在大数据 量下的性能，当数据增至８ １２４条后，分别从８ １２４条数据中 抽取４０００条和８ １２４条数据附加到原８ １２４条数据之后。当 数据从８ １２４条增至１２ １２４条和１６ ２４８条时，算法Ｃｏｒｅ＊的 时间效率基本不变，而算法Ｃｏｒｅ运行时间大幅度增加。 表３从分析芝 和∑ｌ ｓｅｔｉ Ｉ变化的角度，给出了算法 ｌ≈ｌ ｉ＝１ Ｃｏｒｅ＊运行时间的变化。 ｍ ｍ 表３∑ 和∑Ｉ ８ Ｉ的变化 ｉ＝１ ｉ＝１ 由表３可见，当数据从２ ０００条增至８ １２４条时，∑Ｉ ｌ ｉ＝ｌ 和艺 都增加较快，因此运行时间增长。当数据从８ １２４条 ｉ＝１ 增至１２ １２４条和１６ ２４８条时，由于增加的是重复数据， Ｉ ｓｅｔ，ｉ＝１ Ｉ不再发生变化，虽然芝ｎ 仍在变大，但增加较慢，因 ｉ＝１ 此运行时间增加较慢，基本保持不变。 从表２和表３不难看出，算法Ｃｏｒｅ＊的时间效率受数据 量影响较小，受数据立方体的非空单元集Ｕｓｅｔ。和实际计算了 ｉ＝１ 下钻集的单元数影响较大。因此，算法Ｃｏｒｅ 适合计算大数 据量下的决策表属性核。 ４结束语 本文提出的属性核计算方法Ｃｏｒｅ 充分利用了数据立方 体中聚合后的度量信息，给出了一种新的粗集理论研究途径。 因此，基于数据立方体，研究海量数据下相容决策表的属性 约筒、不相容或不完备决策表的属性核及属性约简计算方法 是本文下一步的工作重点。 参考文献 ［１１ Ｐａｗｌａｋ Ｚ．Ｒｏｕｇｈ Ｓｅｔｓ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ，１９８２，１ｌ（５）：３４１—３５６． ［２】叶东毅，陈昭炯．一个新的差别矩阵及其求核算法［Ｊ１．电子学报 ２００２，３０（７）：１０８６—１０８８． 【３］赵军，王 国，吴中福，等．一种高效的属性核计算方法Ｉ Ｊ１． 小型微型计算机系统，２００３，２４（１ １）：１９５０—１９５３． ［４］高学东，王文贤，武森．基于数据立方体的关联规则的挖 掘方法［Ｊ】．计算机工程，２００３，２９（１４）：７４—７６．
