张迪，张云泉，张广治

(1.中国传媒大学 计算机学院，北京 100024；2.中国科学院 计算技术研究所，北京 100190)

一种在图连接项集上发掘精简模式的方法

张迪1，张云泉2，张广治1

(1.中国传媒大学 计算机学院，北京 100024；2.中国科学院 计算技术研究所，北京 100190)

项集通常具备两个特点：(1)观测样本来自于不同的实体，这些实体间存在着相似关系；(2)样本量稀少，导致模式发掘不完整。本文考虑如何在这类数据上有效地发掘精简的模式集合。首先，通过定义一个扩散核函数，可将每个节点下的小样本扩展至图中的所有节点，并通过权重来标识他们与当前节点的相似度：继而这一权重值，又可以自然地引入到精简模式的搜索与评估过程中。这样我们不仅从理论上给出了图结构对MDL评估的影响，并且在实现上也相对简单，只需对现有算法添加一个预处理过程，并进行少量修改即可。实验表明，这一方案的挖掘效果，比通常的独立挖掘、全局挖掘方式均具备明显的优势。而且，由于只有一个额外的预处理过程，计算代价也较低。

模式发掘；最小描述长度；图；扩散核

1 引言

模式挖掘技术，研究如何在数据表的项集中发现潜在的共现关系。经典的频繁模式发掘，如Apriori[1]，通过对所有数据项的出现次数进行排序，并滤去其中的低频模式，并将剩下的高频模式作为结果输出。这些模式既可以作为最终结果直接输出，也可以作为特征供后续的数据挖掘任务作为输入。该方式由于原理直观，计算简便，获得了较为广泛的应用。……