酷米网(kmw.com),专注高端域名快速交易!

  1. 当前位置: 
  2. 首页 > 
  3. 域名资讯  > 基于粒子群的聚类算法改进及其在访问模式中的应用研究
服务器时间:2018-07-20 09:14:44 (CST +08:00)

基于粒子群的聚类算法改进及其在访问模式中的应用研究

2017-12-17 17:33:22     浏览量: 36

天津大学

硕士学位论文

基于粒子群的聚类算法改进及其在访问模式中的应用研究

姓名:陈君彦

申请学位级别:硕士

专业:信息管理与信息系统

指导教师:张慧颖

20070101

,

中文摘要

从大量顾客日志数据中挖掘有意义的用户访问模式及相关的潜在顾客群,是目前数据挖掘技术在Internet上的重要应用之一,挖掘用户访问网站的模式,可以使网站建设者清楚地了解自己网站不同用户的兴趣和整个网站页面的访问情况,并可进一步优化网站的组织结构或建立自适应网站,从而从中发现商机并方便不同用户的访问。由于现实需求的急迫,越来越多的研究者将目光对准了这个领域,使得Web访问模式挖掘技术得到很快的发展,本论文正是在这样的背景下对用户访问模式聚类算法进行了研究。

本文通过分析Web数据特点及现有聚类算法,得出用户访问模式聚类的特点,提出将粒子群优化算法与K-均值相结合应用于Web访问模式聚类的可能。

通过分析K-均值算法与粒子群优化算法(ParticleSwarmOptimization,PSO),对现有的几种基于粒子群的K.均值聚类算法进行了实验验证,并根据粒子群算法在数据分析应用中的不足,提出了一种基于随机搜索方向的K.均值与粒子群算法结合的聚类算法RVPSO-K,它能够通过改变粒子轨迹提高粒子本身的搜索能力,从而可能尽快地找到全局最优解。经Iris、Zoo、Wine数据集对K.均值算法、粒子群算法及相关的4种改进算法进行测试,结果表明,RVPSO-K算法聚类能力较强,收敛性较好。

RVPSO。K算法应用于用户访问模式时,本文详细地分析了预处理阶段的各项任务,构造了本文算法所适用的UserlD—URL关联矩阵,对聚类中心代表含义进行了说明,提出设定不同的阈值的概念来解决用户后续推荐问题,从而提高调控推荐网页的数量的灵活性,满足不同的推荐需求。实验结果表明,在大量及高维度的用户数据情况下,与其他改进算法对比,RVPSO-K算法具有较强的搜索能力和较好稳定性,且精度较好,速度有明显提升。关键词:粒子群算法K.均值聚类分析Web访问模式

,

ABSTRACT

ItisoneofthemostimportantapplicationsinpresentdataminingtohavetheabilitytodiscoverusefulWebUsagePatternsandpotentialcustomersfromlargevolumesofuseraccesslogs.TheWebUsageMining

userscanmakethewebsite’Screatorsaccessunderstandthedifferentinterestsoftheir

website.Theycanandtheoverallsituationoftheiroralsoorganizethelogicstructureofthewebpage

outsetupaself-adaptiveWebsite,thusdigging

user.Becausethereisabusinessopportunitiesandfacilitatingeacharean

anhighdemandforWebusagemining,thereimcreasingexponential

onnumberofresearchers.ThereforeWebUsageMiningisdevelopingatrate.ThisdissertationmainlystudiestheclusteringofWebUsagePatterns

situations.these

The

charactercharacteroftheclusteringofWebUsagePatternWaSgivenbyWebdataandclusteringmethods.Then,thecombination

onofParticleSwarmIntelligence(PSO)andK-meansisproposedtobeappliedtheWebUsageMining.

TheeffectivemethodwasextractedbyexperimentstotestsomekindsofexistingameliorationofK—meaBsbased

clusteringmethod,RVPSO—KonPSObyanalysingK-meansandPSO.AnewexpatiatedbasedonWaStherandomresearchcombiningK—meansandPSOaccordingtheinsufficiencyofPSOinthedataanalysis.Thesearchingabilityoftheindividualparticlewasenhancedbychangetheflyingtrajectoryoftheparticle,thustheoptimumwouldbefoundin

onarelativelyshortamountoftime.Theexperimentswergconducted

whichshowsthattheRVPSO—KisaIris,WineandGlassdatasets,ofbetterconvergenceandbetterclusteringabilitycomparedwiththeother4relatedmethods.

IntheapplicationoftheWebUsagePattern,themostpopularmethodofdatapreprocessingwerecarriedoutand

ThemeaningoftheclusteringaUserlD-URLrelevantmatrixwasconstructed.wasexplainedcenterandadifferentthresholdwasproposedtobeimplemented,thereforetheagilityoftherecommendedwebwasimprovedtOsatisfydistinctrequirements.TheexperimentsareimplementedonWeblogdataafterpreprocessing,showingthattheRVPSO—Khasstrongersearchingability,betterstabilityandhigherprecisioncomparedwithrelatedmethods.

KEYWORDS:PSO;K—means;Clustering;WebUsagePattern;

,

独创性声明

本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果,除了文孛特别加以标注和致谢之处矫,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得鑫鲞盘鲎或其他教育机构的学位域证书焉使照过的材料。与我一囝工作的露志对本研究所傲的锰何贡献均已在论文中作了明确的说明并表示了谢意。

学位论文作者签名:髓;忍鸟签字目期:砷’年f月纠同

学位论文版权使用授权书

本学位论文作者完全了解叁鲞蕉堂有关保留、使用学位论文的规定。特授权叁洼基堂可以将学位论文的全部或部分内容编入有关数据库进行检索,并采用影印、缩印或扫描等复制手段保存、汇编瑷供查阅和借阕。同意学校向国家有关部门或机构送交论文的复印件和磁盘。

(保密的学位论文在解密螽适用本授权说蹋)

学位论文作者签名:芦。另岛

签字同期:砖审年f月凡7日导师签名:旅棼纯签字日期:私口7年,月zj日

,

第一章绪论

第一章绪论

1.1选题背景与研究意义

近年来,Intemet的快速普及和迅猛发展使得各种信息可以以非常低的成本在网络上获得,使得其成为一个巨大的、分布广泛的和全球性的信息服务中心以及人们获得信息的重要媒介。但随着网络应用的不断深入,各种新型应用向计算机网络提出了新的挑战。对于访问者而言,从海量的网络信息中寻找有用的知识,早已成为迫切需求。对于网站设计运营人员来说,Web站点的规模和复杂程度的增加使得站点设计、网络运行和维护工作,变得越来越困难,需要运用自动辅助设计工具为客户提供快捷、高效的网络链接。在这样的市场需求下,出现了基于Web的个性化信息服务。

早期的基于Web的个性化信息服务主要是新闻、股票、目录推荐等内容组成。随着电子商务的发展,个性化信息服务应用于网上产品推荐和营销,例如Amazon书店、当当网站、Dell计算机公司,都已获得了巨大成功。其原因就是它们能满足不同客户的需求,便捷了与顾客的联系方式,创造出前所未有的经营方式,大大降低了公司的运营成本。随着Web领域技术的不断完善和发展,个性化信息服务将渗透到用户的许多个人业务处理范畴。Web信息将扩展为真正的个人信息,并帮助用户理解和管理这些信息,这种新的服务将成为一种深入到用户个体生活工作各个层面的普及性辅助工具。

目前,这种个性化服务主要体现在Web定制服务、推荐系统以及自适应站点智能服务上,而解决这方面需求的有力工具就是面向Web的挖掘技术。

Web挖掘是从数据挖掘发展起来的,是在大量的非结构化、异构的Web信息资源中抽取感兴趣的、潜在的模式和隐含信息,也是将数据挖掘技术和理论应用于互联网资源的一个新兴研究领域,涉及机器学习、模式识别、人工智能、统计学、计算机语言学、计算机网络技术、信息学等多个领域。Web所处理的对象包括静态网页、Web数据库、Web结构、用户使用记录等信息。Web挖掘当前研究主要有三种分类,Web内容挖掘、Web结构挖掘以及Web访问模式挖掘(Web使用挖掘)。

Web访问模式挖掘是Web数据挖掘的一个主要分支,也是Web个性化的一个重要组成部分。它旨在将数据挖掘技术应用于Web服务器日志文件,通过分

,

第一章绪论

日志文件,发现用户访问特征,页面被访问的规律,设计者的领域知识等,进而研究如何使网站结构设计更加合理化,如何使网站更加吸引访问者以及如何从中发掘更多商业机会。大型的Web站点每天可以有数以百兆字节的Web日志记录,研究Web日志数据库可获得有关Web动态的丰富信息。

在Web访问模式挖掘中,现阶段较为常见的应用分析技术包括:聚类分析、关联规则、序列模式、分类等。Web访问模式挖掘中的聚类分析包括页面聚类和用户聚类。用户聚类是把具有相似浏览模式的用户分成可用于电子商务应用的市场分片和或其它个性化服务,然后依据当前用户所在的用户组为其进行推荐。因此,基于Web用户聚类的数据挖掘对于电子商务中的市场决策和向用户提供个性化服务是非常有帮助的。

另一方面,基于人工智能的群集智能算法是一种新型的模拟进化算法和迭代的并行优化算法。在解决连续优化问题和复杂的组合优化问题方面,与传统启发式优化算法相比都具有明显的优越性。并且如何将它的优点和传统算法的优点相结合,构造出有特色有实用价值的混合算法是当前算法改进的一个重要方向。

本文将就用户在Web访问模式聚类问题进行研究,尤其对群智能中的粒子群算法在Web用户聚类中的应用进行研究。

1.2Web数据挖掘研究现状

Web数据挖掘是从数据挖掘发展过来的,与熟知的数据挖掘定义类似,我们可将Web挖掘定义为:从大量的、不完全的、有噪声的针对包括Web页面内容的、页面之间的结构、用户访问信息、电子商务信息等在内的各种Web数据,提取隐含的、未知的、潜在有用的信息和知识的过程。在Web挖掘中所处理的数据可以来源于服务器、客户端或者代理服务器,也可以来自其他相关的数据源。Web所处理的对象包括静态网页、Web数据库、Web结构、用户使用记录等信息。

1.2.1Wreb数据特点

Web挖掘与传统的数据挖掘定义相类似,但是还有许多独特之处。Web对有效的资源和知识发现具有极大的挑战性,Web挖掘的特性及面临的问题具体表现在:

1.庞大的数据

由于Web为消息在全球范围发布和传播提供了机会,它允许任何人在任何地方任何时间传播和获取信息,使得Web上的信息与日俱增,爆炸性增长。据

,

第一章绪论

2006年上半年的中国互联网络发展状况统计报告调查显示,网民人数、上网计算机数分别达到了1.23亿人、5450万台,与去年同期相比分别增长了19.4%和19.5%;中国域名总数为2,950,500个,其中CN下注册的域名达到1,190,617个,与去年同期相比,增长了91.3%;中国网站总数达到了788,400个。

2.半结构化数据

Web页面的复杂性远比任何传统的文本文档复杂得多。Web页面缺乏同一的结构,Web上的大量文档无法按某一排列次序加以组织,它没有分类索引,也没有特定的模型描述,每一个站点的数据都各自独立设计,并且数据本身具有自述性和动态可变性。因而,Web上的数据虽具有一定的结构性,但因其自述层次的存在,从而是一种非完全结构化的数据,这也被称之为半结构化数据。

3.异构性

从数据库研究的角度出发.,Web网站上的信息也可以看作一个数据库,一个更大、更复杂的数据库。Web上的每一个站点就是・个数据源,每个数据源都是异构的,这就构成了一个巨大的异构数据库环境。

4.动态性

Web不仅以极快的速度增长,而且其信息还在不断地发生着更新。新闻、公司广告、股票市场、Web服务中心等都在不断的更新着各自的页面。链接信息和访问记录也在频繁更新之中。

1.2.2Web数据挖掘分类

由于Web具有这些与传统数据挖掘不同的特点,使得要从这些分散的、异构的、没有统一管理的海量信息中快速、准确地获取信息也成为Web挖掘所要解决的一个难点,也使得用于Web的数据挖掘技术不能照搬用于数据库的数据挖掘技术。所以,开发新的Web挖掘技术这一课题成为目前国内外的研究热点。目前web挖掘主要分为三类:Web内容挖掘(WebConmntMining)、Web结构挖掘(WebStmctureMining)和Web访问模式挖掘(Web使用挖掘,WebUsageMining)。

Web内容挖掘主要包括文本挖掘和多媒体挖掘两类,其对象包括文本、图像、音频、视频和其他各种类型的数据。Web文本挖掘可以对Web上大量文档集合的内容进行关联分析、总结、分类、聚类以及利用Web文档进行趋势预测等,是Web挖掘中比较重要的技术领域。Web上多媒体挖掘主要是利用多媒体提取工具进行特征提取,然后对这些特征进行关联规则或者分类的挖掘操作。多媒体数据挖掘包括对图像、视频和声音的挖掘。Web结构挖掘是挖掘Web潜在的链接结构模式,主要是通过对Web站点的

,

第一章绪论

结构进行分析、变形和归纳,将Web页面进行分类,以利于信息的搜索。这种模式可以用于网页归类,荠且可以由此获得有关不同网页间相似度及关联度的信息。结构挖掘有助于用户找到相关主体的权威站点,并且可以指向众多权威站点相关主题的站点。当前的Web结构挖掘的研究分为两个方向【3】:一般的访问模式追踪,即通过分析使用记录来了解用户的访问模式和倾向,以改进站点的组织结构;个性化的使用记录追踪,即分析单个用户的偏好,根据不同用户的访问模式为每个用户提供定制的站点。

Web访问模式挖掘是对用户访问Web时在服务器上留下的访问数据进行挖掘,来发现用户访问Web页面的模式。这些数据包括:Web服务器日志记录、代理服务器的日志记录、客户端的日志记录、用户简介、注册信息等,因此访问模式挖掘主要是Web日志的挖掘。Web日志分为Server

CookieLogs,ErrorLogs和Logs,日志记录了网页被使用的信息,如IP地址、访问时间、哪一页、字节大小等,因此对用户访问Web站点的存取方式进行挖掘可以实现用户聚类、页面聚类和发现频繁访问路径,可以发现用户访问站点的浏览模式、页面的访问频率等信息,进而可以改善网站设计和为用户提供个性化服务。

1.3结构安排及创新点

本论文的章节安排如下:

第一章简要说明了文章的选题背景及意义,介绍了Web数据挖掘的研究现状,最后概括本文结构安排及创新点。

第二章介绍了数据挖掘技术的理论及相关应用,总结了关联规则、序列模式、分类和聚类等基本理论,同时对进化计算中的群智能算法进行了概述。通过分析Web数据特点及现有聚类算法,得出用户访问模式聚类的特点,分析了现有Web访问模式聚类算法的不足之处。提出将粒子群优化算法与艮均值相结合应用于Web访问模式聚类的可能。

第三章首先概述粒子群相关内容,包括:粒子群优化算法的基本原理、算法的数学描述、算法程序实现流程等,其中探讨了相关参数设置。同时,把粒子群的聚类思想与K.均值算法相结合,提出了基于搜索方向改进的RVPSO.K算法,并详细论述了该算法的实现原理和流程。并采用UCI机器学习数据库中的Iris、Zoo、Wine数据集合对K.均值算法、粒子群算法及相关的4种改进算法进行实验,结果表明,RVPSO.K算法精度最高,收敛性较好。

第四章首先对Web访问模式的理论研究及应用进行了说明。该章主要实现了在用户访问模式(Web日志挖掘)聚类中的应用:描述了实验数据来源及预处理4

,

第一章绪论

方法,定义了UsedD。URL关联矩阵,对本文提出的RVPSO.K算法在用户访问模式聚类进行了实现,同时给出了相关的定义和详细的算法流程图。实验结果表明,在大量及高维度的用户数据情况下,与其他改进算法对比,RVPSO.K算法的精度最高。该算法不仅可用于用户模式聚类,也可广泛用于其他应用领域。

第五章为论文的结束部分,对论文进行了总结,指出了存在的不足以及进一步的研究方向。

本文的创新点主要包括以下几点:

1.通过对传统粒子群算法的分析及对K.均值与粒子群结合的相关改进聚类算法的验证,提出基于速度改进的RVPSO.K算法,这一改进解决了粒子群全局最优位置不是位于初始粒子位置与一个局部最优位置之间情况下,且许多粒子都在同样方向上搜索时,对全局最优解区域形成搜寻盲区的问题,能够通过改变粒子轨迹提高粒子本身的搜索能力,从而可能尽快地找到全局最优解。该算法具有较强的搜索能力和较好稳定性,且精度较好,速度有明显提升。

2.在本文提出的RVPSO-K算法基础上,将其应用于Web访问模式挖掘的用户聚类中。通过实验对聚类算法进行测试与分析,表明该算法较其他几种粒子群与K.均值结合算法,能够很好的提高聚类的准确率指标。

3.在Web日志挖掘的用户访问模式聚类中,对聚类中心代表含义进行了说明,提出设定不同的阈值的概念来解决用户后续推荐问题,从而提高调控推荐网页的数量的灵活性,满足不同的推荐需求。

,

第二章相关技术及理论介绍

第二章相关技术及理论介绍

2.1数据挖掘相关技术及理论介绍

2.1.1关联规则

关联规则挖掘通过统计方法归纳、提取有价值的iothen规则。Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题…,以后关联规则的挖掘问题的大量研究包括对原有的算法进行优化以提高算法挖掘规则的效率,对关联规则的应用进行推广等。在零售业中,关联规则挖掘技术可以发掘商品之间的在销售过程中相互关联关系,利用这些相关性,就可以更好的组织站点的内容和结构,为用户推荐相关的商品,实施更有效的市场策略,从而得到了广泛的应用。比如利用页面之间的这种相关性可以进行交叉销售,从而提高销售量。

基本定义:设I={il,i2,...,in)是二进制文字的集合,其中的元素称为项(item)。记D为交易(transaetion)T的集合,这里交易T是项的集合,并且T酉。对应每一个交易有唯一的标识,如交易号,记作TID。设X是一个I中项的集合,如果

X__cT,那么称交易T包含X。

一个关联规则是形如XjY的蕴涵式,这里XcI,Yci,并且XnY=①。规则XjY在交易数据库D中的支持度(support)是交易集中包含x和Y的交易数与所有交易数之比,记为support(X=>Y),即:

support(Xj驴I{T:XuY匕T,TeD}I/IDl

规则xjY在交易集中的置信度(confidence)是指包含X和Y的交易数与包含X的交易数之比,记为confidence(X≥Y),即

confidence(X:=>Y)=I{T:XwY_cT,TeD}I/I{T:XcT,TeD}I

给定一个交易集D,挖掘关联规则问题就是产生支持度和置信度分别大于用户给定的最小支持度(minsupp)和最小置信度(minconf)l拘关联规则。【I】

关联规则挖掘用来寻找给定数据集中项之间的有趣联系。关联规则的挖掘过程一般分两步进行,其中,第二步比较简单,挖掘关联规则的总体性能主要由第一步决定:

1.找出所有的频繁项集。根据定义,这些项集出现的频率至少和预定义的最小支持计数一样。

2.由频繁项集产生强关联规则:根据定义,这些规则必须满足最小支持度6