访问路径

访问路径（精选四篇）

访问路径 篇1

XMPP (Extensible Messaging and Presence Protocol, 可扩展消息与存在协议) 是一种基于XML的即时消息协议[1]。它继承了XML灵活性和扩展性, 已经应用到其它非IM领域[2]。有学者提议XMPP作为物联网领域的标准协议[3]。也有学者将其应用到分布式数据存储领域, 将提供相同数据的服务器放在网络中的不同位置, 以减少网络资源的消耗、提供数据的安全性和多用户的Qo S (Quality of Service) [4]。但是, 在相同服务器资源和网络资源下, 不同的访问路径将导致不同的网络状态, 会出现服务器负载和网络资源负载不平衡等问题。因此有必要对访问路径优化问题进行探讨。本文将对问题就行分析, 建立数学模型, 利用遗传算法就行求解。通过模拟实验网络, 构建XMPP路径优化服务器, 实验验证得出在双目标双约束条件下的不同解[5,6]。

1 问题说明

基于XMPP的分布式数据的访问Qo S路径优化的目标是优化网络中数据流的传输路径, 实现服务器负载平衡以及网络资源消耗平衡。由于各个数据流占用的服务器资源和网络资源不同, 本研究的问题就是将网络中数据流分别重定向到不同服务器的路径优化问题[7]。此外, 为了满足网络数据流的路径优化, 需建立XMPP路径优化服务器。它将定时收集网络相关信息, 进行分析处理后得出在不同约束下的最优路径。如图1所示, 模拟了基于XMPP的分布式数据的访问网络的拓扑图。其中包括30条链路 (E0~E29) , 30个用户节点 (C0~C29) , 4个服务器节点 (S0~S3) 。

将访问数据的网络看成一个有向连通图G (V, E) , 其中, V为节点集;E为链路集。节点集V包括:

(1) 服务器节点S;

(2) 用户访问节点C。

假设G (V, E) 中C, S和E的数量分别为m, n, l, 用户与各个服务器之间的链路都采用TCP/IP协议获得访问路径[8], 则每个用户有n种可选链路, 整个网络就存在nm种可选状态。这里求解的问题就是从这些可选状态中选取一种, 以使网络在满足约束条件的情况下整体性能最优, 下面给出了它的问题模型。

优化的目标是链路集E服务器负载均衡、网络资源负载均衡。XMPP路径优化服务器收集的信息存储到以下矩阵中:

(1) CR=[cri]m:用户占用服务器资源矩阵, cri表示用户i占用的服务器资源;

(2) CB=[cbi]m:用户占用网络资源矩阵, cbi表示用户i占用的网络资源;

(3) SR=[srj]m:服务器资源矩阵, srj表示服务器j所能提供的最大服务器资源;

(4) EB=[ebk]m:网络资源矩阵, ebk表示链路k所能提供的最大网络资源;

(5) p=[pi, j]m×n:链路分布矩阵, pi, j表示用户i到服务器j是否链接, 若链接pi, j=1, 若未链接pi, j=0;

(6) x=[xi]m:决策变量, xi表示用户i选择的服务器。

将路径优化问题用上面的矩阵数学描述为如下双目标优化问题:

其中,

公式 (2) 中, f1 (x) 表示各服务器利用率的最大值;f2 (x) 表示各链路网络资源利用率的最大值。

要实现数据访问的Qo S, 各用户请求所消耗的网络资源之和必须小于各条链路的网络资源, 所消耗的服务器资源之和必须小于各个服务器的资源, 则约束条件表示为:

2 问题求解

从上述数学模型可知, 问题为一个多目标多约束优化问题, 运用遗传算法求解该问题的过程如下:

(1) 编码

染色体编码采用x=x1x2x3…xm的形式, 基因xi表示用户i所选择的服务器, 因此一条染色体表示一种网络路径状态。基因xi的可选值为服务器的数量, 取0到n-1范围内的任意整数。

(2) 适应度函数

利用权重系数法, 得到适应度的求解公式:

其中w1, w2分别表示两个目标函数的权重, 每一组权重对应一个解, 调节权重值可以得到Pareto最优解集[7]。实际应用中需要根据网络情况来选定一组权重值, 从而获得对应的解作为路径优化的目标。

(3) 群体设定

为了使得群体能够覆盖基因的所有可能取值, 种群的规模H与数据库服务器的数量n有关:

其中, α为种群规模系数, α>1。

(4) 选择

采用最优复制与比例选择相结合的方法进行选择操作。在每一代进化过程中, 保留h个当前最优的个体不参与交叉、变异等遗传操作, 直接将它们复制到下一代群体中。

其余个体在下一代群体中生存的数目N计算如下:

其中, h为最优个体保留数量;Fr为个体r的适应度值。

(5) 交叉

采用随机取交叉点的方式, 选取多个交叉点就行交叉操作。随机交叉点的取值范围为0到m-1。

(6) 变异

采用随机取数的方式获取变异点, 取值范围为0到m-1;在变异点处采用随机取值的方式完成基因的变异。变异的基因值取值范围为0到n-1。变异的概率为MRandom。

(7) 终止条件

在一定代数内没有更优解出现时将自动终止, 公式 (7) 作为解的终止条件函数。

其中, E (F (k) , F (k+λ) ) 为第k代到第k+λ代的相对误差;max (Fr (k) ) 是第k代各染色体的最大适应度;ε是给定的评判标准。由于选择过程中保留前h个最优个体, 相邻两代的最优个体经常相同, 因此E取λ代间隔的相对误差。

算法的C#总体实现过程如下:

3 实验模拟及结果

从图1的模拟环境可知m=30, n=4, l=30。服务器S0~S3的资源矩阵SR= (30, 20, 40, 30) , 其他参数如表1、表2所示。

设置遗传算法的参数为:种群规模系数α=3;最优个体保留数量h=1, 交叉点数量CP=4;变异率MRadom=0.03。以模拟环境为基础, 用C#编程, 改变w1, w2的值, 在迭代次数都小于60次的情况下收敛, 表3为计算结果。

表3中列出5种权重条件下的各链路与服务器之间的关系。各服务器的利用率和各链路网络资源的利用率, 如图2、图3所示。

如图2、图3所示, 当w1=0时 (N2) , 网络资源利用率高, 利用率都超过60%, 部分达到堵塞现象;当w2=0时 (N1) , 服务器负载的变化很大, 利用率超过70%;当w1=0.5, w2=0.5时 (N2) , 数据库服务器利用率集中在40%左右, 网络资源利用率在40%到60%左右;当w1, w2权重分配就行随机发配时 (N4, N5) , 数据库服务器和网络资源利用率处在30%到70%之间。

4 总结

为了提高XMPP网络分布式数据库数据访问效率必须进行路径优化。本文从多目标优化角度运用遗传算法处理这个问题, 给出了满足Qo S多约束前提下的路径优化的算法模型与实现过程。实验结果表明本算法在不同权重系数下可以收敛于各个指标的最优值, 实现路径的多目标组合优化。

有待研究的内容:

(1) 如何提高算法的执行效率。初步想法通过改变编码方式 (如格雷码) , 研究执行效率;

(2) 引入更多约束条件, 使之更符合实践需求;

(3) 建立物理实验环境, 就行实验研究。

参考文献

[1]P.Saint-Andre, Ed.Extensible Messaging and Presence Protocol (XMPP) :Core.http://www.faqs.org/rfcs/rfc3920.txt[OL].

[2]黄剑.基于XMPP的端到端连接建立机制的研究与实现[D].国防科学技术大学, 2009.

[3]张卫, 张峻峰, 罗长寿.XMPP应用于物联网通讯协议的研究[J].中国农学通报, 2012, 28 (09) :289-292.

[4]张丽, 曲攀.自组织覆盖网络QoS组播动态路径优化研究[J].计算机工程与应用, 2013, 3 (24) :83-87.

[5]Liu Junli, Chen Shuangxi, Mao Jie.Genetic algorithm study on the university course timetabling problem[R].2012 IEEE International Conference on Cyber Technology in Automation, Control, andIntelligent Systems (CYBER) .Bangkok, Thailand.2012:179-182.

[6]Chang Wook Ahn, R.S.Ramakrishna.A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations[J].IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION Jun, 2002:566-579.

[7]惠雯, 尹浩, 林闯, 杨扬.内容分发网络请求路径研究[J].计算机科学, 2012, 2 (12) :1-7.

访问路径 篇2

在win7旗舰版电脑中运行软件时提示“无法访问指定设备路径或文件

，

第二中方法：咱们进入到Windows文件夹中，找到其中的注册表，也就是regedit.exe选项，然后右键点击该项，选择重命名，将文件后缀名“exe”改为“com”。

访问路径 篇3

1 Apriori算法与Web日志的关系

1.1 Web日志挖掘

主要是针对用户浏览信息进行分析, 因此用户会话的提取是首要任务。所谓的用户会话就是某个用户在某个时间段内请求页面的集合。因为各种不确定因素的存在导致Web日志不完整, 增大用户会话的识别难度。Web日志预处理就是用一定的方法处理服务器日志, 从而对用户会话进行识别。

1.2 Apriori算法的不足

Apriori算法虽然可以生成有效关联规则, 但算法的效率不高。因为主要有2个方面影响算法的效率:

(1) 为了生成频繁项集每次会生成大量的候选项集, 候选项集中会存在大量不相关的数据从而影响分析效率。

(2) 每次生成候选项集需要扫描数据库, 数据库存储在磁盘中, 多次的I/O操作浪费大量的时间。所以随着数据库中需要挖掘的数据数据量的增大, 所需时间呈几何级的增长, 严重影响数据挖掘效率。

1.3 Apriori算法和Web日志分析结合

会话识别出来的序列形成事务序列, 我们对网站的数据挖掘和研究基于事务序列的组成, 而事务序列的挖掘刚好可以应用于Apriori算法的频繁项集中, 进行针对网站的网络拓扑结构而产生的事务序列, 在Apriori的改进上生成数组模式的挖掘方式。

2 Apriori基于网络拓扑结构的改进

根据Apriori算法的缺点提出基于数组的改进方法, 改进的主要思想是将事务数据库中的数据扫描一次, 利用数组向量存储事务和每个事务出现的个数, 然后通过对数组向量的扫描进行频繁项集的产生, 并最终生成关联规则。

性质1:如果K维项目集X={i1, i2, i3......, ik}中, 满足j∈X, 且Lk-1 (j) |<k-1, 那么K维项集X一定不是频繁的。

性质2:候选k-项集Ck的频度和长度小于k的事务无关, 因此不必扫描。

算法改进后具体步骤:

(1) 单趟扫描事务数据库D, 将事务数据库中的事务映射到数组向量中, 根据事务长度不同存入大小不同的二维数组中, 行代表事务, 列代表事务的项, 相同长度的事务存入相同大小的数组, 数组的每行代表一个事务, 并且事务按照项的顺序在数组中进行存储。用一个单独数组记录对应事务的次数, 每次扫描到相同的事务次数就加1。直到扫描整个数据库结束。例如:将事务数据库D中的事务映射到数组向量中。如表1所示。

(2) 连接步:Lk-1与自身相连接生成候选集Ck。根据性质3先计算频繁项集Lk-1中项目各个频度, 如果项目频度小于k-1, 即|Lk-1 (j) |<k-1, 设为M={j||Lk-1 (j) |<k-1}, 那么就删除Lk-1中所有包含M中任何元素的项集。删除后得到一个新的频繁项集L’k-1。然后对L’k-1的频度进行判断, 如果L’k-1的频度小于或者等于1, 那么候选集Ck为空集。否则就对L’k-1进行自身相连接生成候选集Ck。

(3) 频度计算步:计算候选集Ck中的各个项集的频度。扫描数组向量时如果数组维数小于k就不扫描, 否则进行扫描并计算频度。即扫描维数大于等于k的数组。从而减少扫描次数, 提高扫描效率。最后和最小支持度相比较, 保留大于等于最小支持度的项集, 构成频繁项集Lk。

3 改进的Apriori算法Web日志应用

实验环境:

计算机硬件为Intel Core2 Duo CPU T7250+2.00GB内存, 开发平台为Mierosoft Windows XP Professional, JDK和JRE环境配置, 开发工具Eclipse4.2.1, 使用JAVA语言开发。对Weka重新编译, 将改进的Apriori算法带入weka中进行预处理后的Web日志数据挖掘。

将改进后的算法命名为Apriori Array, 在相同事务数不同最小支持度条件下, Apriori算法改进前后进行比较。

数据事务数为1589, 最大事务长度为9, 最小支持度区间为0.1-0.4, 对Apriori算法和Apriori Array算法进行比较。

结果表明, Apriori Array产生的关联规则数和频繁项集数与改进前经典的Apriori算法一致, 证明Apriori Array算法的正确性。

从图1的算法改进后的对比中可知, 通常当最小支持度使用不同的数据以及保持事务处理数据衡定的条件下, 通过获得的数据进行传统的Apriori算法以及改进后的Apriori数组算法测试, 所得的结果是改进后的Apriori数组算法在处理数据的时间开销方面比Apriori算法的处理数据的时间开销要低很多, 由此可知, 改进后的Apriori数组算法更能适合应用的需求, 数据库处理数据的能力也大大加强。

参考文献

[1]顾春华, 崔桂勇, Web使用挖掘中数据预处理技术研究[J].现代计算机 (专业版) , 2009-02-25, 13-17.

[2]李天霞.数据仓库的设计与数据预处理技术的实现[J].吉林大学硕士论文, 2008-04-01:26-30.

[3]蔡伟杰, 张晓辉, 朱建秋, 朱扬勇.关联规则挖掘综述[J].计算机工程, 2001-05-01:3-7.

访问路径 篇4

互联网规模和覆盖面的迅速增长带来了信息超载的问题———过量信息,使得用户无法从中获取对自己有用的部分,信息使用效率反而降低[7]。个性化推荐系统作为一种信息过滤的重要手段,由系统主导用户的浏览顺序,引导用户发现需要的结果,它不仅能为用户提供高质量的个性化服务,而且能够与用户建立长期稳定的关系、提高用户忠诚度,防止用户流失。而个性化推荐的基础是Web挖掘技术。通过分析、挖掘用户Web访问日志,提供实时个性化页面推荐[1]、优化的站点结构成为网站管理者提高网站竞争力的重要手段。然而由于本地缓存和代理服务器的存在,使得日志中保存的用户访问路径不完整,因而在挖掘日志之前必须对进行用户访问路径补全。

自1999年Pyle提出在数据挖掘过程中增加数据预处理[2],Cooley在文献[3]中提出Web日志挖掘的预处理的关键任务在于如何修复错误数据和处理缺失数据以来,学者们提出一系列路径补全算法[4,6],并运用这些方法对Web日志中的用户访问路径进行了补全。这些方法有一个共同点,即在路径补全时都结合了网站的静态拓扑结构。在个性化推荐等技术应用日趋广泛的情况下,不同用户在访问同一个站点时,站点的拓扑结构是动态变化的,用以上方法对这些网站的Web日志进行路径补全,得到的结果准确率较低。针对这个问题,本文提出了一种动态站点结构下基于页面类型的路径补全算法PCBPS,较好地解决了动态站点结构下的用户访问路径缺失的问题。

1 Web挖掘及Web日志数据预处理

Web挖掘分为Web内容挖掘、Web结构挖掘和Web应用挖掘等三方面内容[5],其中,Web应用挖掘的应用较为广泛,它是分析Web日志、发现用户频繁访问模式的重要手段。Web应用挖掘过程分为三个阶段:数据预处理、模式发现和模式分析。模式发现和模式分析以数据预处理产生的结果为数据基础,其结果的好坏决定了模式发现和模式分析的准确性,因而数据预处理是Web日志挖掘中非常重要的一个阶段。

从站点结构的角度出发,个性化推荐改变了网站以往的页面和静态链接构成静态站点的结构,它使网站的站点结构随着用户的不同而动态变化。在早期的数据预处理模型下,预处理得到的数据已经不能适应这种动态的站点结构。通过对传统的数据预处理模型进行分析,结合动态站点结构下用户访问路径缺失问题,本文提出了一种改进的Web日志数据预处理模型(如图1所示),并在该模型下进行路径补全。

(1)数据清理Web日志中存在大量的干扰数据,主要包括非用户直接请求页面、Web Robot访问记录和噪声数据。这些数据严重干扰了Web日志挖掘结果的准确性,Web日志预处理的第一个阶段任务是清理这些干扰数据。

(2)用户识别Web日志中不同IP地址代表不同的用户,但由于代理服务器、防火墙的存在,多个用户可能使用同一公共IP访问网站,此时必须进行用户识别。本文采用以下策略进行用户识别。

(1)不同IP代表不同用户;

(2)同一IP不同代理服务器,表示不同用户;

(3)若IP和代理服务器相同,则查看浏览器种类,不同浏览器类型代表不同用户;

(4)若IP、代理服务器和浏览器种类都相同,则查找页面的参考页,参考页面若不在前面的访问序列中,则代表不同用户。

(3)会话识别在时间跨度较大的Web日志服务器中,用户可能多次访问一个站点。这个时候需进行会话识别。文献[8]给出了一个较好的用户会话识别方法,本文采用此方法进行用户会话识别。

(4)Frame页面过滤文献[9]提出了一种数据预处理中的Frame页面过滤算法,去除了用户访问路径中影响挖掘频繁访问路径的Frame页面。

(5)路径补全在Web预处理过程中另一个重要的问题是确定访问日志中是否有重要的请求没有被记录。由于客户端本地缓存和代理服务器缓存的存在,用户在通过以下三种方式进行页面访问时,会造成服务器端日志记录的缺失。(1)利用浏览器中的“后退”按钮进行后退(最常见);(2)链接已经访问过的页面;(3)直接从浏览器历史列表中点击一个链接。

为了发现服务器中缺失的用户访问页面,得到真实的用户访问路径,通常采用以下几种方法[6]:

(1)网站设计时,在标志中设置过期时间,使本地缓存失效,这样Web日志中不会出现用户访问页面缺失的情况。但这种方式必然增加服务器的负荷,降低服务的质量。

(2)利用cookie文件包含用户名字、过期时间、访问路径等有用信息的特性,实现用户真实访问路径的补全。但如果用户关闭了cookie,服务器将无法使用cookie进行路径补全。

(3)结合访问日志、站点拓扑结构实现路径补全。这种方法是目前广泛使用的方法,取得了一定的成果。文献[3]提出了用户浏览路径补全算法PRM(Pattern Restore Method);文献[5]结合站点的拓扑结构,提出最短向后父节点算法SBFN(Shortcut Backwards Father Node)。然而在个性化推荐技术如此广泛应用的网络时代,站点结构会动态变化,这些方法无法准确地进行路径补全。

由于个性化推荐技术的存在,使得不同用户同一时间或同一用户不同时间在访问网站时,网站展现给用户的站点结构往往不同,据此本文采用在动态站点结构下基于页面类型的路径补全算法,提出动态站点结构的构造方法,以解决动态站点结构问题。将页面分为框架页面、导航页面、内容页面,根据页面类型的不同,总结出用户在不同页面类型下用户的访问习惯,根据缺失页面点参考页面的类型进行路径补全。

2 用户访问路径补全算法

在对用户访问路径进行补全前,首先采集用户访问页面时的站点信息,然后建立网站的动态站点结构,确定站点结构的存储形式,最后完成路径补全算法。

2.1 静态站点结构信息

一个网站由多个网页组成,在建立网站之初,网站的设计者已经确定了每个网页的基本信息,包括页面的内容及页面的出度。内容是指用户感兴趣的信息,出度是指页面包含的链接个数。通过提取每个页面的基本信息,本文建立网站的静态站点结构,并对其进行管理。

定义1静态站点信息文件。存储站点每个页面的基本信息及各个页面之间的静态链接信息的集合称为网站的静态站点信息文件,用于存储在建立网站时已存在的页面信息和页面间的链接。文件中的记录表示为:Si:[Ui,Pi,URLi]。各属性含义如下:

Ui:页面的URL。

URLi:页面包含的静态URL,如果包含多个URL,每个URL之间用“;”分隔。网页中存在大量的图片,由于页面尺寸大小有限,很多图片是以缩略图形式存在,需点击后浏览图片的详细内容,此时的链接并非路径补全算法所需要的链接。为了节省存储空间,同时减少查询所需的时间,本文在存储包含的链接时,去除这种链接,同时去除类似的链接,如.doc、.xls、.rar、.zip等。

Pi:页面类型。本文将页面分为三类,框架页面、导航页及内容页面。框架页面是定义多窗口页面的大小、位置及内容并包含一些内容的页面;导航页是用户为获得感兴趣的页面而访问的一些页面;内容页面则是包含了用户感兴趣的信息而浏览的页面。

2.2 动态站点结构信息

当用户访问存在个性化推荐技术的页面时,假如该页面存在动态链接,本文把相应的页面信息存储于动态站点信息文件,记录下用户访问时站点的链接状态,从而建立每个用户每次访问的站点拓扑结构。

定义2动态站点信息文件。用于存储所有用户访问存在动态链接页面信息的集合称为动态站点信息文件,文件中的第i条记录表示为Di:[Ti,Ui,Ii,P-URLi]。各属性含义如下:

Ti:用户访问页面的时间,唯一标记每条记录。

Ui:用户访问的页面的URL。

Ii:用户的IP地址。

P-URLi:用户所请求的页面Ui内,通过个性化推荐技术产生的动态链接的URL。如果包含多个URL,每个URL之间用“;”分隔。与静态站点结构中的URLi相同,去掉路径补全算法不需要的链接。

2.3 站点结构的存储

根据路径补全算法PCBPS的需要,本文把站点的拓扑结构分为静态站点结构和动态站点结构。

定义3网站的静态结构。一个网站本身所固有的页面之间的链接,将网站的各个页面链接为一个连通整体,这个整体称为网站的静态结构。

定义4通过个性化推荐技术,不同用户访问站点或同一用户在不同时间访问站点时,页面之间动态添加链接,这些页面间的链接,使网站的站点结构在不同用户面前呈现不同的结构,这种结构称为网站动态站点结构。

由于站点页面包含的链接数目不同,考虑到存储代价,站点的页面集合多以树型结构进行存储。树的根节点,即网站的首页,首页内每个链接作为根节点的一个树支,每个链接的页面作为根节点每个子树的根节点。然而,随着网站规模的扩大,网站的复杂性也随之增大,因此会出现页面链接有很多回溯的情况。个性化推荐技术的应用更加增大了站点复杂性,不仅会出现更多回溯情况,而且会出现一个子树的中间节点和这个子树根节点的兄弟节点或兄弟节点的孩子节点有链接(如图2所示),在这种情况下,用树进行存储极易造成链接混乱,固本文采用图的存储形式对页面进行存储,如图3所示。

由于邻接矩阵能容易地确定图中两个点是否有链接关系,固本文采用邻接矩阵存储结构对站点结构进行存储。

定义5定义静态站点结构图G1=(V1,E1),V1代表网站的各个页面,即图中顶点,顶点顺序依次为(v0,v1,…,vn),E1为站点页面间的链接,即图中顶点间的有向链接,G1的邻接矩阵A1是n阶方阵,规定:

则图2的邻接矩阵如图4所示。

对一个用户的一次访问的路径进行补全时,需要结合网站静态站点结构图和动态站点信文件建立相应的动态站点结构图。

定义6定义动态站点结构图G2=(V2,E2),V1代表网站的各个页面,即图中顶点,顶点顺序依次为(v0,v1,…,vn),E1为站点页面间的链接,即图中顶点间的有向链接,G1的邻接矩阵A2是n阶方阵,规定:

则图3的邻接矩阵如图5所示。

2.4 路径补全算法PCBPS

PCBPS算法的基本思想,是利用日志中的引用域和动态站点结构,结合页面类型进行缺失页面的补全。恢复的日志文件格式为Ci:[Ui,Ti,Li,Ri,Mark],其中,Ui为第i条记录的用户IP;Ti为第i条记录的时间戳;Li为第i条记录用户请求的URL;Ri为第i条记录的参考页面;Mark为第i条记录的标记,用以区分原始记录和恢复的记录。

算法首先检查会话的第一条记录的引用域(R1)是否有数据,如果有,且引用信息属于当前站点,那么一定有一条日志记录丢失,需要将其还原。将每一条日志记录Ci的引用URL(Ri)与前一条记录的URL(Li-1)进行比较,如果它们相同,说明没有页面缺失,如果它们不同,说明在当前记录之前一定有数据丢失,需进行路径补全。如果当前记录的引用URL(Ri)与本次会话前面中Ci前面的所有Lm(其中10)条记录Cl的Ll相同,则首先找到距Ci最近的Cl。本文将页面的类型分为框架页面、导航页面、内容页面,PCBPS算法将根据页面类型的不同分别进行路径补全。

算法过程:

2.5 算法实现

(1)静态站点结构抽取本文使用Web爬虫提取站点中页面的链接关系,并将其写入Struct数据库表中,url字段中存储当前页面的URL,suburl字段中存储当前页面包含的所有静态链接的url。同时提取Frame页面关系,并将其写入Frame Relation数据库表中,frame字段存储Frame页面的URL,subframe字段存储Sub Frame页面的URL。

(2)动态站点结构采集在收集Web日志的同时,如果用户访问了包含个性化推荐的页面,记录用户访问页面的动态链接状态,并将其写入Dynamic Struct数据库表中,time字段存储用户访问的时间,url存储用户访问页面的URL,suburl存储页面中动态链接的URL。

(3)数据准备路径补全为数据处理的最后一个阶段,首先对取得的日志数据进行数据清理、用户识别、会话识别和Frame页面过滤,并将结构存入Session Log数据库表中,SessionLog包括:记录编号、用户编号、会话编号、用户IP、访问时间、页面URL、参考URL和标记的字段。

(4)路径补全(1)根据表Struct和Dynamic Struct生成静态站点结构矩阵和动态站点结构矩阵;(2)使用本文提出的路径补全算法对每个会话进行路径补全,并将补充的路径写入SessionLog表;(3)处理过所有会话后,算法结束。

3 实验结果及分析

本文以沈阳航空工业学院研究生部网站(http://yjs.syiae.edu.cn)的日志为实验数据,整个站点包括235个html页面和431个asp页面。为了测试算法的准确性,本文设计5条不同的浏览路径,对服务器端的每组Web日志数据分别运行PCBPS算法、PRM算法和SBFN算法,最后将结果与原始模式进行比较,结果见图6。

对每个会话进行路径补全,算法的正确率P=T/T+F,T为正确补全访问记录的个数,F为错误的路径补全个数,其值为以下三种情况值之和:(1)错误补全的记录数;(2)未补全的记录数;(3)多补全的记录数(真实路径中包含的页面)。R表示设计的路径。AVG表示平均正确率。

在设计这5条访问路径时,更多考虑了使用个性化推荐产生的链接进行页面跳转,通过实验发现,PCBPS算法的平均准确率为0.928,PRM算法和SBFN算法的平均准确率分别为0.818和0.833,可以看出在动态站点结构下PCBPS算法的准确率要远高于PRM算法和SBFN算法。同时,在文献[4]中PRM算法的第一阶段的平均准确率为0.966,第二阶段的平均准确率为0.867,本文中PRM算法的准确率为0.818,远低于在普通站点结构下的准确率,进一步证明PRM等算法目前存在的局限性。

4 总结

本文针对传统数据预处理模型中没有考虑个性化推荐技术的存在对站点结构的影响,以及页面类型对用户浏览模式的影响,提出了一种在个性化推荐模式下的路径补全算法:基于页面类型的路径补全算法(PCBPS)。本文提出了动态站点结构的概念,同时对站点存储的数据结构进行改进,使用邻接矩阵存储站点页面,虽然矩阵的稀疏性提高了,浪费了一些存储空间,但在算法运行过程中很大程度上提高了程序运行的效率。最后,通过实验证明,在个性推荐模式下,PCBPS算法的准确性远高于传统的算法,具有一定的可行性。由于在路径恢复时,需要建立用户的动态站点结构,算法的时间复杂度有所增高,在今后的研究中,重点在于提高算法的执行效率,降低算法的时间复杂度。

摘要：路径补全是Web日志数据预处理的重要阶段,目前的路径补全技术大多基于静态网站结构实施。个性化推荐技术的广泛应用,使站点结构由静态结构转变为动态结构。针对目前各种路径补全算法无法解决动态站点结构下用户访问路径中页面缺失的问题,提出动态站点结构的概念、构造方法及站点结构的图结构存储策略。在此基础上,提出一种在动态站点结构下的基于页面类型的用户访问路径补全算法PCBPS(Path Complement Based on Page Sort)。实验证明在动态站点结构下,这种方法能较准确地恢复用户访问路径中的缺失页面,较好地提高了路径补全的准确率。

关键词：个性化推荐,路径补全,动态站点结构,页面类型

参考文献

[1]王实,高文,李锦涛.基于分类方法的Web站点实时个性化推荐[J].计算机学报,2002,25(8):845-852.

[2]Pyle D.Data Preparation for Data Mining[M].Morgan Kaufmann Pub-lishers Inc,San Francisco,CA,1999:540.

[3]Robert Cooley,Bamshad Mobasher,Jaideep Srivastava.Data Preparationfor Mining World Wide Web Browsing Patterns[J].Knowledge and In-formation Systems,1999,1(1).

[4]I-Hsien Ting,Chris Kimble,Daniel Kudenko.A Pattern Restore Methodfor Restoring Missing Patterns in Server Side Clickstream Data[J].Web Technologies Research and Development,2005,3399:501-512.

[5]Jaideep Srivastava,Robert Cooley.Web Usage Mining:Discovery andApplications of Usage Patterns from Web Data.SIFKDD Explorations,2000,1(2):12-23.

[6]王琼,刘珏,徐汀荣.结合Web站点结构的路径补充[J].计算机技术与发展,2007,17(6):121-122.

[7]许海玲,吴潇,李晓东,等.互联网推荐系统比较研究[J].软件学报,2009,20(2):350-362.

[8]董志锋,陈俊杰,付裕峰.Web日志会话的个性化识别方法的研究[J].计算机工程与应用,2008,44(8):179-182.