海量数据集上主观兴趣度的关联规则优化算法

摘要

一种海量数据集上主观兴趣度的关联规则优化算法，本发明使用复合模板同时优化分析，即分为总体印象知识模板(GI)、相对精确知识模板(RPC)，这种分类扩大了用户含义表达范围，有助于从不同侧重点对关联规则进行优化，此外，把限制与包含模板的作用转而体现在不同兴趣度上，细化兴趣度为四种类型，包括一致度、后件不可预知度、前件不可预知度、不可预知度，使得优化粒度非常清晰；优化结合了复合模板的兴趣度计算模型，使得兴趣度的计算能合理适应复合分析环境。

说明书

技术领域

本发明是一种有关海量数据集上主观兴趣度的关联规则优化算法，该方法能 够发现大量数据中项集之间有趣的关联或者相关联系，可以帮助许多商务决策的 制定，如分类设计、交叉购物和贱卖分析等，属于关联规则挖掘中的关联规则优 化算法领域。

背景技术

对海量数据进行关联挖掘导出的关联规则数量巨大，这给分析、决策人员的 判断带来了困难，而且仅基于支持度-置信度框架的传统关联规则挖掘算法并不 能指出用户真正感兴趣的规则，给用户对所导出规则的分析带来了不便，规则优 化则成为了提升规则质量、发现有价值规则的有效手段。

目前现有的规则优化算法主要从两个方面对关联规则进行优化：

1.客观关联规则优化：一般从规则的结构、集合性质、统计结果、离差模型 等入手进行分析，这类方法包括RuleCover算法、冗余删除算法。客观性优化方 法能有效删除多余、无效的规则。

2.主观关联规则优化：一般利用领域知识、模板、兴趣度等主观量度对规则 进行分析。Piatetsky-Shapiro首先提出了兴趣度问题。Hoschka和Klosgen首次提 出模板的概念。离差分析法被提出用来衡量真实结果与期望结果间的距离，而 Piatetsky-Shapiro和Matheus把离差与兴趣度相结合，分析了离差的兴趣度。 Klemettinen等人在中也提出了规则模板的概念，并使用包含模板和限制模板分 别过滤有趣规则和非有趣规则。

虽然客观优化方法删除多余规则的效果明显，但无法实现主观优化方法所带 来的优点。从用户需求分析，对主观思路进行研究有以下两点意义：①面对挖掘 出来的规则，用户唯一的目标就是去寻找那些特殊的、没有被发现的规则。若仅 给出一堆杂乱无序的规则，用户便需要花费较多的时间来分析和发现有价值的规 则。②当规则数量成千上万时，用户希望能快速切入主题、发现价值，而不是面 对规则无从下手。

同时，模板是主观兴趣度算法中使用到的一个重要的工具，是用户表达含义 的载体，但目前基于模板的优化方法一般仅涉及一个模板的分析。兴趣度是规则 有趣程度的客观度量，目前基于兴趣度的优化方法一般结合具体领域知识提出相 应的兴趣度计算模型，用来衡量规则的有趣程度。

然而，在一般的规则优化方案中，模板使用单一模板进行优化分析，用户含 义表达受限；模板类型种类少，部分论文提出限制模板、包含模板这两种模板类 型用于过滤与匹配规则。另一方面兴趣度，一般只涉及一种兴趣度类型，分析的 细化程度受限；兴趣度计算模型单一、杂乱，优化效果难以评判。

发明内容

本发明针对目前兴趣度优化算法存在的不足：兴趣度计算方法欠妥；用户含 义表达受限；领域知识、模板、兴趣度等主观量度未有机结合，本算法提出了一 种海量数据集上主观兴趣度的关联规则优化算法对上述不足进行了改进

本发明为解决上述技术问题所采用的技术方案是：

海量数据集上主观兴趣度的关联规则优化算法，其特征在于该优化算法包 括：

1-(a).数据获取步骤：为优化算法提供基础数据；

1-(b).用户指定模板步骤：所述模板是用户表达含义的载体，具体地：形如 A₁...A_i...A_k=>A_k+1,的蕴含式，其中A_i可以是属性名、类名或者C+、C*的表达式， 若为C+表示一个或多个类C的实例，若为C*表示零或多个类C的实例；用户选择 指定GI模板、RPC模板或者同时指定GI模板和RPC模板；

所述GI模板：用户因项间关系模糊而给出的不确定的知识模板，称为总体印 象知识模板，简称GI模板，表示为gi[S₁,...,S_m]其中，S_i可以是一个属性名、类 名或者一条表达式；

所述RPC模板:用户知晓项间关系且明确关系方向而给出的相对合理的知识 模板，称为相对精确知识模板，简称RPC，表示为rpc[S₁,...,S_m=>V₁,...,V_g]其中， S_k可以是一个属性名、类名或者一条表达式；

1-(c).解析模板步骤：根据模板对待优化的关联规则进行扫描计数；

1-(d).获取相关参数步骤：获取模板的相关数据及不匹配度量；

1-(e).计算模板权重累计值步骤：当指定多个模板时，模板权重为weight=1/n， 其中n模板数，设X_ij、Y_ij分别为R_i中前件、后件与GI_j或RPC_j中前件、后件不匹配 程度的度量。TX_i为X_ij的权重累计值，TY_i为Y_ij的权重累计值。TX_i、TY_i按如下公 式计算：

TX_i=TX_i+1/n*X_ij;

TY_i=TY_i+1/n*Y_ij;

1-(f).兴趣度计算：

1-(f-1).根据公式计算一致度的步骤：规则R_i的兴趣度表示规则前件、后件与 指定模板集U匹配的程度，用符号conf_i表示，称为规则R_i的一致度；

conf_i＝TX_i*TY_i

1-(f-2).根据公式计算后件不可预知度的步骤：规则R_i的兴趣度表示规则后件 与指定模板集U不匹配的程度，用符号unexpY_i表示，称为规则R_i的后件不可预知 度；

${\mathrm{unexpY}}_i=\left(\begin{array}{c}{\mathrm{TX}}_i-{\mathrm{TY}}_i,{\mathrm{TX}}_i-{\mathrm{TY}}_i>0\\ 0,{\mathrm{TX}}_i-{\mathrm{TY}}_i\le 0\end{array}\right)$

1-(f-3).根据公式计算前件不可预知度的步骤：规则R_i的兴趣度表示规则前件 与指定模板集U不匹配的程度，用符号unexpX_i表示，称为规则R_i的前件不可预知 度；

${\mathrm{unexpX}}_i=\left(\begin{array}{c}{\mathrm{TY}}_i-{\mathrm{TX}}_i,{\mathrm{TY}}_i-{\mathrm{TX}}_i>0\\ 0,{\mathrm{TY}}_i-{\mathrm{TX}}_i\le 0\end{array}\right)$

1-(f-4).根据公式计算不可预知度的步骤：规则R_i的兴趣度表示规则前件、后 件与指定模板集U不匹配的程度，用符号unexp_i表示，称为规则R_i的不可预知度；

unexp_i=1-max(conf_i,unexpY_i,unexpX_i)。

进一步地，当用户仅指定GI模板时，所述一致度公式为:

${\mathrm{conf}}_1=\left(\begin{array}{ccc}0,& & {\mathrm{TX}}_1=0,{\mathrm{TY}}_1=0\\ {\mathrm{TY}}_1,& & {\mathrm{TX}}_1=0,{\mathrm{TY}}_1\ne 0\\ T{X}_1,& & {\mathrm{TX}}_1\ne 0,{\mathrm{TY}}_1=0\\ {\mathrm{TX}}_1*{\mathrm{TY}}_1,& & \mathrm{others}.\end{array}\right)$

具体地，所述获取相关参数步骤包含：

若为GI模板：

设TN_j为GI_j中元素总数；XM_ij、YM_ij分别为R_i中前件、后件与GI_j中元素相匹 配的个数；TM_ij为GI_j中已被R_i中元素所匹配的元素总数

若TN_j=0，则TM_ij/TN_j=1

$X_{\mathrm{ij}}=\left(\begin{array}{c}\min ({\mathrm{XM}}_{\mathrm{ij}}/{\mathrm{XN}}_i,{\mathrm{TM}}_{\mathrm{ij}}/{\mathrm{TN}}_j)\\ ,\mathrm{if}{\mathrm{XM}}_{\mathrm{ij}}/{\mathrm{XN}}_i>{\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i\\ {\mathrm{XM}}_{\mathrm{ij}}/{\mathrm{XN}}_i,\mathrm{else}{\mathrm{XN}}_{\mathrm{ij}}/{\mathrm{XN}}_i\le {\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i\end{array}\right)$

$Y_{\mathrm{ij}}=\left(\begin{array}{c}{\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i,\mathrm{if}{\mathrm{XM}}_{\mathrm{ij}}/{\mathrm{XN}}_i>{\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i\\ \min ({\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i,{\mathrm{TM}}_{\mathrm{ij}}/{\mathrm{TN}}_j)\\ ,\mathrm{else}{\mathrm{XM}}_{\mathrm{ij}}/{\mathrm{XN}}_i\le {\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i\end{array}\right)$

若为RPC模板：

设TXN_j、TYN_j分别为RPC_j中前件、后件所含元素总数；XM_ij、YM_ij分别为R_i中 前件、后件与RPC_j中前件、后件所含元素相匹配的个数；TXM_ij、TYM_ij分别为RPC_j中前件、后件已被R_i中前件、后件所匹配的元素总数

若TXN_j=0，则TXM_ij/TXN_j=1

若TYN_j=0，则TYM_ij/TYN_j=1

X_ij＝min(XM_ij/XN_i,TXM_ij/TXN_j)

Y_ij＝min(YM_ij/YN_i,TYM_ij/TYN_j)。

进一步地，所述兴趣度计算完成后有对含不同类型兴趣度的规则集排序步 骤。

由于本专利提出的基于主观兴趣度的关联规则优化算法涉及到模板、兴趣度 两个方面，下面详细阐述这两点。

模板是主观兴趣度算法中使用到的一个重要的工具，是用户表达含义的载 体，但目前基于模板的优化方法一般仅涉及一个模板的分析。兴趣度是规则有趣 程度的客观度量，目前基于兴趣度的优化方法一般结合具体领域知识提出相应的 兴趣度计算模型，用来衡量规则的有趣程度。

本专利引入模板权重模型和计算方法，丰富了用户含义。引入模板权重将支 持用户指定多个模板同时进行分析，通过叠加多个模板的带权兴趣度得到最终兴 趣度，从而实现多模板的最终兴趣度排序。

为便于描述，预先给出相关符号的说明：设有原始关联规则集 R₀＝{X_iY|i＝1,...,n}，其中，X_iY是关联规则，R_i为R₀中的一条规则。XN_i为规 则R_i中前件X_i所含元素个数，YN_i为规则R_i中后件Y所含元素个数。

设GI＝{GI_j|j＝0,...,l}为用户指定的GI模板集合，RPC＝{RPC_j|j＝0,...,k}为用户指 定的RPC模板集合，U＝{U_j|U_jGI,或U_jRPC,j＝1,...,n}为指定模板总集。

为简化算法描述，这里默认模板权重值为weight=1/n，n为U中模板数。设 X_ij、Y_ij分别为R_i中前件、后件与GI_j或RPC_j中前件、后件不匹配程度的度量（作 为过渡值而无特殊含义）。TX_i为X_ij的权重累计值，TY_i为Y_ij的权重累计值。TX_i、 TY_i按如下公式计算：

TX_i=TX_i+1/n*X_ij;TY_i=TY_i+1/n*Y_ij;

兴趣度作为对规则有趣程度的度量，从侧面反映了规则对用户而言价值的高 低。

原一致度的计算缺乏特殊情况下的考虑，当指定的模板仅为GI时，规则的 一致度值几乎全为零而将进行没有意义的排序。本专利引入对计算兴趣度的算法 增加了仅指定一个GI模板情况下对一致度的分类处理，完善了兴趣度的计算方 法和模型，计算方法如下：

当指定模板仅为GI模板时，若前、后件的权重累计值均为0，一致度才为0； 若前、后件权重累计值之一为0，则一致度为权重累计值不为0的那个值；其他 情况下一致度为前、后件权重累计值的乘积。

一致规则的兴趣度表示规则前件、后件与指定模板集匹配的程度，称为规则 的一致度。通俗说，就是完全匹配度，与模板完全匹配的程度。

本专利中对计算兴趣度的算法增加了仅指定一个GI模板情况下对一致度 conf_i的分类处理。当指定模板仅为GI模板时（此时i＝1），计算i＝1的公式如下：

${\mathrm{conf}}_1=\left(\begin{array}{ccc}0,& & {\mathrm{TX}}_1=0,{\mathrm{TY}}_1=0\\ {\mathrm{TY}}_1,& & {\mathrm{TX}}_1=0,{\mathrm{TY}}_1\ne 0\\ T{X}_1,& & {\mathrm{TX}}_1\ne 0,{\mathrm{TY}}_1=0\\ {\mathrm{TX}}_1*{\mathrm{TY}}_1,& & \mathrm{others}\end{array}\right)$

除此之外，conf_i仅由下列公式计算：conf_i=TX_i*TY_i。

本算法的核心思想：对每条解析后的模板，均扫描一次规则集；扫描过程中， 根据模板对每条规则进行多方面的统计；综合规则的各统计值，计算其一致度、 后件不可预知度、前件不可预知度、不可预知度；最后，规则集基于其中一种兴 趣度的值降序排列，并返回结果。

本发明的技术保护点和本发明有益效果：

1.单一模板下对兴趣度的特殊处理，完善了兴趣度的计算方法和模型，也就构 建了完善的兴趣度的计算方法；

2.基于复合模板的兴趣度分析，从而实现多模板的最终兴趣度排序。

3.通过叠加多个模板的带权兴趣度得到最终兴趣度，对基于主观兴趣度的关联规 则优化算法总流程进行再造，使得兴趣度的计算能合理适应复合分析环境，该新 构建的主观兴趣度分析算法其优化能力得到了有效增强。

基于主观兴趣度的关联规则优化算法在指定一条GI模板时，计算兴趣度conf_i的值不会出现全为零而进行无意义排序的情况，且其支持用户指定多条模板，扩 大了用户的分析范围，使用户能表达更加丰富的含义，有效增强了算法的优化能 力。算法有效避免了按conf_i值无意义排序的情况，且多模板的支持使用户能表达 更加丰富的含义，有效增强了算法的优化能力。而由于海量数据进行关联挖掘导 出的关联规则数量巨大，该算法则可提升规则质量和更优地发现有价值规则。

附图说明

图1是不含模板的兴趣度优化流程图；

图2是支持多类复合模板的主观兴趣度优化流程图；

具体实施方式

为使本发明能够更加明显易懂,下面结合附图和具体实施方式对本发明作进 一步详细的说明：

主观兴趣度优化算法步骤：

1获取数据

示例数据说明：GA代表专业课成绩，一共有7门专业课GA1～GA7；GB代 表基础课成绩，一共有7门基础课GB1～GB7。各个课程的等级用1、2、3来表 示，1表示最差，2表示中等，3表示优秀。使用关联规则算法挖掘得到以下12 条规则，这几条规则的特点是规则前件均为GA，规则后件均为GB。

编号 规则 编号 规则 R1 GA1-3→GB2-3 R7 GA4-1→GB7-2 R2 GA4-3→GB4-3 R8 GA6-2→GB7-2 R3 GA2-3→GB2-3 R9 GA5-1,GA2-2→GB2-2 R4 GA2-3→GB5-1 R10 GA5-2,GA1-2→GB3-2

R5 GA6-1→GB1-3 R11 GA6-1,GA3-3→GB6-3 R6 GA4-2→GB3-3 R12 GA7-2,GA3-3→GB4-3

2.用户指定模板

RPC[GA-good+→GB-good]   GI[GB2-3]

以上为RPC与GI的复合模板，其中GA-good表示成绩为3的所有GA课 程，GB-good表示成绩为3的所有GB课程，加号“+”表示GA-good课程出现 1次或1次以上。用户指定这个复合模板想表达含义是，专业课程学得好的是否 能推出其基础课程也学得好。

3.计算模板权重累计值之前先获取两种模板下的相关参数

a)若为GI模板：

设TN_j为GI_j中元素总数；XM_ij、YM_ij分别为R_i中前件、后件与GI_j中元素相匹 配的个数；TM_ij为GI_j中已被R_i中元素所匹配的元素总数。

若TN_j=0，则TM_ij/TN_j=1

$X_{\mathrm{ij}}=\left(\begin{array}{c}\min ({\mathrm{XM}}_{\mathrm{ij}}/{\mathrm{XN}}_i,{\mathrm{TM}}_{\mathrm{ij}}/{\mathrm{TN}}_j)\\ ,\mathrm{if}{\mathrm{XM}}_{\mathrm{ij}}/{\mathrm{XN}}_i>{\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i\\ {\mathrm{XM}}_{\mathrm{ij}}/{\mathrm{XN}}_i,\mathrm{else}{\mathrm{XN}}_{\mathrm{ij}}/{\mathrm{XN}}_i\le {\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i\end{array}\right)$

$Y_{\mathrm{ij}}=\left(\begin{array}{c}{\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i,\mathrm{if}{\mathrm{XM}}_{\mathrm{ij}}/{\mathrm{XN}}_i>{\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i\\ \min ({\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i,{\mathrm{TM}}_{\mathrm{ij}}/{\mathrm{TN}}_j)\\ ,\mathrm{else}{\mathrm{XM}}_{\mathrm{ij}}/{\mathrm{XN}}_i\le {\mathrm{YM}}_{\mathrm{ij}}/{\mathrm{YN}}_i\end{array}\right)$

针对模板GI[GB2-3]，TN₁＝1；XM_1-1＝0，XM_2-1＝0，XM_3-1＝0，……， XM_12-1＝0；YM_1-1＝1，YM_2-1＝0，YM_3-1＝1，……，YM_12-1＝0；TM_1-1＝1， TM_2-1＝0，TM_3-1＝1，……，TM_12-1＝0；X_i-1，Y_i-1

b)若为RPC模板：

设TXN_j、TYN_j分别为RPC_j中前件、后件所含元素总数；XM_ij、YM_ij分别为R_i中 前件、后件与RPC_j中前件、后件所含元素相匹配的个数；TXM_ij、TYM_ij分别为RPC_j中前件、后件已被R_i中前件、后件所匹配的元素总数。

若TXN_j=0，则TXM_ij/TXN_j=1

若TYN_j=0，则TYM_ij/TYN_j=1

X_ij＝min(XM_ij/XN_i,TXM_ij/TXN_j)

Y_ij＝min(YM_ij/YN_i,TYM_ij/TYN_j)

针对模板RPC[GA-good+→GB-good]，有公式可得：TXN₁＝1，TYN₁＝1； XM_1-1＝1，XM_2-1＝1，XM_3-1＝1，……，XM_12-1＝1；YM_1-1＝1，YM_2-1＝1， YM_3-1＝1，……，YM_12-1＝1；TXM_1-1＝1，TXM_2-1＝1，TXM_3-1＝1，……， TXM_12-1＝1；TYM_1-1＝1，TYM_2-1＝1，TYM_3-1＝1，……，TYM_12-1＝1；X_i-1，Y_i-1

4.计算模板权重累计值

这里默认模板权重值为weight=1/n，n为U中模板数。设X_ij、Y_ij分别为R_i中 前件、后件与GI_j或RPC_j中前件、后件不匹配程度的度量。TX_i为X_ij的权重累 计值，TY_i为Y_ij的权重累计值。TX_i、TY_i按如下公式计算：

TX_i=TX_i+1/n*X_ij;

TY_i=TY_i+1/n*Y_ij;

上述实例中有weight＝1/n＝1/2；TX_i，TY_i按上述公式进行叠加计算出结果。

5.四种兴趣度的计算

当指定模板仅为GI模板时（此时i＝1），计算conf_i的公式如下：

${\mathrm{conf}}_1=\left(\begin{array}{ccc}0,& & {\mathrm{TX}}_1=0,{\mathrm{TY}}_1=0\\ {\mathrm{TY}}_1,& & {\mathrm{TX}}_1=0,{\mathrm{TY}}_1\ne 0\\ T{X}_1,& & {\mathrm{TX}}_1\ne 0,{\mathrm{TY}}_1=0\\ {\mathrm{TX}}_1*{\mathrm{TY}}_1,& & \mathrm{others}\end{array}\right)$

除此之外，conf_i仅由下列公式计算：

conf_i=TX_i*TY_i

下列公式用于计算unexpY_i、unexpX_i、unexp_i：

${\mathrm{unexpY}}_i=\left(\begin{array}{c}{\mathrm{TX}}_i-{\mathrm{TY}}_i,{\mathrm{TX}}_i-{\mathrm{TY}}_i>0\\ 0,{\mathrm{TX}}_i-{\mathrm{TY}}_i\le 0\end{array}\right)$

${\mathrm{unexpX}}_i=\left(\begin{array}{c}{\mathrm{TY}}_i-{\mathrm{TX}}_i,{\mathrm{TY}}_i-{\mathrm{TX}}_i>0\\ 0,{\mathrm{TY}}_i-{\mathrm{TX}}_i\le 0\end{array}\right)$

unexp_i=1-max(conf_i,unexpY_i,unexpX_i)

6.对含不同类型兴趣度的规则集排序，得到规则集排序结果。 conf_i

unexpY_i

unexpX_i

unexp_i

虽然这里结合具体的实施例对本发明进行了描述，但是对本领域技术人员来 说，很多其它的变化、改进以及应用将是很明显的。因此，本发明不应当受此处 特定公开的限制，而应由附加的权利要求来限定。