第4期 温云霞，等：横向拆分形势背景下的快速规则提取方法 ·527· 种层次关系有利于规则提取[6-10。在概念格的规则 例化关系，可作为数据分析与知识获取的一种有效 提取方面学者们进行了一定的研究，王志海等[6-刃 工具。形式背景1上对应的概念格如图1。 提出了概念格上规则提取的一般算法和渐近式算法 表1形式背景 并研究了概念格与关联规则发现。针对不同的形式 Table 1 Formal context 背景有不同的规则提取方法，如李金海等[8]提出的 AU a b c d e f g h i 在决策形式背景上的规则提取。还有一些提取规则 1110000100 的改进方法，如梁吉业等)提出的基于概念格的规 2110000110 则产生集挖掘算法等。近来对概念格的研究也主要 3111 00011 0 是围绕概念格的约简、缩小概念格的构造和规则提 41010001 取的复杂度[-]。但上述规则提取方法，一方面大 5110101000 都是针对一个形式背景，且得到的规则集数量较多、 规模较大。而用户有时可能只需要一部分感兴趣的 (12345,a) 规则信息，而从规模较大的规则集中找出这些感兴 (1235.ab) (1234,g） 趣的规则信息也是一个难题。另一方面规则形式大 (123,abg (234,ag 都是文献[6]和文献[10]提出的规则形式，这种规 则结构不便于两个规则集之间的合并研究。 (23.abgh) (34.acgh) 针对上述问题，本文提出一种伪规则的概念，给 (3.abcgh) (4.acgh0） 出渐近式获取伪规则的方法。同时说明了通过伪规 (5abdf) 则集，用户可以得到原概念格上的蕴含规则。伪规 则集的规模相对较小，其结构适于两个规则集的合 (o.abcdefghi) 并。用户可以根据自己的兴趣有选择地从伪规则集 1 L(U,(a,b,c,dffg,h,i,) 合中产生出所需的蕴含规则。在伪规则集的基础 Fig.1 L(U,a,b,c,df,g,h,i],I) 上，提出了将两个伪规则集进行合并的方法，通过此 1.2规则提取 方法用户可以直接利用伪规则集得到范围更大的规 下面简要介绍由文献[6]提出的规则提取方法 则集。最后通过实验验证了该方法的有效性。 的主要依据定理，该方法的基本思想是依据其双亲 1基本定义 节点即直接泛化的个数及形式来对格中每个节点生 成其无冗余的所有规则。关于此方法的详细描述可 1.1概念格 参考文献[6]。 在形式概念分析】中，形式背景用一个三元组 定理1[6]如果格中节点H=(X1,Y)只有一 K=(U,A,I)表示，如表1所示，其中U是对象集 个双亲节点M=(X2,Y2),则H所产生的规则前件 合，A是属性集合，I是U和A之间定义的一个二元 只能为单个描述符，且Hp∈{Y,-Y2},都存在一 关系。对于Hx∈U,Hy∈A,若x具有属性y,那 条无冗余规则p一Y,-P。 么x与y之间具有关系1，记为x山。关系I与一个 定理26]如果格中节点H=(X1,Y)具有d 偏序集合对应，并且这偏序集合产生一种格结构如 个双亲节点M(X2,Y2),M2(X3,Y),…,M(X, 图1所示。这种由I诱导的格L就称为一个概念 Y),则对于任意一个描述符p∈{Y,-(Y2UY3U 格。格中的每个节点是一个序偶，记为(X,),称 …UY)},都存在一条规则p→Y-p。 X是概念(X,)的外延，Y是概念(X,Y)的内涵。 定理36]若果格中节点H=(X1,Y)具有两 两者之间满足如下两个映射函数∫和g: 个双亲节点M(X2,Y2)和M2(X,Y),则对于每个 fx)={y∈A|Hx∈X,xy} 元素P1∈{Y2-Y2∩Y}和Hp2∈{Y,-Y2∩ g(y)={x∈U1Hy∈Y,xly} 格中所有概念的集合用L(K)表示。给定格中 Y3},都存在一条规则P1P2→Y-PP2。 注：只有当‖X‖>k时，才可能有前件至多 两个概念C,=(X1,Y),C2=(X2,Y2),满足X,C 为k个描述符的规则，并且规则前件的描述符个数 X2,则称(X,Y)是(X2,Y2)的子概念，记为 至多为其双亲节点的数目。除了前件为单个描述符 (X1,Y)≤(X2,Y2)。根据此偏序关系可以生成 的规则之外，其他规则的形式与数目仅仅依赖于其 Hasse图，揭示了概念的内涵和外延之间的范化和 双亲节点。种层次关系有利于规则提取［６－１０］ 。 在概念格的规则 提取方面学者们进行了一定的研究，王志海等［６－７］ 提出了概念格上规则提取的一般算法和渐近式算法 并研究了概念格与关联规则发现。 针对不同的形式 背景有不同的规则提取方法，如李金海等［８］ 提出的 在决策形式背景上的规则提取。 还有一些提取规则 的改进方法，如梁吉业等［９］ 提出的基于概念格的规 则产生集挖掘算法等。 近来对概念格的研究也主要 是围绕概念格的约简、缩小概念格的构造和规则提 取的复杂度［１１－２３］ 。 但上述规则提取方法，一方面大 都是针对一个形式背景，且得到的规则集数量较多、 规模较大。 而用户有时可能只需要一部分感兴趣的 规则信息，而从规模较大的规则集中找出这些感兴 趣的规则信息也是一个难题。 另一方面规则形式大 都是文献［６］和文献［１０］提出的规则形式，这种规 则结构不便于两个规则集之间的合并研究。 针对上述问题，本文提出一种伪规则的概念，给 出渐近式获取伪规则的方法。 同时说明了通过伪规 则集，用户可以得到原概念格上的蕴含规则。 伪规 则集的规模相对较小，其结构适于两个规则集的合 并。 用户可以根据自己的兴趣有选择地从伪规则集 合中产生出所需的蕴含规则。 在伪规则集的基础 上，提出了将两个伪规则集进行合并的方法，通过此 方法用户可以直接利用伪规则集得到范围更大的规 则集。 最后通过实验验证了该方法的有效性。 １ 基本定义 １．１ 概念格 在形式概念分析［１］ 中，形式背景用一个三元组 Ｋ ＝ （Ｕ，Ａ，Ｉ） 表示，如表 １ 所示，其中 Ｕ 是对象集 合， Ａ 是属性集合， Ｉ 是 Ｕ 和 Ａ 之间定义的一个二元 关系。 对于 ∀ｘ ∈ Ｕ ， ∀ｙ ∈ Ａ ，若 ｘ 具有属性 ｙ ，那 么 ｘ 与 ｙ 之间具有关系 Ｉ ，记为 ｘＩｙ 。 关系 Ｉ 与一个 偏序集合对应，并且这偏序集合产生一种格结构如 图 １ 所示。 这种由 Ｉ 诱导的格 Ｌ 就称为一个概念 格。 格中的每个节点是一个序偶，记为 (Ｘ，Ｙ) ，称 Ｘ 是概念 (Ｘ，Ｙ) 的外延， Ｙ 是概念 (Ｘ，Ｙ) 的内涵。 两者之间满足如下两个映射函数 ｆ 和 ｇ ： ｆ(ｘ) ＝ {ｙ ∈ Ａ ｜ ∀ｘ ∈ Ｘ，ｘＩｙ} ｇ（ｙ） ＝ ｛ｘ ∈ Ｕ ｜ ∀ｙ ∈ Ｙ，ｘＩｙ｝ 格中所有概念的集合用 Ｌ(Ｋ) 表示。 给定格中 两个概念 Ｃ１ ＝ Ｘ１ ，Ｙ１ ( ) ， Ｃ２ ＝ Ｘ２ ，Ｙ２ ( ) ，满足 Ｘ１ ⊆ Ｘ２ ， 则 称 Ｘ１ ，Ｙ１ ( ) 是 Ｘ２ ，Ｙ２ ( ) 的 子 概 念， 记 为 Ｘ１ ，Ｙ１ ( ) ≤ Ｘ２ ，Ｙ２ ( ) 。 根据此偏序关系可以生成 Ｈａｓｓｅ 图，揭示了概念的内涵和外延之间的范化和 例化关系，可作为数据分析与知识获取的一种有效 工具。 形式背景 １ 上对应的概念格如图 １。 表 １ 形式背景 Ｔａｂｌｅ １ Ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ＡＵ ａ ｂ ｃ ｄ ｅ ｆ ｇ ｈ ｉ １ １ １ ０ ０ ０ ０ １ ０ ０ ２ １ １ ０ ０ ０ ０ １ １ ０ ３ １ １ １ ０ ０ ０ １ １ ０ ４ １ ０ １ ０ ０ ０ １ １ １ ５ １ １ ０ １ ０ １ ０ ０ ０ 图 １ Ｌ（Ｕ，｛ａ，ｂ，ｃ，ｄ，ｆ，ｇ，ｈ，ｉ｝，Ｉ） Ｆｉｇ．１ Ｌ（Ｕ，｛ａ，ｂ，ｃ，ｄ，ｆ，ｇ，ｈ，ｉ｝，Ｉ） １．２ 规则提取 下面简要介绍由文献［６］提出的规则提取方法 的主要依据定理，该方法的基本思想是依据其双亲 节点即直接泛化的个数及形式来对格中每个节点生 成其无冗余的所有规则。 关于此方法的详细描述可 参考文献［６］。 定理 １ ［ ６ ］ 如果格中节点 Ｈ ＝ （Ｘ１ ，Ｙ１ ） 只有一 个双亲节点 Ｍ ＝ （Ｘ２ ，Ｙ２ ） ，则 Ｈ 所产生的规则前件 只能为单个描述符，且 ∀ｐ ∈ ｛Ｙ１ － Ｙ２ ｝ ，都存在一 条无冗余规则 ｐ → Ｙ１ － ｐ 。 定理 ２ ［ ６ ］ 如果格中节点 Ｈ ＝ （Ｘ１ ，Ｙ１ ） 具有 ｄ 个双亲节点 Ｍ１（Ｘ２ ，Ｙ２ ） ， Ｍ２（Ｘ３ ，Ｙ３ ） ，…， Ｍｄ（Ｘｄ ， Ｙｄ ） ，则对于任意一个描述符 ｐ ∈ ｛Ｙ１ － （Ｙ２ ∪ Ｙ３ ∪ … ∪ Ｙｄ ）｝ ，都存在一条规则 ｐ → Ｙ１ － ｐ 。 定理 ３ ［ ６ ］ 若果格中节点 Ｈ ＝ （Ｘ１ ，Ｙ１ ） 具有两 个双亲节点 Ｍ１（Ｘ２ ，Ｙ２ ） 和 Ｍ２（Ｘ３ ，Ｙ３ ） ，则对于每个 元素 ∀ｐ１ ∈ ｛Ｙ２ － Ｙ２ ∩ Ｙ３ ｝ 和 ∀ｐ２ ∈ ｛Ｙ３ － Ｙ２ ∩ Ｙ３ ｝ ，都存在一条规则 ｐ１ ｐ２ → Ｙ１ － ｐ１ ｐ２ 。 注：只有当 ‖Ｘ′‖ ＞ ｋ 时，才可能有前件至多 为 ｋ 个描述符的规则，并且规则前件的描述符个数 至多为其双亲节点的数目。 除了前件为单个描述符 的规则之外，其他规则的形式与数目仅仅依赖于其 双亲节点。 第 ４ 期 温云霞，等：横向拆分形势背景下的快速规则提取方法 ·５２７·