Web聚类Hamming算法与K均值算法的研究与实现毕业论文.doc
《Web聚类Hamming算法与K均值算法的研究与实现毕业论文.doc》由会员分享,可在线阅读,更多相关《Web聚类Hamming算法与K均值算法的研究与实现毕业论文.doc(32页珍藏版)》请在三一文库上搜索。
1、 本科生毕业设计(论文)题 目: Web聚类Hamming算法与K均值算法的 研究与实现 姓 名: 陈云峰 学 号: 030300714 学 院: 数学与计算机科学学院 专 业: 年 级: 2003级 指导教师: (签名) 2007 年 6 月 16 日Web聚类Hamming算法与K均值算法的研究与实现摘要聚类分析也称群分析、点群分析,它是研究分类的一种多元统计方法。我们所研究的样品或指标之间存在程度不同的相似性。于是根据一批样品的多个观测指标,具体找出一些能够度量样品或指标之间相似程度的统计量,以这些统计量为划分类型的依据。把一些相似程度较大的样品或指标聚合为一类,把另外一些彼此之间相似程
2、度较大的样品或指标又聚合为另一类,关系密切的聚合到一个小的分类单位,关系疏远的聚合到一个大的分类单位,直到把所有的样品或指标聚合完毕,这就是聚类的基本思想。随着科学技术的不断发展,网络成为了人们生活中必不可少的重要组成部分。因此,关于网页数据的种种研究都有着其重要的现实意义。特别是网页聚类,它关系着人们网上获取信息效率的高低,同时也是网页信息组织的主要依据。本文通过对Web日志数据的挖掘研究,应用两种聚类的算法,Hamming算法和K均值算法,将用户所访问的网页进行聚类。在这两种算法中,首先以Web站点URL为行,UserID为列建立URL-UserID关联矩阵.两种不同算法构造的矩阵中的元素
3、值不同,文中会详细说明,然后对行向量进行相似性分析,可以得到相似的Web群体类,从而完成对Web网页的聚类。关键词:网页聚类, 数据挖掘, Web日志, K均值算法, Hamming算法Web Polymerization: The Reaserch and Realization of Hamming Algorithms and Kmeans AlgorithmsAbstractCluster analysis is also called cluster analysis, cluster analysis point, it is a classification study of m
4、ultivariate statistical methods. The samples or indicators we studies exist different degrees of similarity. In accordance with the number of samples over observation indicators, we can find some specific samples to measure or indicator the degree of similarity between the statistics which are treat
5、ed the basis for the type of division. Some sample or indicators which have the high similar functions divided into the same polymerization, another similarity samples also do the same thing. Lower polymerization is classified into a small unit, while the closing polymerization is put into a large u
6、nit, until polymerization of all the samples or indicators are finished -that is the basic idea of clustering. With scientific and technological development, network has become the essential component of peoples live. Therefore, the data on the website of the various studies have important practical
7、 significance. Particularly in the filed of website clustering, which related to the efficiency of people getting the information on the website, is the basis of website information organization. Based on web log data mining research and application of the two polymerization algorithm, Hamming algor
8、ithms and kmeans algorithmms,polymerizing the websites which users visited. In both algorithms, making the URL of web site as line and Users ID as row for the establishment of URL-Users ID correlation matrix. Two different algorithms give birth to different values of the matrix elements which will b
9、e explained in detail in the text, and then analysis the similarity among them to get the similar web category. And that is the end of web polymerization. Keywords : Web Clustering, Data Mining, Web Log, K-Means Algorithm, The Algorithm Hamming第1章 绪论1.1 聚类和聚类分析的概念及其相关分类1.1.1 聚类和聚类分析的相关概念所谓类,通俗地说,就是指
10、相似元素的集合。 那么我们所讲的聚类,从字面上就可以看出,就是将某个领域内的一些同一属性的事物,根据它们个体之间的相似性,将其分为几个群集1。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种多元统计方法。严格的数学定义是较麻烦的,在不同问题中类的定义是不同的。聚类分析起源于分类学,在考古的分类学中,人们主要依靠经验和专业知识来实现分类。随着生产技术和科学的发展,人类的认识不断加深,分类越来越细,要求也越来越高,有时光凭经验和专业知识是不能进行确切分类的,往往需要定性和定量分析结合起来去分类,于是数学工具逐渐被引进分类学中,形成了数值分类学2。后来随着多元分析的引进,聚类分析又逐渐从数值
11、分类学中分离出来而形成一个相对独立的分支。在社会经济领域中存在着大量分类问题,比如对我国30个省市自治区独立核算工业企业经济效益进行分析,一般不是逐个省市自治区去分析,而较好地做法是选取能反映企业经济效益的代表性指标,如百元固定资产实现利税、资金利税率、产值利税率、百元销售收入实现利润、全员劳动生产率等等,根据这些指标对30个省市自治区进行分类,然后根据分类结果对企业经济效益进行综合评价,就易于得出科学的分析。又比如若对某些大城市的物价指数进行考察,而物价指数很多,有农用生产物价指数、服务项目价指数、食品消费物价指数、建材零售价格指数等等。由于要考察的物价指数很多,通常先对这些物价指数进行分类
12、。总之,需要分类的问题很多,因此聚类分析这个有用的数学工具越来越受到人们的重视,它在许多领域中都得到了广泛的应用。31.1.2 聚类分析算法的分类聚类分析是数据挖掘中的一个很活跃的研究领域,在这个领域里人们已经提出并实现了许多不同的聚类算法。这些算法可以被分为划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法4。 1 、划分方法(PAM:Partitioning method)5, 首先创建k个划分,k为要创建的划分个数,然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。典型的划分方法包括k-means,k-medoids,CLARA(Clustering
13、 LARge Application),CLARANS(Clustering Large Application based upon RANdomized Search)EM(Expectation Maximization)则是不将对象明显地分到几个簇,而是根据表示可能性的权来分配对象.2、 层次方法(hierarchical method),创建一个层次以分解给定的数据集。该方法可以分为自上而下(分解)和自下而上(合并)两种操作方式。为弥补分解与合并的不足,层次合并经常要与其它聚类方法相结合,如循环定位6。典型的这类方法中第一个是BIRCH(Balanced Iterative Redu
14、cing and Clustering using Hierarchies) 方法,它首先利用树的结构对对象集进行划分;然后再利用其它聚类方法对这些聚类进行优化。第二个是CURE(Clustering Using REprisentatives) 方法,它利用固定数目代表对象来表示相应聚类,然后对各聚类进行收缩处理。第三个是ROCK方法,它利用聚类间的连接进行聚类合并。最后一个CHEMALOEN,它则是在层次聚类时构造动态模型。3、 基于密度方法,根据密度完成对象的聚类7。它根据对象周围的密度(如DBSCAN)不断增长聚类。典型的基于密度方法包括:GDBSCAN,DBCLASD,DENCLUE
15、(DENsity-based CLUstEring),DBSCAN(Densit-based Spatial Clustering of Application with Noise)。DBSCAN算法通过不断生长足够高密度区域来进行聚类,它能从含有噪声的空间数据库中发现任意形状的聚类。此方法将一个聚类定义为一组“密度连接”的点集。OPTICS(Ordering Points To Identify the Clustering Structure)并不明确产生一个聚类,而是为自动交互的聚类分析计算出一个增强聚类顺序8。4、 基于网格方法,首先将对象空间划分为有限个单元以构成网格结构;然后利用
16、网格结构完成聚类。STING(STatistical INformation Grid) 就是一个利用网格单元保存的统计信息进行基于网格聚类的方法9。CLIQUE(Clustering In QUEst)和Wave-Cluster 则是一个将基于网格与基于密度相结合的方法。5、基于模型方法,它假设每个聚类的模型并发现适合相应模型的数据10。典型的基于模型方法有统计方法COBWEB,它是一个常用的且简单的增量式概念聚类方法。它的输入对象是采用符号量(属性-值)对来加以描述的。采用分类树的形式来创建一个层次聚类。CLASSIT是COBWEB的另一个版本。它可以对连续取值属性进行增量式聚类。它为每个
17、结点中的每个属性保存相应的连续正态分布(均值与方差),并利用一个改进的分类能力描述方法,即不像COBWEB那样计算离散属性(取值)而是对连续属性求积分11。但是CLASSIT方法也存在与COBWEB类似的问题。因此它们都不适合对大数据库进行聚类处理.还有就是AutoClass,它采用贝叶斯统计分析来估算结果簇的数目.1.1.3 本次设计所用算法介绍本次设计中,主要用到两个聚类算法,一个就是以上提到的K均值聚类算法,而别一个则是Hamming聚类算法12。 K均值算法:有多个对象组成的数据集,将其划分为k个类,k是人为指定的。先随机地从数据集中取出k个对象,每个对象初始地代表一个簇的平均值(或中
18、心点)。对剩下的每个对象,根据与各中心的距离,将其赋给最近的簇。每个簇就增加了一些对象,用每个簇这些对象重新计算每个簇平均值,得到新的簇平均值,再重新计算每个对象到各新平均值的距离,每个对象重新分簇,直到对象重新分簇不再变化。Hamming算法:我们认为一些网页页面具有相似性,可以归为一类,而这种分类是根据这些网页之间的Hamming距离的大小来进行衡量的。我们说一个URL-UserID关联矩阵可以构造出一个URL-URL关联矩阵,此矩阵又能根据一定的算法算出一个阈值。如果根据算出的两个元素间的hamming距离小于这个阈值,我们便认为这两个页面具有相似性,可以归为一类。下面说明一下hammi
19、ng距离的定义式:设X,Y为n维向量,其中,分别表示n维向量X,Y的第i个元素的值,而Hamming距离H(X,Y)可以表示为(X,Y)=所以这次设计的主要算法之一也就是上面所介绍的hamming聚类算法,我们算出URL-UserID关联矩阵中每两个URL向量间的hamming距离,再与算出的阈值做比较,如果小于此阈值,我们便把这两个页面认为是相似的,归为同一类,聚为同一个类别。1.2 数据挖掘技术的发展研究现状数据挖掘是一个新兴的边缘学科,它汇集了来自机器学习、模式识别、数据库、统计学、人工智能以及管理信息系统等各学科的成果。多学科的相互交融和相互促进,使得这一新学科得以蓬勃发展,而且已初具
20、规模。13人工智能研究领域的科学家也普遍认为,下一个人工智能应用的重要课题之一,将是以机器学习算法为主要工具的大规模的数据库知识发现。尽管数据挖掘还是一个很新的研究课题,但它所固有的为企业创造巨大经济效益的潜力,已使其很快有了许多成功的应用,具有代表性的应用有市场预测、投资、制造业、银行、通讯等几个方面。美国钢铁公司和神户钢铁公司利用基于数据挖掘技术的ISPA系统,研究分析产品性能规律和进行质量控制,取得了显著效果。14通用电器公司(GE)与法国飞机发动机制造公司(sNEcMA),利用数据挖掘技术研制了CASSIOPEE质量控制系统,被三家欧洲航空公司用于诊断和预测波音737的故障,带来了可观
21、的经济效益。而在这些数据挖掘的技术中,Web日志数据挖掘的研究逐渐被人们所关注。特别是计算机网络技术的高术发展,对Web日志进行数据挖掘显得越来越重要。当今社会,网络已经成为人们生活中的重要组成部分,网络是人们获取信息的一个相当重要的途径,随着电子网务技术的发展,网上购物也逐渐被人们所接纳且终将成为世界经济发展的广阔市场。所以人们对网页相关科技的发展也越来越关注。网页聚类技术,作为当前网络科技研究的一大方向,一直都因有着巨大的作用而被人们关注。一个正确的,高效的网页聚类方案的实现,将从根本上解决大部分的网络获取信息中遇到的难题。比如,网页松散而又海量,人们有时难以从这样海量的数据中寻找自己要的
22、信息。即使有搜索工具进行辅助,也必须有好的预处理网页的聚类方案,才能使搜索更加准确而有效,所以Web聚类技术的研究虽然发展不是很久,但处在这样一个科技高速发展的形式下,倍受人们的关注。1.3 设计出发点及主要设计任务和目标为便于从大量组织松散动态性强的Web网页中快速有效地发现知识,很早人们便提出了网页搜索技术,但是由于网上信息的海量、动态和无结构性,使得用户信息迷向,影响检索效率。这是因为:搜索引擎无法覆盖全部万维网信息;万维网具有动态性,搜索引擎索引中包含的“断链接”和“过时网页”削弱了搜索引擎的作用;搜索引擎返回的结果中相关信息和无关信息混杂;自然语言中存在的“一义多词”与“一词多义”现
23、象,也导致用户提出的查询信息往往不能清楚地表达自己的真正需要。于是人们便开始提出用聚类的方法自动组织搜索引擎的搜索结果,同时个性化服务于该系统,主动对外界反馈信息做出响应,方便用户发现真正需要的万维网信息。所以本次设计的主要任务是以聚类算法为核心,根据若干用户访问网页的Web日志信息,将这些网页通过具体的聚类算法进行分类。通过聚类得到的若干个网页的类体,这些类型的网页有着不同程度的某种相关性,在此基础上我们可以实现如何安排网页连接,使用户用起来更方便,更有效率。同时,对两种聚类算法得出的分类结果进行对比分析,列出其异同点,指出各算法的不足之处,希望能对现实生活中的工作需求有所帮助,从而使本次的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Web 聚类 Hamming 算法 均值 研究 实现 毕业论文
链接地址:https://www.31doc.com/p-3903241.html