毕业论文Web聚类Hamming算法与K均值算法的研究与实现

本科生毕业设计（论文）题 目： Web聚类Hamming算法与K均值算法的 研究与实现 姓 名： 陈云峰 学 号： 030300714 学 院： 数学与计算机科学学院 专 业： 年 级： 2003级 指导教师： （签名） 2007 年 6 月 16 日Web聚类Hamming算法与K均值算法的研究与实现摘要聚类分析也称群分析、点群分析，它是研究分类的一种多元统计方法。我们所研究的样品或指标之间存在程度不同的相似性。于是根据一批样品的多个观测指标，具体找出一些能够度量样品或指标之间相似程度的统计量，以这些统计量为划分类型的依据。把一些相似程度较大的样品或指标聚合为一类，把另外一些彼此之间相似程度较大的样品或指标又聚合为另一类，关系密切的聚合到一个小的分类单位，关系疏远的聚合到一个大的分类单位，直到把所有的样品或指标聚合完毕，这就是聚类的基本思想。随着科学技术的不断发展，网络成为了人们生活中必不可少的重要组成部分。因此，关于网页数据的种种研究都有着其重要的现实意义。特别是网页聚类，它关系着人们网上获取信息效率的高低，同时也是网页信息组织的主要依据。本文通过对Web日志数据的挖掘研究，应用两种聚类的算法，Hamming算法和K均值算法，将用户所访问的网页进行聚类。在这两种算法中，首先以Web站点URL为行，UserID为列建立URL-UserID关联矩阵.两种不同算法构造的矩阵中的元素值不同,文中会详细说明,然后对行向量进行相似性分析,可以得到相似的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 multivariate 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 treated 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 unit, 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 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 algorithms 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 be 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 聚类和聚类分析的相关概念所谓类，通俗地说，就是指相似元素的集合。 那么我们所讲的聚类，从字面上就可以看出，就是将某个领域内的一些同一属性的事物，根据它们个体之间的相似性，将其分为几个群集1。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种多元统计方法。严格的数学定义是较麻烦的，在不同问题中类的定义是不同的。聚类分析起源于分类学，在考古的分类学中，人们主要依靠经验和专业知识来实现分类。随着生产技术和科学的发展，人类的认识不断加深，分类越来越细，要求也越来越高，有时光凭经验和专业知识是不能进行确切分类的，往往需要定性和定量分析结合起来去分类，于是数学工具逐渐被引进分类学中，形成了数值分类学2。后来随着多元分析的引进，聚类分析又逐渐从数值分类学中分离出来而形成一个相对独立的分支。在社会经济领域中存在着大量分类问题，比如对我国30个省市自治区独立核算工业企业经济效益进行分析，一般不是逐个省市自治区去分析，而较好地做法是选取能反映企业经济效益的代表性指标，如百元固定资产实现利税、资金利税率、产值利税率、百元销售收入实现利润、全员劳动生产率等等，根据这些指标对30个省市自治区进行分类，然后根据分类结果对企业经济效益进行综合评价，就易于得出科学的分析。又比如若对某些大城市的物价指数进行考察，而物价指数很多，有农用生产物价指数、服务项目价指数、食品消费物价指数、建材零售价格指数等等。由于要考察的物价指数很多，通常先对这些物价指数进行分类。总之，需要分类的问题很多，因此聚类分析这个有用的数学工具越来越受到人们的重视，它在许多领域中都得到了广泛的应用。31.1.2 聚类分析算法的分类聚类分析是数据挖掘中的一个很活跃的研究领域，在这个领域里人们已经提出并实现了许多不同的聚类算法。这些算法可以被分为划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法4。 1 、划分方法(PAM:Partitioning method)5， 首先创建k个划分，k为要创建的划分个数,然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。典型的划分方法包括k-means,k-medoids,CLARA(Clustering LARge Application),CLARANS(Clustering Large Application based upon RANdomized Search)EM(Expectation Maximization)则是不将对象明显地分到几个簇,而是根据表示可能性的权来分配对象.2、 层次方法(hierarchical method)，创建一个层次以分解给定的数据集。该方法可以分为自上而下（分解）和自下而上（合并）两种操作方式。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位6。典型的这类方法中第一个是BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies) 方法，它首先利用树的结构对对象集进行划分；然后再利用其它聚类方法对这些聚类进行优化。第二个是CURE(Clustering Using REprisentatives) 方法，它利用固定数目代表对象来表示相应聚类，然后对各聚类进行收缩处理。第三个是ROCK方法，它利用聚类间的连接进行聚类合并。最后一个CHEMALOEN，它则是在层次聚类时构造动态模型。3、 基于密度方法，根据密度完成对象的聚类7。它根据对象周围的密度（如DBSCAN）不断增长聚类。典型的基于密度方法包括：GDBSCAN，DBCLASD，DENCLUE(DENsity-based CLUstEring)，DBSCAN(Densit-based Spatial Clustering of Application with Noise)。DBSCAN算法通过不断生长足够高密度区域来进行聚类，它能从含有噪声的空间数据库中发现任意形状的聚类。此方法将一个聚类定义为一组“密度连接”的点集。OPTICS(Ordering Points To Identify the Clustering Structure)并不明确产生一个聚类，而是为自动交互的聚类分析计算出一个增强聚类顺序8。4、 基于网格方法，首先将对象空间划分为有限个单元以构成网格结构；然后利用网格结构完成聚类。STING(STatistical INformation Grid) 就是一个利用网格单元保存的统计信息进行基于网格聚类的方法9。CLIQUE(Clustering In QUEst)和Wave-Cluster 则是一个将基于网格与基于密度相结合的方法。5、基于模型方法，它假设每个聚类的模型并发现适合相应模型的数据10。典型的基于模型方法有统计方法COBWEB，它是一个常用的且简单的增量式概念聚类方法。它的输入对象是采用符号量（属性-值）对来加以描述的。采用分类树的形式来创建一个层次聚类。CLASSIT是COBWEB的另一个版本。它可以对连续取值属性进行增量式聚类。它为每个结点中的每个属性保存相应的连续正态分布（均值与方差），并利用一个改进的分类能力描述方法，即不像COBWEB那样计算离散属性（取值）而是对连续属性求积分11。但是CLASSIT方法也存在与COBWEB类似的问题。因此它们都不适合对大数据库进行聚类处理.还有就是AutoClass，它采用贝叶斯统计分析来估算结果簇的数目.1.1.3 本次设计所用算法介绍本次设计中，主要用到两个聚类算法，一个就是以上提到的K均值聚类算法，而别一个则是Hamming聚类算法12。 K均值算法：有多个对象组成的数据集，将其划分为k个类，k是人为指定的。先随机地从数据集中取出k个对象，每个对象初始地代表一个簇的平均值（或中心点）。对剩下的每个对象，根据与各中心的距离，将其赋给最近的簇。每个簇就增加了一些对象，用每个簇这些对象重新计算每个簇平均值，得到新的簇平均值，再重新计算每个对象到各新平均值的距离，每个对象重新分簇，直到对象重新分簇不再变化。Hamming算法：我们认为一些网页页面具有相似性，可以归为一类，而这种分类是根据这些网页之间的Hamming距离的大小来进行衡量的。我们说一个URL-UserID关联矩阵可以构造出一个URL-URL关联矩阵，此矩阵又能根据一定的算法算出一个阈值。如果根据算出的两个元素间的hamming距离小于这个阈值，我们便认为这两个页面具有相似性，可以归为一类。下面说明一下hamming距离的定义式：设X，Y为n维向量，其中,分别表示n维向量X，Y的第i个元素的值，而Hamming距离H(X，Y)可以表示为(X，Y)=所以这次设计的主要算法之一也就是上面所介绍的hamming聚类算法，我们算出URL-UserID关联矩阵中每两个URL向量间的hamming距离，再与算出的阈值做比较，如果小于此阈值，我们便把这两个页面认为是相似的，归为同一类，聚为同一个类别。1.2 数据挖掘技术的发展研究现状数据挖掘是一个新兴的边缘学科，它汇集了来自机器学习、模式识别、数据库、统计学、人工智能以及管理信息系统等各学科的成果。多学科的相互交融和相互促进，使得这一新学科得以蓬勃发展，而且已初具规模。13人工智能研究领域的科学家也普遍认为，下一个人工智能应用的重要课题之一，将是以机器学习算法为主要工具的大规模的数据库知识发现。尽管数据挖掘还是一个很新的研究课题，但它所固有的为企业创造巨大经济效益的潜力，已使其很快有了许多成功的应用，具有代表性的应用有市场预测、投资、制造业、银行、通讯等几个方面。美国钢铁公司和神户钢铁公司利用基于数据挖掘技术的ISPA系统，研究分析产品性能规律和进行质量控制，取得了显著效果。14通用电器公司(GE)与法国飞机发动机制造公司(sNEcMA)，利用数据挖掘技术研制了CASSIOPEE质量控制系统，被三家欧洲航空公司用于诊断和预测波音737的故障，带来了可观的经济效益。而在这些数据挖掘的技术中，Web日志数据挖掘的研究逐渐被人们所关注。特别是计算机网络技术的高术发展，对Web日志进行数据挖掘显得越来越重要。当今社会，网络已经成为人们生活中的重要组成部分，网络是人们获取信息的一个相当重要的途径，随着电子网务技术的发展，网上购物也逐渐被人们所接纳且终将成为世界经济发展的广阔市场。所以人们对网页相关科技的发展也越来越关注。网页聚类技术，作为当前网络科技研究的一大方向，一直都因有着巨大的作用而被人们关注。一个正确的，高效的网页聚类方案的实现，将从根本上解决大部分的网络获取信息中遇到的难题。比如，网页松散而又海量，人们有时难以从这样海量的数据中寻找自己要的信息。即使有搜索工具进行辅助，也必须有好的预处理网页的聚类方案，才能使搜索更加准确而有效，所以Web聚类技术的研究虽然发展不是很久，但处在这样一个科技高速发展的形式下，倍受人们的关注。1.3 设计出发点及主要设计任务和目标为便于从大量组织松散动态性强的Web网页中快速有效地发现知识，很早人们便提出了网页搜索技术，但是由于网上信息的海量、动态和无结构性，使得用户信息迷向，影响检索效率。这是因为：搜索引擎无法覆盖全部万维网信息；万维网具有动态性，搜索引擎索引中包含的“断链接”和“过时网页”削弱了搜索引擎的作用；搜索引擎返回的结果中相关信息和无关信息混杂；自然语言中存在的“一义多词”与“一词多义”现象，也导致用户提出的查询信息往往不能清楚地表达自己的真正需要。于是人们便开始提出用聚类的方法自动组织搜索引擎的搜索结果，同时个性化服务于该系统，主动对外界反馈信息做出响应，方便用户发现真正需要的万维网信息。所以本次设计的主要任务是以聚类算法为核心，根据若干用户访问网页的Web日志信息，将这些网页通过具体的聚类算法进行分类。通过聚类得到的若干个网页的类体，这些类型的网页有着不同程度的某种相关性，在此基础上我们可以实现如何安排网页连接，使用户用起来更方便，更有效率。同时，对两种聚类算法得出的分类结果进行对比分析，列出其异同点，指出各算法的不足之处，希望能对现实生活中的工作需求有所帮助，从而使本次的设计有其现实的意义。1.4 论文的组织本论文主要有以下五个部分：第1章 绪论。主要介绍关于web聚类分析的概念和发展现状、课题任务等。第2章 开发环境技术背景。主要介绍课题的开发环境和技术背景。第3章 设计部分。主要介绍课题的概要设计和详细设计。第4章 系统实现及结果分析。主要介绍系统的具体实现和核心代码段和聚类分析。 最后 致谢与参考文献第2章 开发环境和技术背景2.1 开发技术本课题是利用VC+语言完成的。主要用到了数据存储技术、MFC编程框架技术等。利用MFC编程框架可以比较方便的调用MFC库来产生Windows环境下的可视化界面。2.2 关键技术2.2.1 MFC编程框架 MFC (Microsoft Foundation Class)中的各种类结合起来构成了一个应用程序框架，它的目的就是让程序员在此基础上来建立Windows下的应用程序，这是一种相对SDK来说更为简单的方法。因为总体上，MFC框架定义了应用程序的轮廓，并提供了用户接口的标准实现方法，程序员所要做的就是通过预定义的接口把具体应用程序特有的东西填入这个轮廓。Microsoft Visual C+提供了相应的工具来完成这个工作：AppWizard可以用来生成初步的框架文件（代码和资源等）；资源编辑器用于帮助直观地设计用户接口；ClassWizard用来协助添加代码到框架文件；最后，编译，则通过类库实现了应用程序特定的逻辑。 （1）封装性 构成MFC框架的是MFC类库。MFC类库是C+类库。这些类或者封装了Win32应用程序编程接口，或者封装了应用程序的概念，或者封装了OLE特性，或者封装了ODBC和DAO数据访问的功能，等等。（2）继承性首先，MFC抽象出众多类的共同特性，设计出一些基类作为实现其他类的基础。这些类中，最重要的类是CObject和CCmdTarget。CObject是MFC的根类，绝大多数MFC类是其派生的，包括CCmdTarget。针对每种不同的对象，MFC都设计了一组类对这些对象进行封装，每一组类都有一个基类，从基类派生出众多更具体的类。这些对象包括以下种类：窗口对象，基类是CWnd；应用程序对象，基类是CwinThread；文档对象，基类是Cdocument，等等。（3）虚拟函数和动态约束MFC以“C+”为基础，自然支持虚拟函数和动态约束15。但是作为一个编程框架，有一个问题必须解决：如果仅仅通过虚拟函数来支持动态约束，必然导致虚拟函数表过于臃肿，消耗内存，效率低下。MFC建立了消息映射机制，以一种富有效率、便于使用的手段解决消息处理函数的动态约束问题。这样，通过虚拟函数和消息映射，MFC类提供了丰富的编程接口。程序员继承基类的同时，把自己实现的虚拟函数和消息处理函数嵌入MFC的编程框架。（4）MFC的宏观框架体系 如前所述，MFC实现了对应用程序概念的封装，把类、类的继承、动态约束、类的关系和相互作用等封装起来。这样封装的结果对程序员来说，是一套开发模板（或者说模式）。针对不同的应用和目的，程序员采用不同的模板。2.3 课题开发环境和技术综述本课题是在Microsoft Visual C+ 6.0 开发环境下利用C+语言和MFC编程框架完成的。由于MFC编程框架技术的稳定性和简易性，将会使程序更加健壮和便于维护。第3章 设计部分本部分包括概要设计和详细设计部分。3.1 概要设计网页聚类分析的设计算法有很多种，以上概论中已经有详细的说明。而本次设计采取了两种算法来进行网页的聚类和分析。分析的结果精确度和所取的数据量的大小有很大的关系，数据量越大，聚类的结果就越准确，越有应用价值。由于需要处理的数据，数据量很大，我们需要对数据进行预处理。当数据处理完后，进行数据的输入，进而在编程环境下进行编程实现对数据的分类，即对网页进行聚类，当结果出来后，对相应算法的结果进行分析和对比，阐述两种算法的优缺点和现实应用价值，对以后的科学研究和应用提供一点参考。设计的概要框架如图3-0所示：图3-0 设计概要框架图3.2 详细设计3.2.1 数据预处理与数据存储3.2.1.1 Log日志的源数据格式及包含的信息网络日志LOG文件记录了，用户访问网页的详细信息，是我们研究网页聚类和用户聚类的一个很有价值的数据资源。本次设计所用的处理数据就是网络日志，从对网络日志进行数据挖掘，来对网页进行聚类分析。下面是本次设计所用网络日志文件中源数据的截图和信息说明，如图3-1：图3-1 Log日志源文件截图我们发现每条日志记录都包含了几块相同的信息：1.访问用户的IP，在第一条记录的开头都记录访问用的IP地址，如“125.41.34.6”2.用户访问的具体时间及访问端口号，包括年，月，日，时，分，秒的精确表示，如“30/Apr/2007:00:00:02 +0800”3.用户访问网页的URL地址,如:GET /skins/green/images/fzuc2007_green_search_01.gif HTTP/1.14.访问请求是否成功的代码表示等信息.3.2.1.2 数据预处理 从上面的LOG日志文件中我们看到，这些文件中有本次设计所需要的两大块信息，用户IP和用户访问的网页的地址，而其它的信息对我们来讲就是多余的，不必要的。又因为数据量非常之大，本次设计所用的网络日志文件有7万多条记录。如果不进行数据的预处理，将造成程序运行相当缓慢，所以数据预处理这一块是本次设计工作量比较大的一部分。本次的数据预处理过程分为以下几个步聚：1.将用户访问的URL地址用数字代号（以#XXXX表示,如#0001）一一对映的进行替换，同时将URL地址与对应的数字代码存储在txt文档中，以便后续聚类结果分析的对比分析。如下图3-2和3-3所示：图3-2 URL整理替换后的源数据图3-3 URL与对应的编号2.将用户IP地址用数字代号（以XXXX表示,如0001）一一对映的进行替换，同时将IP地址与对应的数字代码存储在txt文档中，以便后续聚类结果分析的对比分析。如图3-4和3-5所示：图3-4 用户IP整理后的源数据图3-5 用户IP与对应的编号3.最后去掉不需要的多余数据，剩下用户IP编码和其访问的URL地址编码，如图3-6所示： 图3-6 最终输入数据整理完成后，对用户IP和URL进行统计，共有IP地址1506个，URL地址1700个，去掉访问请求未成功的记录，一共有访问记录5万多条。3.2.1.3 数据存储数据存储方式：本次设计采用矩阵存储的方式进行数据存储，首先定义一个足够大的静态整形二维数组做为URL-IP数据存储矩阵URL-IP 。其中矩阵元素的初值根据不同算法有不同的要求：1.K均值算法中URL-IP矩阵元素的初值： 我们知道，同一个URL可能被同一个IP访问多次，从本是否被访问的角度上来讲，我们只要考虑该URL_i是否有被IP_j访问，若有则置URL-IPij=1,若无则置URL-IPij=0;而K均值聚类的算法还将访问频率，即被访问的次数做为分类的参考因子，所以在K均值聚类中URL-IP矩阵元素值URL-IPij为URL_i被IP_j访问的次数，相应的代码如图3.5所示：2.Hamming算法中URL-IP矩阵元素的初值：在Hamming算法中，我们只考虑URL_i是否有被IP_j访问过，若有，不管访问几次只要有被访问就将URL-IP矩阵元素值URL-IPij置1，若无则置0.3.2.2 URL地址存储本次网页聚类系统的设计中，对于聚类结果的显示，本设计可以显示每个分类中具体的URL编号对应的具体的URL地址，所以在初始化编程数据时，需要对URL对应编号进行存储，以便要显示具体URL地址时的查找与调用显示。3.2.3 各模块功能介绍3.2.3.1 K均值聚类算法实现模块该模块主要是在K均值初始化的数据矩阵的基础上，通过计算URL-IP矩阵的行向量间的距离将所有网页归入事先定义好的类别中，而后重新计算出每一类也就是自定义类别中URL（,）的平均值，再进行分类，直到分类不再变化为止，即分类结束。3.2.3.2 Hamming聚类算法实现模块该模块是与K均值聚类算法的实现不一样，没有事先自定义分为几类，而是在初始化矩阵的数据基础上，构造出一个新的URL-URL矩阵，其中每个元素的值URL-URLij为URLi和URLj中不同元素的个数，而后算出Hamming阈值，然后根据阈值来进行URL聚类，如果大元素值URL-URLij小于阈值，则URLi和URLj为一类。3.2.3.3 聚类结果显示模块由于聚类的结果是要将分类后的URL显示给用户，然而我们知道URL一共有1700个，如果全部一起显示给用户会使用户无法清晰地分析聚类的结果，所以我们先在LIST中显示出分类后的URL代号，每一类的URL都显示在LIST中的一行，由于显示的窗口大小有限，所以有些类含URL很多无法在一行中全部显示给用户，所以用户双击这一行，则会显示出全部的URL代号，而后点击详细显示，则显示详细的URL编号与地址。第4章 系统实现本章主要包括两种聚类算法K均值聚类和Hamming聚类的实现，以及聚类结果的分析显示，还有相关的数据处理的详细过程和代码分析。4.1 初始化数据模块4.1.1 数据结构的选择数组是存储数据的一种典型而又简单可靠的数据结构，数组在进行查找，排序操作是很方便的，而且数组可以动态分配这一方法又使数组的灵活性有所提高。数组一般用在顺序存储中。顺序存储表示是将数据元素存放于一个连续的存储空间，利用物理相邻来表示逻辑关系，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小如果是静态分配的，一经定义，在整个程序运行期间不会发生变化，因此，它不易扩充。同时，由于在插入或删除时，为保持原有顺序，平均需要移动一半(或近一半)元素，修改效率不高。 链式存储15表示的存储空间一般在程序运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生溢出的问题。同时在插入和删除时不需要保持数据元素的原有物理顺序，只需要保持原有的逻辑顺序就行了，故不必移动元素，只需修改它们的链接指针，修改效率高。但在存取表中的数据元素时，只能循链顺序进行访问，且需要额外的指针，存储效率和访问效率低于顺序存储表示。而本次设计主要的数据处理都是顺序存储的，而且关联到很多的顺序对应运算，用数组进行数据存储是最优的选择。现给出本次设计中数据初始化中相关数组的定义，程序代码描述如下：几个全局静态数组的定义：Define int URl-IP20002000: K均值初始化矩阵define float HamU-I20002000: Hamming初始化矩阵extern CString url2000: URL地址存储字符串数组4.1.2 两种算法的矩阵数据初始化4.1.2.1 K均值算法矩阵数据初始化根据K值聚类的算法描述，我们知道K均值聚类算法中的影响因子有数据量大小，也就是URL地址数目和用户IP数目的大小和同一IP访问同一URL的次数，也就是访问频率两个方面。其数据矩阵初始化的编程代码表示如图4-1：图4-1 K均值数据矩阵初始化代码4.1.2.2 Hamming聚类算法矩阵数据初始化和K均值算法不一样，Hamming算法所进么分类的标准主要是此URL是否被某IP访问，有被访问则置1，否则置0. 其数据矩阵初始化的编程代码表示如图4-2：图4-2 Hamming数据矩阵初始化代码4.1.2.3 URL地址字符串数组数据初始化由于聚类的结果是要将分类后的URL显示给用户，然而我们知道URL数目很多，很难一起显示给用户，或者说会使用户无法清晰地分析聚类的结果，所以我们先在LIST中显示出分类后的URL代号，再显示出对应的具体的URL地址，因而我们需要对URL地址与其对应的编号以字符串数组的形式进行存储，以便要显示具体URL地址时查找，调用和显示。其数据矩阵初始化的编程代码表示如图4-3：图4-3 url存储数组初始化代码4.2 K均值算法的实现4.2.1 分配一个URL向量到每个类中作为初始化类的平均URL向量按照K均值算法的描述，我们要事人为指定分类的个数K，并随机地抽取其中的K个向量做为每一类的平均向量，因为第一次分配后每个分类中只有一个向量，所以这K个向量便为K个类的平均向量。在本次设计中并没有真正随机分配，而是将第1,N,2N,n个分别作为第一次初始化的各类的平均向量。在系统中的程序编码实现如图4-4：图4-4 K均值初始化的各类的中心向量代码以上代码段中，变量kjm代表要进行分类的URL个数，定义两个m_knum维的字符串数组*kstr,*kstr1，是由于在后面的分类过程中需要循环地将kim个URL行向量分配到m_knum个类中，在这个基础上要再次计算分配后的每个类的向量的平均值，就需要知道分配到每个类的的URL行向量是哪几个，其中*kstr1记录的是变化后的各类中URL行向量的序号，而*kstr记录的是变化前各类中的URL行向量的序号。同时这两个数组也是后面判断循环结束的条件因子之一。4.2.2 循环迭代分类过程给定每一分类的初始URL行向量后，我们就可以将kjm个URL行向量进行筛选分配到每个类中，并且计算每个新类的平均URL行向量，记下分类的情况，之而要进行新类与旧类的对比，若分类有更新说明聚类过程仍未结束，则继续循环迭代进行分类，直到分类结束。其中编程代码如图4-5所示：图4-5 K均值循环分类过程代码上面的程序段中包含两段代码用一句话带过，具体的实现方式在下列进行说明：进行一次遍历，将URL分配到各个相应的类中的代码段如图4-6所示：图4-6 URL分配到各个相应的类中的代码计算平均值向量的过程，从前面定义的字符串数组*str中取出对应的第j类中包含的URL行向量对应的行号，将其取出，将j类中包含的所有URL行向量的对应元素值相加再除以URL的个数算出分配后类j的平均向量的每个元素值，从而得出分配后每个类的平均向量，为下一次分配作准备，其编程代码实现如图4-7：图4-7 计算分配后各类的平均向量4.2.3 聚类结果显示最后完成聚类，并进行结果显示，显示的结果如图4-8所示，因为软件第上显示窗口无法将分类全部显示出来，只好进行再次显示，双击每一条分类，则进行完全显示，在二次结果显示的窗口中单击“详细URL地址列表”则进行对应的详细的URL地址显示，其运行结果及界面如图4-8所示：图4-8 K均值运行结果显示窗口我们看到第三行中分类后含的URL个数没能完全显示出来，双击此行则出现二次显示窗口，如图4-9：图4-9 K均值二次显示窗口在二次查看窗口中，我们仍是只能看分类后，每个类中包含的URL的对应编号，而未能查看具体的URL地址，单击“详细URL列表”，则进行URL编号和地址的详细显示，如图4-10：图4-10 K均值具体url显示窗口4.3 Hamming聚类算法实现4.3.1 Hamming算法描述如前所述，URL-IP矩阵M的行向量M.,j反映了客户对本站点的不同页面的访问情况，如果客户对某些页面的访问情况相同或相似，那么，这些页面理应为相关页面，可以聚为一类。聚类时，同样先对URL-IP关联矩阵 M进行预处理，去掉所含元素值都为0的行向量，在本次设计中无考虑此情况，因为如果行向量值为0，则说明没有任何用户访问此网页，那就不在我们的考虑之内，我们所研究的是用户所访问的网页的聚类。对于Mi,j0,可先令Mi,j=1，再根据hamming距离公式计算并构造出行向量间的距离矩阵。在此矩阵中，表示第i个行向量和第j个行向量之间的Hamming距离，对角元素值为0.接下来根据阈值公式求URL-URL关联矩阵的阈值：对于，如果,那么就将第i个URL和所有满足这个条件的第j个URL划分为一个类。4.3.2 构造行向量间的距离矩阵由于本次设计不考虑URL行向量值为0的情况，所以可以根据HamU_I矩阵通过Hamming距离公式直接构造出URL行向量间的距离矩阵，其编程实现过程如图4-11所示：图4-11 构造URL-URL关联矩阵代码4.3.3 求URL行向量间距离矩阵的阈值从已经构造好的行向量间距离矩阵中，根据阈值的计算公式，我们可以算出URL行向量矩阵的阈值，阈值是整个聚类过程的唯一，重要的参考指标，所以说阈值取值情况将决定Hamming聚类的结果的精确与否。所以在阈值的求解上，我们将公式可调化，也就是说阈值的求值公式中的某些参数的值可以由用户来进行调整，使聚类的结果满足用户的最终需求，其编程中的实现过程如图4-12所示：图4-12 Hamming阈值求解代码4.3.4 Hamming聚类算法核心代码段由于Hamming算法是一个需要对分类中的每个值进行对应向量代号进行循环再分类，其工作时间复杂度较高，因此，本次设计从i=0着手分出第一类，然后作一次数据优化，去掉被其包含的子类。由于i=0对应的行向量kcl0j所包含的元素个素是最多的，有hjm-1个，如果元素值kcl0j为1的数目多，则分出的第一类元素个数就比较多，可能包含的子类就更多，进行的数据优化的效果就越好。下面是求出第一类的代码分析，如图4-13所示：图4-13 求出第一类的代码求出第一个类后，我们对数据矩阵进行优化，我们把存在不属于第一个类的行向量i作记号kclii=1，而行向量j上所含元素都在第一类中已存在的，我们说它完全包含于第一类，我们也作标记kcljji=0;经过数据优化后，我们只对kclii值为1的行向量进行分类，同时当分出第二类时我们也作同样的数据优化，再次排除掉无效的行直到分类结束。下面是编程代码的解析，如图4-14所示：图4-14 分出第一类后的数据优化代码中间分类及分类后的数据优化代码这里省略，原理和第一个类的分类过程是一样的。4.3.5 Hamming聚类的结果显示结果显示与K均值的显示界面及功能都基本相同，这里不再阐诉设计思想。显示如图4-15，图4-16，图4-17所示：图4-15 Hamming聚类窗口图4-16 Hamming聚类结果显示窗口图4-17 Hamming聚类二次显示窗口4.4聚类结果分析4.4.1 聚类的精确度分析根据实现的结果，本次设计将用户访问的URL地址分为以下9个大类：（1.）GET /skins/（2.）GET /images/（3.）GET /zh/（4.）GET /xywz/（5.）GET /h（6.）GET /xxq/（7.）GET / pqu /（8.）GET /fujian/（9.）其它我们根据URL地址的基本结构，自定义一个衡量聚类精确度的方法：设聚类的结果分为n类，去掉只含一个元素的类，误分率大于50%的类和含大量元素的类（因为如果只含一个元素也就没有正确与否之说，更不用谈什么精确度了，如果误分率大于50%，则我们不会去利用这样的分类结果，而含有大量元素的类，我们说这种类在本设计的两种算法中都会出现，是不可避免的，特别是在数据量巨大时，由于这样的类含的元素太多，肯定会包含以上所说的多种URL地址，这样的情况下，我们也无法去解析它的精确度），剩下的分类数为N，我们把分析的对象定为含有一定数量元素的这样一些类。设类i中共有y个URL，其中有x个URL与类中其它大部分元素是不同的，我们说这x个URL被错分到类i中，这样我们定义一个精确度值=1-x/y,=x/y，而总的分类精确度下面我们进行两种聚类算法的精确度分析：1.Hamming聚类精确度计算：根据聚类结果显示：当输入数据为“Ip_Url.txt”时，结果总共分为46类，其中去掉大量元素类7个，剩下可分析类39个,下面列出各类的精确度（未写出的都是全部正确的）：w=1/11;w=1/11;w=1/6;w=2/18;w=1/3;w=1/10;w=1/34;w=3/39;计算得出R97.4%2.K均值聚类精确度计算：根据聚类结果显示：当输入数据为“Ip_Url.txt”时，与Hamming分类数一样设为46类，其中去掉大量元素类和单元素类17个，剩下可分析类29个,下面列出各类的精确度（未写出的都是全部正确的）：w=4/17;w=2/11;w=7/43;w=2/15;w=1/36;w=8/38;w=1/21;w=2/11;w=6/23w=2/17;w=3/10;w=1/40;w=5/26;w=6/21;计算得出R91.8%为了使比较更为直观，我们将两个算法精度曲线描绘出来，如下图4-18分类精确度曲线所示： 图4-18 Kmeans与Hamming聚类确精度对比曲线其中纵坐标为每一分类中的分类精确度，最高为1，最小为0.5。前面定义精确度的时候说过，如果分类精确度小于0.5，也就是误分率大于50%，那么这一分类我们认为是不理想的，不会采纳，所以排除在分析对象之外。横坐标为上面所对应的可分析分类的类号，相互比较，我们清楚地看到在本设计相同的输入中，当分类的个数一样时，Hamming聚类的精确度比K均值聚类的精确度要高，同时，我们也看到二者的精确度都在90%以上，这说明两种聚类的算法都是有效的，都能够较好地将具有相同或相似的URL聚在同一类。4.4.2 Hamming阈值对聚类结果的影响 前面我们提到Hamming阈值是分类过程中唯一也是最重要的衡量指标，那么阈值的变化对整个聚类的结果会有什么样的影响呢？下面跟据实验数据的对比和分析，我们将指出Hamming阈值的变化对聚类结果的具体影响。我们分3种情况，第一种为阈值与公式计算所得一样不发生改变和调整;第二种为通过系统提供的阈值调整功能让阈值变小;第三各为通过系统提供的阈值调整功能让阈值变大. 下面比较三种情况下聚类的情况：阈值不变：此时分类数目为46，阈值为2.07301，阈值参数未作调整，如图4-19所示：图4-19 阈值不变时的Hamming聚类结果此时分析聚类的结果，去掉大量元素类7个，剩下可分析类39个,下面给出可分析类的精确度曲线，如图4-20所示：图4-20 阈值不变时Hamming聚类精确度曲线2.阈值变大：通过对阈值参数N作调整使阈值变大，调整参数N为1.5，阈值为3.10952，分类数目43如图-21所示：图4-21 阈值变大后Hamming聚类的结果此时分析聚类的结果，去掉大量元素类7个，误分率超过50%的少量元素类3个，剩下可分析类33个,下面给出可分析类的精确度曲线，如图4-22所示： 图4-22 阈值变大后Hamming聚类的精确度曲线3.阈值变小：通过调整阈值参数N使阈值变小，调整参数N为0.85，阈值为1.76206，分类的数目为85，如图4-23所示：图4-23 阈值变小后的Hamming聚类结果此时分析聚类的结果，去掉误分率大于50%的少量元素类3个，大量元素类30个，剩下可分析类52个，下面给出可分析类的精确度曲线，如图4-24所示： 图4-24 阈值变小后Hamming聚类的精确度曲线通过对三种情况的分类精确度的分析，我们看到，当阈值变大时，分类的数目减少了，这说明分类变得比较粗糙，因此有可能造成分类精确度较低。通过精确度曲线图也证实了精确度比较差;而如果调小阈值，我们发现分类的数目变大，且幅度比较高，但是同时产生的大量元素类的数目也有较大的提高，这说明分类虽然多了，详细了，但也使非利用类的数目变大（这是非利用类指的是大量元素类），可分析类的数目也有提高，而且从精确度曲线图上，我们可以看出大部分分类的精确度都在90%以上，整条曲线比较平稳，精确度较高，可以达到较为理想的聚类效果。下面我们用一个表较为直观地显示三者的对比结果，如表4-25所示：表4-1 阈值的变化对分类精确度的影响情况阈值变化总分类数变化可析类数变化大量元素类数误分率高类数分类精确度变小85变大52变大30变大3较好不变463970一般变大433373较差4.4.3 分类数目变化对K均值聚类结果的影响由于K均值聚类是根据我们自定义的数目来进行分类的，但是因为我们随机分配给每个类的初始量不一定就是不现于其它类的量，有可能在第一次分配时就使这一类为空，这样就使分类无法正常进行，于是在本设计中，如果某次分配后发现有空的类，则会把初始分量再次赋给它，等待下次的分配，其编程代码在上文有说明，参看图4-5。那么下面我们将根据实验得出的数据对分类数目进行三种变化，从而分析分类数目变化对K均值聚类结果的影响。为了能和Hamming聚类结果进行比较，K均值分类的数目将和上面Hamming聚类三种情况下分类的数目取相同的数据。分类数目不变：分类数目为46，如图4-25所示：图4-25 分类数目不变时的K均值聚类结果下面我们对分类的精确度进行分析，去掉大量元素类1，单元素类13，误分率较大类3，剩下可分析类29，其精确度曲线如图4-26所示：图4-26 分类数目不变时的K均值聚类精确度曲线分类数目变大：分类数目为85，如图4-27所示：图4-27 分类数目变大时的K均值聚类结果下面我们对分类的精确度进行分析，去掉大量元素类1，单元素类32，误分率较大类4，剩下可分析类43，其精确度曲线如图4-28所示：图4-28 分类数目变大时的K均值聚类精确度曲线3.分类数目变小：分类数为43，如图4-29所示：图4-29 分类数目变小时的K均值聚类结果下面我们对分类的精确度进行分析，去掉大量元素类1，单元素类14，误分率较大类6，剩下可分析类22，其精确度曲线如图4-30所示：图4-30 分类数目变小时的K均值聚类精确度曲线通过三种情况的对比分析，我们可以看到，当分类数目变大时单元素类大量增加，但是分类的精确度确是有所提高，分类精确度曲线出现的都较陡的坡度，这说明很少有连续的误分类，只有个别误分类穿插出现;而当分类数目变小时，精确度并不是有很大的变化，但是从坡度上我们可以看出坡度都较缓，这说明会有大量的连续的误分类，所以其实上当分类数变小时精确度有所下降。下面用表格较为直观地进行说明，如表4-2所示：表4-2 分类数目的变化对分类精确度的影响分类数目变化单元素类数大量元素类数可分析类数误分率高类数分类精确度43变小14无明显变化1无变化22减小6增大降代46不变131293一般85变大32大量增多1无变化43增多4变化不大增高4.4.4 两种聚类方法的对比总结通过以上对两种聚类方法的结果进行详细的对比和分析，我们看到，在相同分类数的情况下，Hamming聚类的精确度要比K均值的分类精确度高。但是两种聚类的算法，在相应的参数选择好的情况下，如Hamming阈值的调整，和K均值的分类数目，如果参数选得好都可以达到较为满意的聚类结果。此次通过两种算法K均值算法和Hamming算法分别来对网页进行分类，其中Hamming算法的设计是参照宋擒豹 沈钧毅关于Web日志高效多能挖掘算法中的Hamming聚类算法12.在本次实验中，对于原作者对Hamming阈值的计算公式进行了调整。在实验过程中，根据实验的数据，若根据原来的Hamming阈值计算公式求阈值，会导致最后的分类数目极少，甚至只有一类。因此，在本次实验中，原作者所提的阈值公式12在本次设计中并不合适，在调适运行过程中，本次设计对其公式进行改进最后使分类能够顺利进行，而且效果也比较理想。此次验证性实验证时，Hamming算法中的阈值是要根据不同情况下的输入进行相应的调节，才能使分类更加精准有效，同时本次设计及实验结果也说明了两种算法都是有效的聚类算法，都可以较理想地进行聚类分析。致谢在这次毕业设计过程中，首先感谢白清源教授在算法上的详细解释，在算法资料上的提供，在论文格式及要求上的检查和改正。感谢林鑫显在系统实现过程的帮助,感谢身边同学在设计过程中的鼓励与帮助。参考文献1 高新波.模糊聚类分析及其应用.西安：西安电子科技大学出版社.2004：23-45.2 李恒峰，李国辉.基于内容的音频检索与分类.计算机工程与应用.2000.7.3（加）韩家炜，堪博 著，范明，孟小峰 译.数据挖掘概念与技术.北京：机械工业出版社.2007：18-90.4刘书香，卢才武.数据挖掘中的客户聚类分析及其算法实现.信息技术.2004年1月，第28卷第1期，PP.4-10.5 尹松，周永叔，李陶深.数据聚