一种以主题词为特征的排序划界网站聚类算法*

路文华,罗钧旻,赵 丹,高武奇

(西安工业大学 计算机科学与工程学院,西安 710021)

clustering

互联网的快速发展使得网络信息呈指数级增长,虽然信息越来越丰富,但是人们很难取得真正需要的信息,搜索引擎通过对网络信息的组织与管理为人们有效获取信息提供了便利,网页作为网络信息的载体,让计算机理解网络信息语义,可以更好的把网页按照各类主题进行分类,对其进行有效分类可以极大提高人们获取信息的效率.

为了让计算机理解Web资源的意义,Berners-Lee提出了语义Web[1]的概念；文献[2]认为语义Web的核心——本体没有考虑到主体agent[3]的能动性,将agent的概念引入到本体中得到动态本体的概念,文献[4]用动态本体描述语言来描述动态本体,文献[5]认为语义是与agent的自我意识分不开的,以动态本体描述语言为基础对agent的自我意识进行了研究.文献[6]在文献[5]的研究基础上,将整个互联网看成是一个由具有自我意识的网站agent、网眼agent以及客户agent组成的动态本体.网眼agent对其所认知的网站agent、客户agent、信息资源、及其之间关系的描述就构成了网眼agent的自我意识,也就构成了Web的语义结构,而网站agent间的分类关系[7]是其中最重要的一种关系,文中通过对网站结构[8]的分析,提出了一种基于主题词的网站特征值排序划界聚类算法,并对网站进行聚类,以期更好地设计出Web语义结构.

1 主题词与网站结构分析

从用户角度仔细观察每个网站可知,一个网站是由一个主网页和多级子网页组成.每一个网页的上方或者侧面都会显示与该网页要表述内容相关的子网页的标题,点开这些标题就会连接到相关的子网页,这些子网页的标题称为该网页的主题词.网页的中间部分一般是网站推荐的一些以主题词为标题的子栏目,子栏目是这个主题词代表的子网页的重要内容的目录.最下方是有关网站的自我介绍等内容.因此,可把网站看成是由主题词组成的树型结构,一个主题词的下层主题词是对这个主题词的解释.网站主页是一个网站的总体概括,含有表现这个网站主要内容的主题词.

2 基于主题词的网站聚类思想

基于主题词的网站特征值排序划界聚类算法可以分为三个阶段:主题词收集、网站特征值收集和网站聚类.

1) 主题词收集:收集尽可能多的网页,抓取其上的主题词并计算该词出现的频率,按出现频率从大到小对主题词排序,对同义词合并、删除无意义词及出现频率极小的主题词等精简优化处理后得到有序的主题词表,那么这个主题词表就是对整个Web网站要表述内容的抽象；

2) 网站特征值收集:设计一个无符号大整数,其位数与这个主题词表中主题词个数相同,位次与这个主题词表中主题词出现频率对应,每个网站对应这样一个无符号大整数,若某个主题词在这个网站上出现,就把对应位置1,否则置0,我们称这个无符号大整数为这个网站的特征值；

3) 网站聚类:根据特征值的大小对网站排序,计算相邻网站的距离[9],根据距离值的大小对网站分类.

3 主题词收集

删除无意义词及出现频率极小的主题词等精简优化处理后,得到1536*64条主题词,根据主题词出现频率从大到小排序,主题词表navword(ID,Nav,Number,Frequecy),其属性含义见表1.

表1 主题词表

4 网站特征值的收集

4.1 相关数据结构的设计

在网站特征值收集阶段,与其相关的数据结构包括三个,分别为:

1) 定义一个元素类型为URL的数组WS,用于存放要聚类的m个网站的URL.

2) 定义一个二维long型数组metadata[m][n]:用于存放m个网站的特征值,每个网站的特征值由n个long型数组成.

3) 定义一特征词表nav_index(ID,Nav,Number,Frequecy,LL,BB,value),前四项字段含义同主题词表,后三项的字段含义见表2.

其部分数据见表3.

表2 特征词表

表3 特征词表部分数据

4.2 获取网站特征值

依次取WS中网站主页的主题词与特征词表中的特征词进行匹配,若特征词表中有该主题词,则把该网站特征值中代表该特征词的那一位置1,即把该词的value值与该词所对应的网站特征值中的long型变量的值相加,得到该网站的特征值.具体算法如下:

① 定义并初始化二维long型数组metadata,初值为0；

② 查看网站表中是否有未被抓取过的主页地址,如果有,则取出一条未被抓取过的记录,转③,否则,结束；

③ 取得该记录的网站编号id和网站主页URL；

④通过该URL获取该网站主页的内容content；

⑤ 使用正则表达式匹配获取该网站主页的所有主题词；

⑥ 将得到的主题词依次与特征词表nav_index中的主题词进行匹配,如果没有,则丢弃,如果有,则从特征词表中找到该主题词属于网站特征值的第几个long型值l和该词的value值v；

⑦ 计算网站特征值,metadata[id][l]=metadata[id][l]+v；

⑧ 查看该主页的主题词是否已匹配完,如果没有,取下一主题词,转⑥,否则,转②.网站搜狐的特征值为:

{0:12 890 906 240 245 811,1:213 198 865 169 606 298 6,2:139 418 397 535 119 38,……,153 3:0,153 4:0,153 5:0}

5 Web网站聚类

5.1 Web网站排序

用基数排序算法根据网站特征值(1536个long型值)从大到小对网站数组WS排序,得到一个有序的网站数组SW.

5.2 计算网站距离

由于内容相似的网站特征值会比较接近,可以分为一类,因此,用SW中两个相邻网站间特征值的差作为分类的依据,差值越小网站内容越相似.用数组distance[m-1][n]来记录数组SW中相邻网站间的距离,由相邻两个网站的特征值异或得到.

5.3 网站距离号

定义一整型数组DS用来记录SW中相邻网站间的距离从大到小排序的排序号,简称距离号.距离号越小,说明网站间距离越大,网站内容差异越大.

由于相邻网站之间的距离值由n个long型数组成,不方便计算,因此,以距离号作为网站类别划分的参数,计算方便且不会对分类结果造成影响.

5.4 聚类算法

根据给定的分类数Cn,计算对应的距离号Δ(Δ=Cn-1),则小于等于Δ的距离号称作类分割距离号.类分割距离号把SW中的网站分割成Cn类,每一类的第一个网站称作类分割点.因此,对SW中的网站聚类,就是根据Δ寻找SW中的类分割点,两个类分割点之间的网站被划分成一类.寻找类分割点的算法如下:

① 定义一个整型数组CDP[Δ],记录类分割点,初始化为0；定义一个整型变量j,记录CDP中元素的下标,初始化为0；

定义一个整型变量i作为DS的下标,初始化为0；

② 判断DS[i]是否小于等于Δ,如果是,则DS[i]是一个类分割距离号,转③,否则,转④；

③ CDP[J]=i,j++.判断i是否等于m-1,如果是,则结束,否则,转④；

④i++,转②；

5.5 测试结果及分析

实验一:选取20个网站作为聚类的网站对象,利用文中算法将其划分成5类；匹配特征词表中的主题词获取到各个网站的元数据,并根据网站元数据的大小对其进行排序,得到的SW如表4中所示的websiteURL列；计算相邻网站间的距离并根据距离大小排序,得到每个网站的距离排序号,记录在DS中,见表4中所示的ds列；由于要划分为5类,可确定Δ是4,根据Δ寻找类分割点,见表4中所示的websiteID列.

表4 网站聚类数据1

从表4中可以看出,该算法将20个网站划分成了主题较为鲜明的5个类别,在网站的分类上是有效的.

实验二:选取90个网站作为聚类的网站对象,文中算法将其分为9类,部分数据见表5.

表5 网站聚类部分数据2Fig.5 Data of website clustering 2

表5中为90个网站的部分数据,只显示了四个分割点.从分类结果来看,得到的网站类别主题较为鲜明,文中算法可以对网站进行有效分类.

在这9个类别中的某些类别中,存在主题有所偏差的网站,如:在类别1中的第1个网站是有关房产的,而其他都是军事类的.造成偏差的原因为:用于获取网站特征值的主题词的语义没有进行统一定义,同一主题词可能被网站设计者用于不同的场合,赋予不同的语义,从而引起分类混乱.因此,对Web上主题词的语义进行统一定义,形成标准,对语义Web的设计可以减少偏差,这也是课题未来的研究方向.

6 结 论

1) 收集并精简处理了互联网特征词即主题词,根据特征词的出现频率对主题词进行排序,将这个主题词序列作为网站特征值的结构；根据特征词在某网站是否出现计算出该网站的特征值,将网站根据网站特征值的大小进行降序排序；计算相邻网站之间的距离,并根据距离大小进行排序；根据要求的分类数k,取前k个距离作为类分割点对网站进行聚类.聚类测试结果分类准确,主题鲜明,可以对网站进行有效聚类.

2) 测试结果有个别网站的所属类别存在偏差,其原因为:网站主题词的语义没有进行统一,同一主题词可能被赋予不同语义,进而造成分类混乱.

3) 未来的研究将从两个方面进行:① 对Web上主题词的语义进行统一定义,形成标准,设计出语义Web的语义结构,以减少主题词歧义；② 将基于主题词的网站特征值排序划界聚类算法进行抽象,形成基于距离序的划界聚类算法,使其聚类的数据类型更广泛.

参考文献:

[1] BEMERS-LEE T,HENDLER J,LASSILA O.The Semantic Web[J].Scientific American,2001,23(3):21.

[2] 罗钧旻,王蕾.基于互表性的动态本体体系结构的研究[J].微电子学与计算机,2013(2):124.

LUO Junmin,WANG Lei.Research on Architecture of Dynamic Ontology Based on Mutual-description Principle[J].Microelectronics and Computer,2013(2):124.(in Chinese)

[3] GUERRA-HERNANDEZ A,FALLAH- SEGHROU-CHNI A E I,SOLDANO H.Learning in BDI Multi-agent Systems[J].Lecture Notes in Computer Science,2004,3259:39.

[4] 罗钧旻,谢磊.动态本体描述语言的研究[J].西安工业大学学报,2014,34(1):44.

LUO Junmin,XIE Lei.Research on Description Language of Dynamic Ontology[J].Journal of Xi’an Technological University,2014,34(1):44.

(in Chinese)

[5] 罗钧旻,李俊伟.Agent自我意识的研究[J].微电子学与计算机,2015(12):72.

LUO Junmin,LI Junwei.Research on Self-consciousness of Agents[J].Microelectronics and Computer,2015(12):72.(in Chinese)

[6] 罗钧旻,赵丹,高武奇,等.基于自我意识的语义Web研究[J].微电子学与计算机,2016,30(10):50.

LUO Junmin,ZHAO Dan,GAO Wuqi,et al.Research on Semantic Web Based on Self Consciousness.[J].Microelectronics and Computer ,2016,30(10):50.

(in Chinese)

[7] SRIRAM B,FUHRY D,DEMIR E,et al.Short Text Classification in Twitter to Improve Information Filtering[C]//Proceeding of the International ACM SIGIR Conference on Research and Development in Information Retrieval,2010,Geneva:DBLP,2010:841.

[8] 罗钧旻,桑蓓蓓.基于动态本体的语义B/S研究[J].微电子学与计算机,2014,31(8):136.

LUN Junmin,SANG Beibei.Research on Semantic B/S Based on Dynamic Ontology[J].Microelectronics and Computer ,2014,31(8):136.(in Chinese)

[9] ZHU C H,WEN F,SUN J.A Rank-order Distance Based Clustering Algorithm for Face Tagging[C]//Computer Vision and Pattern Recognition 2011,Springs:IEEE,2011:481.