编者按：随着互联网的发展，如今的网页做得越来越多姿多彩、千奇百怪。丰富的网络内容，与我们的工作息息相关。而打印网页上的内容，则成了许多人经常要面对的一件工作。想要打印网页，其实会面临很多问题。比如，其实我们想打印的有用内容，往往只占整个网页的很少一部分，但打印机却全然不管，一股脑都给打印出来。浪费纸张和墨盒不说，可用的部分字体还小得可怜。那么，有什么办法可以让网页打印变得更轻松呢？

 
图1：程序首次推荐                     图2：打印预览

本工作详细内容请参见：

Linpeng Tang, Lei Zhang, Ping Luo, Min Wang. Incorporating Occupancy into Frequent Pattern Mining for High Quality Pattern Recommendation. in CIKM 2012. (Appendix)

Lei Zhang, Linpeng Tang, Ping Luo, Enhong Chen, Limei Jiao, Min Wang, Guiquan Liu. Harnessing the Wisdom of the Crowds for Accurate Web Page Clipping. in KDD 2012.

慧打印

    最近，来自惠普中国研究院的小组成员们研究开发了一个具备了全新“学习功能”的打印系统：“慧打印”。

    当程序安装之后，会在您的IE或Firefox浏览器命令栏（Command Bar）中出现按钮：

    现在，只要您点选了想要打印的页面（比如用户想打印惠普公司副总裁Told的简历，http://www8.hp.com/us/en/company-information/executive-team/todd-bradley.html），如果该网页或类似的网页是第一次被打印的话，程序会首先帮您计算出一个您可能需要的打印范围；如图1所示：   

    您若对此推荐的“打印范围”不满意，可进行手动调整：既可以增加内容，也可以删除内容。如图3所示，我们在此网页上选中了三个区域：Told的图片、职务以及详细简历。

 
图3：用户初次调整                   图4：打印预览
 

    而当您调整完毕按下打印按钮的时候，您对于该网页的内容筛选方式（内容标记），就会被自动记录并发往数据中心（在获得您同意的前提下）。当您下次要再想打印类似网页的时候（比如打印惠普CEO Meg的简历http://www8.hp.com/us/en/company-information/executive-team/meg-whitman.html）该程序就会根据您之前的操作，自动给出最合理的“打印范围”。如图5所示，该软件会直接推荐Meg的图片、职称以及详细简历供打印：

 
图5：程序首次推荐                     图6：打印预览

    这是不是为您节省了许多时间，为您节省了打印资源？此外，不止是您，您的同事、邻居、朋友、或者网络上任意一个人，只要他们调整过的打印页面，均会被记录下来，并成为日后帮助他人计算打印范围的数据。也就是说，这个程序使用的人越多，它就会变得越智慧，这也是 “慧打印”名字的由来。下面我们将具体介绍慧打印系统背后的核心算法。

核心算法：利用群体智能做更准确的打印推荐

    这里涉及了几个问题：第一，怎样表示打印日志数据库；第二，怎样形式化这个打印推荐问题；第三，怎么设计高效算法以满足实时推荐。
    下面我们将逐一解答这些问题。

打印日志数据库

    对于第一个问题，我们将打印日志存储到事务数据库（Transaction Database）中，该数据库的每行对应一条打印日志。例如，我们在图5的网页上选择了三个打印区域（每个打印区域称为一个Clip）：图片、职称以及详细简历，那么该网页的打印日志包含三个Clip。

图 7：（左）打印日志数据库，（右）事务数据库   

    那么，打印日志数据库（Print Log Database）就可以转换成事务数据库（Transaction Database）。其中每一个事务（Transaction）就是数据库中的一行，包含了对某个网页选择的所有Clip。例如，图7数据库的第一条打印日志就包含了三个Clip，分别是B、C、E。

打印推荐问题形式化

    我们将打印区域推荐的问题转换成模式挖掘（Pattern Mining）的问题。
    当用户在某网页上点击“慧打印”按钮后，经过一些通信和计算，我们可获得该网页中可供推荐的所有Clip的集合，记为Q。那么，我们的问题就转化为如何选择Q的某个子集进行推荐。
    在我们的方法中，结合打印日志数据库，我们利用两个度量指标来衡量一个模式（Pattern）的质量；它们分别是：频繁度（support）和完整度（Occupancy）。

图 8： 一个Transaction Database 例子

模式的频繁度

    如图8中的例子，它包含五个记录；其中，记录1、3和5都包含模式BC。那么，模式BC的频繁度值为3/5。
    模式的频繁度越高，意味着选择该模式（Clip的组合）进行打印的次数越高。因此，我们倾向于选择频繁度高的模式进行推荐。

模式完整度

    然而，在打印推荐中，仅仅利用模式的频繁度衡量模式的质量是不够的。
    我们不仅需要某个模式在数据库中频繁出现，该模式能够占有包含它的记录的大部分。这样的话，所推荐的模式才会更加完整，以避免漏掉某些Clip。
    因此，在此工作中，我们提出一个刻画完整性的度：

    计算模式的完整性时，首先得确定包含该模式的所有记录。以图8中的模式BC为例，包含它的记录有三条，分别是记录1、3和5。在每条记录中，我们可以分别计算模式BC在该记录中的完整性；例如，记录1总共包含三个clip，那么模式BC在记录1中的占有率为2/3；同样，我们也可以计算出模式BC在记录3和5中的占有率；最后，我们把在各个记录中的占有率平均起来，作为该模式在整个数据库中的完整性度量。
    在图8 的数据库中，模式BC的完整性则为 

频繁模式 （Frequent Pattern）
    如果一个模式的频繁度高于一个阈值α的话，那么称该模式为频繁模式。当α=0.5，图8中模式BC是一个频繁模式。
主导模式 （Dominant Pattern)
    如果一个模式的完整度高于一个阈值β的话，那么称该模式为主导模式。当β=0.5，图8中模式BC是一个主导模式。
胜任模式（Qualified Pattern）
    如果一个模式既是一个频繁模式又是一个主导模式，那么称该模式为胜任模式。
胜任值（Quality Value）
    我们用加权的方法把模式的频繁度和完整度结合成一个度量，模式的频繁度+λ*模式的完整度；该度量值可以作为模式的胜任值。

图 9

    有了上面的一些定义，我们给出如下的模式挖掘问题：
    给定一个事务数据库、阈值α、β和参数λ，我们的问题是：在所有胜任的模式中找到胜任值最大的模式。
    图9是该问题的一个形象化表示：左边的椭圆部分表示所有频繁模式的集合，右边的椭圆部分表示所有主导模式的集合，中间交集部分表示所有胜任模式的集合。我们的任务就是交集区域中选出胜任值最大的模式，以此推荐给用户进行打印。

模式挖掘快速算法
    现实中的事务数据库通常会很大，如何高效的完成该模式挖掘的计算，以实现实时推荐，成为我们必须解决的问题。下面，我们对该算法进行简要介绍。

图 10： 词典子集树（Lexicographic Subset Tree） 

    模式挖掘算法通常采用词典子集树（Lexicographic Subset Tree）表示搜索空间。例如，图10是一个只有四个Clip（A、B、C、D）的词典子集树。树中的每个结点对应一个模式，整个树实际上列出了所有需要考虑的模式。
    一个很直接的方法就是对树中的每个结点计算其频繁度和完整度，然后通过比较获得胜任值最大的模式。然而这个方法太耗时。
    之前关于频繁模式挖掘（Frequent Pattern Mining）的工作主要是利用模式的反单调性性（Anti-monotone）进行减枝，减少搜索空间。模式的反单调性性告诉我们，如果一个模式是非频繁的，那么它的所有超集（Supersets）也是非频繁的。
    如图10中，模式 { A,B,C } 是非频繁的，那么它的超集 { A,B,C,D } 一定也是非频繁的。因此，树的遍历其实就是找到一条减枝线（Cut Line），其中位于减枝线上面的所有模式都是频繁的，位于减枝线下面的所有模式都是非频繁的。在图10中，红线就是频繁模式挖掘的减枝线。

图 11： 利用胜任值上界（quality upper bound）对树进行减枝

    下面，我们将介绍如何利用完整度的一些特性进一步减小搜索空间。
    具体的说，我们可以给出在一个子树中所有结点的胜任值上界；也就是说，在该子树中的所有结点的胜任值都不大于这个上界值。例如，图11中以 {C} 为根结点的子树，我们可以很快计算出这颗子树的胜任值的上界为0.6。换句话说，在这个子树中的所有结点（包含结点 {C} 和结点{C，D} ）的胜任值不大于0.6。
    那么，我们就可以利用这个上界进一步减小搜索空间。具体的说，我们在搜索的过程中记录当前搜索到的最大的胜任值。比如，图11中，当我们搜索到结点{C}时，我们知道了结点 {BC} 是当前最大的胜任模式，其胜任值为0.8。此时，若以结点{C}为根节点的子树的胜任值上界小于0.8，则不必对该子树进行进一步搜索。
    图11中蓝线就是所提出方法的减枝线。可以很清楚地看到，利用胜任值上界可以进一步减小搜索空间。

结语

    传统的网页内容打印推荐一般都是基于网页自身的视觉信息，学习哪些内容重要，哪些内容不重要。然而，网页格式和类型千奇百怪，这些方法很难达到很高的准确率，以满足打印的需求。
    与之前方法不同的是，我们利用了群体智能（人的智慧）来提供更加准确的网页内容推荐。具体讲，我们利用了之前用户打印相似网页所形成的知识库；基于此知识库，我们把打印推荐问题转换成了一个模式挖掘问题。除了利用传统频繁模式挖掘中的模式频繁度，我们还提出了一个新的度量，即完整度，来度量模式在其支持数据项中的占有度。模式的占有度越高意味着推荐的内容就越完整。综合频繁度和完整度，我们将获得更加满意的模式进行推荐。