畢業(yè)論文Web聚類Hamming算法與K均值算法的研究與實現(xiàn)

《畢業(yè)論文Web聚類Hamming算法與K均值算法的研究與實現(xiàn)》由會員分享，可在線閱讀，更多相關(guān)《畢業(yè)論文Web聚類Hamming算法與K均值算法的研究與實現(xiàn)（32頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 本科生畢業(yè)設(shè)計（論文）題 目： Web聚類Hamming算法與K均值算法的 研究與實現(xiàn) 姓 名： 陳云峰 學(xué) 號： 030300714 學(xué) 院： 數(shù)學(xué)與計算機科學(xué)學(xué)院 專 業(yè)： 年 級： 2003級 指導(dǎo)教師： （簽名） 2007 年 6 月 16 日Web聚類Hamming算法與K均值算法的研究與實現(xiàn)摘要聚類分析也稱群分析、點群分析，它是研究分類的一種多元統(tǒng)計方法。我們所研究的樣品或指標之間存在程度不同的相似性。于是根據(jù)一批樣品的多個觀測指標，具體找出一些能夠度量樣品或指標之間相似程度的統(tǒng)計量，以這些統(tǒng)計量為劃分類型的依據(jù)。把一些相似程度較大的樣品或指標聚合為一類，把另外一些彼此之間相似程

2、度較大的樣品或指標又聚合為另一類，關(guān)系密切的聚合到一個小的分類單位，關(guān)系疏遠的聚合到一個大的分類單位，直到把所有的樣品或指標聚合完畢，這就是聚類的基本思想。隨著科學(xué)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)成為了人們生活中必不可少的重要組成部分。因此，關(guān)于網(wǎng)頁數(shù)據(jù)的種種研究都有著其重要的現(xiàn)實意義。特別是網(wǎng)頁聚類，它關(guān)系著人們網(wǎng)上獲取信息效率的高低，同時也是網(wǎng)頁信息組織的主要依據(jù)。本文通過對Web日志數(shù)據(jù)的挖掘研究，應(yīng)用兩種聚類的算法，Hamming算法和K均值算法，將用戶所訪問的網(wǎng)頁進行聚類。在這兩種算法中，首先以Web站點URL為行，UserID為列建立URL-UserID關(guān)聯(lián)矩陣.兩種不同算法構(gòu)造的矩陣中的元素

3、值不同,文中會詳細說明,然后對行向量進行相似性分析,可以得到相似的Web群體類，從而完成對Web網(wǎng)頁的聚類。關(guān)鍵詞：網(wǎng)頁聚類， 數(shù)據(jù)挖掘， 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 聚類和聚類分析的概念及其相關(guān)分類1.1.1 聚類和聚類分析的相關(guān)概念所謂類，通俗地說，就是指

10、相似元素的集合。 那么我們所講的聚類，從字面上就可以看出，就是將某個領(lǐng)域內(nèi)的一些同一屬性的事物，根據(jù)它們個體之間的相似性，將其分為幾個群集1。聚類分析又稱群分析，它是研究（樣品或指標）分類問題的一種多元統(tǒng)計方法。嚴格的數(shù)學(xué)定義是較麻煩的，在不同問題中類的定義是不同的。聚類分析起源于分類學(xué)，在考古的分類學(xué)中，人們主要依靠經(jīng)驗和專業(yè)知識來實現(xiàn)分類。隨著生產(chǎn)技術(shù)和科學(xué)的發(fā)展，人類的認識不斷加深，分類越來越細，要求也越來越高，有時光憑經(jīng)驗和專業(yè)知識是不能進行確切分類的，往往需要定性和定量分析結(jié)合起來去分類，于是數(shù)學(xué)工具逐漸被引進分類學(xué)中，形成了數(shù)值分類學(xué)2。后來隨著多元分析的引進，聚類分析又逐漸從數(shù)值

11、分類學(xué)中分離出來而形成一個相對獨立的分支。在社會經(jīng)濟領(lǐng)域中存在著大量分類問題，比如對我國30個省市自治區(qū)獨立核算工業(yè)企業(yè)經(jīng)濟效益進行分析，一般不是逐個省市自治區(qū)去分析，而較好地做法是選取能反映企業(yè)經(jīng)濟效益的代表性指標，如百元固定資產(chǎn)實現(xiàn)利稅、資金利稅率、產(chǎn)值利稅率、百元銷售收入實現(xiàn)利潤、全員勞動生產(chǎn)率等等，根據(jù)這些指標對30個省市自治區(qū)進行分類，然后根據(jù)分類結(jié)果對企業(yè)經(jīng)濟效益進行綜合評價，就易于得出科學(xué)的分析。又比如若對某些大城市的物價指數(shù)進行考察，而物價指數(shù)很多，有農(nóng)用生產(chǎn)物價指數(shù)、服務(wù)項目價指數(shù)、食品消費物價指數(shù)、建材零售價格指數(shù)等等。由于要考察的物價指數(shù)很多，通常先對這些物價指數(shù)進行分類

12、。總之，需要分類的問題很多，因此聚類分析這個有用的數(shù)學(xué)工具越來越受到人們的重視，它在許多領(lǐng)域中都得到了廣泛的應(yīng)用。31.1.2 聚類分析算法的分類聚類分析是數(shù)據(jù)挖掘中的一個很活躍的研究領(lǐng)域，在這個領(lǐng)域里人們已經(jīng)提出并實現(xiàn)了許多不同的聚類算法。這些算法可以被分為劃分方法、層次方法、基于密度方法、基于網(wǎng)格方法和基于模型方法4。 1 、劃分方法(PAM:Partitioning method)5， 首先創(chuàng)建k個劃分，k為要創(chuàng)建的劃分個數(shù),然后利用一個循環(huán)定位技術(shù)通過將對象從一個劃分移到另一個劃分來幫助改善劃分質(zhì)量。典型的劃分方法包括k-means,k-medoids,CLARA(Clustering

13、 LARge Application),CLARANS(Clustering Large Application based upon RANdomized Search)EM(Expectation Maximization)則是不將對象明顯地分到幾個簇,而是根據(jù)表示可能性的權(quán)來分配對象.2、 層次方法(hierarchical method)，創(chuàng)建一個層次以分解給定的數(shù)據(jù)集。該方法可以分為自上而下（分解）和自下而上（合并）兩種操作方式。為彌補分解與合并的不足，層次合并經(jīng)常要與其它聚類方法相結(jié)合，如循環(huán)定位6。典型的這類方法中第一個是BIRCH(Balanced Iterative Redu

14、cing and Clustering using Hierarchies) 方法，它首先利用樹的結(jié)構(gòu)對對象集進行劃分；然后再利用其它聚類方法對這些聚類進行優(yōu)化。第二個是CURE(Clustering Using REprisentatives) 方法，它利用固定數(shù)目代表對象來表示相應(yīng)聚類，然后對各聚類進行收縮處理。第三個是ROCK方法，它利用聚類間的連接進行聚類合并。最后一個CHEMALOEN，它則是在層次聚類時構(gòu)造動態(tài)模型。3、 基于密度方法，根據(jù)密度完成對象的聚類7。它根據(jù)對象周圍的密度（如DBSCAN）不斷增長聚類。典型的基于密度方法包括：GDBSCAN，DBCLASD，DENCLUE

15、(DENsity-based CLUstEring)，DBSCAN(Densit-based Spatial Clustering of Application with Noise)。DBSCAN算法通過不斷生長足夠高密度區(qū)域來進行聚類，它能從含有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。此方法將一個聚類定義為一組“密度連接”的點集。OPTICS(Ordering Points To Identify the Clustering Structure)并不明確產(chǎn)生一個聚類，而是為自動交互的聚類分析計算出一個增強聚類順序8。4、 基于網(wǎng)格方法，首先將對象空間劃分為有限個單元以構(gòu)成網(wǎng)格結(jié)構(gòu)；然后利用

16、網(wǎng)格結(jié)構(gòu)完成聚類。STING(STatistical INformation Grid) 就是一個利用網(wǎng)格單元保存的統(tǒng)計信息進行基于網(wǎng)格聚類的方法9。CLIQUE(Clustering In QUEst)和Wave-Cluster 則是一個將基于網(wǎng)格與基于密度相結(jié)合的方法。5、基于模型方法，它假設(shè)每個聚類的模型并發(fā)現(xiàn)適合相應(yīng)模型的數(shù)據(jù)10。典型的基于模型方法有統(tǒng)計方法COBWEB，它是一個常用的且簡單的增量式概念聚類方法。它的輸入對象是采用符號量（屬性-值）對來加以描述的。采用分類樹的形式來創(chuàng)建一個層次聚類。CLASSIT是COBWEB的另一個版本。它可以對連續(xù)取值屬性進行增量式聚類。它為每個

17、結(jié)點中的每個屬性保存相應(yīng)的連續(xù)正態(tài)分布（均值與方差），并利用一個改進的分類能力描述方法，即不像COBWEB那樣計算離散屬性（取值）而是對連續(xù)屬性求積分11。但是CLASSIT方法也存在與COBWEB類似的問題。因此它們都不適合對大數(shù)據(jù)庫進行聚類處理.還有就是AutoClass，它采用貝葉斯統(tǒng)計分析來估算結(jié)果簇的數(shù)目.1.1.3 本次設(shè)計所用算法介紹本次設(shè)計中，主要用到兩個聚類算法，一個就是以上提到的K均值聚類算法，而別一個則是Hamming聚類算法12。 K均值算法：有多個對象組成的數(shù)據(jù)集，將其劃分為k個類，k是人為指定的。先隨機地從數(shù)據(jù)集中取出k個對象，每個對象初始地代表一個簇的平均值（或中

18、心點）。對剩下的每個對象，根據(jù)與各中心的距離，將其賦給最近的簇。每個簇就增加了一些對象，用每個簇這些對象重新計算每個簇平均值，得到新的簇平均值，再重新計算每個對象到各新平均值的距離，每個對象重新分簇，直到對象重新分簇不再變化。Hamming算法：我們認為一些網(wǎng)頁頁面具有相似性，可以歸為一類，而這種分類是根據(jù)這些網(wǎng)頁之間的Hamming距離的大小來進行衡量的。我們說一個URL-UserID關(guān)聯(lián)矩陣可以構(gòu)造出一個URL-URL關(guān)聯(lián)矩陣，此矩陣又能根據(jù)一定的算法算出一個閾值。如果根據(jù)算出的兩個元素間的hamming距離小于這個閾值，我們便認為這兩個頁面具有相似性，可以歸為一類。下面說明一下hammi

19、ng距離的定義式：設(shè)X，Y為n維向量，其中,分別表示n維向量X，Y的第i個元素的值，而Hamming距離H(X，Y)可以表示為(X，Y)=所以這次設(shè)計的主要算法之一也就是上面所介紹的hamming聚類算法，我們算出URL-UserID關(guān)聯(lián)矩陣中每兩個URL向量間的hamming距離，再與算出的閾值做比較，如果小于此閾值，我們便把這兩個頁面認為是相似的，歸為同一類，聚為同一個類別。1.2 數(shù)據(jù)挖掘技術(shù)的發(fā)展研究現(xiàn)狀數(shù)據(jù)挖掘是一個新興的邊緣學(xué)科，它匯集了來自機器學(xué)習(xí)、模式識別、數(shù)據(jù)庫、統(tǒng)計學(xué)、人工智能以及管理信息系統(tǒng)等各學(xué)科的成果。多學(xué)科的相互交融和相互促進，使得這一新學(xué)科得以蓬勃發(fā)展，而且已初具

20、規(guī)模。13人工智能研究領(lǐng)域的科學(xué)家也普遍認為，下一個人工智能應(yīng)用的重要課題之一，將是以機器學(xué)習(xí)算法為主要工具的大規(guī)模的數(shù)據(jù)庫知識發(fā)現(xiàn)。盡管數(shù)據(jù)挖掘還是一個很新的研究課題，但它所固有的為企業(yè)創(chuàng)造巨大經(jīng)濟效益的潛力，已使其很快有了許多成功的應(yīng)用，具有代表性的應(yīng)用有市場預(yù)測、投資、制造業(yè)、銀行、通訊等幾個方面。美國鋼鐵公司和神戶鋼鐵公司利用基于數(shù)據(jù)挖掘技術(shù)的ISPA系統(tǒng)，研究分析產(chǎn)品性能規(guī)律和進行質(zhì)量控制，取得了顯著效果。14通用電器公司(GE)與法國飛機發(fā)動機制造公司(sNEcMA)，利用數(shù)據(jù)挖掘技術(shù)研制了CASSIOPEE質(zhì)量控制系統(tǒng)，被三家歐洲航空公司用于診斷和預(yù)測波音737的故障，帶來了可觀

21、的經(jīng)濟效益。而在這些數(shù)據(jù)挖掘的技術(shù)中，Web日志數(shù)據(jù)挖掘的研究逐漸被人們所關(guān)注。特別是計算機網(wǎng)絡(luò)技術(shù)的高術(shù)發(fā)展，對Web日志進行數(shù)據(jù)挖掘顯得越來越重要。當今社會，網(wǎng)絡(luò)已經(jīng)成為人們生活中的重要組成部分，網(wǎng)絡(luò)是人們獲取信息的一個相當重要的途徑，隨著電子網(wǎng)務(wù)技術(shù)的發(fā)展，網(wǎng)上購物也逐漸被人們所接納且終將成為世界經(jīng)濟發(fā)展的廣闊市場。所以人們對網(wǎng)頁相關(guān)科技的發(fā)展也越來越關(guān)注。網(wǎng)頁聚類技術(shù)，作為當前網(wǎng)絡(luò)科技研究的一大方向，一直都因有著巨大的作用而被人們關(guān)注。一個正確的，高效的網(wǎng)頁聚類方案的實現(xiàn)，將從根本上解決大部分的網(wǎng)絡(luò)獲取信息中遇到的難題。比如，網(wǎng)頁松散而又海量，人們有時難以從這樣海量的數(shù)據(jù)中尋找自己要的

22、信息。即使有搜索工具進行輔助，也必須有好的預(yù)處理網(wǎng)頁的聚類方案，才能使搜索更加準確而有效，所以Web聚類技術(shù)的研究雖然發(fā)展不是很久，但處在這樣一個科技高速發(fā)展的形式下，倍受人們的關(guān)注。1.3 設(shè)計出發(fā)點及主要設(shè)計任務(wù)和目標為便于從大量組織松散動態(tài)性強的Web網(wǎng)頁中快速有效地發(fā)現(xiàn)知識，很早人們便提出了網(wǎng)頁搜索技術(shù)，但是由于網(wǎng)上信息的海量、動態(tài)和無結(jié)構(gòu)性，使得用戶信息迷向，影響檢索效率。這是因為：搜索引擎無法覆蓋全部萬維網(wǎng)信息；萬維網(wǎng)具有動態(tài)性，搜索引擎索引中包含的“斷鏈接”和“過時網(wǎng)頁”削弱了搜索引擎的作用；搜索引擎返回的結(jié)果中相關(guān)信息和無關(guān)信息混雜；自然語言中存在的“一義多詞”與“一詞多義”現(xiàn)

23、象，也導(dǎo)致用戶提出的查詢信息往往不能清楚地表達自己的真正需要。于是人們便開始提出用聚類的方法自動組織搜索引擎的搜索結(jié)果，同時個性化服務(wù)于該系統(tǒng)，主動對外界反饋信息做出響應(yīng)，方便用戶發(fā)現(xiàn)真正需要的萬維網(wǎng)信息。所以本次設(shè)計的主要任務(wù)是以聚類算法為核心，根據(jù)若干用戶訪問網(wǎng)頁的Web日志信息，將這些網(wǎng)頁通過具體的聚類算法進行分類。通過聚類得到的若干個網(wǎng)頁的類體，這些類型的網(wǎng)頁有著不同程度的某種相關(guān)性，在此基礎(chǔ)上我們可以實現(xiàn)如何安排網(wǎng)頁連接，使用戶用起來更方便，更有效率。同時，對兩種聚類算法得出的分類結(jié)果進行對比分析，列出其異同點，指出各算法的不足之處，希望能對現(xiàn)實生活中的工作需求有所幫助，從而使本次的

24、設(shè)計有其現(xiàn)實的意義。1.4 論文的組織本論文主要有以下五個部分：第1章 緒論。主要介紹關(guān)于web聚類分析的概念和發(fā)展現(xiàn)狀、課題任務(wù)等。第2章 開發(fā)環(huán)境技術(shù)背景。主要介紹課題的開發(fā)環(huán)境和技術(shù)背景。第3章 設(shè)計部分。主要介紹課題的概要設(shè)計和詳細設(shè)計。第4章 系統(tǒng)實現(xiàn)及結(jié)果分析。主要介紹系統(tǒng)的具體實現(xiàn)和核心代碼段和聚類分析。 最后 致謝與參考文獻第2章 開發(fā)環(huán)境和技術(shù)背景2.1 開發(fā)技術(shù)本課題是利用VC+語言完成的。主要用到了數(shù)據(jù)存儲技術(shù)、MFC編程框架技術(shù)等。利用MFC編程框架可以比較方便的調(diào)用MFC庫來產(chǎn)生Windows環(huán)境下的可視化界面。2.2 關(guān)鍵技術(shù)2.2.1 MFC編程框架 MFC (M

25、icrosoft Foundation Class)中的各種類結(jié)合起來構(gòu)成了一個應(yīng)用程序框架，它的目的就是讓程序員在此基礎(chǔ)上來建立Windows下的應(yīng)用程序，這是一種相對SDK來說更為簡單的方法。因為總體上，MFC框架定義了應(yīng)用程序的輪廓，并提供了用戶接口的標準實現(xiàn)方法，程序員所要做的就是通過預(yù)定義的接口把具體應(yīng)用程序特有的東西填入這個輪廓。Microsoft Visual C+提供了相應(yīng)的工具來完成這個工作：AppWizard可以用來生成初步的框架文件（代碼和資源等）；資源編輯器用于幫助直觀地設(shè)計用戶接口；ClassWizard用來協(xié)助添加代碼到框架文件；最后，編譯，則通過類庫實現(xiàn)了應(yīng)用程序

26、特定的邏輯。 （1）封裝性 構(gòu)成MFC框架的是MFC類庫。MFC類庫是C+類庫。這些類或者封裝了Win32應(yīng)用程序編程接口，或者封裝了應(yīng)用程序的概念，或者封裝了OLE特性，或者封裝了ODBC和DAO數(shù)據(jù)訪問的功能，等等。（2）繼承性首先，MFC抽象出眾多類的共同特性，設(shè)計出一些基類作為實現(xiàn)其他類的基礎(chǔ)。這些類中，最重要的類是CObject和CCmdTarget。CObject是MFC的根類，絕大多數(shù)MFC類是其派生的，包括CCmdTarget。針對每種不同的對象，MFC都設(shè)計了一組類對這些對象進行封裝，每一組類都有一個基類，從基類派生出眾多更具體的類。這些對象包括以下種類：窗口對象，基類是CW

27、nd；應(yīng)用程序?qū)ο?，基類是CwinThread；文檔對象，基類是Cdocument，等等。（3）虛擬函數(shù)和動態(tài)約束MFC以“C+”為基礎(chǔ)，自然支持虛擬函數(shù)和動態(tài)約束15。但是作為一個編程框架，有一個問題必須解決：如果僅僅通過虛擬函數(shù)來支持動態(tài)約束，必然導(dǎo)致虛擬函數(shù)表過于臃腫，消耗內(nèi)存，效率低下。MFC建立了消息映射機制，以一種富有效率、便于使用的手段解決消息處理函數(shù)的動態(tài)約束問題。這樣，通過虛擬函數(shù)和消息映射，MFC類提供了豐富的編程接口。程序員繼承基類的同時，把自己實現(xiàn)的虛擬函數(shù)和消息處理函數(shù)嵌入MFC的編程框架。（4）MFC的宏觀框架體系 如前所述，MFC實現(xiàn)了對應(yīng)用程序概念的封裝，把類、

28、類的繼承、動態(tài)約束、類的關(guān)系和相互作用等封裝起來。這樣封裝的結(jié)果對程序員來說，是一套開發(fā)模板（或者說模式）。針對不同的應(yīng)用和目的，程序員采用不同的模板。2.3 課題開發(fā)環(huán)境和技術(shù)綜述本課題是在Microsoft Visual C+ 6.0 開發(fā)環(huán)境下利用C+語言和MFC編程框架完成的。由于MFC編程框架技術(shù)的穩(wěn)定性和簡易性，將會使程序更加健壯和便于維護。第3章 設(shè)計部分本部分包括概要設(shè)計和詳細設(shè)計部分。3.1 概要設(shè)計網(wǎng)頁聚類分析的設(shè)計算法有很多種，以上概論中已經(jīng)有詳細的說明。而本次設(shè)計采取了兩種算法來進行網(wǎng)頁的聚類和分析。分析的結(jié)果精確度和所取的數(shù)據(jù)量的大小有很大的關(guān)系，數(shù)據(jù)量越大，聚類的結(jié)

29、果就越準確，越有應(yīng)用價值。由于需要處理的數(shù)據(jù)，數(shù)據(jù)量很大，我們需要對數(shù)據(jù)進行預(yù)處理。當數(shù)據(jù)處理完后，進行數(shù)據(jù)的輸入，進而在編程環(huán)境下進行編程實現(xiàn)對數(shù)據(jù)的分類，即對網(wǎng)頁進行聚類，當結(jié)果出來后，對相應(yīng)算法的結(jié)果進行分析和對比，闡述兩種算法的優(yōu)缺點和現(xiàn)實應(yīng)用價值，對以后的科學(xué)研究和應(yīng)用提供一點參考。設(shè)計的概要框架如圖3-0所示：圖3-0 設(shè)計概要框架圖3.2 詳細設(shè)計3.2.1 數(shù)據(jù)預(yù)處理與數(shù)據(jù)存儲3.2.1.1 Log日志的源數(shù)據(jù)格式及包含的信息網(wǎng)絡(luò)日志LOG文件記錄了，用戶訪問網(wǎng)頁的詳細信息，是我們研究網(wǎng)頁聚類和用戶聚類的一個很有價值的數(shù)據(jù)資源。本次設(shè)計所用的處理數(shù)據(jù)就是網(wǎng)絡(luò)日志，從對網(wǎng)絡(luò)日志進

30、行數(shù)據(jù)挖掘，來對網(wǎng)頁進行聚類分析。下面是本次設(shè)計所用網(wǎng)絡(luò)日志文件中源數(shù)據(jù)的截圖和信息說明，如圖3-1：圖3-1 Log日志源文件截圖我們發(fā)現(xiàn)每條日志記錄都包含了幾塊相同的信息：1.訪問用戶的IP，在第一條記錄的開頭都記錄訪問用的IP地址，如“125.41.34.6”2.用戶訪問的具體時間及訪問端口號，包括年，月，日，時，分，秒的精確表示，如“30/Apr/2007:00:00:02 +0800”3.用戶訪問網(wǎng)頁的URL地址,如:GET /skins/green/images/fzuc2007_green_search_01.gif HTTP/1.14.訪問請求是否成功的代碼表示等信息.3.2.

31、1.2 數(shù)據(jù)預(yù)處理 從上面的LOG日志文件中我們看到，這些文件中有本次設(shè)計所需要的兩大塊信息，用戶IP和用戶訪問的網(wǎng)頁的地址，而其它的信息對我們來講就是多余的，不必要的。又因為數(shù)據(jù)量非常之大，本次設(shè)計所用的網(wǎng)絡(luò)日志文件有7萬多條記錄。如果不進行數(shù)據(jù)的預(yù)處理，將造成程序運行相當緩慢，所以數(shù)據(jù)預(yù)處理這一塊是本次設(shè)計工作量比較大的一部分。本次的數(shù)據(jù)預(yù)處理過程分為以下幾個步聚：1.將用戶訪問的URL地址用數(shù)字代號（以#XXXX表示,如#0001）一一對映的進行替換，同時將URL地址與對應(yīng)的數(shù)字代碼存儲在txt文檔中，以便后續(xù)聚類結(jié)果分析的對比分析。如下圖3-2和3-3所示：圖3-2 URL整理替換后的

32、源數(shù)據(jù)圖3-3 URL與對應(yīng)的編號2.將用戶IP地址用數(shù)字代號（以XXXX表示,如0001）一一對映的進行替換，同時將IP地址與對應(yīng)的數(shù)字代碼存儲在txt文檔中，以便后續(xù)聚類結(jié)果分析的對比分析。如圖3-4和3-5所示：圖3-4 用戶IP整理后的源數(shù)據(jù)圖3-5 用戶IP與對應(yīng)的編號3.最后去掉不需要的多余數(shù)據(jù)，剩下用戶IP編碼和其訪問的URL地址編碼，如圖3-6所示： 圖3-6 最終輸入數(shù)據(jù)整理完成后，對用戶IP和URL進行統(tǒng)計，共有IP地址1506個，URL地址1700個，去掉訪問請求未成功的記錄，一共有訪問記錄5萬多條。3.2.1.3 數(shù)據(jù)存儲數(shù)據(jù)存儲方式：本次設(shè)計采用矩陣存儲的方式進行數(shù)據(jù)

33、存儲，首先定義一個足夠大的靜態(tài)整形二維數(shù)組做為URL-IP數(shù)據(jù)存儲矩陣URL-IP 。其中矩陣元素的初值根據(jù)不同算法有不同的要求：1.K均值算法中URL-IP矩陣元素的初值： 我們知道，同一個URL可能被同一個IP訪問多次，從本是否被訪問的角度上來講，我們只要考慮該URL_i是否有被IP_j訪問，若有則置URL-IPij=1,若無則置URL-IPij=0;而K均值聚類的算法還將訪問頻率，即被訪問的次數(shù)做為分類的參考因子，所以在K均值聚類中URL-IP矩陣元素值URL-IPij為URL_i被IP_j訪問的次數(shù)，相應(yīng)的代碼如圖3.5所示：2.Hamming算法中URL-IP矩陣元素的初值：在Ham

34、ming算法中，我們只考慮URL_i是否有被IP_j訪問過，若有，不管訪問幾次只要有被訪問就將URL-IP矩陣元素值URL-IPij置1，若無則置0.3.2.2 URL地址存儲本次網(wǎng)頁聚類系統(tǒng)的設(shè)計中，對于聚類結(jié)果的顯示，本設(shè)計可以顯示每個分類中具體的URL編號對應(yīng)的具體的URL地址，所以在初始化編程數(shù)據(jù)時，需要對URL對應(yīng)編號進行存儲，以便要顯示具體URL地址時的查找與調(diào)用顯示。3.2.3 各模塊功能介紹3.2.3.1 K均值聚類算法實現(xiàn)模塊該模塊主要是在K均值初始化的數(shù)據(jù)矩陣的基礎(chǔ)上，通過計算URL-IP矩陣的行向量間的距離將所有網(wǎng)頁歸入事先定義好的類別中，而后重新計算出每一類也就是自定義

35、類別中URL（,）的平均值，再進行分類，直到分類不再變化為止，即分類結(jié)束。3.2.3.2 Hamming聚類算法實現(xiàn)模塊該模塊是與K均值聚類算法的實現(xiàn)不一樣，沒有事先自定義分為幾類，而是在初始化矩陣的數(shù)據(jù)基礎(chǔ)上，構(gòu)造出一個新的URL-URL矩陣，其中每個元素的值URL-URLij為URLi和URLj中不同元素的個數(shù)，而后算出Hamming閾值，然后根據(jù)閾值來進行URL聚類，如果大元素值URL-URLij小于閾值，則URLi和URLj為一類。3.2.3.3 聚類結(jié)果顯示模塊由于聚類的結(jié)果是要將分類后的URL顯示給用戶，然而我們知道URL一共有1700個，如果全部一起顯示給用戶會使用戶無法清晰地分

36、析聚類的結(jié)果，所以我們先在LIST中顯示出分類后的URL代號，每一類的URL都顯示在LIST中的一行，由于顯示的窗口大小有限，所以有些類含URL很多無法在一行中全部顯示給用戶，所以用戶雙擊這一行，則會顯示出全部的URL代號，而后點擊詳細顯示，則顯示詳細的URL編號與地址。第4章 系統(tǒng)實現(xiàn)本章主要包括兩種聚類算法K均值聚類和Hamming聚類的實現(xiàn)，以及聚類結(jié)果的分析顯示，還有相關(guān)的數(shù)據(jù)處理的詳細過程和代碼分析。4.1 初始化數(shù)據(jù)模塊4.1.1 數(shù)據(jù)結(jié)構(gòu)的選擇數(shù)組是存儲數(shù)據(jù)的一種典型而又簡單可靠的數(shù)據(jù)結(jié)構(gòu)，數(shù)組在進行查找，排序操作是很方便的，而且數(shù)組可以動態(tài)分配這一方法又使數(shù)組的靈活性有所提高。

37、數(shù)組一般用在順序存儲中。順序存儲表示是將數(shù)據(jù)元素存放于一個連續(xù)的存儲空間，利用物理相鄰來表示邏輯關(guān)系，實現(xiàn)順序存取或(按下標)直接存取。它的存儲效率高，存取速度快。但它的空間大小如果是靜態(tài)分配的，一經(jīng)定義，在整個程序運行期間不會發(fā)生變化，因此，它不易擴充。同時，由于在插入或刪除時，為保持原有順序，平均需要移動一半(或近一半)元素，修改效率不高。 鏈式存儲15表示的存儲空間一般在程序運行過程中動態(tài)分配和釋放，且只要存儲器中還有空間，就不會產(chǎn)生溢出的問題。同時在插入和刪除時不需要保持數(shù)據(jù)元素的原有物理順序，只需要保持原有的邏輯順序就行了，故不必移動元素，只需修改它們的鏈接指針，修改效率高。但在存取

38、表中的數(shù)據(jù)元素時，只能循鏈順序進行訪問，且需要額外的指針，存儲效率和訪問效率低于順序存儲表示。而本次設(shè)計主要的數(shù)據(jù)處理都是順序存儲的，而且關(guān)聯(lián)到很多的順序?qū)?yīng)運算，用數(shù)組進行數(shù)據(jù)存儲是最優(yōu)的選擇?，F(xiàn)給出本次設(shè)計中數(shù)據(jù)初始化中相關(guān)數(shù)組的定義，程序代碼描述如下：幾個全局靜態(tài)數(shù)組的定義：Define int URl-IP20002000: K均值初始化矩陣define float HamU-I20002000: Hamming初始化矩陣extern CString url2000: URL地址存儲字符串數(shù)組4.1.2 兩種算法的矩陣數(shù)據(jù)初始化4.1.2.1 K均值算法矩陣數(shù)據(jù)初始化根據(jù)K值聚類的算法

39、描述，我們知道K均值聚類算法中的影響因子有數(shù)據(jù)量大小，也就是URL地址數(shù)目和用戶IP數(shù)目的大小和同一IP訪問同一URL的次數(shù)，也就是訪問頻率兩個方面。其數(shù)據(jù)矩陣初始化的編程代碼表示如圖4-1：圖4-1 K均值數(shù)據(jù)矩陣初始化代碼4.1.2.2 Hamming聚類算法矩陣數(shù)據(jù)初始化和K均值算法不一樣，Hamming算法所進么分類的標準主要是此URL是否被某IP訪問，有被訪問則置1，否則置0. 其數(shù)據(jù)矩陣初始化的編程代碼表示如圖4-2：圖4-2 Hamming數(shù)據(jù)矩陣初始化代碼4.1.2.3 URL地址字符串數(shù)組數(shù)據(jù)初始化由于聚類的結(jié)果是要將分類后的URL顯示給用戶，然而我們知道URL數(shù)目很多，很難

40、一起顯示給用戶，或者說會使用戶無法清晰地分析聚類的結(jié)果，所以我們先在LIST中顯示出分類后的URL代號，再顯示出對應(yīng)的具體的URL地址，因而我們需要對URL地址與其對應(yīng)的編號以字符串數(shù)組的形式進行存儲，以便要顯示具體URL地址時查找，調(diào)用和顯示。其數(shù)據(jù)矩陣初始化的編程代碼表示如圖4-3：圖4-3 url存儲數(shù)組初始化代碼4.2 K均值算法的實現(xiàn)4.2.1 分配一個URL向量到每個類中作為初始化類的平均URL向量按照K均值算法的描述，我們要事人為指定分類的個數(shù)K，并隨機地抽取其中的K個向量做為每一類的平均向量，因為第一次分配后每個分類中只有一個向量，所以這K個向量便為K個類的平均向量。在本次設(shè)計

41、中并沒有真正隨機分配，而是將第1,N,2N,n個分別作為第一次初始化的各類的平均向量。在系統(tǒng)中的程序編碼實現(xiàn)如圖4-4：圖4-4 K均值初始化的各類的中心向量代碼以上代碼段中，變量kjm代表要進行分類的URL個數(shù)，定義兩個m_knum維的字符串數(shù)組*kstr,*kstr1，是由于在后面的分類過程中需要循環(huán)地將kim個URL行向量分配到m_knum個類中，在這個基礎(chǔ)上要再次計算分配后的每個類的向量的平均值，就需要知道分配到每個類的的URL行向量是哪幾個，其中*kstr1記錄的是變化后的各類中URL行向量的序號，而*kstr記錄的是變化前各類中的URL行向量的序號。同時這兩個數(shù)組也是后面判斷循環(huán)結(jié)

42、束的條件因子之一。4.2.2 循環(huán)迭代分類過程給定每一分類的初始URL行向量后，我們就可以將kjm個URL行向量進行篩選分配到每個類中，并且計算每個新類的平均URL行向量，記下分類的情況，之而要進行新類與舊類的對比，若分類有更新說明聚類過程仍未結(jié)束，則繼續(xù)循環(huán)迭代進行分類，直到分類結(jié)束。其中編程代碼如圖4-5所示：圖4-5 K均值循環(huán)分類過程代碼上面的程序段中包含兩段代碼用一句話帶過，具體的實現(xiàn)方式在下列進行說明：進行一次遍歷，將URL分配到各個相應(yīng)的類中的代碼段如圖4-6所示：圖4-6 URL分配到各個相應(yīng)的類中的代碼計算平均值向量的過程，從前面定義的字符串數(shù)組*str中取出對應(yīng)的第j類中包

43、含的URL行向量對應(yīng)的行號，將其取出，將j類中包含的所有URL行向量的對應(yīng)元素值相加再除以URL的個數(shù)算出分配后類j的平均向量的每個元素值，從而得出分配后每個類的平均向量，為下一次分配作準備，其編程代碼實現(xiàn)如圖4-7：圖4-7 計算分配后各類的平均向量4.2.3 聚類結(jié)果顯示最后完成聚類，并進行結(jié)果顯示，顯示的結(jié)果如圖4-8所示，因為軟件第上顯示窗口無法將分類全部顯示出來，只好進行再次顯示，雙擊每一條分類，則進行完全顯示，在二次結(jié)果顯示的窗口中單擊“詳細URL地址列表”則進行對應(yīng)的詳細的URL地址顯示，其運行結(jié)果及界面如圖4-8所示：圖4-8 K均值運行結(jié)果顯示窗口我們看到第三行中分類后含的U

44、RL個數(shù)沒能完全顯示出來，雙擊此行則出現(xiàn)二次顯示窗口，如圖4-9：圖4-9 K均值二次顯示窗口在二次查看窗口中，我們?nèi)允侵荒芸捶诸惡?，每個類中包含的URL的對應(yīng)編號，而未能查看具體的URL地址，單擊“詳細URL列表”，則進行URL編號和地址的詳細顯示，如圖4-10：圖4-10 K均值具體url顯示窗口4.3 Hamming聚類算法實現(xiàn)4.3.1 Hamming算法描述如前所述，URL-IP矩陣M的行向量M.,j反映了客戶對本站點的不同頁面的訪問情況，如果客戶對某些頁面的訪問情況相同或相似，那么，這些頁面理應(yīng)為相關(guān)頁面，可以聚為一類。聚類時，同樣先對URL-IP關(guān)聯(lián)矩陣 M進行預(yù)處理，去掉所含元

45、素值都為0的行向量，在本次設(shè)計中無考慮此情況，因為如果行向量值為0，則說明沒有任何用戶訪問此網(wǎng)頁，那就不在我們的考慮之內(nèi)，我們所研究的是用戶所訪問的網(wǎng)頁的聚類。對于Mi,j0,可先令Mi,j=1，再根據(jù)hamming距離公式計算并構(gòu)造出行向量間的距離矩陣。在此矩陣中，表示第i個行向量和第j個行向量之間的Hamming距離，對角元素值為0.接下來根據(jù)閾值公式求URL-URL關(guān)聯(lián)矩陣的閾值：對于，如果,那么就將第i個URL和所有滿足這個條件的第j個URL劃分為一個類。4.3.2 構(gòu)造行向量間的距離矩陣由于本次設(shè)計不考慮URL行向量值為0的情況，所以可以根據(jù)HamU_I矩陣通過Hamming距離公式

46、直接構(gòu)造出URL行向量間的距離矩陣，其編程實現(xiàn)過程如圖4-11所示：圖4-11 構(gòu)造URL-URL關(guān)聯(lián)矩陣代碼4.3.3 求URL行向量間距離矩陣的閾值從已經(jīng)構(gòu)造好的行向量間距離矩陣中，根據(jù)閾值的計算公式，我們可以算出URL行向量矩陣的閾值，閾值是整個聚類過程的唯一，重要的參考指標，所以說閾值取值情況將決定Hamming聚類的結(jié)果的精確與否。所以在閾值的求解上，我們將公式可調(diào)化，也就是說閾值的求值公式中的某些參數(shù)的值可以由用戶來進行調(diào)整，使聚類的結(jié)果滿足用戶的最終需求，其編程中的實現(xiàn)過程如圖4-12所示：圖4-12 Hamming閾值求解代碼4.3.4 Hamming聚類算法核心代碼段由于Ha

47、mming算法是一個需要對分類中的每個值進行對應(yīng)向量代號進行循環(huán)再分類，其工作時間復(fù)雜度較高，因此，本次設(shè)計從i=0著手分出第一類，然后作一次數(shù)據(jù)優(yōu)化，去掉被其包含的子類。由于i=0對應(yīng)的行向量kcl0j所包含的元素個素是最多的，有hjm-1個，如果元素值kcl0j為1的數(shù)目多，則分出的第一類元素個數(shù)就比較多，可能包含的子類就更多，進行的數(shù)據(jù)優(yōu)化的效果就越好。下面是求出第一類的代碼分析，如圖4-13所示：圖4-13 求出第一類的代碼求出第一個類后，我們對數(shù)據(jù)矩陣進行優(yōu)化，我們把存在不屬于第一個類的行向量i作記號kclii=1，而行向量j上所含元素都在第一類中已存在的，我們說它完全包含于第一類，

48、我們也作標記kcljji=0;經(jīng)過數(shù)據(jù)優(yōu)化后，我們只對kclii值為1的行向量進行分類，同時當分出第二類時我們也作同樣的數(shù)據(jù)優(yōu)化，再次排除掉無效的行直到分類結(jié)束。下面是編程代碼的解析，如圖4-14所示：圖4-14 分出第一類后的數(shù)據(jù)優(yōu)化代碼中間分類及分類后的數(shù)據(jù)優(yōu)化代碼這里省略，原理和第一個類的分類過程是一樣的。4.3.5 Hamming聚類的結(jié)果顯示結(jié)果顯示與K均值的顯示界面及功能都基本相同，這里不再闡訴設(shè)計思想。顯示如圖4-15，圖4-16，圖4-17所示：圖4-15 Hamming聚類窗口圖4-16 Hamming聚類結(jié)果顯示窗口圖4-17 Hamming聚類二次顯示窗口4.4聚類結(jié)果分

49、析4.4.1 聚類的精確度分析根據(jù)實現(xiàn)的結(jié)果，本次設(shè)計將用戶訪問的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.）其它我們根據(jù)URL地址的基本結(jié)構(gòu)，自定義一個衡量聚類精確度的方法：設(shè)聚類的結(jié)果分為n類，去掉只含一個元素的類，誤分率大于50%的類和含大量元素的類（因為如果只含一個元素也就沒有正確與否之說，更不用談什么精確度了，如果誤分率大于50%，則我們不會去利用這樣的分類結(jié)果，而含有大量

50、元素的類，我們說這種類在本設(shè)計的兩種算法中都會出現(xiàn)，是不可避免的，特別是在數(shù)據(jù)量巨大時，由于這樣的類含的元素太多，肯定會包含以上所說的多種URL地址，這樣的情況下，我們也無法去解析它的精確度），剩下的分類數(shù)為N，我們把分析的對象定為含有一定數(shù)量元素的這樣一些類。設(shè)類i中共有y個URL，其中有x個URL與類中其它大部分元素是不同的，我們說這x個URL被錯分到類i中，這樣我們定義一個精確度值=1-x/y,=x/y，而總的分類精確度下面我們進行兩種聚類算法的精確度分析：1.Hamming聚類精確度計算：根據(jù)聚類結(jié)果顯示：當輸入數(shù)據(jù)為“Ip_Url.txt”時，結(jié)果總共分為46類，其中去掉大量元素類7

51、個，剩下可分析類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均值聚類精確度計算：根據(jù)聚類結(jié)果顯示：當輸入數(shù)據(jù)為“Ip_Url.txt”時，與Hamming分類數(shù)一樣設(shè)為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/

52、26;w=6/21;計算得出R91.8%為了使比較更為直觀，我們將兩個算法精度曲線描繪出來，如下圖4-18分類精確度曲線所示： 圖4-18 Kmeans與Hamming聚類確精度對比曲線其中縱坐標為每一分類中的分類精確度，最高為1，最小為0.5。前面定義精確度的時候說過，如果分類精確度小于0.5，也就是誤分率大于50%，那么這一分類我們認為是不理想的，不會采納，所以排除在分析對象之外。橫坐標為上面所對應(yīng)的可分析分類的類號，相互比較，我們清楚地看到在本設(shè)計相同的輸入中，當分類的個數(shù)一樣時，Hamming聚類的精確度比K均值聚類的精確度要高，同時，我們也看到二者的精確度都在90%以上，這說明兩種聚

53、類的算法都是有效的，都能夠較好地將具有相同或相似的URL聚在同一類。4.4.2 Hamming閾值對聚類結(jié)果的影響 前面我們提到Hamming閾值是分類過程中唯一也是最重要的衡量指標，那么閾值的變化對整個聚類的結(jié)果會有什么樣的影響呢？下面跟據(jù)實驗數(shù)據(jù)的對比和分析，我們將指出Hamming閾值的變化對聚類結(jié)果的具體影響。我們分3種情況，第一種為閾值與公式計算所得一樣不發(fā)生改變和調(diào)整;第二種為通過系統(tǒng)提供的閾值調(diào)整功能讓閾值變小;第三各為通過系統(tǒng)提供的閾值調(diào)整功能讓閾值變大. 下面比較三種情況下聚類的情況：閾值不變：此時分類數(shù)目為46，閾值為2.07301，閾值參數(shù)未作調(diào)整，如圖4-19所示：圖4

54、-19 閾值不變時的Hamming聚類結(jié)果此時分析聚類的結(jié)果，去掉大量元素類7個，剩下可分析類39個,下面給出可分析類的精確度曲線，如圖4-20所示：圖4-20 閾值不變時Hamming聚類精確度曲線2.閾值變大：通過對閾值參數(shù)N作調(diào)整使閾值變大，調(diào)整參數(shù)N為1.5，閾值為3.10952，分類數(shù)目43如圖-21所示：圖4-21 閾值變大后Hamming聚類的結(jié)果此時分析聚類的結(jié)果，去掉大量元素類7個，誤分率超過50%的少量元素類3個，剩下可分析類33個,下面給出可分析類的精確度曲線，如圖4-22所示： 圖4-22 閾值變大后Hamming聚類的精確度曲線3.閾值變?。和ㄟ^調(diào)整閾值參數(shù)N使閾值變

55、小，調(diào)整參數(shù)N為0.85，閾值為1.76206，分類的數(shù)目為85，如圖4-23所示：圖4-23 閾值變小后的Hamming聚類結(jié)果此時分析聚類的結(jié)果，去掉誤分率大于50%的少量元素類3個，大量元素類30個，剩下可分析類52個，下面給出可分析類的精確度曲線，如圖4-24所示： 圖4-24 閾值變小后Hamming聚類的精確度曲線通過對三種情況的分類精確度的分析，我們看到，當閾值變大時，分類的數(shù)目減少了，這說明分類變得比較粗糙，因此有可能造成分類精確度較低。通過精確度曲線圖也證實了精確度比較差;而如果調(diào)小閾值，我們發(fā)現(xiàn)分類的數(shù)目變大，且幅度比較高，但是同時產(chǎn)生的大量元素類的數(shù)目也有較大的提高，這說

56、明分類雖然多了，詳細了，但也使非利用類的數(shù)目變大（這是非利用類指的是大量元素類），可分析類的數(shù)目也有提高，而且從精確度曲線圖上，我們可以看出大部分分類的精確度都在90%以上，整條曲線比較平穩(wěn)，精確度較高，可以達到較為理想的聚類效果。下面我們用一個表較為直觀地顯示三者的對比結(jié)果，如表4-25所示：表4-1 閾值的變化對分類精確度的影響情況閾值變化總分類數(shù)變化可析類數(shù)變化大量元素類數(shù)誤分率高類數(shù)分類精確度變小85變大52變大30變大3較好不變463970一般變大433373較差4.4.3 分類數(shù)目變化對K均值聚類結(jié)果的影響由于K均值聚類是根據(jù)我們自定義的數(shù)目來進行分類的，但是因為我們隨機分配給每個

57、類的初始量不一定就是不現(xiàn)于其它類的量，有可能在第一次分配時就使這一類為空，這樣就使分類無法正常進行，于是在本設(shè)計中，如果某次分配后發(fā)現(xiàn)有空的類，則會把初始分量再次賦給它，等待下次的分配，其編程代碼在上文有說明，參看圖4-5。那么下面我們將根據(jù)實驗得出的數(shù)據(jù)對分類數(shù)目進行三種變化，從而分析分類數(shù)目變化對K均值聚類結(jié)果的影響。為了能和Hamming聚類結(jié)果進行比較，K均值分類的數(shù)目將和上面Hamming聚類三種情況下分類的數(shù)目取相同的數(shù)據(jù)。分類數(shù)目不變：分類數(shù)目為46，如圖4-25所示：圖4-25 分類數(shù)目不變時的K均值聚類結(jié)果下面我們對分類的精確度進行分析，去掉大量元素類1，單元素類13，誤分率

58、較大類3，剩下可分析類29，其精確度曲線如圖4-26所示：圖4-26 分類數(shù)目不變時的K均值聚類精確度曲線分類數(shù)目變大：分類數(shù)目為85，如圖4-27所示：圖4-27 分類數(shù)目變大時的K均值聚類結(jié)果下面我們對分類的精確度進行分析，去掉大量元素類1，單元素類32，誤分率較大類4，剩下可分析類43，其精確度曲線如圖4-28所示：圖4-28 分類數(shù)目變大時的K均值聚類精確度曲線3.分類數(shù)目變?。悍诸悢?shù)為43，如圖4-29所示：圖4-29 分類數(shù)目變小時的K均值聚類結(jié)果下面我們對分類的精確度進行分析，去掉大量元素類1，單元素類14，誤分率較大類6，剩下可分析類22，其精確度曲線如圖4-30所示：圖4-3

59、0 分類數(shù)目變小時的K均值聚類精確度曲線通過三種情況的對比分析，我們可以看到，當分類數(shù)目變大時單元素類大量增加，但是分類的精確度確是有所提高，分類精確度曲線出現(xiàn)的都較陡的坡度，這說明很少有連續(xù)的誤分類，只有個別誤分類穿插出現(xiàn);而當分類數(shù)目變小時，精確度并不是有很大的變化，但是從坡度上我們可以看出坡度都較緩，這說明會有大量的連續(xù)的誤分類，所以其實上當分類數(shù)變小時精確度有所下降。下面用表格較為直觀地進行說明，如表4-2所示：表4-2 分類數(shù)目的變化對分類精確度的影響分類數(shù)目變化單元素類數(shù)大量元素類數(shù)可分析類數(shù)誤分率高類數(shù)分類精確度43變小14無明顯變化1無變化22減小6增大降代46不變131293

60、一般85變大32大量增多1無變化43增多4變化不大增高4.4.4 兩種聚類方法的對比總結(jié)通過以上對兩種聚類方法的結(jié)果進行詳細的對比和分析，我們看到，在相同分類數(shù)的情況下，Hamming聚類的精確度要比K均值的分類精確度高。但是兩種聚類的算法，在相應(yīng)的參數(shù)選擇好的情況下，如Hamming閾值的調(diào)整，和K均值的分類數(shù)目，如果參數(shù)選得好都可以達到較為滿意的聚類結(jié)果。此次通過兩種算法K均值算法和Hamming算法分別來對網(wǎng)頁進行分類，其中Hamming算法的設(shè)計是參照宋擒豹 沈鈞毅關(guān)于Web日志高效多能挖掘算法中的Hamming聚類算法12.在本次實驗中，對于原作者對Hamming閾值的計算公式進行了

61、調(diào)整。在實驗過程中，根據(jù)實驗的數(shù)據(jù)，若根據(jù)原來的Hamming閾值計算公式求閾值，會導(dǎo)致最后的分類數(shù)目極少，甚至只有一類。因此，在本次實驗中，原作者所提的閾值公式12在本次設(shè)計中并不合適，在調(diào)適運行過程中，本次設(shè)計對其公式進行改進最后使分類能夠順利進行，而且效果也比較理想。此次驗證性實驗證時，Hamming算法中的閾值是要根據(jù)不同情況下的輸入進行相應(yīng)的調(diào)節(jié)，才能使分類更加精準有效，同時本次設(shè)計及實驗結(jié)果也說明了兩種算法都是有效的聚類算法，都可以較理想地進行聚類分析。致謝在這次畢業(yè)設(shè)計過程中，首先感謝白清源教授在算法上的詳細解釋，在算法資料上的提供，在論文格式及要求上的檢查和改正。感謝林鑫顯在系統(tǒng)實現(xiàn)過程的幫助,感謝身邊同學(xué)在設(shè)計過程中的鼓勵與幫助。參考文獻1 高新波.模糊聚類分析及其應(yīng)用.西安：西安電子科技大學(xué)出版社.2004：23-45.2 李恒峰，李國輝.基于內(nèi)容的音頻檢索與分類.計算機工程與應(yīng)用.2000.7.3（加）韓家煒，堪博 著，范明，孟小峰 譯.數(shù)據(jù)挖掘概念與技術(shù).北京：機械工業(yè)出版社.2007：18-90.4劉書香，盧才武.數(shù)據(jù)挖掘中的客戶聚類分析及其算法實現(xiàn).信息技術(shù).2004年1月，第28卷第1期，PP.4-10.5 尹松，周永叔，李陶深.數(shù)據(jù)聚