摘  要： 提出了一种基于Dirichlet过程的Deep Web数据源聚类方法，该方法采用层次Dirichlet过程（HDP）进行特征提取。首先将查询接口中原本高维稀疏的文本表示为主题特征，该过程能自动确定特征数。然后将文本看成多项式模型，采用Dirichlet过程混合模型聚类。该模型无需人工事先指定聚类个数，由Dirichlet过程根据数据自动计算得到，特别适用于Deep Web数据源数量大、变化快的特点。在通用数据集TEL-8上进行验证实验，并与其他聚类方法在F-measure和熵值两个指标上进行对比，均取得较好的结果。

　　关键词： Deep Web；数据集成；特征提取；dirichlet过程；混合模型

0 引言

　　万维网中不能被传统搜索引擎通过静态链接索引到的内容称为Deep Web。要获取这部分内容只能通过表单提交查询的方式获得[1-2]。Deep Web数据源的分类是指把所有发现的数据源按照领域进行划分，是Deep Web数据源集成的关键步骤之一[3]。目前Deep Web数据源分类，多数研究采用的是有监督的分类方法。而一个标注好的数据集，需要大量的人工知识，并且随着万维网的快速发展，训练集要考虑更新与扩展。这些对于自动化的数据集成都是很大的阻碍。在最新的Deep Web研究进展与综述中[4]，也明确指出结合机器学习，数据挖掘等领域的无监督的研究方法是今后的研究重点。

　　目前也有一部分研究人员关注聚类方法的研究。B.He[5]提出了MDhac方法，将表单属性看做分类数据（categorical data），采用基于模型的聚类，用卡方检验来作为距离函数，进行聚类。L.Barbosa[6]等人提出了基于表单内容和表单页面上下文的K-Means聚类方法。Zhao Pengpeng[7]等人提出基于图模型的聚类方法，算出数据源两两间的权值并连接成有权图，然后进行划分聚类。Xu Guangyue[8]等人提出了先聚类后分类的方法。先用LDA模型进行主题划分，用主题数代表聚类数目，将达到聚类精度的数据作为训练集，训练出分类模型，对前一步中聚类效果不好的数据进行后分类。

　　通过对国内外相关文献的阅读与研究，在了解目前的主要方法后发现，目前在Deep Web数据源特征提取和聚类数目的自动化确定方面还未有研究工作。正如前面提到的这些方法，都需要事先设定聚类个数或者特征个数。而在实际应用中聚类数目往往并不能事先知道，并会随着数据的增多而不断变化。

　　Dirichlet过程[9]（Dirichlet Process）则是一种具有代表性的非参数贝叶斯模型，基于Dirichlet过程的方法可以自动地学习特征数目和聚类个数。结合Deep Web数据源分类问题自身的需求与Dirichlet过程的特点，提出了基于Dirichlet过程的Deep Web数据源聚类方法。

1 聚类策略及相关步骤

　　Deep Web数据源聚类分为表单特征抽取、特征提取、聚类和结果评估四个主要步骤，如图1所示。

　　1.1 表单特征抽取

　　从形式上来说，Deep Web查询接口均以表单的形式出现在页面中，因此利用表单的特征作为Deep Web分类的判断依据是一种合理的解决方式。这也是目前多数研究人员采用的Pre-query[10]方式。观察互联网上的各种表单，一个查询接口中包含了丰富的语义信息，其主要的表现形式为文本信息[11]。以下为一个图书查询接口表单信息。

　　<from>

　　<attrgroup>

　　<attr name="Author"ename="author">

　　<domain format="text_box">

　　</domain>

　　</attr>

　　<attr name="Title"ename="title">

　　<domain format="text_box">

　　</domain>

　　</attr>

　　<attr name="Keyword"ename="keyword">

　　<domain format="text_box">

　　</domain>

　　</attr>

　　<attr name="ISBN"ename="isbn">

　　<domain format="text_box">

　　</domain>

　　</attr>

　　</attrgroup>

　　</form>

　　从以上代码可以看到，每个控件的name属性包含了该接口所属领域的绝大多数关键字，比如在图书领域，“ISBN”、“Title”、“Author”等词都能很好地表达其所属的类别。对通用实验数据集TEL-8进行统计分析后发现，在数据集中共472个查询接口，含有name属性的接口共463个，覆盖率达到98.1%。每个类别的情况如表1所示。

　　提取出name属性的值作为查询接口的表示文本，则可以将Deep Web数据源聚类问题转化为文本聚类问题进行研究。这些抽取出来的文本中含有噪声，对其进行去停用词和词干提取（波特词干器Porter Stemmer），可以提高聚类的效率和效果。

　　1.2 特征提取

　　概率主题模型假设文档由服从某种概率分布的主题组成，而每个主题则由服从某种概率分布的单词组成。Deep Web数据源也符合这种假设。Deep Web数据源由一些潜在的主题构成，比如“书籍”、“音乐”、“车辆”、“机票”等，这些潜在的主题又分别由主题内的词构成。每个词按照一定的概率属于某个主题内，比如“轮胎”、“引擎”等词就会以较高的概率属于“车辆”这一主题。

　　将查询接口进行特征抽取并处理为文本后，若直接应用向量空间模型将文本表示为向量，将造成特征向量高维稀疏的问题，影响聚类的效率与效果。考虑到以上对应关系，本文采用层次Dirichlet过程（HDP）进行特征提取。

　　与LDA模型一样，HDP也属于概率主题模型的范畴。不同的是LDA是参数贝叶斯模型，主题数目需要事先设定；而HDP属于非参数贝叶斯模型，不需要事先设定主题数目。主题数目将作为参数之一由模型根据具体的数据学习得到。

　　HDP模型[12]如图2所示。其中H为基分布，γ和α0为集中度参数。首先，以基分布H和集中度参数γ构成Dirichlet过程，产生全局分布G0。这就使得各个文档的主题可以共享。然后，再以G0为基分布，以α0为集中度参数，分别为文档集中的每一个文档构造Dirichlet过程。这个过程产生的Gj将作为θji的分布，然后从中抽取хji作为文档中每个特征的类别。本文采用HDP模型可以将查询接口抽取出来的文本表示为主题特征，为下一步的聚类做好准备。

　　整个生成过程如式（1）~式（4）：

　　1.3 聚类模型

　　特征提取后，采用Dirichlet过程混合模型进行聚类。用X={x1，x2，…，xn}表示Deep Web数据源，N表示数据源中包含的样本个数，xi={xi1，xi2，…，xin}表示第i个数据源，xij表示第i个数据源的第j个特征值。基于模型的聚类思想认为，X由K个模型混合而成，每个模型的混合系数由πk表示，即πk表示每个模型占的比重，并满足πk≥0，k={1，2，…，K}，且。有限混合模型和无限混合模型的区别在于，K是否事先已知。有限混合模型的K需要事先指定并且固定不变，而无限混合模型则把K作为模型参数，根据数据学习得到。本文建立Dirichlet过程混合模型如式（5）所示：

　　其中，取多项式分布，则该模型中的未知参数θ={π1，π2，…，πk；θ1，θ2，…，θK；K}，其服从Dirichlet过程DP（α，G0）。最后采用Gibbs采样对模型中未知参数θ进行求解，找出K值及其对应的混合系数πk，以及各个多项式分布中的未知参数θi，达到聚类目的。

2 实验结果与分析

　　2.1 实验设置

　　实验中使用了Deep Web数据源分类的通用数据集TEL-8进行试验。实验数据集总共包含472个Deep Web数据源查询接口，取其中含有name属性的查询接口，共463个。在进行表单特征抽取和数据预处理后，去除含有单词数少于3个的简单接口（共34个），最终得到429个查询接口，覆盖了机票、汽车、书籍、租车、酒店、工作、电影和音乐共8个领域。

　　本文采用在文本聚类领域常用的F-measure和熵值两种指标来评价本文聚类方法的效果。同时与同样使用TEL-8数据集的其他三种聚类方法进行比较，分别是B.He提出的MDhac方法、Zhao Pengpeng等人提出的FGC方法以及Xu Guangyue等人提出的基于LDA的先聚类后分类的方法，为下文方便对比，将该方法简称XU。

　　2.2 结果及分析

　　2.2.1 特征提取

　　建立HDP模型进行特征提取，经过100次Gibbs采样，估计出特征数，并将查询接口中的name属性词表示为对应的特征，达到降维的目的。特征数目随迭代次数变化的过程如图3所示。从图中可见，特征数目稳定在15左右，在迭代30次左右时达到稳定。经过特征提取后，特征值（接口中出现的不重复单词数）由原本的847降到15。

　　2.2.2 聚类结果比较

　　聚类结果得到9个Cluster，分别与8个领域的对应关系如表2所示。理想的聚类情况应该得到8个Cluster，但是由于本文聚类方法并没有事先指定聚类数目，所以存在较小的误差。认真观察第九个Cluster可以发现，在其中的接口数很少，只占总接口数的2%，明显少于前8个Cluster。考虑到本文方法的完全无监督的特性，认为该误差在可以接受的范围内。

　　对上面的聚类结果应用F-measure和熵值（Entropy）两种指标进行检验，并与其他使用相同数据集的方法进行比较，比较结果如表3、表4所示（注：由于MDhac方法的原文中并没有提供F-measure值，故表3中用“\”表示，同理对XU的Entropy值也用“\”表示）。

　　实验结果显示，本文方法在F-measure上取得的聚类均值优于FGC和XU两种方法，原因在于本文实验结果在8个领域上的F-measure值较为平均，没有小于0.8的情况。而在熵值这一评价指标上，FGC方法效果最佳。本文方法在电影、汽车和书籍三个领域上的熵值最优，但是由于在音乐和酒店两个领域的熵值过大，而使得平均值不理想。结合表2分析可以看到，原本属于酒店领域的接口比较容易被错误分到机票领域，而音乐和电影领域也存在类似情况。同时，分析第九个Cluster可以看到，这个导致误差的小聚类中，主要是来自音乐和电影类的接口，其原因主要在于酒店和机票领域，以及电影和音乐领域本来就存在一定的相似性。考虑其接口属性，以酒店领域和机票领域为例，它们基本上都会包含日期、地点、价格等关键词，在提取主题特征时容易将其视为同一特征。

3 结束语

　　Deep Web数据源分类是大规模Deep Web数据源集成的关键问题之一。结合Deep Web数据源分类问题自身的需求与Dirichlet过程的特点，本文提出了一种基于Dirichlet过程的Deep Web数据源聚类方法。实验表明，本文提出的方法可以有效实现Deep Web数据源聚类，并使整个聚类过程不需要人工干预，但是在聚类效果上，比如如何有效区分比较相似的领域，使得聚类结果更精确，还需要进一步探究。

参考文献

　　[1] BERGMAN M K. The deep web： surfacing hidden value[J]. The Journal of Electronic Publishing，2001，7（1）：8912-8914.

　　[2] 王成良，桑银邦.Deep Web集成系统中同类主题数据源选择方法[J].计算机应用研究，2011，28（9）：3364-3367.

　　[3] EL-GAMIL B R， WINIWARTER W， BO?譕IC B， et al. Deep web integrated systems： current achievements and open issues[C]. Proceedings of the 13th International Conference on Information Integration and Web-based Applications and Services. ACM， 2011：447-450.

　　[4] NAYAK R， SENELLART P， SUCHANEK F M， et al. Discovering interesting information with advances in Web technology[J]. ACM SIGKDD Explorations Newsletter， 2013， 14（2）： 63-81.

　　[5] HE B， TAO T， CHANG K C C. Organizing structured web sources by query schemas： a clustering approach[C]. Proceedings of the Thirteenth ACM International Conference on Information and Knowledge Management，ACM，2004：22-31.

　　[6] BARBOSA L， FREIRE J， SILVA A. Organizing hidden-web databases by clustering visible web documents[C]. IEEE 23rd International Conference on Data Engineering. IEEE， 2007： 326-335.

　　[7] Zhao Pengpeng， Huang Li， Fang Wei， et al. Organizing structured deep web by clustering query interfaces link graph[M]. Berlin： Springer， 2008：683-690.

　　[8] Xu Guangyue， Zheng Weimin， Wu Haiping， et al. Combining topic models and string kernel for deep web categorization[C]. Fuzzy Systems and Knowledge Discovery （FSKD）， 2010 Seventh International Conference on. IEEE， 2010：2791-2795.

　　[9] ISHWARAN H， JAMES L F. Gibbs sampling methods for stick-breaking priors [J]. Journal of the American Statistical Association， 2001，96（453）：161-173.

　　[10] MORAES M C， HEUSER C A， MOREIRA V P， et al. Prequery discovery of domain-specific query forms： a survey[J]. Knowledge and Data Engineering， IEEE Transactions on， 2013，25（8）：1830-1848.

　　[11] 祝官文，王念滨，王红滨.基于主题和表单属性的深层网络数据源分类方法[J].电子学报，2013，41（2）：260-266.

　　[12] TEH Y W， JORDAN M I， BEAL M J， et al. Hierarchical dirichlet processes [J]. Journal of the American Statistical Association， 2006，101（476）：1566-1581.