一种基于网址结构的网络论坛页面聚类方法及设备

摘要

本发明涉及一种基于网址结构的网络论坛聚类方法及设备，该方法涉及数据挖掘领域，是为解决大规模网页分类问题而提出的。该方法从网址总体中抽取部分样本，利用网络论坛网址高度结构化的特性，对每个网址进行结构划分，构造结构向量，使用本发明提出的距离函数评估结构向量之间的距离，接着使用密度峰值聚类方法对样本结构向量进行聚类分析，提取出每簇的特征结构，构造用于描述簇中所有样本网址的解析器，用于对总体中剩余网址进行解析和分类。经实验验证，本方法具有较高的准确度和执行效率。

说明书

技术领域

本发明属于网络数据挖掘的技术领域，尤其涉及一种基于网址结构的网络论坛页面聚类方法及设备。

背景技术

网址是用于唯一确定一个网页的基本特征。而页面分类对网络数据挖掘具有重要意义，是对不同种类页面进行后续处理前的最重要的准备工作。目前，对网页进行分类的方法有根据语义结构进行分类；使用遗传算法，以网页标签和属性为分类特征进行分类；利用上下文特征，使用支持向量机进行分类。使用蚁群算法根据优选特征进行分类等等。但是，在实际中，论坛页面之间的共性并不显著，使得网页特征提取具有随意性；此外，网络论坛中页面众多，上述方法均难以满足大规模分类的速度需求。目前，基于论坛页面网址结构，构造结构向量进行聚类分析的方法尚未出现。

综上所述，在现有技术中针对网络论坛页面如何有效进行网页分类，提高网页分类的准确度与效率的问题，尚缺乏有效的解决方案。

发明内容

本发明为了解决上述问题，提供一种基于网址结构的网络论坛页面聚类方法及设备。本发明根据网址构造结构向量，并计算结构向量之间的相异度，使得可以使用聚类分析方法对网页进行分类，针对网络论坛页面有效实现网页分类，提高网页分类的准确度与效率。

本发明的第一目的是提供一种基于网址结构的网络论坛页面聚类方法。

为了实现上述目的，本发明采用如下一种技术方案：

一种基于网址结构的网络论坛页面聚类方法，该方法包括以下步骤：

(1)按照网页所属域名对所有网页进行初步分组，对于初步分组后的每一组网页进行抽样组成样本，并在样本中插入带标记的待筛选网页形成样本网页；

(2)将样本网页的除域名外的网址根据符号进行分割，对分割后的每一部分网址的类别和内容进行编号，构造出结构块；

(3)将同一网址的各个结构块按顺序依次排列，构成该网址的结构向量；计算样本网页中的任意两个结构向量的相异度，和网页样本中最小较高密度结构向量相异度即任意一个结构向量与大于其局部密度且与其相异度最小的结构向量的相异度；分别作为横坐标和纵坐标构造决策图，确定簇中心，采用广度优先结构向量归属确定法确定非簇中心结构向量的归属簇；

(4)根据步骤(3)的决策图构造出解析规则，将解析规则应用于初步分组后的每一组网页中的非样本网页，进行网页聚类筛选，并采用评价指标进行评价。

进一步的，所述步骤(2)中构造的结构块，用于定量表示网页分割后每部分网址的结构；其构造的具体步骤为：

将样本网页的除域名外的网址根据符号进行分割，判断分割后的每一部分网址的类别和内容是否已有编号；

若某类别或内容已有编号，则采用此编号；

否则，赋予该部分网址的类别和内容一个新编号；

重复上述步骤，直至构成所有样本网页的结构块。

进一步的，所述步骤(3)中网址的结构向量，将结构块组合以表示完整网址的结构；一个结构向量S(u)由若干结构块编号元组p(u,i)组成：

p(u，i)＝(t(u,i),v(u,i))(1)

S(u)＝{p(u，i)|i＝1，2，…，N}(2)

其中，u为网址，i为网址中第i个结构块，t(u,i)为类别编号，v(u,i)为值即内容编号，p(u,i)为结构块编号元祖，N为总结构块数，S(u)为结构向量。

进一步的，所述步骤(3)中样本网页中的任意两个结构向量的相异度的计算方法为：

其中，u_m,u_n为不同的网址，p(u,i)为结构块编号元组,i为网址中第i个结构块，N为总结构块数，D(u_m,u_n)为网址u_m,u_n的相异度。

进一步的，所述步骤(3)中计算网页样本中最小较高密度结构向量相异度的具体步骤为：

对网页样本中的每个结构向量，分别计算其局部密度；

对于网页样本中的任一结构向量，判断其局部密度与其他结构向量的局部密度，在局部密度大于其局部密度的结构向量中，比较该结构向量与其他大于其局部密度的结构向量的相异度，选择最小的相异度作为网页样本中该结构向量的最小较高密度结构向量相异度。

进一步的，所述步骤(3)中结构向量的局部密度ρ_i为：

其中，KNN(i)为结构向量i的K近邻集合，d_ij为结构向量i与结构向量j的相异度，ρ_i为结构向量i的局部密度；

所述步骤(3)中最小较高密度结构向量相异度δ_i为：

其中，δ_i为结构向量i的最小较高密度结构向量相异度。

进一步的，所述步骤(3)中构造决策图的具体步骤为：

分别以每个结构向量的ρ_i值和δ_i值为横纵坐标做散点图；

选择ρ_i值和δ_i值均较高的若干结构向量作为聚类的簇中心；

采用广度优先结构向量归属确定法确定非簇中心结构向量的归属簇；

进一步的，所述步骤(3)中采用广度优先结构向量归属确定法确定非簇中心结构向量的归属簇的具体步骤为：

对于每个簇中心，将其K近邻的结构向量加入该簇，并加入队列；

每次取队列队首的结构向量，对于其K近邻的结构向量，判断其是否被分配至任何簇，若未被分配至任何簇，则加入队首所在簇并加入队列；

重复上述步骤直至确认除簇中心的结构向量外的其他结构向量的归属。

进一步的，所述步骤(4)中构造出解析规则的具体步骤为：

在决策图中，选出样本网页中插入的带标记的待筛选网页所在的簇；

在选出的簇中，对于该网页结构向量中的每个位置，记录所有该位置的结构块的类别和内容，当出现超过5种不同的内容时，不再记录内容，仅记录类别；

得到解析规则。

进一步的，所述步骤(4)中采用评价指标进行评价时，分别采用召回率R，准确率P和F值进行聚类评价的指标：

其中，N_et为提取待筛选网页数，N_t为待筛选网页数，N_e为提取数。

F值越高，则说明信息提取效果越好。

本发明的第二目的是提供一种基于网址结构的网络论坛页面聚类方法的存储设备。

为了实现上述目的，本发明采用如下一种技术方案：

一种存储设备，其中存储有多条指令，所述指令适于由处理器加载并执行：

(1)按照网页所属域名对所有网页进行初步分组，对于初步分组后的每一组网页进行抽样组成样本，并在样本中插入带标记的待筛选网页形成样本网页；

(2)将样本网页的除域名外的网址根据符号进行分割，对分割后的每一部分网址的类别和内容进行编号，构造出结构块；

(3)将同一网址的各个结构块按顺序依次排列，构成该网址的结构向量；计算样本网页中的任意两个结构向量的相异度，和网页样本中最小较高密度结构向量相异度即任意一个结构向量与大于其局部密度且与其相异度最小的结构向量的相异度；分别作为横坐标和纵坐标构造决策图，确定簇中心，采用广度优先结构向量归属确定法确定非簇中心结构向量的归属簇；

(4)根据步骤(3)的决策图构造出解析规则，将解析规则应用于初步分组后的每一组网页中的非样本网页，进行网页聚类筛选，并采用评价指标进行评价。

本发明的第三目的是提供一种基于网址结构的网络论坛页面聚类方法的终端设备。

为了实现上述目的，本发明采用如下一种技术方案：

一种终端设备，包括：

处理器，适于实现各指令；以及

存储设备，适于存储多条指令，所述指令适于由处理器加载并执行：

(1)按照网页所属域名对所有网页进行初步分组，对于初步分组后的每一组网页进行抽样组成样本，并在样本中插入带标记的待筛选网页形成样本网页；

(2)将样本网页的除域名外的网址根据符号进行分割，对分割后的每一部分网址的类别和内容进行编号，构造出结构块；

(3)将同一网址的各个结构块按顺序依次排列，构成该网址的结构向量；计算样本网页中的任意两个结构向量的相异度，和网页样本中最小较高密度结构向量相异度即任意一个结构向量与大于其局部密度且与其相异度最小的结构向量的相异度；分别作为横坐标和纵坐标构造决策图，确定簇中心，采用广度优先结构向量归属确定法确定非簇中心结构向量的归属簇；

(4)根据步骤(3)的决策图构造出解析规则，将解析规则应用于初步分组后的每一组网页中的非样本网页，进行网页聚类筛选，并采用评价指标进行评价。

本发明的有益效果：

本发明的一种基于网址结构的网络论坛页面聚类方法及设备，根据网址构造结构向量，并计算结构向量之间的相异度，使得可以使用聚类分析方法对网页进行分类，具有高准确度和执行效率。尤其针对共性不显著的论坛页面，本发明构造结构向量进行聚类分析，满足大规模分类的速度需求。

附图说明

图1为本发明整体方法的流程图。

具体实施方式：

应该指出，以下详细说明都是例示性的，旨在对本申请提供进一步的说明。除非另有指明，本发明使用的所有技术和科学术语具有与本申请所属技术领域的普通技术人员通常理解的相同含义。

需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本申请的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。

在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。下面结合附图与实施例对本发明作进一步说明。

实施例1：

正如背景技术所介绍的，本发明为了解决上述问题，提供一种基于网址结构的网络论坛页面聚类方法及设备。本发明根据网址构造结构向量，并计算结构向量之间的相异度，使得可以使用聚类分析方法对网页进行分类，针对网络论坛页面有效实现网页分类，提高网页分类的准确度与效率。

为了实现上述目的，本发明采用如下一种技术方案：

一种基于网址结构的网络论坛页面聚类方法，该方法包括以下步骤：

(1)按照网页所属域名对所有网页进行初步分组，对于初步分组后的每一组网页进行抽样组成样本，并在样本中插入带标记的待筛选网页形成样本网页；

(2)将样本网页的除域名外的网址根据符号进行分割，对分割后的每一部分网址的类别和内容进行编号，构造出结构块；

(3)将同一网址的各个结构块按顺序依次排列，构成该网址的结构向量；计算样本网页中的任意两个结构向量的相异度，和网页样本中最小较高密度结构向量相异度即任意一个结构向量与大于其局部密度且与其相异度最小的结构向量的相异度；分别作为横坐标和纵坐标构造决策图，确定簇中心，采用广度优先结构向量归属确定法确定非簇中心结构向量的归属簇；

(4)根据步骤(3)的决策图构造出解析规则，将解析规则应用于初步分组后的每一组网页中的非样本网页，进行网页聚类筛选，并采用评价指标进行评价。

在本实施例中，利用网络爬虫在互联网上随机爬取了若干网页，经过人工去除非论坛网页、广告页等无关网页，剩余有效网页数13346，其中主题帖网页数5888，在所有有效网页中，Discuz！论坛页面11822，独立论坛页面数1524。这些页面来自不同领域不同话题的论坛。本实施例旨在筛选出主题帖页面。

如图1所示，

步骤一：对网页进行初步分组。同一论坛内的网址在结构上呈现高度同一性，而不同论坛的网址不具有此性质。在本实施例中，按照网页所属域名对所有网页进行初步分组，以便在后续操作中对不同论坛单独构造解析规则。在后续步骤中，本实施例仅描述对其中一个论坛的处理过程，其他论坛过程与之类似。

步骤二：抽样。对于初步分组后的每一组网页进行抽样组成样本，构造解析规则不需要同时处理所有网页，故从所有网页中抽取部分网页进行处理。

步骤三：指定主题帖页面。在样本中插入带标记的待筛选网页形成样本网页；为了方便在分类后的簇中快速确定主题帖页面所在的簇，本实施例事先将一个带有标记的主题帖页面插入到样本中形成样本网页。

步骤四：构造结构块。经过初步分组，所有页面都隶属于同一论坛，故可以忽略所有网址的域名部分。将样本网页的网址的剩余部分根据符号进行分割，对于每一部分，为其类别和内容分别赋予一个编号，若某类别或内容已有编号，则采用此编号，否则赋予新编号。以此构成该部分的结构块。

步骤五：构造结构向量。将同一网址的各个结构块按顺序依次排列，构成该网址的结构向量。

构造结构向量的具体方法如下：

每个网址都可以转化为一个结构向量，而一个结构向量由若干结构块编号元组组成，二者的定义分别为：

p(u，i)＝(t(u,i),v(u,i))(8)

S(u)＝{p(u，i)|i＝1，2，…，N}(9)

其中，u为网址，i指网址中第i个结构块，t(u,i)为类别编号，v(u,i)为值编号，p(u,i)为结构块编号元祖，N为总结构块数，S为结构向量。

若有如下5条网址在数据集中：

1.http://example.com/query.php？id＝001&grade＝100

2.http://example.com/query.php？id＝001&grade＝99

3.http://example.com/query.php？id＝002&grade＝100

4.http://example.com/query.php？id＝002&grade＝99

5.http://example.com/query.php？id＝003

分别简记他们为u₁到u₅，则对类型可以有如下编号：

表1类型编号

对值有如下编号：

表2值编号

根据式8和式9，先对每个位置构造结构块，后将结构块进行拼合，构造的结构向量为：

S(u₁)＝[(1，1)，(1，2)，(1，3)，(2，4)，(1，5)，(2，6)]

S(u₂)＝[(1，1)，(1，2)，(1，3)，(2，4)，(1，5)，(2，7)]

S(u₃)＝[(1，1)，(1，2)，(1，3)，(2，8)，(1，5)，(2，6)]

S(u₄)＝[(1，1)，(1，2)，(1，3)，(2，8)，(1，5)，(2，7)]

S(u₅)＝[(1，1)，(1，2)，(1，3)，(2，9)，(0，0)，(0，0)]

实际上，为了节约编号，每个位置可以采用完全独立的编号，本例中为简化说明而采用的统一编号。

步骤六：计算相异度。对样本中任意两个结构向量，计算其相异度，具体计算公式为

N_s(u_m，u_n)＝min{i|p(u_m，i)≠p(u_n，i)}(10)

其中，u_m，u_n代表不同的网址，p(u，i)为结构块编号元组，N为总结构块数，D(u_m，u_n)为网址u_m，u_n的相异度。

步骤七：计算局部密度。对样本中每个结构向量，分别计算其局部密度，具体计算公式为

其中，KNN(i)为点i的K近邻集合，d_ij为结构向量i与结构向量j的相异度，ρ_i为结构向量i的局部密度。

步骤八：计算最小较高密度结构向量相异度。对样本中每个结构向量，其最小较高密度结构向量相异度即是该结构向量与局部密度大于之，且与之相异度最小的结构向量的相异度，具体计算公式为

其中，δ_i为结构向量i的最小较高密度结构向量相异度。

步骤九：作决策图。分别以每个结构向量的ρ值和δ值为横纵坐标做散点图，选择ρ值和δ值均较高的若干结构向量作为聚类的簇中心。

步骤十：确定其他结构向量归属。采用广度优先结构向量归属确定法确定非簇中心结构向量的归属簇；对于每个簇中心，将其K近邻结构向量加入该簇，并加入队列；每次取队首结构向量，对于其K近邻结构向量，若未被分配至任何簇，则加入队首所在簇并加入队列。

步骤十一：构造规则。选出带有标记的页面所在的簇，对于结构向量中的每个位置，记录所有该位置的结构块的类别和内容，当出现超过5种不同的内容时，不再记录内容，仅记录类别。其结果为解析规则。

步骤十二：应用规则。将解析规则应用于非样本网页，筛选出所有与解析规则相匹配的网页，得到主题帖的分类结构。

判断得到的主题帖是否正确，若正确输出网页，否则，返回步骤四重新进行聚类分析。

该方法从网址总体中抽取部分样本，利用网络论坛网址高度结构化的特性，对每个网址进行结构划分，构造结构向量，使用本发明提出的距离函数评估结构向量之间的距离，接着使用密度峰值聚类方法对样本结构向量进行聚类分析，提取出每簇的特征结构，构造用于描述簇中所有样本网址的解析器，用于对总体中剩余网址进行解析和分类。本实施例的整体主代码如下：

上述代码为本实施例基于网址结构的网络论坛页面聚类方法的整体代码，输入值为网页统一资源定位符urls和近邻数K，输出值为统一资源定位符urls；

上述代码第二行为步骤二，从所有网页中抽取部分网页进行处理。步骤一为网页数据预处理过程。

上述代码第三行-第四行为步骤三，将一个带有标记的主题帖页面插入到样本中。

上述代码第六行-第八行为步骤四和步骤五，构造结构块，并由结构块构造结构向量。

上述代码第九行为步骤六到步骤十，进行网页聚类分析，得到簇。

上述代码第十行为步骤十一，选出带有标记的页面所在的簇；上述代码第十一行为步骤十一，得到解析规则。

上述代码第十二行为步骤十二，将解析规则应用于非样本网页，筛选出所有与解析规则相匹配的网页，得到主题帖的分类结构。

上述代码为本实施例聚类分析方法的代码，即基于网址结构的网络论坛页面聚类方法的整体代码的第9行的函数代码，描述了步骤六到步骤十的过程。

上述代码为本实施例广度优先结构向量归属确定方法的代码，即基于网址结构的网络论坛页面聚类方法的整体代码的第9行的函数代码，聚类分析方法的代码的第15行的函数代码，描述了步骤十的过程。

在信息提取领域，通用的评价指标是召回率R，准确率P和F值。三者的计算公式分为：

其中，N_et为提取主题帖数，N_t为主题帖网址数，N_e为提取数。F值越高，则说明信息提取效果越好。

本例中对十个论坛的聚类结果如表3所示。

表3聚类方法结果

从表中可得，本发明提出的网页聚类方法的准确率均为100％，召回率均在90％以上，F值均在95％以上，能够准确地对网页进行分类，其结果令人满意。

实施例2：

本发明的第二目的是提供一种基于网址结构的网络论坛页面聚类方法的存储设备。

为了实现上述目的，本发明采用如下一种技术方案：

一种存储设备，其中存储有多条指令，所述指令适于由处理器加载并执行：

(1)按照网页所属域名对所有网页进行初步分组，对于初步分组后的每一组网页进行抽样组成样本，并在样本中插入带标记的待筛选网页形成样本网页；

(2)将样本网页的除域名外的网址根据符号进行分割，对分割后的每一部分网址的类别和内容进行编号，构造出结构块；

(3)将同一网址的各个结构块按顺序依次排列，构成该网址的结构向量；计算样本网页中的任意两个结构向量的相异度，和网页样本中最小较高密度结构向量相异度即任意一个结构向量与大于其局部密度且与其相异度最小的结构向量的相异度；分别作为横坐标和纵坐标构造决策图，确定簇中心，采用广度优先结构向量归属确定法确定非簇中心结构向量的归属簇；

(4)根据步骤(3)的决策图构造出解析规则，将解析规则应用于初步分组后的每一组网页中的非样本网页，进行网页聚类筛选，并采用评价指标进行评价。

实施例3：

本发明的第三目的是提供一种基于网址结构的网络论坛页面聚类方法的终端设备。

为了实现上述目的，本发明采用如下一种技术方案：

一种终端设备，包括：

处理器，适于实现各指令；以及

存储设备，适于存储多条指令，所述指令适于由处理器加载并执行：

(1)按照网页所属域名对所有网页进行初步分组，对于初步分组后的每一组网页进行抽样组成样本，并在样本中插入带标记的待筛选网页形成样本网页；

(2)将样本网页的除域名外的网址根据符号进行分割，对分割后的每一部分网址的类别和内容进行编号，构造出结构块；

(3)将同一网址的各个结构块按顺序依次排列，构成该网址的结构向量；计算样本网页中的任意两个结构向量的相异度，和网页样本中最小较高密度结构向量相异度即任意一个结构向量与大于其局部密度且与其相异度最小的结构向量的相异度；分别作为横坐标和纵坐标构造决策图，确定簇中心，采用广度优先结构向量归属确定法确定非簇中心结构向量的归属簇；

(4)根据步骤(3)的决策图构造出解析规则，将解析规则应用于初步分组后的每一组网页中的非样本网页，进行网页聚类筛选，并采用评价指标进行评价。

本发明的有益效果：

本发明的一种基于网址结构的网络论坛页面聚类方法及设备，根据网址构造结构向量，并计算结构向量之间的相异度，使得可以使用聚类分析方法对网页进行分类，具有高准确度和执行效率。尤其针对共性不显著的论坛页面，本发明构造结构向量进行聚类分析，满足大规模分类的速度需求。

以上所述仅为本申请的优选实施例而已，并不用于限制本申请，对于本领域的技术人员来说，本申请可以有各种更改和变化。凡在本申请的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。