电子商务的飞速发展使得人们更愿意通过网络快捷地选择商品和服务。但由于Web数据库中通常蕴含海量数据，增加了用户选择商品的成本。大多数推荐系统能通过偏好抽取的手段获取用户的偏好要求，并以经济的方式获取商品的信息。因此研究用户条件偏好的挖掘具有十分重要的意义。
目前已存在的一些电子商务推荐系统在实际运用中还存在着问题，推荐效率较低，有些还不能满足用户的个性化需求。优化具有条件偏好(即本文所指的上下文偏好)的查询功能的数据库系统引起了数据库领域研究者极大的兴趣。无论是电子商务还是个性化推荐系统，用户偏好在系统模型的设计中都是基本要素[1]。消费者偏好是一种消费心理，反映消费者对某种产品或服务的兴趣或爱好程度，受消费者个性特征以及外界环境等主客观因素的共同影响，把握消费者偏好的变化规律比较困难，消费者的偏好往往通过购买行为体现[2]，因此偏好抽取是关键技术所在。偏好抽取的结果能使用户明白自身的偏好要求，并能以最经济的方式获取偏好商品信息。偏好挖掘的使用方法中，基于关联规则的技术是较为热门的，但在实际应用中，关联规则推荐技术也存在着一些问题，比如：发现关联规则比较困难，关联规则的产生仅与用户消费的结果有关而忽视了产生偏好的上下文约束，而用户的偏好不稳定往往随着上下文的不同变化。本文主要阐述用偏好挖掘的算法获取用户的潜在偏好，使用的是系统事先收集的样本，用成对出现的数据表达用户的偏好。用户偏好由一系列条件偏好规则详细说明，这些规则满足一定的兴趣标准，并具有较强的预测性。本文提出基于条件的偏好规则的模型为i+≻i-| X，它表示在上下文X的约束下，相对于i-，用户更偏好i+。这里的条件约束就是指上下文约束。
例如，电影偏好数据库中的元组信息表明了用户的偏好，这些偏好是由用户对点击电影标记表示他们的兴趣而产生的。标记A、B、C、D、E分别代表电影的导演、主演、影片类型等。如：A为张艺谋，B为章子怡，C为戏剧片，D为巩俐，E为动作片，每个ti(i=1, 2, …, n)代表用户的事物标记TID，假设用户点击了10次t1，点击了6次t3，则表明他们对与t1有关的电影更感兴趣，就得到一条偏好，用〈t1, t3〉表示，以此形成一个偏好数据库P，如图 1(b)所示。
|
图 1 影片数据库及偏好数据库 Figure 1 Movie database and preference database |
分析偏好规则〈t1, t3〉，发现无论在哪个元组中包含了标记A(张艺谋)和标记C(戏剧片)，用户更喜欢带有标记D(巩俐)而不是带有标记B(章子怡)主演的电影。所以条件偏好规则为：在两部由张艺谋执导的戏剧片中人们更喜欢巩俐主演的电影而不是章子怡主演的。这里的导演和影片类型就构成了这条规则的上下文。本文提出的用户偏好是由一系列条件偏好规则构成的，这些规则要满足稳定性和简洁性：所谓稳定性是指规则与大量的用户偏好吻合，与少量的不一致；简洁性是指生成的偏好规则集尽可能地小。
偏好规则的挖掘通过关联规则实现。尽管关联规则是挖掘算法中的基本方法之一，但是它的改进方法有很多，本文将改进的关联规则算法MaxClique用于条件偏好挖掘(Conditional Preference Mining, CPM)算法中来挖掘用户偏好规则。
1 相关工作挖掘具有条件偏好的偏好规则引起了众多专家学者的兴趣。目前一些主要的研究工作包括:开发偏好建模推理框架的研究, 为个性化数据库应用提供说明性和应用性很强的偏好查询语言。然而专注于偏好规则抽取的工作不多。偏好抽取就是让用户知道在一个数据库中什么是他们的偏好并且通过较低的成本获取这些偏好。提取用户偏好代表性的研究方法可以分为以下两类：
1) 通过一个查询界面输入用户偏好。这种情况下用户偏好的表达受到了很大的限制。用户偏好只能用简单模糊词标记元组或属性的方式表达，而且用户要参与到反馈的过程中，如果用户真的能够准确地表达自己的偏好，也就不需要偏好挖掘了，所以通过这种方式获取用户的偏好很困难[3]。
2) 用挖掘算法获取用户潜在的偏好。一般情况下，偏好受各种因素的影响，用户无法准确地表达自己的偏好[3]。随着数据挖掘关联规则技术的日益成熟，利用关联规则从用户的历史记录中挖掘隐式用户偏好，抽取一系列具有简洁性和稳定性的偏好规则成为目前的研究热点。文献[4]使用了用户喜欢与不喜欢这样的语义表达帮助个性化查询, 对上文考虑不多。文献[5]是利用贝叶斯网络(Bayesian Network, BN)结合上下文挖掘偏好，计算量较为复杂。文献[6]将偏好公式嵌入到关系代数SQL(Structured Query Language)中，其优点是查询速度快。文献[7]中提到的条件偏好查询使用规则集挖掘偏好，并对规则集的top-k条规则进行了评估。文献[8]提出了基于上下文的偏好挖掘，针对不同数据源产生的偏好规则可能出现重复和矛盾的现象，建立离线先验组存放具有代表性的偏好规则。文献[9]介绍了集格理论可用于搜索空间的压缩, 对本文的研究有一定的启示作用。文献[10]通过分析消费者的浏览频率、浏览时间、连接路径以及路径深度作为用户偏好商品的权重，并结合双向关联规则理论挖掘具有相互依赖关系的商品，计算消费者对商品的偏好程度。但是没有考虑上下文对消费者偏好的影响。文献[11]给出了基于上下文的数据库查询规则排序算法，提出了上下文偏好模型。文献[12]给出了一种利用普适计算技术进行上下文感知的数据库查询系统，但是需要偏好规则样本集。文献[13]则将上下文感知用于移动用户的偏好挖掘中，讨论了上下文独立和非独立条件下的两种偏好挖掘方法。文献[14]提出按属性排序挖掘偏好的方法。文献[15]是在电影数据集中设计的一个推荐系统，利用的是电影导演和演员提供的信息而不是用户的评级，对于用户偏好的挖掘显然有误差。
偏好规则一般是通过关联规则或改进的关联规则挖掘出来的。类关联规则算法(Class Association Rule, CAR)[16]是一种专注于挖掘特殊子集的关联规则算法，目标是在数据库中找出一组规则进行精确分类。基于划分的算法[17]将数据划分成内存能处理的块，第一次扫描数据库产生局部频繁集，第二次扫描数据库形成全局频繁项集，缺点是会产生部分假频繁项集。文献[18]提出了一种基于抽样的关联规则抽取算法。文献[19]对基于抽样的关联规则算法的有效性进行了分析。CMAR(Classification based on Multiple Class-Association Rules)算法[20]是一种基于多关联规则的分类算法，该方法拓展了频繁模式挖掘方法，有效地挖掘大型数据库。
目前尽管有大量的研究工作致力于用户偏好的表达和处理，但是这些用户偏好很难应用到实际中, 因为在查询结果和算法执行效率上每种方法都存在自己的不足。本文在挖掘算法中采用生成最大团的图模型算法，旨在减少系统内存的占用，压缩数据集的扫描次数。在此基础上结合上下文(条件)，提出了CPM算法用于挖掘偏好规则，从而能得出用户的偏好。这一方法提高了偏好规则的产生效率和偏好的准确性。
2 上下文偏好 2.1 上下文偏好规则定义设I为项目集合，X是I的子集，即X⊆I，事务数据库D是I的多项集，每个项集是数据库的一个元组，如图 1(a)中的一行。偏好数据库P⊆D×D是成对事务，每条记录代表用户的一个偏好，如：〈t, u〉∈P，意味着，与u相比用户更偏好t。偏好数据库和事务数据库的联系如图 2所示。
|
图 2 偏好数据库与事务数据库联系 Figure 2 Relation of preference database and transaction database |
定义1 上下文偏好。i+≻i-|X，X⊆I，i-和i+是I-X中的项集，称为上下文偏好规则。如：D≻E|AB表示在出现上下文AB时，相对于E，用户更加偏好D。偏好规则R=i+≻i-|X所关联的偏好数据库元组t≻R u，由如下方式来构造：
(X∪{ i+}⊆t)∧(X∪{i-} ⊆ u)∧(i-∉t)∧(i+∉u)
例如偏好规则D≻E|A所关联到的一个元组为：ACD≻ABCE，它表示当出现A时，用户对CD的偏好优于对BCE。
定义2 偏好规则的覆盖集。设agree(R, P)={〈t, u〉∈P|t≻R u}，表示R满足P中的成对集合〈t, u〉，即用户相对u更偏好t。设contradition(R, P)={〈t, u〉∈P|u≻R t}表示偏好规则R，满足成对集合〈t, u〉∈P，表明用户相对于t更偏好u，则覆盖集记作：
cov(R, P)=agree(R, P)∪contradition(R, P)
2.2 上下文规则的支持度、可信度和最小偏好规则定义3 偏好规则的支持度。一条上下文偏好规则R在偏好数据库P中的支持度描述如下：
sup(R, P)=|agree(R, P)| / |P|
如：上下文关联规则D≻E|A与图 1(b)中的p1，p2相匹配，D≻E|B与p2相匹配，前者的支持度为sup(D≻E| A, P)=|{p1, p2}| / |P|=2/5=0.4；而后者的支持度sup(D≻E|B, P)=|{p2}|/|P|=1/5=0.2。支持度反映了一个上下文关联规则R对偏好数据库中元组的匹配程度，同时也反映了一条上下文偏好规则的兴趣度。显然，规则D≻E| A比规则D≻E|B更有趣。
定义4 可信度。一条上下文偏好规则R对应于偏好数据库P的可信度描述如下：
conf(R, P)=|agree(R, P)| / |cov(R, P)|
如：conf(D≻E| A, P)=2/2=1；conf(D≻E| ∅, P)=2/3。
可信度用来衡量一个上下文偏好规则与用户偏好相悖的程度，就这点而言，D≻E| A比D≻E| ∅更有价值。如果一条上下文偏好规则R的支持度超过某一指定值即阈值(用min_sup表示)称为频繁关联规则。如果一条频繁关联规则的可信度超过某一指定值即阈值(min_conf)，称为强关联规则。可利用支持度阈值和可信度阈值进行剪枝即去掉非频繁项。图 1中D≻E|B和D≻E|AB具有相同的支持度和可信度，希望保留上下文更短的规则，即最小的上下文规则。本文将采用可扩展的关联规则方法进行频繁规则的挖掘，第3章将描述这一问题。
定义5 最小偏好规则。与偏好数据库P关联的上下文偏好规则R：i+≻i-|X，如果不存在另一条规则R′：i+≻i-|Y, (Y⊂X)∧(sup(i+≻i-|Y, P)=sup (i+≻i-|X, p))∧(conf((i+≻i-|Y, P)=conf (i+≻i-|X, p))，称R为最小上下文偏好规则。利用最小上下文规则可以大幅减少上下文偏好规则的数量，如D≻E|B是最小的上下文偏好规则而D≻E|AB不是，即可剪去。在给定的偏好数据库中，指定支持度和可信度的阈值，抽取出超过支持度和可信度阈值的最小的上下文偏好规则，是本文要解决的主要问题。一组偏好规则的简洁性由其基数的大小衡量，稳定性则由代价函数来考量。给定一条偏好规则π，偏好数据库p，上下文偏好规则集Π，用户偏好和Π匹配可表示为：
定义6 代价函数。给定偏好数据集p，上下文偏好规则集Π，与p关联的Π代价函数即
Cost(Π, p)=(|p\cover(Π, p)| + |contradict(Π, p)|) / |p|
直观来看，用户偏好集Π的代价函数表示偏好数据库p中的偏好没有被Π中的任何一条规则覆盖或者与Π中的部分规则相反的偏好在p中所占的百分比。按照这一定义，用户偏好的稳定性是指Cost函数的值最小。若某一偏好数据库上p的偏好规则为R，Π⊆R满足简洁性和代价最小，称Π是与p关联的用户偏好。本文第4章会有相应的算法。
3 可扩展关联规则算法可扩展的关联规则算法是一种发现频繁项集的高效算法，主要是利用频繁项集的结构性质实现快速查找。采用的方法是将项目集分解成小的独立的子集格从而组成一个子集格搜索空间，可在内存空间中完成搜索，可高效地确定长频繁项集及其子集，即可完成一般规模的数据集处理，对大数据集也有效，因此称为可扩展的关联规则算法。它是对传统关联规则作拓展与改进。本文所用的最大团方法就是这种方法。
3.1 集格理论关于一些集格理论的术语，文献[8]中有很好的叙述。现在回顾一下主要的内容。
定义7 集格。L在有限的交、并集合的操作中是闭合的，称之为集格。(L; ⊆)是由子集关系⊆定义的偏序集格。X∨Y=X∪Y且X∧Y=X∪Y。A(L)表示L原子集。
引理1 所有频繁集的子集都是频繁的，非频繁项的超集都是非频繁的。在自底向上的搜索频繁项集的过程中，这是一个有力的剪枝策略。
引理2 最大频繁项集唯一决定了所有频繁项集。
引理3 对于一个有限的布尔集格L，若x∈L，x=∨{y∈A(L) | y≤x}，元素是以原子集的子集的并的形式给出的。
引理4 对于任意存在的元素X∈P(L)，令J={Y∈A(P(L))|Y≤X}，
定义8 等价关系。令P是一个集合，一种在P上的等价关系是一种二元关系≡，若X、Y、Z∈P，这种等价关系满足：
1) 自反性。X≡X。
2) 对称性。若X≡Y，则Y≡X。
3) 传递性。若X≡Y, Y≡Z，则X≡Z。
这种等价关系将集合P分成不相交的子集，称作等价类。一个等价类的元素X∈P以[X]={Y∈P|X≡Y}的形式给出。定义一个等价前缀函数：
p：P(L)×N→P(L)
函数p(X, K)=X[1:K]，K是X的前缀长度，集格P(L)上的等价关系θk定义如下：
∀X, Y∈P(L), X≡θkY ⇔ p(X, k)=p(Y, k)
两个项集若享有一个公共的长度为k的前缀，它们在一个类中，θk称为基于前缀的等价关系。
引理5 所有θk包含的等价类[X]θk是P(L)的子集格。
任意的[X]θ1是一个含有它本身原子的一个布尔集格。设[A]θ1的原子集是{AC, AD, AT, AW}，通过引理3和引理4的应用可求出所有类的项目集的支持度。应当特别注意的是必须自底向上处理等价类，按字典顺序的逆序，即处理[W]之后处理[T]，然后是[D]，[C]，[A]，这样才能保证在剪枝的过程中所有子集的信息都是可靠的。应用这一方法，可以递归地分解不能一次纳入内存的等价类，使其能被独立地解决且可以在反字典的顺序中进行剪枝。
3.3 最大团方法生成更小的类定义9 伪等价关系。令P为一个集合，≡表示P上的一种二元关系，称为伪等价关系，对所有X、Y∈P，满足：
1) 自反性。X≡X。
2) 对称性。若X≡Y，则Y≡X。
这种伪等价关系将P分成可能重叠的子集，称为伪等价类。
定义10 最大团。如果一张图的所有顶点之间均有连线，称其为完全图。完全图的子图叫作团。令FK表示频繁K项集的集合，定义一张K关联图，以GK=(V, E)的形式给出，顶点集V={X|∈F1}，边集E={(X, Y)|X, Y∈V且∃Z∈F(k+1)，X, Y∈Z}，令MK表示GK的最大团的集合，图 3展示了F2所示的关联图G1，若频繁二项集为：{12, 13, 14, 15, 16, 17, 18, 23, 25, 27, 28, 34, 35, 36, 45, 46, 56, 58, 68, 78}，其中最大团M1={1235, 1258, 1287, 13456, 1568}。
|
图 3 前缀类和最大团类 Figure 3 Prefix classes and MaxClique classes |
定义一种基于幂集格P(L)的伪等价关系φk。∀X，Y∈P(L)，X≡φkY ⇔ ∃C∈Mk同时有X, Y∈C且p(X, k)=p(Y, k)。这说明X, Y是相关的，它们同为一个最大团的子集，并且共享长度为k的公共前缀，φk为基于最大团的伪等价关系。
引理6 由伪等价关系φk生成的伪等价类[X]φk是幂集P(L)的子集格。
引理7 令Nk表示基于最大团关系φk生成的伪等价类的集合，由φk生成的伪等价类[Y]φk是某些由前缀关系θk生成的伪等价类[Y]θk的子集。从另一方面来说，[X]θk是一组伪等价类ψ的并集，记作[X]θk=∪{[Z]φk|Z∈ψ⊆Nk}。
用φk来取代θk可以生成更小的集格。这些小集格对内存的需求更少。从图 3中可以看出基于前缀的类[1]={12345678}，包含了所有的项；而基于最大团的类[1]={1235, 1258, 1278, 13456, 1568}比基于前缀的类小。最大团生成算法对稀疏的K阶关联图会产生效果，对稠密图则不可行。
定义11 覆盖集合。对于类[x]，y∈[x]，称y覆盖了[x]的子集，记为cov(y)=[y]∩[x]。对于每个类C，首先确定它的覆盖集合：{y∈C |cov(y) ≠ ∅且对于任意z∈C，z < y，cov(y)⊄cov(z)}。计算关联图中顶点2的覆盖集的cov(2)={3, 5, 7}=[2]。对图中的例子而言cov(y)=[y]，因为所有的y都包含在类[1]中，类[1]的覆盖集为[[2], [3], [5]]，4不在集合中，因为cov(4)=[5, 6]，它是cov(3)=[4, 5, 6]的子集。在最大团的生成算法中，对于当前类只需要考虑它的覆盖集中的元素(算法步骤3)。对每一类覆盖集中的元素递归地生成最大团。每个从覆盖集中获得最大团都用从当前类获得的最大团的类标号作前缀。在插入新的团之前所有的副本或子集都会被淘汰。如果新团是已有团的子集，新团就不会被插入。
算法1 覆盖集生成算法Gencov。
输入 电影数据库；
输出 所有类的覆盖集。
1) for all tag[i]∈ AllTag do
2) for all tag[j]∈ AllTag do
3) if (tag[i]≠tag[j] ∧ IsFrequent(tag[i], tag[j]))
4) insert(ver[i].CoveringSet, j);
5) end
6) end
算法1中将不同的电影标签作为一类，存储在向量ver中，步骤1)和步骤2)针对所有的电影标签进行频繁集的搜索，步骤4)生成所有类的覆盖集。
算法2 最大团生成算法Genmax。
输入 电影数据集；
输出 每一类的最大团。
1) Gencov(ver);
2) foreach i:N→1 do
3) ver[i].CliqList=∅;
4) for all x∈ver[i].CoveringSet do
5) for all c∈ver[x].CliqList do
6) M=c∩ver[i].CoveringSet;
7) if (!M.empty)
8) M=M∪[i];
9) if(Not Exist X‖Y∈ver[i].CliqList, X⊆Y‖Y⊆X)
10) insert(M, ver[i].CliqList);
11) endif
12) endfor
13) endfor
14) endfor
算法中的ver是一个向量，它的最大容量为N即电影标签的总数量，步骤1)中调用算法1, 产生所有的覆盖集，步骤5)~8)描述了最大团的生成过程。
算法3 所有团的生成算法Genall。
输入每一类的最大团；
输出所有的团。
1) allCliq=∅;
2) foreach i:1→N do
3) for allcliq∈ver[i].CliqList
4) for allsubCliq of cliq
5) if (Not Exist Cliq∈allCliq == subCliq)
6) insert(subCliq, allCliq);
7) endif
8) endfor
9) endfor
10) endfor
算法中allCliq是一个用于存储所有团的集合，步骤2)~6)描述了利用所有类的最大团分解为不同的子团的过程，值得注意的是，所有的这些子团即为所有团。
4 挖掘偏好规则算法 4.1 偏好规则挖掘算法为了保证规则的简洁性，通过减少深度优先搜索解空间的剪枝方法来达到这一目的。
引理8 剪枝标准。如果一个上下文偏好规则i+≻i-|X是非频繁且非最小化的，则任何规则i+≻i-|Y(X是Y的前缀)都是非频繁且不是最小的上下文偏好规则。
算法4 用户偏好规则挖掘算法CPM。
输入 电影数据库，偏好数据库，最小支持度阈值minsuppt, 最小可信度阈值minconf；
输出 偏好规则集。
| $ \begin{align} &1)\ \ rules=\varnothing ;\text{ } \\ &2)~\text{ Genall}(\text{Genmax}());\text{ } \\ &3)~\text{ for}\ \text{all}\ Cliq1\in allCliq\ \text{do } \\ &4)~\text{ }\ \ \ \ \ \text{for}\ \text{all}\ Cliq2\in allCliq\ \text{do } \\ &5)~\ \ \ \ \ \ \ \ \ flag=0;~ \\ &6)~\text{ }\ \ \ \ \ \ \ \ \text{if }\ (Cliq1.length\text{ }==~\ Cliq2.length~)\text{ } \\ &7)~\text{ }\ \ \ \ \ \ \ \ \ \ \text{for }\ (k=1;k\text{ }\le NumOfTag;k++)\ \text{ do } \\ &8)~\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{if}\ (Cliq1.tag\left[k \right]\text{ }\ne \text{ }Cliq2.tag\left[k \right])\text{ }\ flag++;~ \\ &9)~\text{ }\ \ \ \ \ \ \ \ \ \ \text{endif } \\ &10)~\ \ \ \ \ \ \ \text{ endfor } \\ &11)~\text{ }\ \ \ \ \ \text{endif } \\ &12)~\ \ \ \ \ \ ~\text{if }\ (flag==1~)\text{ } \\ &13)~\text{ }\ \ \ \ \ \ \ \ \ suppt1=suppt\left( Cliq1, Cliq2 \right);\text{ } \\ &14)~\text{ }\ \ \ \ \ \ \ \ \ suppt2=suppt\left( Cliq2, Cliq1 \right);\text{ } \\ &15)~\ \ \ \ \ \ \ \text{ if}\ (suppt1>minsuppt~\And \And ~suppt1/\left( suppt1+suppt2 \right)>~minconf~) \\ &16)~\ \ \ \ \ \ \ \ \ \ \ \ \ \text{insert}\ (rules, \text{ }Cliq1, \text{ }Cliq2);\text{ } \\ &17)~\text{ }\ \ \ \ \ \ \ \text{endif } \\ &18)~\text{ }\ \ \ \ \ \text{endif } \\ &19)~\text{ }\ \ \ \text{endfor } \\ &20)~\text{ endfor } \\ &21)~\text{ return}\ rules \\ \end{align} $ |
NumOfallCliq是所有团的数目, 标记量flag表示两个团是否符合规则交叉的条件，算法步骤7)描述了长度相等且只有一项不等。步骤3)~14)，描述了如何判断两个团符合交叉生成规则的条件的过程，算法步骤15)~21)则描述了对两个满足交叉条件的团进行支持度判断以及生成规则的过程。由算法得知，根据其前缀上下文，一个最小前缀上下文规则是最小的。前缀最小是有约束的最小。用深度优先的方法可以相对容易地获得最小前缀规则集合。
4.2 频繁项集搜索策略1) 自底向上的搜索。
自底向上的搜索是基于等价关系θk，采用递归的策略将类分解为更小的类。等价类格可以由深度优先搜索和广度优先搜索策略生成。
假如原子集为{A, C, D, T, W}由广度优先搜索生成的类为{[AC], [AT], [AW]}，继续往下生成的类应该是{[ACT], [ATW], [ACW]}，最后是[ACTW]。计算任何项集的支持度，只需要简单地把前一阶段生成的它的两个子集做项目列表的交运算就可以了。算法输入的是集格S中原子项通过对不同的成对项做交集来产生频繁项，并通过递归的方法产生出某一阶段的频繁项集，并将上一阶段重复的项集删除。
算法5 CONTENUM算法。
输入偏好数据库P，前缀为X的规则;
输出偏好规则集S。
| $ \begin{align} &1)~\ \ S=\varnothing ~ \\ &2)\text{ }\ \text{for all}~i\in C~\text{do } \\ &3)\ \ \ \ \ \ \ \text{ }s12=supp\left( i1\succ i2|X\cup \left\{ i \right\}, P \right)\text{ } \\ &4)\text{ }\ \ \ \ \ \ \ s21=supp\left( i2\succ i1|X\cup \left\{ i \right\}, P \right)\text{ } \\ &5)\text{ }\ \ \ \ \ \ \ \text{if }((s12\ge \sigma )\vee (\text{ }s21\ge \sigma ))\wedge \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ((s21<\text{ }supp\left( i1\succ i2|X \right))\vee \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\text{(}s12\text{ }<\text{ }supp\left( i2\succ i1|\text{ }X \right)\text{)}\ \text{then} \\ &6)\ \ \ \ \ \ \ \ \ \text{ }\ \text{if }((s12\ge \sigma )\wedge \left( s12/\left( s12+s21 \right)\ge \kappa \right)\text{ } \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{then }S=S\cup \left\{ \text{ }i1\succ i2|\text{ }X\cup \left\{ i \right\} \right\}\text{ } \\ &7)\text{ }\ \ \ \ \ \ \ \ \ \ \text{if }(\left( s21\text{ }\ge ~\sigma \right)\wedge \left( s21\text{ }/\text{ }\left( s12+s21 \right)\text{ }\ge \text{ }\kappa \right)\text{ } \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{then }S=S\cup \left\{ \text{ }i2\succ i1|\text{ }X\cup \left\{ i \right\} \right\}~ \\ &8)\text{ }\ \ \ \ \ \ \ \ \ \ S=S\cup \text{CONTENUM}(\left( i1, i2 \right), \text{ }X\cup \left\{ i \right\}, \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{ }\{c\in C|i<ic\}, P, \sigma, \text{ }\kappa )\text{ } \\ &9)\text{ }\ \ \ \ \ \ \ \ \ \ \ \ \text{end if } \\ &10)\text{ }\ \ \ \ \ \text{end for } \\ &11)\text{ return}~S \\ \end{align} $ |
2) 自顶向下的搜索。
自顶向下的搜索方法从集格的最顶层元素开始，如果顶层元素为K项集，则需要进行K轮的交集运算。这种策略的优势是如果最大元素相当长，可以避免计算它的子集的支持度。搜索从顶层开始，如果顶层项集是频繁的，算法结束；否则进行下一阶段k-1项的判断，直到所有的最小频繁项被找到为止。算法构造的过程中可采用哈希表，记录存储非频繁项集，避免重复检索。自顶向下的搜索策略只需要将项目列表存入内存即可。
5 实验结果及分析本章将用实验评价CPM算法在抽取上下文偏好规则中的表现。5.1节描述了实验中所使用的真实的数据集。在此基础上描述了不同类型的实验结果。5.2节的实验主要用于评价CPM算法在抽取有趣条件偏好规则中的表现。5.3节对用最大团算法挖掘频繁集与传统的Aprori算法以及CONTENUM算法在挖掘效率上进行了对比。所有的实验程序用C++完成。所有实验在计算机上运行通过，计算机为Windows操作系统，8 GB内存，CPU为i7-4710hq，4核心8线程。
5.1 实验使用的数据集在本节的中实验采用的第1个真实数据集来源于www.movielens.org。数据集由71 567个用户对65 133部电影的10 000 054个评分(评分的范围为1~5分)，每个用户至少标记了20部电影，每部电影的属性描述包括类型、导演、年份、主演等。第2个数据集为last.fm数据集，包含1 892个用户对17 632个音乐家作品的92 834条播放信息，用户共对音乐家添加了186 479个标签(含11 946个不重复的标签)。
在电影实验数据集中提取了所有的用户的评分数据。用于比较CPM算法和基于Apriori的算法[21]以及CONTENUM算法对偏好规则的抽取效率。在表 1中，可以明显地发现数据集的主要特征，即每个用户的ID以及每个用户评价的电影数目(电影数据集D)，每一部被评价的电影的不同特征(属性值集合L)和由该数据集产生的偏好(两部电影若评分之差超过一个阈值则认为用户对这两部电影存在偏好)构成的成对的电影偏好(偏好数据集P)。
|
表 1 真实世界的电影偏好数据集 Table 1 Real world preference dataset over movies |
用不同规模的数据集训练CPM算法，从而发现算法的效率差异是极为重要的实验环节，可以通过修改评分差的阈值来简单地生成不同规模的偏好数据集。
5.2 电影数据集中的偏好规则抽取图 4的(a)和(b)中展示了随着支持度和可信度的逐渐增加，CPM算法从所有用户的数据集中提取偏好规则的数目会随着支持度和可信度的增加而不断减少。当最小可信度接近1时，提取到的规则数目急剧下降，这是由于实验采用的数据集极为庞大，很难保证在极高的可信度下规则不被噪声数据影响。
|
图 4 支持度和可信度变化时的规则数目和执行时间 Figure 4 Numer of rules and execution time according to variation of confidence and support |
图 4的(c)中描述了CPM算法在0.1%到1%的最小支持度阈值(对应三种不同的最小可信度)下的执行时间。从图中可以看出，最小可信度阈值并不是影响CPM算法执行时间的主要因素，这是因为CPM算法基于最小支持度生成候选上下文前缀，通过候选上下文的交叉运算来生成规则，而当候选上下文前缀的数目确定后，算法所需执行的时间便仅与数据集的规模有关。
通过CPM挖掘得到的偏好规则(其中最小支持度=0.1%)，如表 2所示，本文中按支持度列出了前10条偏好规则, 这些偏好规则是从400万条电影偏好数据库中发现的。例如，规则显示了用户普遍不太偏好动作电影(规则1，2，3，5，9)，规则4表明在惊险类的电影中用户普遍偏好犯罪类型的影片而不喜欢恐怖片；规则6则显示了用户比起纪录片更喜欢探险类的影片；规则7说明了同样是喜剧类电影，用户更喜欢犯罪类型电影，而不是奇幻类电影。规则8中显示用户更喜欢惊险类电影中的动作片而不是喜剧片，在魔幻类电影中，用户更喜欢正剧而不是喜剧。
|
|
表 2 挖掘出的偏好规则 Table 2 Preference rules discovered from database |
图 5采用了一个固定的支持度阈值K(即用规则的最小出现次数代替占数据集的最小比例)，展示了在不同K值下，从所有偏好数据集中挖掘出的上下文长度不同的规则(在不同长度上下文约束下)以及占所有规则的比例(最小可信度为0.5)。
|
图 5 不同长度上下文的偏好规则占比 Figure 5 Proportion of preference rules with different length of context |
从图 5的实验结果中可以看出，所有的规则基本集中在上下文长度为0到4的区间上。当K=10时，76.6%的规则的上下文长度为1和2，上下文长度为0的规则仅占7.1%;而当K=5 000时，上下文长度为1和2的规则占比为77%，但不存在上下文长度为4的规则，上下文长度为0的规则占比提升至17.7%。值得注意的是，随着K值的不断提高，长上下文规则的比例不断减小，当K=20 000时，规则的类型减少到仅有两种(上下文长度为0和上下文长度为1的规则)，其中上下文长度为0的规则占比76.9%。这一结果的出现是十分自然的，这是CPM算法挖掘规则的特性，同时说明大部分长上下文规则都是在低出现次数下产生的冗余规则，也进一步地说明最短上下文规则是最具有简洁性和稳定性的。
5.3 相关算法的比较 5.3.1 Movielens数据集图 6(a)比较了CPM算法和基于Apriori的算法以及CONTENUM算法在固定的最小支持度(0.6%)和最小可信度(0.75)下从不同规模的偏好数据库中提取规则所花费的时间。
|
图 6 在Movielens数据集下各算法的执行时间 Figure 6 Execute time of different algorithm on Movielens dataset |
随着数据集的规模的增大，基于Apriori的算法所提取规则耗费的时间以指数形式增长，这是由于基于Apriori的算法需要大量的数据库扫描，同时随着数据集的规模增大，基于Apriori的算法生成了更多的候选上下文前缀，这加剧了偏好数据库的规模对算法执行时间的影响。而CONTENUM算法在数据库规模增大的情况下，时间开销呈线性增长，数据库规模较为巨大的情况下，算法消耗的时间甚至逼近CPM算法，这是由于CONTENUM算法不预先生成候选的上下文前缀，而采用基于短上下文规则扩展的方式。
基于最大团的算法优于以上两种算法，这是因为CPM算法采用基于最大团的混合搜索的方式生成上下文前缀，这种方式不同于Apriori算法请求大量的数据库扫描，只需要两次数据库扫描即可生成候选的上下文前缀，从而快速通过上下文前缀交叉运算生成可能存在的规则。
图 6(a)和(c)描述了在相同的偏好数据库的规模下，不同的支持度阈值和可信度阈值对算法运行时间的影响。基于Apriori的算法随着最小支持度阈值的提升执行时间明显缩短，而CPM算法则几乎没有受到影响(见图(b))，这是因为生成上下文规则前缀的过程仅占时间开销的极小的一部分，故即便使用混合搜索进行剪枝也难以提升性能，而基于Apriori的算法则受益于此，大幅提升算法的性能(但时间开销仍为CPM算法的6倍和CONTENUM算法的4倍以上)。CONTENUM算法随着支持度和可信度的提高，算法的执行时间均有较大比例的减少，这是因为自底向上的算法仅依赖高于支持度和可信度的规则进行递归挖掘。在最小可信度阈值高于0.76时，CONTENUM算法甚至优于CPM算法，这一结果很好地吻合了当支持度和可信度高于某个阈值后，规则大量集中在较短的上下文前缀的类型上。CONTENUM算法没有生成频繁二项集的过程，当规则仅有长度为0或长度为1的上下文前缀时，它的效率非常高。
5.3.2 Last.fm数据集三种算法在Last.fm上的比较结果与其在Movielens上的结论基本一致。需要注意的是，图 7(a)中所有的算法的执行时间都有所增加，原因是Last.fm所提供的数据在一条条目下具有更多的标签，且标签的种类更为丰富。图 7(b)和(c)比较了不同最小支持度阈值和不同最小可信度阈值下各算法的执行时间，无论是Apriori算法还是CONTENUM算法的执行时间都有较大的增加，但CPM算法的执行时间变化不大。其中Aprior算法的时间增加得最为明显，这是由于Apriori算法生成上下文前缀的时间呈指数增长。CONTENUM算法的时间开销的增长也值得关注，CONTENUM算法基于自底向上的方式生成上下文，在这种长前缀且低重复的状况下其剪枝的效率下降极为明显。而CPM算法，只匹配条件符合的团，比在短前缀有较多重复的情况下更加高效。
|
图 7 在Last.fm数据集下各算法的执行时间 Figure 7 Execute time of different algorithm on Last.fm dataset |
本文提出了偏好规则挖掘算法CPM，用于从数据库中挖掘用户偏好，并在真实世界电影用户偏好集上进行了一系列实验，实验证明本文算法是高效的。实验得到的条件偏好规则建立在上下文的基础上，以可读的用户偏好规则的形式呈现。
在个性化的查询领域中，偏好挖掘技术将变得越来越重要，可以把从用户偏好样本中抽取的偏好模型存入知识库中，这些模型可以满足用户通过SQL语句进行的个性化查询，现已有很多文献中都提到了用可扩展的SQL即带有用户偏好查询操作的SQL语言来进行个性化查询。
当然在电子商务普遍应用的推荐系统的发展过程中，偏好挖掘的技术也是必不可少的。实际上随着被推荐商品的数量急剧增长，传统推荐算法的思想即基于由其他用户提供的对商品的评价与用户对购买商品评价之间的相似性计算，越来越受到可扩展性的挑战。偏好技术的发展，使得以简洁偏好形式出现的用户偏好的自动推理变得更有意义，有望解决可扩展性的问题。
下一步将研究如何利用评测规则对挖掘出的偏好规则进行过滤；对用户偏好的评价要能跳出一般的布尔判断；尝试建立以偏好挖掘算法为核心的偏好挖掘框架模型。
| [1] | ZAKI M J. Scalable algorithms for association mining[J]. IEEE Transactions on Knowledge and Data Engineering, 2000, 12(3): 372-390. DOI:10.1109/69.846291 |
| [2] | 张志宏, 寇纪淞, 陈富赞, 等. 基于遗传算法的顾客购买行为特征提取[J]. 模式识别与人工智能, 2010, 23(2): 256-266. (ZHANG Z H, KOU J S, CHEN F Z, et al. Feature extraction of customer purchase behavior based on genetic algorithm[J]. Pattern Recognition and ArtifIcial Intelligence, 2010, 23(2): 256-266.) |
| [3] | AMO S, DIALLO M S, DIOP C T, et al. Contextual preference mining for user profile construction[J]. Information Systems, 2015, 49. |
| [4] | HOLLAND S, ESTER M, KIEBLING W. Preference mining:a novel approach on mining user preferences for personalized applications[C]//Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases. Berlin:Springer, 2003:204-216. |
| [5] | AMO S D, MARCOS L P, ALVES G, et al. Mining user contextual preferences[J]. Journal of Information and Data Management, 2013, 4(1): 37-46. |
| [6] | CHOMICKI J. Preference formulas in relational queries[J]. ACM Transactions on Database System, 2003, 28(4): 427-466. DOI:10.1145/958942 |
| [7] | PEREIRA F S F, AMO S D. Evaluation of conditional preference queries[J]. Journal of Information and Data Management, 2010, 1(3): 521-536. |
| [8] | AGRAWAL R, RANTZAU R, TERZI E. Context-sensitive ranking[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. New York:ACM, 2006:383-394. |
| [9] | DAVEY B A, PRIESTLEY H A. Introduction to Lattices and Order[M]. Cambridge: Cambridge University Press, 2002: 1277-1286. |
| [10] | 刘玫莲, 刘同存, 肖吉军. 基于双向关联规则的网络消费者偏好挖掘研究[J]. 微电子与计算机, 2013, 3(3): 21-26. (LIU M L, LIU T C, XIAO J J. Web consumer preference mining based on bidirectional association rules[J]. Microelectronics and Computer, 2013, 3(3): 21-26.) |
| [11] | 孟祥福, 马宗民, 李昕, 等. 基于上下文偏好的数据库查询结果Top-K排序方法[J]. 计算机学报, 2014, 37(9): 1986-1998. (MENG X F, MA Z M, LI X, et al. A Top-K query results approach based on contextual preferences for Web database[J]. Chinese Journal of Computers, 2014, 37(9): 1986-1998.) |
| [12] | AMO S D, DIALLO M S, DIOP C T, et al. Mining contextual preference rules for building user profiles[C]//Proceedings of the 14th International Conference Data Warehousing and Knowledge Discovery. Berlin:Springer, 2012, 7448:229-242. |
| [13] | ZHU H, CHEN E, YU K, et al. Mining personal context-aware preferences for mobile users[C]//Proceedings of the IEEE 12th International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2012:1212-1217. |
| [14] | DEMBCZYNSK K, KOTLOWSK W, SLOWINSKI R. Learning of Rule Ensembles for Multiple Attribute Ranking Problems[M]. Berlin: Springer, 2011: 217-247. |
| [15] | CHOI S M, KO S K, HAN Y S. A movie recommendation algorithm based on genre correlations[J]. Expert Systems with Applications, 2012, 39(9): 8079-8085. DOI:10.1016/j.eswa.2012.01.132 |
| [16] | LIU B, HSU W, MAY. Integrating classification and association rule mining[EB/OL].[2016-11-20]. http://kckckc.myweb.hinet.net/paper/Integrating_Classification_and_Association_Rule_Mining.pdf. |
| [17] | SAVASERE A, OMIECINSKI E, NAVATHE S B. An efficient algorithm for mining association rules in large databases[EB/OL].[2016-11-20]. http://omega.sp.susu.ru/books/acm_sigmod/vol1/is5/VLDB95/P432.PDF. |
| [18] | TOIVONEN H. Sampling large databases for association rules[C]//Proceedings of the 22nd International Conference on Very Large Data Bases. San Francisco, CA:Morgan Kaufmann Publishers, 1996:134-145. |
| [19] | ZAKI M J, PARTHASARATHY S, LI W, et al. Evaluation of sampling for data mining of association rules[C]//Proceedings of the 7th International Workshop on Research Issues in Data Engineering. Washington, DC:IEEE Computer Society, 1997:42-50. |
| [20] | LI W, HAN J, PEI J. CMAR:Accurate and efficient classification based on multiple class-association rules[C]//Proceedings of the 2001 IEEE International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2001:369-376. |
| [21] | AGRAWAL R, MANNILA H, SRIKANT R. Fast discovery of association rules[J]. Advances in Knowledge Discovery and Data Mining, 1996, 32(3): 307-328. |