文摘gydF4y2Ba

发现从web日志数据访问模式是一个典型的序列模式挖掘的应用程序,很多访问模式挖掘算法。在本文中,我们提出一种改进的方法Gap-BIDE算法从web日志数据中提取用户访问模式。与之前相比Gap-BIDE算法,提出了一套过程的大事件所提供的算法;该方法可以找出频繁事件通过丢弃罕见的事件不发生不断的访问时间生成候选模式。在实验中,我们比较前面的访问模式挖掘算法提出了一个,这表明,我们的方法是非常有效的发现在大型数据库访问模式。gydF4y2Ba

1。介绍gydF4y2Ba

网络已经成为一个重要的通道进行商业交易和电子商务。同时,它提供了一个方便我们相互交流。随着网络技术的快速发展,网络已经成为一个重要和优先分配和获取信息的平台。自动收集的数据网络和应用程序web服务器代表网络用户的导航行为,和这些数据称为web日志数据。gydF4y2Ba

Web挖掘技术发现和从Web日志数据中提取有用的信息。因为巨大的增长的信息来源,各种研究社区的兴趣越来越浓,和最近的兴趣电子商务、网络挖掘的领域已经成为庞大且更有趣。它处理数据与网络有关的事物,如数据隐藏在web内容,数据在web页面和数据存储在web服务器。根据数据的类型,有三个类别的web挖掘:web内容挖掘,网络结构挖掘和web使用挖掘(gydF4y2Ba1gydF4y2Ba]。网络使用数据包括来自Web服务器的访问日志的数据,浏览器代理服务器日志和日志。它也被称为网络访问模式。Web使用挖掘试图发现Web日志文件的访问模式。Web access跟踪可以被定义为Web页面历史gydF4y2Ba2gydF4y2Ba];挖掘任务是一个过程的web访问日志中提取有趣的模式。有很多web使用数据挖掘技术包括统计分析(gydF4y2Ba3gydF4y2Ba),关联规则(gydF4y2Ba4gydF4y2Ba),序列模式(gydF4y2Ba5gydF4y2Ba- - - - - -gydF4y2Ba7gydF4y2Ba)、分类(gydF4y2Ba8gydF4y2Ba- - - - - -gydF4y2Ba10gydF4y2Ba),和聚类gydF4y2Ba11gydF4y2Ba- - - - - -gydF4y2Ba13gydF4y2Ba]。访问模式挖掘是一个受欢迎的序列模式挖掘的方法,从序列数据库中提取频繁子序列(gydF4y2Ba14gydF4y2Ba]。此外,发现访问模式是一个重要的挑战领域的web挖掘。和流行的应用程序的访问模式挖掘是网络用户的行为的获得有用的信息。gydF4y2Ba

很多研究已经提出访问模式挖掘寻找有价值的知识从web日志数据,如AprioriAll算法(gydF4y2Ba15gydF4y2Ba,gydF4y2Ba16gydF4y2Ba和GSP算法(广义序贯模式)gydF4y2Ba17gydF4y2Ba]。所有以上算法挖掘序列模式使用范例的候选人generate-and-test维护一组候选人已经在开采过程中开采模式。巨大的数据集时,它会产生大量的候选模式。换句话说,GSP算法需要多少内存数据集时大。等待算法(gydF4y2Ba18gydF4y2Ba]我频繁模式没有保持候选人模式集,因此它需要更少的空间中挖掘的任务。以上算法关注发现相邻的模式,可能会错过一些隐藏的不连续的模式之间的关系。所以差距应该考虑的约束。在文献[gydF4y2Ba19gydF4y2Ba),作者提出了一种改进的等待算法(Gap-BIDE)矿业闭序列模式约束的差距,认为模式不仅相邻,也非邻接;Gap-BIDE算法已经应用于web挖掘(gydF4y2Ba20.gydF4y2Ba]。和之前的工作gydF4y2Ba21gydF4y2Ba),我们已经改善了Gap-BIDE算法之前丢弃偶发事件生成频繁候选事件并将改进的算法应用于访问模式挖掘和探讨了有效参数值的差距。在本文中,我们执行改进算法和比较与先前的访问模式挖掘算法的效率,比如GSP算法。gydF4y2Ba

本文的其余部分组织如下。部分gydF4y2Ba2gydF4y2Ba介绍了我们的算法与原算法的先例。部分gydF4y2Ba3gydF4y2Ba关注发现访问模式,即预处理、模式发现,和结果分析,它关注的效率方面的建议的方法访问模式挖掘。节gydF4y2Ba4gydF4y2Ba,我们提供了一个广泛的性能研究。最后,我们总结本研究的部分gydF4y2Ba5gydF4y2Ba。gydF4y2Ba

2。算法的改进Gap-BIDEgydF4y2Ba

2.1。Gap-BIDE算法gydF4y2Ba

Gap-BIDE算法在文献[gydF4y2Ba19gydF4y2Ba),它继承了相同的设计理念等待算法。它具有相同的优点,它不需要维护一组候选模式,消费节省了空间,也可以发现一些隐藏的模式,认为差距之间的关系约束。gydF4y2Ba

该算法首先发现的频繁模式,然后矿山gap-constrained闭序列模式和模式gydF4y2Ba作为前缀。在这个过程中,它首先扫描向后前缀模式的空间gydF4y2Ba,采用gap-constrained backscan修剪方法修剪搜索空间,向前扫描空间的前缀gydF4y2Ba,并使用gap-constrained模式检查计划,检查是否关闭模式gydF4y2Ba关闭;最后,它扫描每个前进空间表象的模式gydF4y2Ba发现的所有局部频繁项集,gydF4y2Ba使用每一项gydF4y2Ba延长gydF4y2Ba,矿山gap-constrained闭序列模式为新前缀再次通过调用子程序。gydF4y2Ba

算法,提出空间被定义为给定的模式出现gydF4y2BaPgydF4y2Ba(gydF4y2Ba米gydF4y2Ba,gydF4y2BaNgydF4y2Ba)和三(sid, beginPos endPos)。外表的前进空间范围[endPos +序列的一部分gydF4y2BaendPos +gydF4y2Ba]gydF4y2Ba[endPos,gydF4y2Ba),gydF4y2Ba序列的长度是sid。这里,提出空间(FS)的定义是诱导获得频繁子序列模式。我们可以得到每个子序列的序列支持通过扫描转发空间表象的一个前缀模式。序列的支持度大于或等于最小支持度阈值的方法将一个前缀的频繁子序列模式模式。gydF4y2Ba

落后的定义空间(BS)是很重要的,它被定义为给定的模式出现gydF4y2Ba与三(sid, beginPos end-Pos)。外形的逆向空间序列的一部分sid的范围[beginPos−gydF4y2Ba,beginPos−gydF4y2Ba]gydF4y2Ba 。gydF4y2Ba

建议的方法表明,Gap-BIDE既运行时的性能和空间高效挖掘频繁,关闭序列约束与差距。gydF4y2Ba

2.2。改进Gap-BIDE算法gydF4y2Ba

虽然Gap-BIDE算法在序列模式挖掘的算法先进,仍有很多傻瓜差事期间完成挖掘任务,比如生成一些候选模式偶发事件的原始数据集。避免不必要的内存使用,一种改进的算法。我们的算法是基于Gap-BIDE算法设计;主要的思想是生成频繁候选事件之前抛弃偶发事件;我们称这一过程为一个大事件。gydF4y2Ba

算法gydF4y2Ba1gydF4y2Ba是主要的算法。该算法gydF4y2Ba2gydF4y2Ba子程序的算法gydF4y2Ba1gydF4y2Ba;提出大事件集的过程。一个大事件集(LES)是一个事件组包含事件满足用户指定的最小支持度阈值。莱斯表示交易发生的事件或对象与大部分在整个数据集。本文web日志文件表示的数据集,和一个web页面被定义为一个事件;因此,莱斯表示web页面的集合所访问的网络用户有足够的频率在一段时间。在采矿过程中,生成序列通过莱斯可以减少测试数据的数量来提高挖掘的效率和准确性的任务。在获得大事件集,生成的序列数据只有大事件。然后扫描算法生成的数据库,发现所有频繁项集与长度(长度为1),并调用算法gydF4y2Ba3gydF4y2Ba迭代。算法gydF4y2Ba3gydF4y2BapatternGrowth (gydF4y2Ba)是其他子程序的算法gydF4y2Ba1gydF4y2Ba;它提出了过程我gap-constrained闭序列模式与模式gydF4y2Ba作为前缀。gydF4y2Ba

生成的一个重要定义莱斯是用户会话。用户会话是一个活动,一个用户提供一个独特的IP地址花费在一个网页上指定的一段时间。它可以用来识别一个连续访问用户数据访问的措施。在指定的时间内决定通过一个cookie,也称为web饼干和HTTP cookie,这可以由服务器设置有或没有一个截止日期,由网页设计师修改,设置为缺省值为600秒。在到期日,网络用户的访问是有效的。gydF4y2Ba

3所示。发现的访问模式gydF4y2Ba

在本节中,挖掘任务的过程进行了探讨。gydF4y2Ba

3.1。数据预处理gydF4y2Ba

Web日志文件驻留在Web服务器上记录客户的活动通过Web浏览器访问Web服务器。传统上,有许多类型的web日志文件包括错误日志、访问日志,和参考日志。摘要网络访问日志中的数据被定义为原始数据。网络访问日志记录所有由web服务器处理请求。日志文件中的数据包含了一些缺失值数据和相关属性;它不能直接用于挖掘的任务。在本节中,我们描述了数据清理的过程和属性选择删除不需要的数据。gydF4y2Ba(1)gydF4y2Ba数据清理gydF4y2Ba:删除无关的数据。gydF4y2Ba(一)gydF4y2Ba删除记录的url jpg, png、gif, js, css,等等,这些都是自动生成的,当一个web页面请求。gydF4y2Ba(b)gydF4y2Ba删除数据和错误的雕像的数字开始数字4或5gydF4y2Ba。这些错误的记录是由错误的请求或服务器。例如,HTTP客户端错误:400错误请求和404没有找到和HTTP服务器错误:500内部服务器错误和505 HTTP版本不支持。gydF4y2Ba(c)gydF4y2Ba丢弃缺失值的数据是由打破一个web页面时加载引起的。gydF4y2Ba(2)gydF4y2Ba属性选择gydF4y2Ba:删除不相关的属性。有许多属性web日志文件的一个记录。在本文中,我们需要的属性IP地址,时间,和URL;因此,其他的属性方法,状态,大小,等等,需要被丢弃。gydF4y2Ba(3)gydF4y2Baurl转换为数字代码。gydF4y2Ba

很难区分web日志数据的请求的url在成千上万的记录。通常有很多种类的web页面在成千上万的记录。url可以转换成代码编号为简单。例如,一个web日志数据来自服务器的网站gydF4y2Bahttp://www.vtsns.edu.rs/gydF4y2Ba,有31个不同类型的web页面被访问。我们自己的url转换成代码数字,比如galerija。php→1, nenastavno_osoblje。php→15日和rezultati_ispita。php→21。gydF4y2Ba

我们选择一组数据从web日志文件作为示例数据。数据预处理后,我们得到清洁数据表所示gydF4y2Ba1gydF4y2Ba。gydF4y2Ba

3.2。发现访问模式的过程gydF4y2Ba

在本节中,我们提出的过程发现访问模式的一个例子。gydF4y2Ba

数据预处理后,我们将算法应用于web日志数据。然后,LES生成与分类表中的数据gydF4y2Ba1gydF4y2Ba属性的IP地址和时间;这里,用户会话的时间为简单起见被定义为一个小时。然后,这些数据被分组通过为每个网络用户一个小时;最后,排序数据如表所示gydF4y2Ba2gydF4y2Ba。gydF4y2Ba

然后,我们计算每个事件的支持。例如,对于事件gydF4y2Ba,三次,在时间2“82.117.202.158”,在“82.208.207.41”时间2,在“82.208.255.125”时间2。计算事件的支持后,候选人获得事件集如表所示gydF4y2Ba3gydF4y2Ba。gydF4y2Ba

最后,(度)必须用户指定的最小支持度阈值的定义。度表示一种抽象的水平,是一个程度的概括。选择度是很重要的;如果是低,那么我们可以得到一个详细的事件。如果它是高的,那么我们可以得到一般事件。在这个例子中,度被定义为75%。换句话说,如果一个网页访问大于或等于75%的网络用户,那么这个网页可以被表示为一个大事件。大事件集的过程后,莱斯得到如表所示gydF4y2Ba4gydF4y2Ba。gydF4y2Ba

在获得莱斯,罕见的事件gydF4y2Ba,gydF4y2Ba,gydF4y2Ba从表中移除gydF4y2Ba2gydF4y2Ba事件,然后转换成一组元组(序列标识符,序列)。我们定义的IP地址序列标识符和事件定义为一个序列。序列集如表所示gydF4y2Ba5gydF4y2Ba。gydF4y2Ba

然后,我们称之为原始Gap-BIDE算法来发现频繁序列模式和修剪模式。在这里,被定义为的差距gydF4y2BaggydF4y2Ba(gydF4y2Ba米gydF4y2Ba,gydF4y2BaNgydF4y2Ba),gydF4y2Ba的值是最小的差距,然后呢gydF4y2Ba的值是最大的差距。假设一个模式gydF4y2Ba与gydF4y2BaggydF4y2Ba(gydF4y2Ba米gydF4y2Ba,gydF4y2BaNgydF4y2Ba),它可以表示为gydF4y2BaPgydF4y2Ba(gydF4y2Ba米gydF4y2Ba,gydF4y2BaNgydF4y2Ba]。给出了这种方法的描述约束mingap和maxgap时机。如果该值的gydF4y2Ba米gydF4y2Ba- - - - - -gydF4y2BaNgydF4y2Ba是gydF4y2Ba,然后在一个序列的事件必须发生gydF4y2Ba事件发生在前面的事件。gydF4y2Ba

调用我们的改进算法后,我们得到了封闭模式如表所示gydF4y2Ba6gydF4y2Ba。gydF4y2Ba

从实验结果可以找到有用的信息。web页面的关系很容易,直接和用户行为信息显示。输出顺序模式中的每个数字代表一个网站或一个web用户请求。例如,数字6和7 ispit_raspored_god代表web页面。php和upis_prva。分别php。闭序列模式(gydF4y2Ba6gydF4y2Ba,gydF4y2Ba7gydF4y2Ba表所示)gydF4y2Ba6gydF4y2Ba,这意味着75%的用户会话(3,4)upis_prva web用户访问web页面。php ispit_raspored_god往往总是访问web页面。php。根据这两个网页之间的关系,可以提高web页面的设计。例如,网页设计师ispit_raspored_god可以超链接添加到web页面。php upis_prva.php指向web页面。这种方法可以应用在许多领域。例如,在电子购物车,当顾客完成购物,可以有一些超链接完成网页指向一些相关网页购买历史的根据挖掘结果。当网民看电影,一些超链接指向的网页相关的电影网站上必须存在。gydF4y2Ba

4所示。实验结果和分析gydF4y2Ba

4.1。参数的影响的过程中越来越大事件集gydF4y2Ba

得到一套大型事件的过程旨在提取满足用户定义的事件最小大事件集的支持。它可以丢弃偶发事件减少实验数据库减少搜索空间的大小和时间的准确性和维护的整个过程挖掘的任务。评价参数的效果,我们比较大的数字事件通过改变最小的值大事件集(怪物带有)的支持。在这个实验中,实验数据记录的访问信息网站(gydF4y2Bahttp://www.vtsns.edu.rs/gydF4y2Ba),这是一个机构的官方网站。原始记录在web日志文件的数量是5999,数据预处理后,有269用户会话记录。实验结果显示在图gydF4y2Ba1gydF4y2Ba。我们可以看到,最小支持越小,获得的更广义莱斯。总是存在一个值最低的支持,从价值,大事件的数量不会改变,或将改变很少。这个值总是选择作为最低支持实验的价值。gydF4y2Ba

4.2。与原始Gap-BIDE算法进行比较gydF4y2Ba

在本节中,我们比较我们的算法与原Gap-BIDE算法(gydF4y2Ba19gydF4y2Ba]。实验数据来自互联网信息服务器(IIS)日志为msnbc.com和msn.com新闻相关的部分整个9月28日,1999年。每个序列数据集对应页面浏览量的用户在24小时内。序列中的每个事件对应一个用户请求一个页面。有989818个匿名用户会话;我们选择的测试数据不重复简单随机抽样的方法从这些数据。在实验中,大事件我们定义最小支持度阈值设置为20,最低10闭序列模式的支持,和价值的差距gydF4y2Ba。我们实现了实验2.40 - ghz Pentium PC机和4.00 GB内存算法在Python 2.7 JDK 1.6.0跑去。然后,实验结果如图gydF4y2Ba2gydF4y2Ba。它表明,当应用我们的算法,时间成本小于原来的Gap-BIDE算法。gydF4y2Ba

4.3。与GSP算法gydF4y2Ba

先前的研究已经表明,我们的算法比原始Gap-BIDE算法更有效,当我们发现访问模式应用的算法。在本节中,我们想要证明我们的算法比先前的访问模式挖掘算法更有效。验证它,我们比较算法和GSP算法提出了(gydF4y2Ba17gydF4y2Ba)和一个实验。实验数据来自互联网信息服务器(IIS)日志为msnbc.com和msn.com新闻相关的部分整个9月28日,1999年,我们选择测试数据不重复简单随机抽样的方法从这些数据。在实验中,我们定义最小闭序列模式的支持10,实验结果如图gydF4y2Ba3gydF4y2Ba。这表明我们的算法应用到大型数据库时,时间的成本小于GSP算法。gydF4y2Ba

5。结论gydF4y2Ba

在本文中,我们提出了改进的应用Gap-BIDE闭序列模式发现算法在web日志数据。我们改进算法通过丢弃所有罕见的事件在生成频繁候选事件之前。在数据预处理的过程中,我们把不相关的属性和url转换为代码数字为简单起见,我们把缺失值数据来提高数据的质量。获得的实验数据挖掘任务中,我们改变了web日志数据序列基于时间约束。时间的价值是由到期日的饼干。结果,我们得到新的web网站访问模式,表达顺序访问基于Gap-BIDE算法。与以前的web挖掘方法相比,该方法达到最佳性能的大事件的序列。它减少了序列更有效和准确的结果。我们做一些实验来比较算法与先前的算法。实验表明,我们的算法使用更少的时间比原来Gap-BIDE算法和花费更少的时间比GSP算法在大型数据库发现访问模式。 In future work, we will try to find a more efficient algorithm for mining the closed gap constraint sequential patterns and will try to achieve a more efficient way for transforming web log files into sequence patterns.

承认gydF4y2Ba

这项工作是由韩国国家研究基金会(NRF)授予由韩国政府资助(最高明的)(没有。2012 - 0000478)。gydF4y2Ba