相似性挖掘（共3篇）
相似性挖掘 篇1
0引言
随着遥感影像的爆炸式增长,信息提取的能力与效率已成为限制遥感应用发展的瓶颈问题。由于遥感影像数据库的海量特征,遥感影像数据挖掘已成为空间数据挖掘的主流。传统的遥感影像处理侧重于目标信息的增强和解译,而遥感影像数据挖掘侧重于从遥感影像中发现图像目标之间潜在的、隐藏的有用的模式和规则。遥感影像数据挖掘需要借助遥感影像处理的方法,但其目的是对遥感影像目标更高层面的归纳和总结,在图像索引和检索、图像分类、图像聚类、空间关联规则挖掘和图像变化检测等方面有广泛的应用前景。将数据挖掘技术应用于遥感影像库,能够挖掘隐藏在遥感影像中丰富的时间、空间和光谱知识等规则,为智能信息处理服务[1]。
在遥感影像挖掘中,不可避免的一个问题是如何定义图像之间相似性度量。图像距离函数是衡量图像相似性的一种方法,但对其定义却没有统一的函数形式。Di Gesu[2]在分析对比了多种图像距离函数后,提出了4种函数形式:Hausdorff图像距离、局部图像距离、整体图像距离和对称图像距离。虽然这4种距离都在不同程度上结合了图像的局部和整体特征,但从其定义式来看,对局部和整体结构特性的描述还不充分,算法开销较大。
1图像空间划分的策略
随着成像传感器技术的不断发展,图像的分辨率也越来越高。如果在原始的图像空间来计算图像的相似性度量,会带来2个方面的问题:① 计算量随着分辨率的提高急剧增长,导致图像的聚类、检索等应用的效率十分低下;② 过于关注图像的细节而忽略了图像的局部特性,降低了相似性度量的准确性。因此,非常有必要采取适当策略对原始的图像空间进行划分,本文采用了一种简单、实用的策略:将原始图像空间均匀地划分为2n(n为尺度因子,n=0,1,2,…)个网格,来计算网格之间的相似性度量。网格划分的大小可结合具体的应用和图像的分辨率来确定。例如,针对图像检索的应用,此时考察的是整个图像的相似性,尺度因子n=0,将图像空间划分为一个网格。
2视觉特征提取
选择合适的图像内容特征描述是建立相似性度量的核心问题,特征描述的好坏直接影响相似性度量的准确性。一个好的特征描述应该满足以下几点要求:易于计算,便于比较,所需计算开销小;表述能力强,视觉不相似的图像所对应的特征描述之间应该有显著的差异;与人的感知相接近,特征表述接近的图像在视觉感知上也应该彼此接近;具有较强的抗噪性,并具有一定的几何和光照不变特性。
针对上述要求,本文利用颜色、纹理和形状等低层视觉特征来描述图像内容。
2.1颜色特征
常用的颜色空间有RGB、HSI和YUV空间。RGB 颜色由红、绿和蓝表示,是最常用的颜色空间。直方图是描述颜色空间最常用的形式,要建立颜色特征的直方图表达,首先需要量化颜色空间。颜色空间被量化为m种颜色,统计图像中每种颜色的出现频度得到颜色的直方图H=(hi)i=1…m,归一化后的直方图记为H′=(h′i)i=1…m,其中undefined具有旋转和尺度不变性。
颜色直方图的相似性度量可以采用L1测度、L2测度、直方图交、统计假设检验和Kullback-leiber散度等方法,定义如下:
L1测度:undefined;
L2测度:undefined;
直方图交:undefined;
χ2距离:undefined;
K-L散度:undefined。
2.2纹理特征
纹理是图像中一种重要而又难以描述的特性,至今还没有公认的定义。习惯上把图像中局部不规则、而宏观有规律的特性称之为纹理,以纹理特性为主导的图像称之为纹理图像。人们提出了多种纹理描述方法,比较有代表性的有:共现阵方法[3]、Tamura特征[4]和基于Gabor小波的纹理分析方法[5]等。共现阵方法是一种传统的纹理描述方法,其构造方法众所周知,在此不在赘述,下面仅罗列几个由共现阵导出的特征:
能量:undefined;
熵:undefined
惯性矩:undefined
局部平稳:undefined。
2.3形状特征
形状是现实世界物体的本质特征之一。一般要求形状描述具有平移、旋转和尺度不变性,形状描述有多种分类方法,如内标量和外标量、数值和非数值、信息保持和非信息保持[6]等等。因矩描述方法具有平移、旋转和放缩不变特性,对该方法进行简要介绍。
图像平面上的二维笛卡尔矩定义为:
undefined。
式中,f(x,y)为二值函数或是灰度值。图像的一、二阶矩有其明确的物理意义:一阶矩可表示“重心”,二阶矩可表示“惯性矩”。
对于数字图像,(p+q)阶原点矩和中心矩分别定义为:
undefined
undefined。
式中,undefined;undefined。
规格化的中心矩为:
undefined。
利用上面的关系,可以导出下面的7个不变矩式:
Φ1=η20+η02;
Φ2=(η20-η02)2+4ηundefined;
Φ3=(η30-3η12)2+(3η21-η03)2;
Φ4=(η30+η12)2+(η21+η03)2;
Φ5=(η30-3η12)(η30+μ12)[(η30+η12)2-
3(η21+η03)2]+(3η21-η03)(η21+η03)·
[3(η30+η12)2-(η21+η03)2];
Φ6=(η20-η02)[(η30+η12)2-(η21+η03)2]+
4η11(η30+η12)(η21+η03);
Φ7=(3η21-η03)(η03+η12)[(η30+η12)2-
3(η21+η03)2]-(η30-3η12)(η21+η03)·
[3(η30+η12)2-(η21+η03)2]。
3基于特征网格划分的相似性度量
为了全面描述图像的颜色、纹理和形状等视觉特征,本文列举了十几种特征向量,在实际应用中还要引入其他特征向量,这些特征向量往往是数十维甚至数百维的。如果仍然用适用于低维数据的相似性度量方式来处理这些高维的特征数据,将得不到理想的结果,这就是所谓的维度灾难[7]。更好地克服维度灾难的影响,本文采用了一个新的思路来度量高维特征数据之间的相似性,即先将高维特征空间按一定规则进行划分,以形成特征空间的网格结构,从而在度量2个数据之间的相似性时,只考虑它们落入相同的网格中的维度信息。
划分策略可简单描述如下:对于d维的数据空间,首先为其每维指定一个划分位数bi,于是该维就被划分为2bi个单元。设undefined,那么整个数据空间被划分为2b个单元。
设数据集中任意2点为X=(x1,x2,…,xd)、Q=(q1,q2,…,qd),C[X,Q]为X与Q的各属性值落入同一区间的那些维的集合,那么X与Q之间的距离undefined。该度量方式与欧氏度量的一个重要差别在于,在该函数中占主导地位的是那些X与Q之间差别较小的维,而且,它们接近的维数越多,其之间的相似性也越高。这显然是符合人们判定数据点之间相似性的习惯。
对于图像空间的2个网格N1和N2,定义其颜色特征距离为undefined,采用特征空间网格划分方法得到的纹理和形状特征距离分别为D2和DS,则定义图像网格N1和N2的相似性为:
undefined。
式中,wi为经验权值。
4实验结果
为了验证本文提出的图像相似性度量方法的有效性,对遥感影像数据挖掘中最常见的聚类应用进行实验。采用了一副人工合成的纹理灰度图像,如图1所示。基于本文定义的相似性度量,采用经典的特征空间聚类算法[8]进行图像分割。因本文的重点在于描述图像的相似性度量,对实现分割的具体方法不在此阐述,分割的结果如图2所示。
5结束语
本文提出了一种遥感影像挖掘的相似性度量方法,采用颜色、纹理和形状等直观的视觉特征来描述图像,具有一定的几何和光照不变特性;在计算特征的过程中采用了图像空间和特征空间网格划分的思想来降低数据维数,便于引入更多的特征向量来提高相似性度量的准确性。
参考文献
[1]李德仁,王树良,史文中,等.论空间数据挖掘与知识发现[J].武汉大学学报(信息科学版),2001,26(6):491-499.
[2]GESUD V,STAROVOITOVV.Distance-based Functions for Image Comparison[J].Pattern Recognition Letters,1999(20):207-214.
[3]王润生.图像理解[M].长沙:国防科技大学出版社,1995.
[4]TAMURA H,MORI S,YAMAWAKI T.Texture Features Correspondingto Visual Perception[J].IEEE Trans on SMC,1978,8(6):460-473.
[5]JAINAK,FARROKNIAF.Unsupervised Texture Segmentation Using Gabor Filters[J].Pattern Recognition,1991,24(12):1167-1186.
[6]LIENHART R.Comparison of Automatic Shot Boundary Detection Algorithm[C].USA:In Proc.of SPIE Storage and Retrieval for Image and Video Databases VII,1999:291-301.
[7]贺玲,吴玲达.多媒体数据挖掘中数据间的相似性度量研究[J].国防科技大学学报,2006,28(1):77-80.
[8]COLEMAN G B,ANDREWS H C.Image Segmentation by Clustering[J].Proceeding of IEEE,1979,67(5):773-785.
相似性挖掘 篇2
本文通过GNP类关联规则挖掘方法构建外汇交易模型,通过外汇价格上升下降序列,提取显著的交易规则,并提出全新的GNP-SMT交易策略,基于GNP算法做序列的相似度匹配交易,进行外汇交易。
一、GNP-SMT方法
设Y(t)为在时间t的价格状态,它的值用1或0来表示向上或向下,其计算如下:
属性及其值对应于GNP方法中的判断节点功能。节点的连接被表示为关联规则。 图1显示了GNP类关联规则挖掘节点连接的示例。 其中,P1为一个处理节点,是关联规则的出发点。“Y(t)=1”,“Y(t-1)= 0”和“Y(t-2)=1”表示判断节点的功能。
GNP通过使用的判断节点检查数据库元组的属性值,并通过处理节点计算关联规则的测量。 判断节点通过判断的结果Yes或者No来决定下一个节点,对应着Yes边和No边。 此外,每个判断节点同时也检查t+1步中“Y(t+1)=C,C=1或者2”是否满足。
每个处理节点具有固有数字顺序(P1, P2...Pn),并且都连接到一个判断节点。 开始节点连接到P1。 属性值的检查从每个处理节点开始。 No-侧的判断节点连接到下一个编号的处理节点。 如果Y值从起点Ps检查结束,那么GNP也同样检查数据的下一个步。因此,数据库中的所有数据都进行检查。
CNP-based类关联规则挖掘的过程与一般的类关联规则挖掘方法的不同点在于:每个处理节点的N在每次访问都有更新(初始值N=0);它使用向后传输方法, 其中处理节点每次访问时步骤t更新到当前步骤n(最初n=n0);使用a, b, c, a(U), b(D)和c(D)计算规则的support, confidence和χ2值与以往的方法不同;这个方法会一直持续到得到足够大的n为止。 其中,在n步时刻,GNP向回追溯5步来发现规则,同时移动到下一步n+1,在向回追溯3步,如此一直持续下去……。每一步中向前追溯多长步骤是根据GNP节点的实际判断结果给出的。
当检测结束时,得到规则度量值。 在每个处理节点处,GNP都计算从所有Yes边到处理节点的样例个数,通过其作为测量关联规则的起始点。 N1表示从P1出发的总的记录数, 同时a, b, c分别表示每个判断节点通过Yes-边的记录数,并且a(U), a(D), b(U),b (D), c (U), c (D) 代表a, b, c中下一步为Up和Down的记录数。
利用这些得到的值, 就可以计算重要规则的度量,如使用b(U)/N1计算规则的支撑(support),使用b(D)/N1 计算规则的支撑(support), 使用b (U)/b计算规则的置信度(confidence),使用b(D)/b计算规则的置信度(confidence)。 同时,相应地χ2值也可以通过公式计算得出。
本文定义重要的关联规则满足如下条件:
其中,χ2min和min sup分别表示本文定义的最小χ2值和支撑(support)的阈值。 同时当规则序列为(Y=C),C=0,1时, 使用第三个表达式判断置信度(confidence)值。
所有满足重要性条件的关联规则都存贮在UP池和DOWN池中。 当GNP产生一个重要规则时,其总是要检查该规则是否是新的。GNP个体中的判断节点和处理节点的数目都为初始设定值, 并且每一代中所有的个体都有相同的节点数目, 节点之间的连接也是在初始化GNP个体的时候随机产生的。 GNP的个体并不需要包括所有的判断节点函数, 同时每个函数的数目也是不确定的,GNP个体中可以包含几个相同函数。
关于适应度和遗传算子, 本文使用Shimada等［4］所提出的判断GNP个体适应度的公式,即:
χ2(i),n(i)和αnew(i)分别相应地代表规则i的重要性水平(importance),复杂程度(complexity)和新颖性(novelty)。 考虑该适应度值来提取新的规则的潜在性。本文使用三种不同类型的进化算子:交叉、变异-I(改变节点的连接)、变异-II(改变判断节点的函数)。 每一代中,根据个体适应度值的大小对个体进行排序,将其中前1/3的个体选择出来。 然后,在下一代通过三种类型的进化算子产生3倍的个体组成新的一代。 如果交叉或变异的概率取很小的值, 那池中就会重复产生很多同样的规则,GNP就会过早收敛而达不到效果。所以参数值的设定通过实验决定。
GNP个体进化以提取新的满足条件的规则到池中,而不是像一般GNP算法中得到最高适应度值的个体。 因此,该方法在其进化方式上是与其他进化算法有本质上的区别。
二、投资模型
基于GNP的类别关联规则的数据挖掘与传统的方法有一点不同, 规则的获取是通过价格序列上升和下降得到的。 而投资量的大小则是通过预测以向上和向下的价格确定的概率来决定的。 如表1所示,在第0步设置投资X(0)的初始确认金额。 当它移动到下一个步1,价格下跌,失去了投资X(0),并返回步骤1时的收益R(1)=-X(0)。 然后决定在步骤1投资多少是根据GMP-SMT预测的概率来决定。 这个过程一直持续,在步骤9返回积累的收益R(9)=-X(0)+ X(1)+X(7)+…-X(8)。 而目标是最大化的回报R(N),同时,以降低投资风险。
表1中,U(t) :表示在t步价格上升;D(t) :表示在t步价格下降;x(t) :表示在t步的投资额;R(t) :表示在t步的收益额。
本模型主要解决在给定U (t) 或者D (t),t=0,1,2,3, …,s的条件下, 如何决定在s+1步投资额x(s+1),从而使得最后的收益额R最大化。
(一)价格上升下降概率计算
1.通过GNP-based类关联规则挖掘方法,计算在第s+1步价格上升或下降的概率。
2.依据历史价格上升下降数据, 通过与Up规则和Down规则的匹配来计算数据s的平均匹配度。
3.计算在s+1步价格上升或下降的概率:。
(二)策略计算
根据上式计算的s+1步价格上升的概率Pr(Up, s+1),本节采用两种方法来计算s+1步的策略x(s+1)值。
第一种方法(见图2情形1),其中x(s+1)为Pr(Up,s+1)的单调递增函数;另一种方法(见图2情形2),是通过决定一个正的α值,得到在s+1步平均收益R(s+1),从而来使用Pr(Up, s+1)计算x(s+1)。
三、实证分析
对全样本数据按2500手截取,数据呈现中间大,两端小的正态分布特征。 使用GNP-SMT方法的预测成功率在51.66%±0.32%左右, 其中51.66%为预测的均值,0.32%为预测的标准差。
从训练样本抽取2000个样本数据,GNP-SMT使用策略1累积收益达到70%左右。同时,从测试样本抽取550个样本数据,GNP-SMT使用策略1累积收益虽然在中间有所下降,但最后也达到60%左右。
考虑策略2, 从训练样本抽取2000个样本数据,GNP-SMT使用策略2累积收益表现不够平稳,其中在某个阶段收益率都为负值, 但最后累积的收益率也逐步上升,达到15%左右。从测试样本抽取550个样本数据,GNP-SMT使用策略2累积收益率的表现相当不错,最后可以达到90%左右的累积收益率。
整体最优策略的实证结果如下,全样本来看,年化收益率可以达到116%。 实证表明了GNP-SMT方法的有效性以及获利能力。 但需要注意的是,现实的金融环境错综复杂, 这种历史与现在关系的反映并不是时时刻刻都有效的,只有通过不断的创新发现,才能获取新的收益。
四、结语
GNP-SMT方法利用了技术分析中,“历史是会重复发生”这一假设条件,通过使用GNP得到历史数据里的规则,然后使用SMT技术匹配交易数据和历史数据。 实证也表明了这一方法的有效性以及获利能力。这在一定程度上也说明了市场不是完全有效的,历史的信息对现在的交易存在影响, 通过技术分析手段能够获得超额收益,这也验证了AMH的相关理论。
GNP-SMT为外汇交易提供了新的思路, 它通过预测汇率上升下降的概率进行投资决策, 通过本文的实证表明,GNP的相关算法在外汇市场上可以获得显著的收益率水平, 并且在不同的市场环境下都能够表现出很好的性质。
摘要：提出了一种基于外汇市场的价格上升下降序列的新的GNP-SMT方法 。基于遗传网络编程(GNP)与类关联规则,通过算法迭代,抽取大量的类关联规则,并存储在规则库中(上升池和下降池)。然后,将产生的规则进入池中来计算价格向上和向下价的概率。在训练期间,提取大量的向上和向下的规则后,使用相似度的匹配计算,以处理各个步骤的执行情况。在测试期间,连续交易的投资金额由GNP的SMT的预测概率计算确定。使用两种不同的情况下呈现的结果,模型都显示很好的盈利。
相似性挖掘 篇3
随着互连网技术及其应用的迅速发展,网站已经成为人们浏览和查询信息的一个主要信息源。如何及时无歧义地响应客户的查询请求,如何提高网站的主题分类和请求信息内容的匹配度及准确性成为一个热门的研究方向。在这个研究方向中,针对网站体系结构和网站内容的匹配优化显得尤为重要。Web页面信息是互联网海量信息的主要表现形式之一,具有结构复杂、内容繁多、访问频率高等应用特点。Web 信息的非结构化特点决定了对其挖掘比结构化的数据库挖掘要复杂得多,因此面向Web页面内容的挖掘是一个复杂困难的过程[1]。
本文对基于链接分析的Web结构挖掘算法进行了讨论,介绍了在Web结构挖掘上衍生的相应的由Jon Kleinberg提出的HITS算法[1],并且分析了该算法所存在的不足。在此基础上提出了基于页面相似度的改进型HITS算法,称作DS-HITS算法, 通过实验证明,DS-HITS算法对权威和核心页面的抓取能力较好。
1 Web挖掘的分类模式
Web结构挖掘主要是针对Web页面的链接结构进行分析,其目的是通过分析了解和掌握网站的页面分布形式,以方便页面导向,或者是为了发现网站内的重要页面——按照重要性排序。Web 结构之所以是可挖掘的,是因为网站Web页面的链接往往包含了类似信息的关联规则,这些链接往往暗示了所链接的网页在内容或重要性方面具有同等或近似的特征和地位[2]。
本文依据在线阅读网站的需求提出了改进算法DS-HITS,该算法的主要技术路线可以看成是传统Web挖掘分类模式[3]基础上的拓展。传统的Web挖掘分类模式如图1所示。
为了达到图1所示的各类挖掘目的,关于Web结构挖掘的研究衍生了很多相应的算法。这些算法根据不同的需要,实现了不同的Web结构挖掘的效果,其中较有影响力的是HITS算法。
2 基于链接分析的Web结构挖掘算法
2.1 HITS算法分析
HITS的算法流程简述如下[4]:
1) 获取根集Sroot,将查询q提交给传统的基于关键字匹配的搜索引擎,搜索引擎返回很多网页,从中取前n个网页作为根集Sroot。Sroot满足下述三个条件:
(1) Sroot中网页数量相对较小;
(2) Sroot中网页大多数是与查询q相关的网页;
(3) Sroot中网页包含较多的权威网页。
根据用户查询条件,利用已有的基于关键词的搜索引擎获取相似页面的链接信息,并对相似页面结果进行人工检索,得到相似度最高的网页组成根集Sroot,网页数量一般约为200篇。
2) 对根集进行扩展。将链接根集Sroot的网页或由根集中网页链接的网页加入到根集中,形成拓展集Sextend ,拓展集中的网页数量大概在1000～5000左右。
3) 对拓展集Sextend进行如下运算[7]:
以Sextend中的Hub网页(指向权威网页链接集合的Web网页,它本身可能并不重要,或者说没有几个网页指向它,但是Hub网页却提供了指向就某个主题而言最为重要的站点的链接集合)为顶点集V1,以权威网页为顶点集V2,V1中的网页到V2中的网页的超链接为边集E,形成一个二分有向图SG=(V1,V2,E)。对V1中的任一个顶点v,用H(v)表示网页v的Hub值,对V2中的顶点u,用A(u)表示网页的权威值。开始时H(v)=A(u)=1,对u执行I操作修改它的A(u),对v执行O操作修改它的H(v),然后规范H(v)、A(u),如此不断地重复计算下面的操作I、O。直到H(v)、A(u)收敛[8]。
I操作:
O操作:
每次迭代后需要对A(u)、H(v)进行规范化处理:
式(1)反映了若一个网页由很多好的Hub指向,则其权威值会相应增加(权威值增加为所有指向它的网页的现有Hub值之和)。式(2)反映了若一个网页指向许多好的权威页,则Hub值也会相应增加(Hub值增加为该网页链接的所有网页的权威值之和)。
4) 对拓展集Sextend进行K次运算后,K一般取20,但Kleinberg指出,当K=6～10时,H[n]和A[n]已收敛于固定向量,取出Hub值和Authority值较高的网页作为结果返回给用户。
2.2 HITS算法的优点与不足
HITS算法是基于链接分析的排序算法,它利用页面之间的引用链来挖掘隐含在其中的有用信息(如权威性),具有计算简单和计算效率高的优点,但该算法存在明显不足。
HITS算法完全将网页的内容或文本排除在外,仅考虑网页之间的链接结构来分析网页的权威性。此外,它只靠页面的入度和出度排序文档,未考虑出、入网页相似度。在对初次搜集的页面集Sroot集进行扩展,形成Sextend集的过程中,可能会包含大量主题无关的页面,即存在“主题漂移问题”。因此,为了能够更好地反映网页的内容和文本,提高Web页面的挖掘效率,本文在HITS算法的基础上提出了一种基于页面相似度的改进型链接分析算法,即DS-HITS算法。
3基于页面相识度的改进型链接分析算法—DS-HITS算法
本算法在链接分析的基础上,从页面的相似度角度出发,设计了一种权重赋值函数,利用该函数来进行页面相似度计算,以判断当前页面是否符合主题,并依据相似度的大小对权重进行再次权衡,完善拓展集网页的选取。
为了避免较大的计算量,提高算法效率,在分析大量在线阅读网站的网页的基础上,针对网站内容,本文针对页面总结出来以下特征:
1) 页面文档的标题往往能反映页面的主要内容。
2) 锚文本(超级链接上的文本)及其指向页面的标题等关键属性值是否相似可以判断指向页面是否是相似页面。
3) 脚本中链接及文本可以忽略不计。
4) 网页主题部分往往会重复网页标题,正文部分会独立出来。
5) 字体变化的部分往往反映了页面作者想表达的一种重要信息。
6) 页面上广告部分,独立于页面主体部分,一般放在frame或div框架中,并且具备以下两个特征:广告链接网页跟当前网页主题基本不相干;链接出去的网页指向数个不同网站。这些特征可以用于剔除广告部分对网页权威和中枢值分析的影响。
根据以上特征,本文设计了一种权重赋值函数,针对不同的网页特征赋予不同权重值,在计算页面相似度上,可以侧重考虑文本相似度,而不是以统一度量计算文本的所有特征向量,这样既可避免较大的计算量,同时又能突出网页的重要信息。
DS-HITS算法处理可以归结为以下流程:
1) 获取根集Sroot。获得用户的查询条件,对用户查询进行处理,利用基于关键词的搜索引擎对网站内的页面进行搜索,对得到的搜索结果进行人工筛选,提取出一些主要的实体词 (动词、名词、量词、代词等),得到根集Sroot。
2) 对根集进行如下扩展:
(1) 对根集中的每一页面文档di,根据上述描述的特征4)和6),删除嵌入的广告部分和网站内通用部分,提取包括标题、异字体、页面文档di内的锚文本(链接文字)等关键文字,调用权重赋值函数,针对不同属性赋予不同的权重值,构成其向量空间VSM ,且标题词和锚文本词语的权重值比其它特征词的权重要高。向量空间模型VSM构造如下[9]:设页面集合中共有m个不同的属性项p1,p2,… ,pm,分别计算页面文档di(i=1,…,N)的属性项p1,p2,…,pm的属性权值,这些属性项权值所构成的向量(wi1,wi2,…,wim)成为页面文档di的向量。由于属性项p1,p2,… ,pm互不相同,我们可以把属性项组成m维的空间向量,页面文档之间的相似度可以通过向量的形式转化为向量之间的数学计算模式,使得在进行页面文档归类的计算过程中比较简单、快速。
(2) 得到其指向的页面集合Set。
(3) 对页面t∈Set (t为一页面)进行处理,提取包括标题、异字体以及锚文本,调用权重赋值函数对词条进行赋值,构成页面t的相似度空间向量VSMt。相似度[10]指衡量一篇页面文档向量与用户查询式向量之间的相近程度,即判断某篇页面文档是否是用户所需要的。相似度可定义为向量之间夹角的余弦:
Sim(di,q)=
其中:Wdi为属性项在页面文档中的权重,Wqi为属性项在查询中的权重。
(4) 统一向量VSM和VSMt的维数(一般取最大维数,不足补0。若相似度值大于阈值(比如设置为0.45),则将页面t加入拓展集Sextend中。
3) 对拓展集Sextend进行如下运算:
(1) 计算拓展集中每一网页的Authority值和Hub值。
(2) 分别将Authority矩阵值和Hub矩阵值进行正交单位化。
(3) 对拓展集进行上述两步迭代运算,直至收敛(数值波动小于设定精度)。
4) 取出Hub值和Authority值较高的网页URL作为结果返回给用户。
4 实验结果与分析
本实验中,DS-HITS算法是在Webla的基础上改造而成,Webla是sourceforge的开源项目[5],该项目主要是实现各种流行的链接分析算法,如HITS等。
Webla初始数据存放格式是WebGraph,为此设计了一个简单的基于关键字的爬虫,得到WebGraph样式的网页链接,关键字为“毕业”,限定2级链接,返回前30个页面,爬虫结果如图2所示。
由爬到的结果很容易得到WebGraph格式的文件[6]。
DS-HITS算法实验结果与HITS算法的搜索结果比较如表1所示。
从表1可以看出,DS-HITS算法相比HITS算法在权威和核心页面的抓取能力要好10%左右,这点可在权重总值上得到反映,特别是在图片新闻抓取上,由于在锚文本指向的以图片为主的新闻板块页面在关键词上的相似度比较高,所以以图片为主的页面抓取较多。
此外,DS-HITS算法和HITS算法两者均比基于关键字的搜索效果差。经过分析,原因在于导航条对于基于关键字的链接的爬行效果较好,容易直接找到子版块或学院首页,因而基于关键字的结果在局域网内、组织良好的页面上爬行的结果相对较好。这也提出了针对网站结构优化的要求。
5 结束语
本文讨论了HITS算法的优点以及存在的不足,并提出了一种基于页面相似度的改进型链接分析算法—DS-HITS。本文采用的Web数据挖掘目前只是在Web结构挖掘的基础上进行,没有涉及到Web内容和Web使用挖掘。
参考文献
[1]Joe M Kleinberg.Authoriative sources in a hyperlinked enviroment[J].Journal of the ACM,1999,46(5):604632.
[2]Etzioni O.The world wide Web:Quagmire or gold mine[J].Communi-cations of ACM,1996,39(11):6568.
[3]韩家炜,孟小峰,等.Web挖掘研究[J].计算机研究与发展,2001,38(4).
[4]Gordon S.Linoff,Michael J A.Berry.Miningthe Web:TransformingCus-tomer Data into Customer Value[M].沈钧毅,宋擒豹,燕彩蓉,等译.北京:电子工业出版社,2004.
[5]WebLa:Web Linkage Analysis.2005.http://Webla.sourceforge.net/.
[6]李华虎.基于语义的Web数据挖掘在在线阅读网站应用的研究[D].东华大学,2008.
[7]朱炜,王超,等.Web超链分析算法研究[J].计算机科学,2003,30.
[8]Kleinberg J.Authoritative sources in a hyperlinked environment[C]//Proc.9thACM-SIAMSymposium on Discrete Alogorithms.1998.Extend-ed version in Journal of the ACM46(1999).Also appears as IBM Re-search Report RJ 10076,1997.
[9]战学刚,林鸿飞,姚天顺.Infolite中文检索系统[J].小型微型计算机系统,2000,21(9):989992.