一种基于多阶段分层采样的层次聚类方法和系统

摘要

本发明公开一种基于多阶段分层采样的层次聚类方法和系统，该方法包括：将随机采样得到的初始样本集作为种子构建分层查询策略，并基于分层的估计方差被最小化原则，为每层查询策略分配相应的样本个数；利用分层查询策略对数据源进行分层采样，得到样本代表性较高的代表性样本集；对代表性样本集中的样本进行聚类，基于聚类所得簇的边界点对数据源进行二次采样，得到样本不确定性较高不确定性样本集；基于由初始样本集、代表性样本集及不确定性样本集构成的合集进行聚类，以估计数据源的聚类中心。可见，本发明通过多阶段分层采样保证了样本具有较高的代表性、不确定性，规避了随机采样样本代表性较差的问题，进而提高了数据源聚类的准确度。

说明书

技术领域

本发明属于Deep Web（深度网络）数据处理技术领域，尤其涉及一种基 于多阶段分层采样的层次聚类方法和系统。

背景技术

近年来，作为数据传播的一种方式，Deep Web（数据源）变得越来越流 行，相对于Surface Web（表层网络），Deep Web中蕴含了更高质量的数据， 从而在Deep Web上进行数据挖掘更具价值。而聚类作为数据挖掘研究领域一 个非常活跃的研究课题，可便于了解数据的分布情况，进而可以为后续对Deep  Web数据的应用提供参考依据，因此对Deep Web数据源进行聚类成为该领域 的研究热门。

Deep Web数据存储在后台数据库，只能通过查询接口提交查询获取相应 数据，无法直接获取后台全部数据。基于此种情况，当前，对Deep Web数据 源进行聚类一般采用如下方式：首先从Deep Web中进行随机采样，然后在随 机采样获得的样本上执行传统的聚类算法，例如K-Means或者层次聚类等， 以估算出Deep Web数据源的聚类中心。但该方式由于采用随机采样导致获取 的样本代表性较差、信息含量较低、进而导致聚类准确度较低。

发明内容

有鉴于此，本发明的目的在于提供一种基于多阶段分层采样的层次聚类 方法和系统，以克服现有由于采用随机采样而导致的样本代表性较差、聚类 准确度较低的问题。

为此，本发明公开如下技术方案：

一种基于多阶段分层采样的层次聚类方法，包括：

基于预设的输入属性集，从数据源中随机采样预设个数的样本，所采集 的预设个数的样本构成的集合标记为初始样本集；

利用所述初始样本集，构建基于所述输入属性集的M层查询策略，并基 于分层的估计方差被最小化原则，为所述M层查询策略中的每层查询策略分 配相应的样本个数，其中，所述估计方差基于估计均值获取，所述估计均值 具体为所述初始样本集输出属性值的平均值，所述M为大于1的自然数；

利用所述M层查询策略，对所述数据源进行分层采样，得到代表性较高 的样本，每层采样的样本个数为该层采样所使用的查询策略被分配的样本个 数，所述分层采样得到的所有样本构成代表性样本集；

对所述代表性样本集中的各样本进行聚类，得到k个簇，其中，每个簇 包括至少一个样本，所述k为大于1的自然数；

基于所述k个簇的边界点，对所述数据源进行边界点采样，得到不确定 性较高的样本，所述边界点采样得到的所有样本构成不确定性样本集；

对由所述初始样本集、代表性样本集以及不确定性样本集构成的合集中 的样本进行聚类，并估计聚类中心，估计出的聚类中心作为所述数据源的聚 类中心。

优选的，所述利用所述初始样本集构建基于所述输入属性集的M层查询 策略之前还包括：

设置迭代参数x，并为x赋值1。

优选的，所述对所述k个簇进行边界点采样，得到不确定性样本集之后， 还包括：

判断x的值是否小于预设的迭代次数β；

当判断结果为小于时，则x值加1，将所述初始样本集、所述代表性样本 集以及所述不确定性样本集进行合集，将所述合集替代所述初始样本集作为 新的初始样本集，并转至执行步骤：利用所述初始样本集，构建基于所述输 入属性集的M层查询策略；

当判断结果为不小于时，则转至执行步骤：对由所述初始样本集、代表 性样本集以及不确定性样本集构成的合集中的样本进行聚类，并估计聚类中 心，估计出的聚类中心作为所述数据源的聚类中心。

优选的，所述利用所述初始样本集，构建基于所述输入属性集的M层查 询策略具体包括：

利用所述初始样本集，构建基于所述输入属性集的策略树，所述策略树 中根节点除外的各层与所述输入属性集中的各输入属性一一对应，所述策略 树中每一节点对应相应输入属性的一个域值，策略树每层中各节点对应的输 入属性域值不同；

获取所述策略树中每一根节点至叶子节点的路径上包括的各个输入属性 及所述输入属性对应的域值，将所述各个输入属性及其对应的域值标记为该 叶子节点对应的查询策略。

优选的，所述方法，还包括：

抑制策略树构建过程中对策略树层次的过度分层。

优选的，所述数据源具体为Deep Web数据源。

一种基于多阶段分层采样的层次聚类系统，包括：

随机采样模块，用于基于预设的输入属性集，从数据源中随机采样预设 个数的样本，所采集的预设个数的样本构成的集合标记为初始样本集；

分层查询策略构建模块，用于利用所述初始样本集，构建基于所述输入 属性集的M层查询策略，并基于分层的估计方差被最小化原则，为所述M层 查询策略中的每层查询策略分配相应的样本个数，其中，所述估计方差基于 估计均值获取，所述估计均值具体为所述初始样本集输出属性值的平均值， 所述M为大于1的自然数；

分层采样模块，用于利用所述M层查询策略，对所述数据源进行分层采 样，得到代表性较高的样本，每层采样的样本个数为该层采样所使用的查询 策略被分配的样本个数，所述分层采样得到的所有样本构成代表性样本集；

初始聚类模块，用于对所述代表性样本集中的各样本进行聚类，得到k 个簇，其中，每个簇包括至少一个样本，所述k为大于1的自然数；

边界采样模块，用于基于所述k个簇的边界点，对所述数据源进行边界 点采样，得到不确定性较高的样本，所述边界点采样得到的所有样本构成不 确定性样本集；

聚类模块，用于对由所述初始样本集、代表性样本集以及不确定性样本 集构成的合集中的样本进行聚类，并估计聚类中心，估计出的聚类中心作为 所述数据源的聚类中心。

优选的，所述系统还包括：

设置模块，用于设置迭代参数x，并为x赋值1，所述设置模块与所述随 机采样模块以及所述分层查询策略构建模块相连；

判断模块，用于判断x的值是否小于预设的迭代次数β，若判断结果为 是，则x值加1，将所述初始样本集、所述代表性样本集以及所述不确定性样 本集进行合集，将所述合集替代所述初始样本集作为新的初始样本集，并转 至执行所述分层查询策略构建模块；若判断结果为否，则转至执行所述聚类 模块。

优选的，所述分层查询策略构建模块具体包括：

策略树构建单元，用于利用所述初始样本集，构建基于所述输入属性集 的策略树，所述策略树中根节点除外的各层与所述输入属性集中的各输入属 性一一对应，所述策略树中每一节点对应相应输入属性的一个域值，策略树 每层中各节点对应的输入属性域值不同；

查询策略获取单元，用于获取所述策略树中每一根节点至叶子节点的路 径上包括的各个输入属性及所述输入属性对应的域值，将所述各个输入属性 及其对应的域值标记为该叶子节点对应的查询策略。

优选的，所述分层查询策略构建模块还包括：

抑制单元，用于抑制策略树构建过程中对策略树层次的过度分层。

由于本发明采用多阶段分层采样，通过将随机采样所得的初始样本集作 为种子，利用该初始样本集构建用于对数据源进行分层采样的分层查询策略， 以及基于分层的估计方差被最小化原则，为每层查询策略分配相应的样本个 数，保证了对数据源进行分层采样所得样本的代表性；并通过对代表性样本 集进行聚类发现聚类所得簇的边界点，基于边界点对数据源进行二次采样， 保证了采集样本的不确定性；最终采集的样本包括了初始样本集、代表性样 本集以及不确定性样本集。可见，本发明采用的多阶段分层采样获得的样本 代表性较高、不确定性较高，具有较高的信息含量，规避了现有由于采用随 机采样获取样本而导致样本代表性较差的问题，后续基于由初始样本集、代 表性样本集以及不确定性样本集构成的合集进行聚类，估计数据源的聚类中 心，提高了数据源聚类的准确度。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实 施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面 描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不 付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是本发明实施例一提供的基于多阶段分层采样的层次聚类方法的一 种流程图；

图2是本发明实施例一提供的查询策略的构建过程流程图；

图3是本发明实施例一提供的策略树的实例示意图；

图4是本发明实施例二提供的基于多阶段分层采样的层次聚类方法的另 一种流程图；

图5是本发明实施例四提供的基于多阶段分层采样的层次聚类系统的一 种结构示意图；

图6是本发明实施例四提供的基于多阶段分层采样的层次聚类系统的另 一种结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发 明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述， 显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于 本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获 得的所有其他实施例，都属于本发明保护的范围。

本发明公开一种基于多阶段分层采样的层次聚类方法和系统，适用于对 Deep Web数据源进行聚类，估算Deep Web数据源的聚类中心。

由于Deep Web的后台数据库无法直接获得，想要获得整个Deep Web数 据源的数据并不现实，因此，对Deep Web进行聚类必须建立在采样获得的样 本之上，本发明旨在通过从Deep Web中采集信息含量较高的、能够反映Deep  Web数据分布的样本，对采集的样本进行聚类，来估算Deep Web的聚类中心， 以提高聚类的准确度。由于一个样本的代表性越高，此样本对于提高聚类的 效果就越有帮助，而一个样本的不确定性越大时，表明该样本的信息含量越 高，能有效提高聚类的准确度、精度，因此，本发明以样本的代表性、不确 定性作为衡量样本信息含量的指标。

在Deep Web环境下，考虑输出属性OS={O₁,O₂,...,O_q}的分布时，一般将 OS认为是统计变量。因此，当一个样本的输出属性平均值与真实环境下输出 属性的平均值非常接近时，可认为此样本为代表性样本。由于Deep Web数据 只能通过查询接口提交查询获取，无法直接获取后台全部数据，从而导致输 出属性的真实平均值无法直接获取，所以目标转化为寻找对输出属性平均值 的一个较好的估计。以下将通过各实施例对本发明的方法和系统进行详细说 明。

实施例一

本发明实施例一公开了一种基于多阶段分层采样的层次聚类方法，如图1 所示，该方法包括：

S1：基于预设的输入属性集，从数据源中随机采样预设个数的样本，所 采集的预设个数的样本构成的集合标记为初始样本集。

其中，数据源可以是无法直接获取、而需要通过查询接口提交查询获取 的后台数据，本实施例中，数据源具体为Deep Web数据源。

本步骤S1从Deep Web中随机采集预设个数的样本，一般情况下，此阶 段的随机采样的样本个数为实现聚类共需采样样本个数的一半。本实施例中， 假设实现对目标Deep Web（数据源）进行聚类共需采集2X个样本，则此阶 段从该Deep Web中随机采样X个样本，其中，X为大于1的自然数。

S2：利用所述初始样本集，构建基于所述输入属性集的M层查询策略， 并基于分层的估计方差被最小化原则，为所述M层查询策略中的每层查询策 略分配相应的样本个数，其中，所述估计方差基于估计均值获取，所述估计 均值具体为所述初始样本集输出属性值的平均值，所述M为大于1的自然数。

其中，请参见图2，利用初始样本集，构建基于输入属性集的M层查询 策略具体包括：

S201：利用所述初始样本集，构建基于所述输入属性集的策略树，所述 策略树中根节点除外的各层与所述输入属性集中的各输入属性一一对应，所 述策略树中每一节点对应相应输入属性的一个域值，策略树每层中各节点对 应的输入属性域值不同；

具体地，对于目标Deep Web，IS={I₁,I₂,...,I_p}表示输入属性的集合， OS={O₁,O₂,...,O_q}表示输出属性的集合，其中，每个输入属性关联相应的属性 取值领域（包括一定个数的域值）。

本步骤S2以随机采样所得的初始样本集为种子，利用该初始样本集构建 用于对Deep Web进行分层采样的各层查询策略。具体地，利用初始样本集通 过对输入属性进行分层构建一棵查询空间的策略树，最终查询策略在该树的 叶子节点上获取，策略树的构建过程如下：

首先，创建根节点，其中，根节点对应包含全部查询策略的查询空间。

其次，通过分裂上层节点的查询空间获取下层节点，实现获取策略树的 各层节点，最终实现构建策略树。策略树构建过程中，对于树中待分裂的某 一节点（待分裂时刻，该节点为当前树中的叶子节点），Q表示其对应的查询 空间，它由输入属性的集合组成，记为：SI，该叶子节点LN关联的潜在分裂 输入属性PI=IS-SI，PI包含那些没有包含在Q中的输入属性的集合。在LN 的查询子空间下，输出属性O_j∈OS的方差可以通过公式（1）计算：

$\mathrm{Var}\left(O_j\right)=\frac{1}{n}\times \underset{i=1}{\overset{n}{\Sigma }}{(x_i-{\bar{x}}_i)}^2---\left(1\right)$

其中，x_i表示输出属性O_j的取值，表示对输出属性O_j的估计均 值，n表示初始样本在LN查询空间下的样本个数。

对于潜在分裂输入属性P_i∈PI，假设其关联的属性取值领域为 DM_i={a_i,1,…,a_i,t}，则对于输出属性O_j∈OS的方差下降可通过如下公式(2)计算：

$\Delta {\mathrm{Var}}_{i,j}=\mathrm{Var}\left(O_j\right)-\underset{k}{\Sigma }p(P_i=a_{i,k}|Q)\times {\mathrm{Var}}_k\left(O_j\right)---\left(2\right)$

其中，表示在查询空间Q下，输入属性P_i指定 取值为a_i,k时的条件概率。此处，本实施例作出一个假设，即假设deep web 数据源提供输入属性的先验概率，例如与p(Q)，从而可以计算出条件概率 p(P_i=a_i,k|Q)。

在使用潜在分裂输入属性P_i∈PI对LN下的查询空间分层时，通过对潜在 分裂输入属性P_i指定属性值（域值），LN下可以产生t个潜在的子结点。Var_k(O_j) 表示在第k个潜在子结点下输出属性O_j的方差，其获取方法与Var(O_j)相似， 可参考公式（1）。与计算输出属性OS的方差下降类似，对于潜在分裂输入属 性P_i∈PI，输出属性OS的方差下降ΔVar_i为每个输出属性方差下降的和：

$\Delta {\mathrm{Var}}_i=\underset{j}{\Sigma }\Delta {\mathrm{Var}}_{i,j}---\left(3\right)$

基于公式（3）可以获取拥有最大方差下降的潜在分裂输入属性P_i，该潜 在分裂输入属性P_i被用于分裂LN的查询子空间。最终，通过多次节点分裂获 取所需的策略树，查询策略在该树的叶子节点上获取，且初始样本集中所有 样本均对应分配在相应叶子节点的查询策略下。

此处，需要说明的是，分层采样中的“层”与查询策略的层次相对应， 其与策略树的层次为不同概念，查询策略的层次数具体是指最终构建的策略 树中叶子节点的个数，每个叶子节点对应一个查询策略，若策略树中有x个 叶子节点，即表示共可获取x个查询策略，相应可对Deep Web进行x层采样。

S202：获取所述策略树中每一根节点至叶子节点的路径上包括的各个输 入属性及所述输入属性对应的域值，将所述各个输入属性及其对应的域值标 记为该叶子节点对应的查询策略。

请参见图3，图3为本实施例提供的策略树的一个示例，其中，叶子节点 LN对应的查询策略为（I1=1980，I2=1）。

在构建对Deep Web进行分层查询的各层查询策略后，接下来对各层查询 策略分配需要采样的个数。基于尽可能从Deep Web中采集代表性较高的样本 这一原则，本发明采用Neymann分配为各层查询策略分配样本个数，其建立 在分层的估计方差被最小化的基础上，当第i层的样本大小与层的大小以及第 i层目标属性的方差成比例时，分层的估计方差会被最小化。在Deep Web环 境下，目标属性指输出属性的取值。

对于输出属性O_j∈OS，x_j表示O_j的取值，表示初始样本集在第i层查 询策略下的样本的输出属性O_j取值的平均值。则可以通过如下公式(4)估计输 出属性O_j的平均值：

${\bar{x}}_j={\Sigma }_{i=1}^H\frac{N_i}{N}{\bar{x}}_{j,i}---\left(4\right)$

其中，N表示Deep Web中总体数据记录（一个样本对应一条数据记录） 的数目，N_i表示Deep Web中由第i层查询策略划分的子层包含数据记录的数 目，H表示查询策略的层数，即策略树中叶子节点的个数。

预先设定分层采样阶段共需采样n个样本，其中，n＜X，对于某个特定 的输出属性O_j∈OS，为了减小估计均值的方差，对于第i层需要采样的样本数 ni可以通过如下公式(5)计算：

$n_i=\frac{n}{{\Sigma }_r{N}_r{\sigma }_r}{N}_i{\sigma }_i---\left(5\right)$

其中，是第r层输出属性O_j的方差。在执行采样分配的时候，需要将 输出属性集合OS当作一个整体来考虑。表示对输出属性O_j∈OS估计均 值的方差，则输出属性集合OS的估计均值的方差和可表示为 为了最小化输出属性集合OS的方差，采样样本分配的个 数ni可以通过公式(6)计算：

$n_i=\frac{n}{{\Sigma }_r{N}_r{\sigma }_r^{\prime }}{N}_i{\sigma }_i^{\prime }---\left(6\right)$

其中，是和的平方根，表示第i层的输出属性O_j∈OS的 方差。因此，本发明方法倾向在输出属性方差较大的层采集更多的样本，从 而可以最小化总体的综合方差。

可见，本实施例的样本个数分配基于分层的估计方差被最小化原则，保 证了后续分层采样样本具有较高的代表性。

S3：利用所述k层查询策略，对所述数据源进行分层采样，得到代表性 较高的样本，每层采样的样本个数为该层采样所使用的查询策略被分配的样 本个数，所述分层采样得到的所有样本构成代表性样本集。

本步骤基于构建的各层查询策略，以及为各层查询策略对应分配的样本 个数，从Deep Web中进行分层采样。采样所得的各样本具有较高的代表性。

S4：对所述代表性样本集中的各样本进行聚类，得到k个簇，其中，每 个簇包括至少一个样本，所述k为大于1的自然数。

为了从Deep Web中获取更多的更具信息含量的样本，在分层采样获得代 表性样本之后，本发明对分层采样所得的各代表性样本进行初始聚类，并在 聚类的基础上对Deep Web进行二次采样。具体地，本实施例采用一种改进的 层次聚类方法对代表性样本集进行初始聚类。用NS表示分层采样获得的代表 性样本集，假设在第i层采样了n_i个样本，Deep Web中由第i层查询策略划分 的子层包含数据记录的数目为N_i，则每个样本代表Deep Web中条记录， 从而用代表每个样本的权值。

与传统的层次聚类方法类似，本实施例的分层层次聚类的每一步都会将 拥有最小距离的两个簇合并成一个簇，直到剩下k个簇为止，其中，k为是预 先设定的数值，k为大于1的自然数。两条数据记录（样本）之间的距离可以 使用数据记录包含的输出属性的欧式距离来计算，例如：对于两条数据记录 D₁∈NS,D₂∈NS，该两条数据记录的距离Dist(D_l，D₂)可以通过公式(7)来计算， 其中，输出属性O_j∈OS：

$\mathrm{Dist}(D_1,D_2)=\sqrt{{\Sigma }_j{(O_{1,j}-O_{2,j})}^2}---\left(7\right)$

计算两个簇之间的距离Dist(C₁，C₂)时，本发明使用所有数据记录的加权平 均距离取代原始计算距离的方法，如公式(8)所示，其中，D_i∈C₁,D_j∈C₂，C_i表 示簇，w_i,w_j表示D_i,D_j关联的权值：

$\mathrm{Dist}(C_1,C_2)=\frac{{\Sigma }_i{\Sigma }_j{w}_i\times w_j\times \mathrm{Dist}(D_i,D_j)}{{\Sigma }_i{\Sigma }_j{w}_i\times w_j}---\left(8\right)$

第i个簇的中心向量计算也运用加权平均的方法获得，如公式(9)所示：

${\bar{m}}_i=\frac{{\Sigma }_r{w}_r\times o_r}{{\Sigma }_r{w}_r}---\left(9\right)$

簇的半径通过公式如下(10)估计，其中，表示输出属性上的 欧式距离：

${\bar{R}}_i=\frac{{\Sigma }_r{w}_r\times \mathrm{Dist}(o_r,{\bar{m}}_i)}{{\Sigma }_r{w}_r}---\left(10\right)$

S5：基于所述k个簇的边界点，对所述数据源进行边界点采样，得到不 确定性较高的样本，所述边界点采样得到的所有样本构成不确定性样本集。

一个样本的不确定性越大，则该样本的信息含量就越高，利用该样本能 提高对数据源聚类的准确率。通过在代表性样本集上执行初始聚类，有利于 发现边界点，簇边界附近样本点具有较大的不确定性，即具有较高的信息含 量。基于此，本步骤S5在初始聚类获得k个簇的基础上，获取各个簇的边界 样本点。

具体地，对于某个簇i中的样本p，p到该簇i中心的距离记为d(p,m_i)， 若存在某个簇l，l≠i，满足如下条件：

$o\le d(p,m_i)-d(p,m_l)\le ({\bar{R}}_i+{\bar{R}}_l)\times \theta ---\left(11\right)$

则样本p可以被认为是簇i的边界样本点，其中，θ是预先设定的值，与分别表示簇i与l的半径。

由于初始聚类基于分层采样所得的代表性样本集，结合主动学习的不确 定性衡量指标，本发明倾向于基于包含更多边界点的层采集更多的样本。对 于分层采样中的某个层，Q_t∈QS代表此层所对应的查询策略，其对应包含边 界点的概率表示为其中n_t,b表示该层对应包含的边界点的个数，n_t为层中包含的样本的数目，这两个值都可在代表性采样阶段获得。形式上， 基于包含边界点的层，采用该层的查询策略Q_t需要从Deep Web中进行边界采 样的样本数目nt_′可用公式(12)计算：

$n_t^{\prime }=\frac{p\left(Q_t\right)\times U_t}{{\Sigma }_{r}p\left(Q_r\right)\times U_r}\times m---\left(12\right)$

其中，m表示边界采样阶段需要采集的样本数目，m=X-n。

S6：对由所述初始样本集、代表性样本集以及不确定性样本集构成的合 集中的样本进行聚类，并估计聚类中心，估计出的聚类中心作为所述数据源 的聚类中心。

本步骤基于分阶段采样所得的全部样本进行聚类，估计聚类中心，估计 出的聚类中心作为Deep Web的聚类中心。具体地，分阶段采样所得样本包括： 随机采样获得的X个样本、分层采样所得的n个样本以及边界点采样所得的 m个样本，共2X个样本。本步骤的聚类所采用的具体方法与上述初始聚类的 过程类似，具体请参考以上初始聚类的描述过程，此处不再详述。

本实施例中，分层采样的样本个数n与边界采样的样本个数m之和为X， 即总体所需采样样本个数的一半，其中，n与m的具体数值的分配，可由本 领域技术人员基于采集样本的信息含量最大化这一原则依据经验而定，本发 明中，n与m具体采用3:1的比例。

综上，由于本发明采用多阶段分层采样，通过将随机采样所得的初始样 本集作为种子，利用该初始样本集构建用于对数据源进行分层采样的分层查 询策略，以及基于分层的估计方差被最小化原则，为每层查询策略分配相应 的样本个数，保证了对数据源进行分层采样所得样本的代表性；并通过对代 表性样本集进行聚类发现聚类所得簇的边界点，基于边界点对数据源进行二 次采样，保证了采集样本的不确定性；最终采集的样本包括了初始样本集、 代表性样本集以及不确定性样本集。可见，本发明采用的多阶段分层采样获 得的样本代表性较高、不确定性较高，具有较高的信息含量，规避了现有由 于采用随机采样获取样本导致样本代表性较差的问题，后续基于由初始样本 集、代表性样本集以及不确定性样本集构成的合集进行聚类，估计数据源的 聚类中心，提高了数据源聚类的准确度。

实施例二

本发明实施例二公开了基于多阶段分层采样的层次聚类方法的另一种流 程，请参见图4，其在实施例一的方法的基础上，还包括：

S7：设置迭代参数x，并为x赋值1。

本步骤S7具体在步骤S1及S2之间。

S8：判断x的值是否小于预设的迭代次数β。若判断结果为是，则执行 步骤S9；否则，若判断结果为否，则执行步骤S6。

S9：x值加1，将所述初始样本集、所述代表性样本集以及所述不确定性 样本集进行合集，将所述合集替代所述初始样本集作为新的初始样本集。转 至执行步骤S2。

为了从Deep Web中采集更具信息含量的样本，本实施例继续对实施例一 种的方法进行优化，在多阶段采样中的分层采样和边界点采样阶段，设计了 一个调节因子β，使分层采样和边界点采样共迭代β次完成X个样本的采集， β的大小视X的大小而定。每次迭代完成X/β个样本的采集，其中，分层采 样的样本数目n’与边界点采样的样本数目m’的比例为3:1，每次迭代中， 构建分层查询策略所使用的样本集均为上次迭代前使用的初始样本与上次迭 代所采集的代表性样本、不确定性样本的合集。

实施例三

本实施例三继续对实施例一和实施例二中的方法进行优化，其在以上实 施例的基础上，还包括：抑制策略树构建过程中对策略树层次的过度分层。

由于分层可能会涉及到过度分层的问题，而过度分层会导致分层采样的 结果恶化。因此，本实施例通过统计假设测试检验输出属性的方差下降是否 是有意义的，来决定在构建策略树时，是否对策略树继续分层，若输出属性 的方差下降有意义，则继续对策略树的当前节点LN进行分层，若无意义，则 终止策略树中当前节点LN的分层。具体通过如下思想进行检验：当潜在分裂 属性P_i与输出属性集合之间没有重大的联系时，在结点LN下输出属性OS的 分布将与其子节点中的相似，从而导致方差下降非常小，即无意义；相反， 当在分裂属性P_i与输出属性集合之间有很强的联系时，输出属性的方差下降将 变得十分有意义。

基于以上思想，本发明使用卡方假设检验，H₀：P_i与输出属性集合OS 之间不存在有意义的联系；H₁：P_i与输出属性集合OS之间存在有意义的联系。 假设检验的判别规则建立在统计数s之上，s可以通过如下公式(13)计算：

$s=-n^{,,}\times \ln \left(\begin{array}{c}{\Sigma }_{\mathrm{sub}}|\\ \left|\Sigma \right|\end{array}\right)---\left(13\right)$

其中，n”代表初始样本在LN查询策略下的样本个数，｜Σ｜表示在LN查 询策略下输出属性集合OS协方差Σ的行列式，Σ_sub表示协方差矩阵Σ_sub的行 列式值。

协方差Σ可以通过如下公式(14)估计算：

$\Sigma =\frac{{\Sigma }_l(o_l-\hat{o})\times {(o_l-\hat{o})}^{\prime }}{n}---\left(14\right)$

其中，o_l表示OS中输出属性取值的向量，表示平均向量，可以通过 公式(15)计算。

$\hat{o}=\frac{{\Sigma }_l{o}_l}{n}---\left(15\right)$

Σ_sub为潜在子节点LF查询子空间的协方差矩阵的加权和：

Σ_sub=∑_kp(P_i=a_i,k|Q)×Σ_k               (16)

其中，Σ_k表示在第k个潜在子节点LF的查询空间之下输出属性OS的协 方差，计算方法与公式(14)相似。

在空假设H₀下，统计数s服从自由度q(t-1)的卡方检验分布，其中q=|OS| 表示输出属性的个数，t=|DM_i|表示潜在分裂属性P_i取值领域的大小。当显著 水平为95%时，判别规则如下：当统计数s>χ_0.05(q(t-1))，拒绝空假设H₀，则 可以得出结论P_i与OS之间没有重大的联系，其中，χ_0.05可以通过查询标准统 计学的概率表获得。

实施例四

本发明实施例四公开一种基于多阶段分层采样的层次聚类系统。相应于 实施例一中公开的基于多阶段分层采样的层次聚类方法的流程，本实施例首 先公开该系统的一种结构，请参见图5，其包括随机采样模块100、分层查询 策略构建模块200、分层采样模块300、初始聚类模块400、边界采样模块500 和聚类模块600。

随机采样模块100，用于基于预设的输入属性集，从数据源中随机采样预 设个数的样本，所采集的预设个数的样本构成的集合标记为初始样本集。

分层查询策略构建模块200，用于利用所述初始样本集，构建基于所述输 入属性集的M层查询策略，并基于分层的估计方差被最小化原则，为所述M 层查询策略中的每层查询策略分配相应的样本个数，其中，所述估计方差基 于估计均值获取，所述估计均值具体为所述初始样本集输出属性值的平均值， 所述M为大于1的自然数。

其中，分层查询策略构建模块200具体包括策略树构建单元和查询策略 获取单元。策略树构建单元，用于利用所述初始样本集，构建基于所述输入 属性集的策略树，所述策略树中根节点除外的各层与所述输入属性集中的各 输入属性一一对应，所述策略树中每一节点对应相应输入属性的一个域值， 策略树每层中各节点对应的输入属性域值不同；查询策略获取单元，用于获 取所述策略树中每一根节点至叶子节点的路径上包括的各个输入属性及所述 输入属性对应的域值，将所述各个输入属性及其对应的域值标记为该叶子节 点对应的查询策略。

分层采样模块300，用于利用所述M层查询策略，对所述数据源进行分 层采样，得到代表性较高的样本，每层采样的样本个数为该层采样所使用的 查询策略被分配的样本个数，所述分层采样得到的所有样本构成代表性样本 集。

初始聚类模块400，用于对所述代表性样本集中的各样本进行聚类，得到 k个簇，其中，每个簇包括至少一个样本，所述k为大于1的自然数。

边界采样模块500，用于基于所述k个簇的边界点，对所述数据源进行边 界点采样，得到不确定性较高的样本，所述边界点采样得到的所有样本构成 不确定性样本集。

聚类模块600，用于对由所述初始样本集、代表性样本集以及不确定性样 本集构成的合集中的样本进行聚类，并估计聚类中心，估计出的聚类中作为 所述数据源的聚类中心。

相应于实施例二中基于多阶段分层采样的层次聚类方法的流程，本实施 例继续公开该系统的另一种结构，其除了包括以上各模块、单元之外，如图6 所示，还包括设置模块700和判断模块800。

其中，设置模块700，用于设置迭代参数x，并为x赋值1，该设置模块 700与随机采样模块100以及分层查询策略构建模块200相连。

判断模块800，用于判断x的值是否小于预设的迭代次数β，若判断结果 为是，则x值加1，将所述初始样本集、所述代表性样本集以及所述不确定性 样本集进行合集，将所述合集替代所述初始样本集作为新的初始样本集，并 转至执行分层查询策略构建模块200；若判断结果为否，则转至执行聚类模块 600。

相应于实施例三中基于多阶段分层采样的层次聚类方法的流程，本实施 例四公开的系统还包括抑制单元，用于抑制策略树构建过程中对策略树层次 的过度分层。

对于本发明实施例四公开的基于多阶段分层采样的层次聚类系统而言， 由于其与以上各实施例公开的基于多阶段分层采样的层次聚类方法相对应， 所以描述的比较简单，相关相似之处请参见以上各实施例中基于多阶段分层 采样的层次聚类方法部分的说明即可，此处不再详述。

综上所述，本发明借鉴主动学习的思想，使用代表性和不确定性来度量 样本的重要程度，将代表性、不确定性较高的样本作为信息含量较高的样本。 在采样阶段，规避现有的随机采样的方式，具体采用多阶段分层采样，并采 用多次迭代的样本分配策略提高采样样本的代表性。每次迭代中样本重新分 配（分层采样样本和边界采样样本分配）后，首先采集部分代表性样本进行 初始聚类，聚类所得簇的边界附近样本点具有较大的不确定性，即具有较高 的信息量，基于这些边界点在DeepWeb数据源进行二次采样，提高了采集到 的样本的代表性，进而提高了聚类的准确度。

需要说明的是，本说明书中的各个实施例均采用递进的方式描述，每个 实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似 的部分互相参见即可。

为了描述的方便，描述以上装置、系统时以功能分为各种模块或单元分 别描述。当然，在实施本申请时可以把各模块或单元的功能在同一个或多个 软件和/或硬件中实现。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普 通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润 饰，这些改进和润饰也应视为本发明的保护范围。