基于查询接口连接图的深层网页数据源分类管理方法

1.一种基于查询接口连接图的深层网页数据源分类管理方法，其特征在于，包括下列步骤：
(1)获取深层网页查询接口表单集合；
(2)自动抽取步骤(1)获取的查询接口表单的特征值，所述特征值包括表单标签的名称以及属性值；
(3)构造表单特征向量，包括，将提取的标签的名称和属性值分别构造特征空间LS和VS，对LS和VS中的每个表单形成的特征集合构造一个对应的特征向量，由此获得向量集合；
(4)在步骤(3)获得的向量集合中，对每个向量之间通过相似性计算获得关于标签、属性值、标签与属性值组合的查询接口连接图，分别可用LableMatrix、ValueMatrix、LableValueMatrix邻接矩阵来表示，查询接口之间的关联度计算方法为：
在基于标签的表单关联度计算中，利用标签的相同特征项的数量进行衡量，并进行标准化，
其中，sw表示表单F1和F2具有相同标签的个数，len表示F1和F2中标签特征向量的平均长度，两者相除进行标准化，SimL(F1，F2)表示基于标签(Label，L)的表单F1和F2的关联权值；
基于属性值以及标签与属性值组合的表单关联度计算，我们利用其向量之间的相似度函数进行计算，
式中，W1k和W2k分别表示表单F1和F2中属性值(Value，V)集合构成的向量表示，利用向量余弦公式计算得到基于属性值的表单F1和F2的关联权值SimV(F1，F2)，基于标签与属性值(Label&Value，LV)组合的表单关联权值SimLV(F1，F2)与SimV(F1，F2)的计算方法类似，但其中W1k和W2k分别表示表单F1和F2中标签和属性值共同构成集合的向量表示；
(5)构造查询接口连接图：
将步骤(4)得到的三个矩阵LableMatrix、ValueMatrix、LableValueMatrix进行加权合并，即将上述三个矩阵中的相似度值进行加权求和作为两两互连的查询接口表单之间的关联权值；按照带权无向连接图的构造方法，把每个查询接口作为图中的一个节点，为存在一定关联度的查询接口之间建立一条无向边，此关联权值就作为边的权值；
Sim(F1，F2)＝ω1*SimL(F1，F2)+ω2*SimV(F1，F2)+ω3*SimLV(F1，F2)其中，ω1、ω2、ω3表示为每个关联度分量分配的权重系数，其取值范围ω1为0.25～
0.35，ω2为0.15～0.25，ω3为0.45～0.55，可用基于遗传算法确定这些权值的最优值，Sim(F1，F2)表示查询接口表单F1和F2的关联权值，由此形成一个深层网页查询接口连接图，可用邻接矩阵FormLinkMatrix表示；
(6)利用聚类方法对查询接口表单带权无向连接图进行聚类；
(7)得到深层网页数据源聚类结果，结束。
2.根据权利要求1所述的基于查询接口连接图的深层网页数据源分类管理方法，其特征在于：所述步骤(4)中，从标签空间向量生成表单关联矩阵LableMatrix，从属性值空间向量生成表单关联矩阵ValueMatrix，从标签和属性值相结合空间向量生成表单关联矩阵LableValueMatrix。
3.根据权利要求1所述的基于查询接口连接图的深层网页数据源分类管理方法，其特征在于：所述步骤(5)中，从表单标签关联矩阵LableMatrix、表单属性值关联矩阵ValueMatrix以及表单标签和属性值相结合关联矩阵LableValueMatrix生成查询接口表单连接图。

基于查询接口连接图的深层网页数据源分类管理方法\n技术领域\n[0001] 本发明涉及一种信息自动分类管理方法，具体涉及一种应用于深层网页数据源的分类管理方法。\n背景技术\n[0002] 随着网络数据库的广泛应用，网络正在加速“深化”。互联网上有大量页面是由后台数据库动态产生，这部分信息不能直接通过静态链接获取，只能通过填写表单提交查询来获取，由于传统的网络爬虫(Crawler)不具有填写表单的能力，无法获取这些页面。因此，现有的搜索引擎搜索不出这部分页面信息，从而导致这部分信息对用户是隐藏、不可见的，我们称之为深层网络页面(Deep Web，又称为Invisible Web，Hidden Web)。Deep Web是一个与SurfaceWeb相对应的概念，最初由Dr.Jill Ellsworth于1994年提出，指那些由普通搜索引擎难以发现其信息内容的网络页面。Deep Web信息一般存储在数据库中，和静态页面相比通常信息量更大，主题更专一，信息质量更好，信息结构化更好，增长速度更快。\n研究表明，Deep Web信息是Surface Web信息的500倍，有近450,000个Deep Web站点。\n实现大规模Deep Web数据集成是方便用户使用Deep Web信息的一个有效途径。\n[0003] Deep Web数据源具有异构性、动态性、内容覆盖领域广等特征，海量的Deep Web信息无法由爬虫程序自动获得，只能将查询接口作为Web数据库的唯一入口，用户通过填写表单提交查询，获得查询相关结果。为了能够自动有效地利用自由分布在Web上的丰富资源并加以集成，以帮助用户方便地找到合适的数据库并检索到隐藏的信息，Deep Web数据源的自动分类管理显得尤为重要。很显然利用手工方式来组织信息是一件非常困难的事，目前对查询接口特征的研究为我们目前的工作提供了契机，对查询接口特征的研究方法有待于进一步深入，寻找新的方法实现对Deep Web数据源自动分类管理。分类和聚类是数据集成中数据源分类管理的重要方法，目前对查询接口研究的途径大多局限于分类聚类方法中的Web特征和文本信息的挖掘，未涉及新的途径，图模型的引入为我们对Deep Web数据源分类管理的研究提供了新的途径，这是研究者尚未涉足的领域。\n[0004] 将图挖掘运用于Deep Web数据源分类管理研究中，具有如下优点：首先，Deep Web突出表现为异构性和自治性，大量的Deep Web内部涉及多个领域，因此属于同一领域的Web之间就存在一定程度上的关联，完全符合一个Web图模型的构造过程，而且每个在线数据库的定义是不同的，彼此之间是异构的，这就为我们的信息集成带来了不便，运用图挖掘手段就能挖掘出Web彼此之间的关联特征并进行分类。其次，图挖掘可以发掘很多隐藏的主题特征，那么利用图结构，我们也可以发现隐藏于Deep Web中的多个领域主题。\n[0005] 为了有效地利用自由分布在Web上的丰富资源，帮助用户方便地找到合适的数据库并检索到隐藏的信息，需要这样一项技术，可以实现针对大规模Deep Web数据源进行自动分类管理。\n发明内容\n[0006] 本发明目的是提供一种自动的深层网页数据源分类管理方法，利用深层网页(Deep Web)数据源查询接口的丰富特征和图挖掘的方法，提高深层网页异构数据源的自动分类管理性能，以利于大规模数据集成的实现。\n[0007] 为达到上述目的，本发明的主要构思是：\n[0008] 我们主要针对结构化的查询接口进行聚类分析，结构化的查询接口包含多个属性信息，一个查询接口通常是一个Web页面中用HTML表示的表单。表单包含的控件可以分三大类：INPUT控件、SELECT控件和TEXTAREA控件，INPUT控件的TYPE属性描述了输入的类型元素，有Text、CheckBox、Radio、Submit、Reset、Radio、Image、Hidden八种。查询接口可形式化定义为F＝{a1，a2，...，an}，ai代表表单上的控件属性。每个控件都有相应的标签(Label)描述，即一个描述文本，每个控件可以有一个或多个值(value)。例如一个下拉列表有多个值供用户选择，单选按钮和复选框通常有一个值。逻辑上讲，一个控件和它关联的标签构成了一个属性(attribute)，对应了Deep Web后台数据库中的一个字段。通常一个属性包含一个标签，一个或多个表单控件。属性中的标签我们可以看作属性的名称(attribute name)，属性中的表单控件我们可以看作属性的值(attribute value)。查询接口则可以形式化描述为F＝{(L1，V1)，...，(Ln，Vn)}，其中Li代表标签值，Vi＝{Ej，...Ek}代表与标签对应的一个或多个控件属性值。\n[0009] 深层网页(Deep Web)数据源具有较强的异构性和互联性，因此，整个Deep Web可以抽象为一个异构多关系的图结构。图中的节点表示查询接口表单，图中的边表示查询接口表单之间的关联关系，我们用关联权值来表示二者之间的关联程度。\n[0010] 根据上述构思，本发明采用的技术方案是：一种基于查询接口连接图的深层网页数据源分类管理方法，包括下列步骤：\n[0011] (1)获取深层网页查询接口表单集合；\n[0012] (2)自动抽取步骤(1)获取的查询接口表单的特征值，所述特征值包括表单标签的名称以及属性值；\n[0013] (3)构造表单特征向量，包括，将提取的标签的名称和属性值分别构造特征空间LS和VS，对LS和VS中的每个表单形成的特征集合构造一个对应的特征向量，由此获得向量集合；\n[0014] (4)在步骤(3)获得的向量集合中，对每个向量之间通过相似性计算获得关于标签、属性值、标签与属性值组合的查询接口连接图，分别可用LableMatrix、ValueMatrix、LableValueMatrix邻接矩阵来表示，查询接口之间的关联度计算方法为：\n[0015] 在基于标签的表单关联度计算中，利用标签的相同特征项的数量进行衡量，并进行标准化，\n[0016] \n[0017] 其中，sw表示表单F1和F2具有相同标签的个数，len表示F1和F2中标签特征向量的平均长度，两者相除进行标准化，SimL(F1，F2)表示基于标签(Label，L)的表单F1和F2的关联权值；\n[0018] 基于属性值以及标签与属性值组合的表单关联度计算，我们利用其向量之间的相似度函数进行计算，\n[0019] \n[0020] 式中，W1k和W2k分别表示表单F1和F2中属性值(Value，V)集合构成的向量表示，利用向量余弦公式计算得到基于属性值的表单F1和F2的关联权值SimV(F1，F2)。基于标签与属性值(Label&Value，LV)组合的表单关联权值SimLV(F1，F2)与SimV(F1，F2)的计算方法类似，但其中W1k和W2k分别表示表单F1和F2中标签和属性值共同构成集合的向量表示；\n[0021] (5)构造查询接口连接图：\n[0022] 将步骤(4)得到的的三个矩阵LableMatrix、Valu eMatrix、LableValueMatrix进行加权合并，即将上述三个矩阵中的相似度值进行加权求和作为两两互连的查询接口表单之间的关联权值；按照带权无向连接图的构造方法，把每个查询接口作为图中的一个节点，为存在一定关联度的查询接口之间建立一条无向边，此关联权值就作为边的权值；\n[0023] Sim(F1，F2)＝ω1*SimL(F1，F2)+ω2*SimV(F1，F2)+ω3*SimLV(F1，F2)[0024] 其中，ω1、ω2、ω3表示为每个关联度分量分配的权重系数，其取值范围ω1为\n0.25～0.35，ω2为0.15～0.25，ω3为0.45～0.55，可用基于遗传算法确定这些权值的最优值。Sim(F1，F2)表示查询接口表单F1和F2的关联权值，由此形成一个深层网页查询接口连接图，可用邻接矩阵FormLinkMatrix表示；\n[0025] (6)利用聚类方法对查询接口表单带权无向连接图进行聚类；\n[0026] (7)得到深层网页数据源聚类结果，结束。\n[0027] 上述技术方案中，所述步骤(4)中，从标签空间向量生成表单关联矩阵LableMatrix，从属性值空间向量生成表单关联矩阵ValueMatrix，从标签和属性值相结合空间向量生成表单关联矩阵LableValueMatrix；\n[0028] 上述技术方案中，所述步骤(5)中，从表单标签关联矩阵LableMatrix、表单属性值关联矩阵ValueMatrix以及表单标签和属性值相结合关联矩阵LableValueMatrix生成查询接口表单连接图。\n[0029] 由于上述技术方案运用，本发明与现有技术相比具有下列优点：\n[0030] 本发明通过有效地构造Deep Web数据源查询接口连接图，结合图挖掘技术，提高了大规模Deep Web数据源自动分类管理的性能。\n附图说明\n[0031] 图1是本发明实施例中基于查询接口连接图的深层网页分类管理工作流程示意图；\n[0032] 图2是实施例中基于查询接口连接图的深层网页自动分类管理流程图；\n[0033] 图3是实施例中查询接口表单标签关联矩阵构造流程图；\n[0034] 图4是实施例中查询接口表单属性值关联矩阵构造流程图；\n[0035] 图5是实施例中查询接口表单标签及属性值关联矩阵构造流程图；\n[0036] 图6是实施例中查询接口连接图的构造示意图。\n具体实施方式\n[0037] 下面结合附图及实施例对本发明作进一步描述：\n[0038] 实施例一：参见附图1至附图6所示，一种基于查询接口连接图的深层网页数据源分类管理方法，包括下列步骤：\n[0039] (1)获取深层网页查询接口表单集合；\n[0040] (2)自动抽取步骤(1)获取的查询接口表单的特征值，所述特征值包括表单标签的名称以及属性值；\n[0041] (3)构造表单特征向量，包括，将提取的标签的名称和属性值分别构造特征空间LS和VS，对LS和VS中的每个表单形成的特征集合构造一个对应的特征向量，由此获得向量集合；\n[0042] (4)在步骤(3)获得的向量集合中，对每个向量之间通过相似性计算获得关于标签、属性值、标签与属性值组合的查询接口连接图，分别可用LableMatrix、ValueMatrix、LableValueMatrix邻接矩阵来表示，查询接口之间的关联度计算方法为：\n[0043] 在基于标签的表单关联度计算中，利用标签的相同特征项的数量进行衡量，并进行标准化，\n[0044] \n[0045] 其中，sw表示表单F1和F2具有相同标签的个数，len表示F1和F2中标签特征向量的平均长度，两者相除进行标准化，SimL(F1，F2)表示基于标签(Label，L)的表单F1和F2的关联权值；\n[0046] 基于属性值以及标签与属性值组合的表单关联度计算，我们利用其向量之间的相似度函数进行计算，\n[0047] \n[0048] 式中，W1k和W2k分别表示表单F1和F2中属性值(Value，V)集合构成的向量表示，利用向量余弦公式计算得到基于属性值的表单F1和F2的关联权值SimV(F1，F2)。基于标签与属性值(Label&Value，LV)组合的表单关联权值SimLV(F1，F2)与SimV(F1，F2)的计算方法类似，但其中W1k和W2k分别表示表单F1和F2中标签和属性值共同构成集合的向量表示；\n[0049] (5)构造查询接口连接图：\n[0050] 将步骤(4)得到的的三个矩阵LableMatrix、ValueMatrix、LableValueMatrix进行加权合并，即将上述三个矩阵中的相似度值进行加权求和作为两两互连的查询接口表单之间的关联权值；按照带权无向连接图的构造方法，把每个查询接口作为图中的一个节点，为存在一定关联度的查询接口之间建立一条无向边，此关联权值就作为边的权值；\n[0051] Sim(F1，F2)＝ω1*SimL(F1，F2)+ω2*SimV(F1，F2)+ω3*SimLV(F1，F2)[0052] 其中，ω1、ω2、ω3表示为每个关联度分量分配的权重系数，其取值范围ω1为\n0.25～0.35，ω2为0.15～0.25，ω3为0.45～0.55，可用基于遗传算法确定这些权值的最优值。Sim(F1，F2)表示查询接口表单F1和F2的关联权值，由此形成一个深层网页查询接口连接图，可用邻接矩阵FormLinkMatrix表示；\n[0053] (6)利用聚类方法对查询接口表单带权无向连接图进行聚类；\n[0054] 传统的划分方法是一种硬方法，把每个待处理的对象严格的划分到某个类中，例如C-均值算法，它的隶属度不是1就是0，这种严格的划分没能真实反映现实世界中对象与类之间不确定的隶属关系。在推广的模糊聚类算法中在隶属度函数中引入了权重指数。我们将模糊聚类(FCM)方法运用于查询接口连接图的聚类中，其计算简单且速度快，具有比较直观的几何意义。将已生成的表单连接图以邻接表形式输入，并对边的权值进行规则化，经过FCM聚类计算，得到查询接口表单的聚类簇。\n[0055] (7)得到深层网页数据源聚类结果，结束。