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

本科生畢業(yè)設(shè)計(jì)（論文）題 目： Web聚類Hamming算法與K均值算法的 研究與實(shí)現(xiàn) 姓 名： 陳云峰 學(xué) 號： 030300714 學(xué) 院： 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 專 業(yè)： 年 級： 2003級 指導(dǎo)教師： （簽名） 2007 年 6 月 16 日Web聚類Hamming算法與K均值算法的研究與實(shí)現(xiàn)摘要聚類分析也稱群分析、點(diǎn)群分析，它是研究分類的一種多元統(tǒng)計(jì)方法。我們所研究的樣品或指標(biāo)之間存在程度不同的相似性。于是根據(jù)一批樣品的多個(gè)觀測指標(biāo)，具體找出一些能夠度量樣品或指標(biāo)之間相似程度的統(tǒng)計(jì)量，以這些統(tǒng)計(jì)量為劃分類型的依據(jù)。把一些相似程度較大的樣品或指標(biāo)聚合為一類，把另外一些彼此之間相似程度較大的樣品或指標(biāo)又聚合為另一類，關(guān)系密切的聚合到一個(gè)小的分類單位，關(guān)系疏遠(yuǎn)的聚合到一個(gè)大的分類單位，直到把所有的樣品或指標(biāo)聚合完畢，這就是聚類的基本思想。隨著科學(xué)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)成為了人們生活中必不可少的重要組成部分。因此，關(guān)于網(wǎng)頁數(shù)據(jù)的種種研究都有著其重要的現(xiàn)實(shí)意義。特別是網(wǎng)頁聚類，它關(guān)系著人們網(wǎng)上獲取信息效率的高低，同時(shí)也是網(wǎng)頁信息組織的主要依據(jù)。本文通過對Web日志數(shù)據(jù)的挖掘研究，應(yīng)用兩種聚類的算法，Hamming算法和K均值算法，將用戶所訪問的網(wǎng)頁進(jìn)行聚類。在這兩種算法中，首先以Web站點(diǎn)URL為行，UserID為列建立URL-UserID關(guān)聯(lián)矩陣.兩種不同算法構(gòu)造的矩陣中的元素值不同,文中會詳細(xì)說明,然后對行向量進(jìn)行相似性分析,可以得到相似的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 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 聚類和聚類分析的概念及其相關(guān)分類1.1.1 聚類和聚類分析的相關(guān)概念所謂類，通俗地說，就是指相似元素的集合。 那么我們所講的聚類，從字面上就可以看出，就是將某個(gè)領(lǐng)域內(nèi)的一些同一屬性的事物，根據(jù)它們個(gè)體之間的相似性，將其分為幾個(gè)群集1。聚類分析又稱群分析，它是研究（樣品或指標(biāo)）分類問題的一種多元統(tǒng)計(jì)方法。嚴(yán)格的數(shù)學(xué)定義是較麻煩的，在不同問題中類的定義是不同的。聚類分析起源于分類學(xué)，在考古的分類學(xué)中，人們主要依靠經(jīng)驗(yàn)和專業(yè)知識來實(shí)現(xiàn)分類。隨著生產(chǎn)技術(shù)和科學(xué)的發(fā)展，人類的認(rèn)識不斷加深，分類越來越細(xì)，要求也越來越高，有時(shí)光憑經(jīng)驗(yàn)和專業(yè)知識是不能進(jìn)行確切分類的，往往需要定性和定量分析結(jié)合起來去分類，于是數(shù)學(xué)工具逐漸被引進(jìn)分類學(xué)中，形成了數(shù)值分類學(xué)2。后來隨著多元分析的引進(jìn)，聚類分析又逐漸從數(shù)值分類學(xué)中分離出來而形成一個(gè)相對獨(dú)立的分支。在社會經(jīng)濟(jì)領(lǐng)域中存在著大量分類問題，比如對我國30個(gè)省市自治區(qū)獨(dú)立核算工業(yè)企業(yè)經(jīng)濟(jì)效益進(jìn)行分析，一般不是逐個(gè)省市自治區(qū)去分析，而較好地做法是選取能反映企業(yè)經(jīng)濟(jì)效益的代表性指標(biāo)，如百元固定資產(chǎn)實(shí)現(xiàn)利稅、資金利稅率、產(chǎn)值利稅率、百元銷售收入實(shí)現(xiàn)利潤、全員勞動(dòng)生產(chǎn)率等等，根據(jù)這些指標(biāo)對30個(gè)省市自治區(qū)進(jìn)行分類，然后根據(jù)分類結(jié)果對企業(yè)經(jīng)濟(jì)效益進(jìn)行綜合評價(jià)，就易于得出科學(xué)的分析。又比如若對某些大城市的物價(jià)指數(shù)進(jìn)行考察，而物價(jià)指數(shù)很多，有農(nóng)用生產(chǎn)物價(jià)指數(shù)、服務(wù)項(xiàng)目價(jià)指數(shù)、食品消費(fèi)物價(jià)指數(shù)、建材零售價(jià)格指數(shù)等等。由于要考察的物價(jià)指數(shù)很多，通常先對這些物價(jià)指數(shù)進(jìn)行分類?？傊?，需要分類的問題很多，因此聚類分析這個(gè)有用的數(shù)學(xué)工具越來越受到人們的重視，它在許多領(lǐng)域中都得到了廣泛的應(yīng)用。31.1.2 聚類分析算法的分類聚類分析是數(shù)據(jù)挖掘中的一個(gè)很活躍的研究領(lǐng)域，在這個(gè)領(lǐng)域里人們已經(jīng)提出并實(shí)現(xiàn)了許多不同的聚類算法。這些算法可以被分為劃分方法、層次方法、基于密度方法、基于網(wǎng)格方法和基于模型方法4。 1 、劃分方法(PAM:Partitioning method)5， 首先創(chuàng)建k個(gè)劃分，k為要?jiǎng)?chuàng)建的劃分個(gè)數(shù),然后利用一個(gè)循環(huán)定位技術(shù)通過將對象從一個(gè)劃分移到另一個(gè)劃分來幫助改善劃分質(zhì)量。典型的劃分方法包括k-means,k-medoids,CLARA(Clustering LARge Application),CLARANS(Clustering Large Application based upon RANdomized Search)EM(Expectation Maximization)則是不將對象明顯地分到幾個(gè)簇,而是根據(jù)表示可能性的權(quán)來分配對象.2、 層次方法(hierarchical method)，創(chuàng)建一個(gè)層次以分解給定的數(shù)據(jù)集。該方法可以分為自上而下（分解）和自下而上（合并）兩種操作方式。為彌補(bǔ)分解與合并的不足，層次合并經(jīng)常要與其它聚類方法相結(jié)合，如循環(huán)定位6。典型的這類方法中第一個(gè)是BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies) 方法，它首先利用樹的結(jié)構(gòu)對對象集進(jìn)行劃分；然后再利用其它聚類方法對這些聚類進(jìn)行優(yōu)化。第二個(gè)是CURE(Clustering Using REprisentatives) 方法，它利用固定數(shù)目代表對象來表示相應(yīng)聚類，然后對各聚類進(jìn)行收縮處理。第三個(gè)是ROCK方法，它利用聚類間的連接進(jìn)行聚類合并。最后一個(gè)CHEMALOEN，它則是在層次聚類時(shí)構(gòu)造動(dòng)態(tài)模型。3、 基于密度方法，根據(jù)密度完成對象的聚類7。它根據(jù)對象周圍的密度（如DBSCAN）不斷增長聚類。典型的基于密度方法包括：GDBSCAN，DBCLASD，DENCLUE(DENsity-based CLUstEring)，DBSCAN(Densit-based Spatial Clustering of Application with Noise)。DBSCAN算法通過不斷生長足夠高密度區(qū)域來進(jìn)行聚類，它能從含有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。此方法將一個(gè)聚類定義為一組“密度連接”的點(diǎn)集。OPTICS(Ordering Points To Identify the Clustering Structure)并不明確產(chǎn)生一個(gè)聚類，而是為自動(dòng)交互的聚類分析計(jì)算出一個(gè)增強(qiáng)聚類順序8。4、 基于網(wǎng)格方法，首先將對象空間劃分為有限個(gè)單元以構(gòu)成網(wǎng)格結(jié)構(gòu)；然后利用網(wǎng)格結(jié)構(gòu)完成聚類。STING(STatistical INformation Grid) 就是一個(gè)利用網(wǎng)格單元保存的統(tǒng)計(jì)信息進(jìn)行基于網(wǎng)格聚類的方法9。CLIQUE(Clustering In QUEst)和Wave-Cluster 則是一個(gè)將基于網(wǎng)格與基于密度相結(jié)合的方法。5、基于模型方法，它假設(shè)每個(gè)聚類的模型并發(fā)現(xiàn)適合相應(yīng)模型的數(shù)據(jù)10。典型的基于模型方法有統(tǒng)計(jì)方法COBWEB，它是一個(gè)常用的且簡單的增量式概念聚類方法。它的輸入對象是采用符號量（屬性-值）對來加以描述的。采用分類樹的形式來創(chuàng)建一個(gè)層次聚類。CLASSIT是COBWEB的另一個(gè)版本。它可以對連續(xù)取值屬性進(jìn)行增量式聚類。它為每個(gè)結(jié)點(diǎn)中的每個(gè)屬性保存相應(yīng)的連續(xù)正態(tài)分布（均值與方差），并利用一個(gè)改進(jìn)的分類能力描述方法，即不像COBWEB那樣計(jì)算離散屬性（取值）而是對連續(xù)屬性求積分11。但是CLASSIT方法也存在與COBWEB類似的問題。因此它們都不適合對大數(shù)據(jù)庫進(jìn)行聚類處理.還有就是AutoClass，它采用貝葉斯統(tǒng)計(jì)分析來估算結(jié)果簇的數(shù)目.1.1.3 本次設(shè)計(jì)所用算法介紹本次設(shè)計(jì)中，主要用到兩個(gè)聚類算法，一個(gè)就是以上提到的K均值聚類算法，而別一個(gè)則是Hamming聚類算法12。 K均值算法：有多個(gè)對象組成的數(shù)據(jù)集，將其劃分為k個(gè)類，k是人為指定的。先隨機(jī)地從數(shù)據(jù)集中取出k個(gè)對象，每個(gè)對象初始地代表一個(gè)簇的平均值（或中心點(diǎn)）。對剩下的每個(gè)對象，根據(jù)與各中心的距離，將其賦給最近的簇。每個(gè)簇就增加了一些對象，用每個(gè)簇這些對象重新計(jì)算每個(gè)簇平均值，得到新的簇平均值，再重新計(jì)算每個(gè)對象到各新平均值的距離，每個(gè)對象重新分簇，直到對象重新分簇不再變化。Hamming算法：我們認(rèn)為一些網(wǎng)頁頁面具有相似性，可以歸為一類，而這種分類是根據(jù)這些網(wǎng)頁之間的Hamming距離的大小來進(jìn)行衡量的。我們說一個(gè)URL-UserID關(guān)聯(lián)矩陣可以構(gòu)造出一個(gè)URL-URL關(guān)聯(lián)矩陣，此矩陣又能根據(jù)一定的算法算出一個(gè)閾值。如果根據(jù)算出的兩個(gè)元素間的hamming距離小于這個(gè)閾值，我們便認(rèn)為這兩個(gè)頁面具有相似性，可以歸為一類。下面說明一下hamming距離的定義式：設(shè)X，Y為n維向量，其中,分別表示n維向量X，Y的第i個(gè)元素的值，而Hamming距離H(X，Y)可以表示為(X，Y)=所以這次設(shè)計(jì)的主要算法之一也就是上面所介紹的hamming聚類算法，我們算出URL-UserID關(guān)聯(lián)矩陣中每兩個(gè)URL向量間的hamming距離，再與算出的閾值做比較，如果小于此閾值，我們便把這兩個(gè)頁面認(rèn)為是相似的，歸為同一類，聚為同一個(gè)類別。1.2 數(shù)據(jù)挖掘技術(shù)的發(fā)展研究現(xiàn)狀數(shù)據(jù)挖掘是一個(gè)新興的邊緣學(xué)科，它匯集了來自機(jī)器學(xué)習(xí)、模式識別、數(shù)據(jù)庫、統(tǒng)計(jì)學(xué)、人工智能以及管理信息系統(tǒng)等各學(xué)科的成果。多學(xué)科的相互交融和相互促進(jìn)，使得這一新學(xué)科得以蓬勃發(fā)展，而且已初具規(guī)模。13人工智能研究領(lǐng)域的科學(xué)家也普遍認(rèn)為，下一個(gè)人工智能應(yīng)用的重要課題之一，將是以機(jī)器學(xué)習(xí)算法為主要工具的大規(guī)模的數(shù)據(jù)庫知識發(fā)現(xiàn)。盡管數(shù)據(jù)挖掘還是一個(gè)很新的研究課題，但它所固有的為企業(yè)創(chuàng)造巨大經(jīng)濟(jì)效益的潛力，已使其很快有了許多成功的應(yīng)用，具有代表性的應(yīng)用有市場預(yù)測、投資、制造業(yè)、銀行、通訊等幾個(gè)方面。美國鋼鐵公司和神戶鋼鐵公司利用基于數(shù)據(jù)挖掘技術(shù)的ISPA系統(tǒng)，研究分析產(chǎn)品性能規(guī)律和進(jìn)行質(zhì)量控制，取得了顯著效果。14通用電器公司(GE)與法國飛機(jī)發(fā)動(dòng)機(jī)制造公司(sNEcMA)，利用數(shù)據(jù)挖掘技術(shù)研制了CASSIOPEE質(zhì)量控制系統(tǒng)，被三家歐洲航空公司用于診斷和預(yù)測波音737的故障，帶來了可觀的經(jīng)濟(jì)效益。而在這些數(shù)據(jù)挖掘的技術(shù)中，Web日志數(shù)據(jù)挖掘的研究逐漸被人們所關(guān)注。特別是計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的高術(shù)發(fā)展，對Web日志進(jìn)行數(shù)據(jù)挖掘顯得越來越重要。當(dāng)今社會，網(wǎng)絡(luò)已經(jīng)成為人們生活中的重要組成部分，網(wǎng)絡(luò)是人們獲取信息的一個(gè)相當(dāng)重要的途徑，隨著電子網(wǎng)務(wù)技術(shù)的發(fā)展，網(wǎng)上購物也逐漸被人們所接納且終將成為世界經(jīng)濟(jì)發(fā)展的廣闊市場。所以人們對網(wǎng)頁相關(guān)科技的發(fā)展也越來越關(guān)注。網(wǎng)頁聚類技術(shù)，作為當(dāng)前網(wǎng)絡(luò)科技研究的一大方向，一直都因有著巨大的作用而被人們關(guān)注。一個(gè)正確的，高效的網(wǎng)頁聚類方案的實(shí)現(xiàn)，將從根本上解決大部分的網(wǎng)絡(luò)獲取信息中遇到的難題。比如，網(wǎng)頁松散而又海量，人們有時(shí)難以從這樣海量的數(shù)據(jù)中尋找自己要的信息。即使有搜索工具進(jìn)行輔助，也必須有好的預(yù)處理網(wǎng)頁的聚類方案，才能使搜索更加準(zhǔn)確而有效，所以Web聚類技術(shù)的研究雖然發(fā)展不是很久，但處在這樣一個(gè)科技高速發(fā)展的形式下，倍受人們的關(guān)注。1.3 設(shè)計(jì)出發(fā)點(diǎn)及主要設(shè)計(jì)任務(wù)和目標(biāo)為便于從大量組織松散動(dòng)態(tài)性強(qiáng)的Web網(wǎng)頁中快速有效地發(fā)現(xiàn)知識，很早人們便提出了網(wǎng)頁搜索技術(shù)，但是由于網(wǎng)上信息的海量、動(dòng)態(tài)和無結(jié)構(gòu)性，使得用戶信息迷向，影響檢索效率。這是因?yàn)椋核阉饕鏌o法覆蓋全部萬維網(wǎng)信息；萬維網(wǎng)具有動(dòng)態(tài)性，搜索引擎索引中包含的“斷鏈接”和“過時(shí)網(wǎng)頁”削弱了搜索引擎的作用；搜索引擎返回的結(jié)果中相關(guān)信息和無關(guān)信息混雜；自然語言中存在的“一義多詞”與“一詞多義”現(xiàn)象，也導(dǎo)致用戶提出的查詢信息往往不能清楚地表達(dá)自己的真正需要。于是人們便開始提出用聚類的方法自動(dòng)組織搜索引擎的搜索結(jié)果，同時(shí)個(gè)性化服務(wù)于該系統(tǒng)，主動(dòng)對外界反饋信息做出響應(yīng)，方便用戶發(fā)現(xiàn)真正需要的萬維網(wǎng)信息。所以本次設(shè)計(jì)的主要任務(wù)是以聚類算法為核心，根據(jù)若干用戶訪問網(wǎng)頁的Web日志信息，將這些網(wǎng)頁通過具體的聚類算法進(jìn)行分類。通過聚類得到的若干個(gè)網(wǎng)頁的類體，這些類型的網(wǎng)頁有著不同程度的某種相關(guān)性，在此基礎(chǔ)上我們可以實(shí)現(xiàn)如何安排網(wǎng)頁連接，使用戶用起來更方便，更有效率。同時(shí)，對兩種聚類算法得出的分類結(jié)果進(jìn)行對比分析，列出其異同點(diǎn)，指出各算法的不足之處，希望能對現(xiàn)實(shí)生活中的工作需求有所幫助，從而使本次的設(shè)計(jì)有其現(xiàn)實(shí)的意義。1.4 論文的組織本論文主要有以下五個(gè)部分：第1章 緒論。主要介紹關(guān)于web聚類分析的概念和發(fā)展現(xiàn)狀、課題任務(wù)等。第2章 開發(fā)環(huán)境技術(shù)背景。主要介紹課題的開發(fā)環(huán)境和技術(shù)背景。第3章 設(shè)計(jì)部分。主要介紹課題的概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。第4章 系統(tǒng)實(shí)現(xiàn)及結(jié)果分析。主要介紹系統(tǒng)的具體實(shí)現(xiàn)和核心代碼段和聚類分析。 最后 致謝與參考文獻(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 (Microsoft Foundation Class)中的各種類結(jié)合起來構(gòu)成了一個(gè)應(yīng)用程序框架，它的目的就是讓程序員在此基礎(chǔ)上來建立Windows下的應(yīng)用程序，這是一種相對SDK來說更為簡單的方法。因?yàn)榭傮w上，MFC框架定義了應(yīng)用程序的輪廓，并提供了用戶接口的標(biāo)準(zhǔn)實(shí)現(xiàn)方法，程序員所要做的就是通過預(yù)定義的接口把具體應(yīng)用程序特有的東西填入這個(gè)輪廓。Microsoft Visual C+提供了相應(yīng)的工具來完成這個(gè)工作：AppWizard可以用來生成初步的框架文件（代碼和資源等）；資源編輯器用于幫助直觀地設(shè)計(jì)用戶接口；ClassWizard用來協(xié)助添加代碼到框架文件；最后，編譯，則通過類庫實(shí)現(xiàn)了應(yīng)用程序特定的邏輯。 （1）封裝性 構(gòu)成MFC框架的是MFC類庫。MFC類庫是C+類庫。這些類或者封裝了Win32應(yīng)用程序編程接口，或者封裝了應(yīng)用程序的概念，或者封裝了OLE特性，或者封裝了ODBC和DAO數(shù)據(jù)訪問的功能，等等。（2）繼承性首先，MFC抽象出眾多類的共同特性，設(shè)計(jì)出一些基類作為實(shí)現(xiàn)其他類的基礎(chǔ)。這些類中，最重要的類是CObject和CCmdTarget。CObject是MFC的根類，絕大多數(shù)MFC類是其派生的，包括CCmdTarget。針對每種不同的對象，MFC都設(shè)計(jì)了一組類對這些對象進(jìn)行封裝，每一組類都有一個(gè)基類，從基類派生出眾多更具體的類。這些對象包括以下種類：窗口對象，基類是CWnd；應(yīng)用程序?qū)ο?，基類是CwinThread；文檔對象，基類是Cdocument，等等。（3）虛擬函數(shù)和動(dòng)態(tài)約束MFC以“C+”為基礎(chǔ)，自然支持虛擬函數(shù)和動(dòng)態(tài)約束15。但是作為一個(gè)編程框架，有一個(gè)問題必須解決：如果僅僅通過虛擬函數(shù)來支持動(dòng)態(tài)約束，必然導(dǎo)致虛擬函數(shù)表過于臃腫，消耗內(nèi)存，效率低下。MFC建立了消息映射機(jī)制，以一種富有效率、便于使用的手段解決消息處理函數(shù)的動(dòng)態(tài)約束問題。這樣，通過虛擬函數(shù)和消息映射，MFC類提供了豐富的編程接口。程序員繼承基類的同時(shí)，把自己實(shí)現(xiàn)的虛擬函數(shù)和消息處理函數(shù)嵌入MFC的編程框架。（4）MFC的宏觀框架體系 如前所述，MFC實(shí)現(xiàn)了對應(yīng)用程序概念的封裝，把類、類的繼承、動(dòng)態(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)定性和簡易性，將會使程序更加健壯和便于維護(hù)。第3章 設(shè)計(jì)部分本部分包括概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)部分。3.1 概要設(shè)計(jì)網(wǎng)頁聚類分析的設(shè)計(jì)算法有很多種，以上概論中已經(jīng)有詳細(xì)的說明。而本次設(shè)計(jì)采取了兩種算法來進(jìn)行網(wǎng)頁的聚類和分析。分析的結(jié)果精確度和所取的數(shù)據(jù)量的大小有很大的關(guān)系，數(shù)據(jù)量越大，聚類的結(jié)果就越準(zhǔn)確，越有應(yīng)用價(jià)值。由于需要處理的數(shù)據(jù)，數(shù)據(jù)量很大，我們需要對數(shù)據(jù)進(jìn)行預(yù)處理。當(dāng)數(shù)據(jù)處理完后，進(jìn)行數(shù)據(jù)的輸入，進(jìn)而在編程環(huán)境下進(jìn)行編程實(shí)現(xiàn)對數(shù)據(jù)的分類，即對網(wǎng)頁進(jìn)行聚類，當(dāng)結(jié)果出來后，對相應(yīng)算法的結(jié)果進(jìn)行分析和對比，闡述兩種算法的優(yōu)缺點(diǎn)和現(xiàn)實(shí)應(yīng)用價(jià)值，對以后的科學(xué)研究和應(yīng)用提供一點(diǎn)參考。設(shè)計(jì)的概要框架如圖3-0所示：圖3-0 設(shè)計(jì)概要框架圖3.2 詳細(xì)設(shè)計(jì)3.2.1 數(shù)據(jù)預(yù)處理與數(shù)據(jù)存儲3.2.1.1 Log日志的源數(shù)據(jù)格式及包含的信息網(wǎng)絡(luò)日志LOG文件記錄了，用戶訪問網(wǎng)頁的詳細(xì)信息，是我們研究網(wǎng)頁聚類和用戶聚類的一個(gè)很有價(jià)值的數(shù)據(jù)資源。本次設(shè)計(jì)所用的處理數(shù)據(jù)就是網(wǎng)絡(luò)日志，從對網(wǎng)絡(luò)日志進(jìn)行數(shù)據(jù)挖掘，來對網(wǎng)頁進(jìn)行聚類分析。下面是本次設(shè)計(jì)所用網(wǎng)絡(luò)日志文件中源數(shù)據(jù)的截圖和信息說明，如圖3-1：圖3-1 Log日志源文件截圖我們發(fā)現(xiàn)每條日志記錄都包含了幾塊相同的信息：1.訪問用戶的IP，在第一條記錄的開頭都記錄訪問用的IP地址，如“125.41.34.6”2.用戶訪問的具體時(shí)間及訪問端口號，包括年，月，日，時(shí)，分，秒的精確表示，如“30/Apr/2007:00:00:02 +0800”3.用戶訪問網(wǎng)頁的URL地址,如:"GET /skins/green/images/fzuc2007_green_search_01.gif HTTP/1.1"4.訪問請求是否成功的代碼表示等信息.3.2.1.2 數(shù)據(jù)預(yù)處理 從上面的LOG日志文件中我們看到，這些文件中有本次設(shè)計(jì)所需要的兩大塊信息，用戶IP和用戶訪問的網(wǎng)頁的地址，而其它的信息對我們來講就是多余的，不必要的。又因?yàn)閿?shù)據(jù)量非常之大，本次設(shè)計(jì)所用的網(wǎng)絡(luò)日志文件有7萬多條記錄。如果不進(jìn)行數(shù)據(jù)的預(yù)處理，將造成程序運(yùn)行相當(dāng)緩慢，所以數(shù)據(jù)預(yù)處理這一塊是本次設(shè)計(jì)工作量比較大的一部分。本次的數(shù)據(jù)預(yù)處理過程分為以下幾個(gè)步聚：1.將用戶訪問的URL地址用數(shù)字代號（以#XXXX表示,如#0001）一一對映的進(jìn)行替換，同時(shí)將URL地址與對應(yīng)的數(shù)字代碼存儲在txt文檔中，以便后續(xù)聚類結(jié)果分析的對比分析。如下圖3-2和3-3所示：圖3-2 URL整理替換后的源數(shù)據(jù)圖3-3 URL與對應(yīng)的編號2.將用戶IP地址用數(shù)字代號（以XXXX表示,如0001）一一對映的進(jìn)行替換，同時(shí)將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進(jìn)行統(tǒng)計(jì)，共有IP地址1506個(gè)，URL地址1700個(gè)，去掉訪問請求未成功的記錄，一共有訪問記錄5萬多條。3.2.1.3 數(shù)據(jù)存儲數(shù)據(jù)存儲方式：本次設(shè)計(jì)采用矩陣存儲的方式進(jìn)行數(shù)據(jù)存儲，首先定義一個(gè)足夠大的靜態(tài)整形二維數(shù)組做為URL-IP數(shù)據(jù)存儲矩陣URL-IP 。其中矩陣元素的初值根據(jù)不同算法有不同的要求：1.K均值算法中URL-IP矩陣元素的初值： 我們知道，同一個(gè)URL可能被同一個(gè)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矩陣元素的初值：在Hamming算法中，我們只考慮URL_i是否有被IP_j訪問過，若有，不管訪問幾次只要有被訪問就將URL-IP矩陣元素值URL-IPij置1，若無則置0.3.2.2 URL地址存儲本次網(wǎng)頁聚類系統(tǒng)的設(shè)計(jì)中，對于聚類結(jié)果的顯示，本設(shè)計(jì)可以顯示每個(gè)分類中具體的URL編號對應(yīng)的具體的URL地址，所以在初始化編程數(shù)據(jù)時(shí)，需要對URL對應(yīng)編號進(jìn)行存儲，以便要顯示具體URL地址時(shí)的查找與調(diào)用顯示。3.2.3 各模塊功能介紹3.2.3.1 K均值聚類算法實(shí)現(xiàn)模塊該模塊主要是在K均值初始化的數(shù)據(jù)矩陣的基礎(chǔ)上，通過計(jì)算URL-IP矩陣的行向量間的距離將所有網(wǎng)頁歸入事先定義好的類別中，而后重新計(jì)算出每一類也就是自定義類別中URL（,）的平均值，再進(jìn)行分類，直到分類不再變化為止，即分類結(jié)束。3.2.3.2 Hamming聚類算法實(shí)現(xiàn)模塊該模塊是與K均值聚類算法的實(shí)現(xiàn)不一樣，沒有事先自定義分為幾類，而是在初始化矩陣的數(shù)據(jù)基礎(chǔ)上，構(gòu)造出一個(gè)新的URL-URL矩陣，其中每個(gè)元素的值URL-URLij為URLi和URLj中不同元素的個(gè)數(shù)，而后算出Hamming閾值，然后根據(jù)閾值來進(jìn)行URL聚類，如果大元素值URL-URLij小于閾值，則URLi和URLj為一類。3.2.3.3 聚類結(jié)果顯示模塊由于聚類的結(jié)果是要將分類后的URL顯示給用戶，然而我們知道URL一共有1700個(gè)，如果全部一起顯示給用戶會使用戶無法清晰地分析聚類的結(jié)果，所以我們先在LIST中顯示出分類后的URL代號，每一類的URL都顯示在LIST中的一行，由于顯示的窗口大小有限，所以有些類含URL很多無法在一行中全部顯示給用戶，所以用戶雙擊這一行，則會顯示出全部的URL代號，而后點(diǎn)擊詳細(xì)顯示，則顯示詳細(xì)的URL編號與地址。第4章 系統(tǒng)實(shí)現(xiàn)本章主要包括兩種聚類算法K均值聚類和Hamming聚類的實(shí)現(xiàn)，以及聚類結(jié)果的分析顯示，還有相關(guān)的數(shù)據(jù)處理的詳細(xì)過程和代碼分析。4.1 初始化數(shù)據(jù)模塊4.1.1 數(shù)據(jù)結(jié)構(gòu)的選擇數(shù)組是存儲數(shù)據(jù)的一種典型而又簡單可靠的數(shù)據(jù)結(jié)構(gòu)，數(shù)組在進(jìn)行查找，排序操作是很方便的，而且數(shù)組可以動(dòng)態(tài)分配這一方法又使數(shù)組的靈活性有所提高。數(shù)組一般用在順序存儲中。順序存儲表示是將數(shù)據(jù)元素存放于一個(gè)連續(xù)的存儲空間，利用物理相鄰來表示邏輯關(guān)系，實(shí)現(xiàn)順序存取或(按下標(biāo))直接存取。它的存儲效率高，存取速度快。但它的空間大小如果是靜態(tài)分配的，一經(jīng)定義，在整個(gè)程序運(yùn)行期間不會發(fā)生變化，因此，它不易擴(kuò)充。同時(shí)，由于在插入或刪除時(shí)，為保持原有順序，平均需要移動(dòng)一半(或近一半)元素，修改效率不高。 鏈?zhǔn)酱鎯?5表示的存儲空間一般在程序運(yùn)行過程中動(dòng)態(tài)分配和釋放，且只要存儲器中還有空間，就不會產(chǎn)生溢出的問題。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素的原有物理順序，只需要保持原有的邏輯順序就行了，故不必移動(dòng)元素，只需修改它們的鏈接指針，修改效率高。但在存取表中的數(shù)據(jù)元素時(shí)，只能循鏈順序進(jìn)行訪問，且需要額外的指針，存儲效率和訪問效率低于順序存儲表示。而本次設(shè)計(jì)主要的數(shù)據(jù)處理都是順序存儲的，而且關(guān)聯(lián)到很多的順序?qū)?yīng)運(yùn)算，用數(shù)組進(jìn)行數(shù)據(jù)存儲是最優(yōu)的選擇?，F(xiàn)給出本次設(shè)計(jì)中數(shù)據(jù)初始化中相關(guān)數(shù)組的定義，程序代碼描述如下：幾個(gè)全局靜態(tài)數(shù)組的定義：Define int URl-IP20002000: K均值初始化矩陣define float HamU-I20002000: Hamming初始化矩陣extern CString url2000: URL地址存儲字符串?dāng)?shù)組4.1.2 兩種算法的矩陣數(shù)據(jù)初始化4.1.2.1 K均值算法矩陣數(shù)據(jù)初始化根據(jù)K值聚類的算法描述，我們知道K均值聚類算法中的影響因子有數(shù)據(jù)量大小，也就是URL地址數(shù)目和用戶IP數(shù)目的大小和同一IP訪問同一URL的次數(shù)，也就是訪問頻率兩個(gè)方面。其數(shù)據(jù)矩陣初始化的編程代碼表示如圖4-1：圖4-1 K均值數(shù)據(jù)矩陣初始化代碼4.1.2.2 Hamming聚類算法矩陣數(shù)據(jù)初始化和K均值算法不一樣，Hamming算法所進(jìn)么分類的標(biāo)準(zhǔn)主要是此URL是否被某IP訪問，有被訪問則置1，否則置0. 其數(shù)據(jù)矩陣初始化的編程代碼表示如圖4-2：圖4-2 Hamming數(shù)據(jù)矩陣初始化代碼4.1.2.3 URL地址字符串?dāng)?shù)組數(shù)據(jù)初始化由于聚類的結(jié)果是要將分類后的URL顯示給用戶，然而我們知道URL數(shù)目很多，很難一起顯示給用戶，或者說會使用戶無法清晰地分析聚類的結(jié)果，所以我們先在LIST中顯示出分類后的URL代號，再顯示出對應(yīng)的具體的URL地址，因而我們需要對URL地址與其對應(yīng)的編號以字符串?dāng)?shù)組的形式進(jìn)行存儲，以便要顯示具體URL地址時(shí)查找，調(diào)用和顯示。其數(shù)據(jù)矩陣初始化的編程代碼表示如圖4-3：圖4-3 url存儲數(shù)組初始化代碼4.2 K均值算法的實(shí)現(xiàn)4.2.1 分配一個(gè)URL向量到每個(gè)類中作為初始化類的平均URL向量按照K均值算法的描述，我們要事人為指定分類的個(gè)數(shù)K，并隨機(jī)地抽取其中的K個(gè)向量做為每一類的平均向量，因?yàn)榈谝淮畏峙浜竺總€(gè)分類中只有一個(gè)向量，所以這K個(gè)向量便為K個(gè)類的平均向量。在本次設(shè)計(jì)中并沒有真正隨機(jī)分配，而是將第1,N,2N,n個(gè)分別作為第一次初始化的各類的平均向量。在系統(tǒng)中的程序編碼實(shí)現(xiàn)如圖4-4：圖4-4 K均值初始化的各類的中心向量代碼以上代碼段中，變量kjm代表要進(jìn)行分類的URL個(gè)數(shù)，定義兩個(gè)m_knum維的字符串?dāng)?shù)組*kstr,*kstr1，是由于在后面的分類過程中需要循環(huán)地將kim個(gè)URL行向量分配到m_knum個(gè)類中，在這個(gè)基礎(chǔ)上要再次計(jì)算分配后的每個(gè)類的向量的平均值，就需要知道分配到每個(gè)類的的URL行向量是哪幾個(gè)，其中*kstr1記錄的是變化后的各類中URL行向量的序號，而*kstr記錄的是變化前各類中的URL行向量的序號。同時(shí)這兩個(gè)數(shù)組也是后面判斷循環(huán)結(jié)束的條件因子之一。4.2.2 循環(huán)迭代分類過程給定每一分類的初始URL行向量后，我們就可以將kjm個(gè)URL行向量進(jìn)行篩選分配到每個(gè)類中，并且計(jì)算每個(gè)新類的平均URL行向量，記下分類的情況，之而要進(jìn)行新類與舊類的對比，若分類有更新說明聚類過程仍未結(jié)束，則繼續(xù)循環(huán)迭代進(jìn)行分類，直到分類結(jié)束。其中編程代碼如圖4-5所示：圖4-5 K均值循環(huán)分類過程代碼上面的程序段中包含兩段代碼用一句話帶過，具體的實(shí)現(xiàn)方式在下列進(jìn)行說明：進(jìn)行一次遍歷，將URL分配到各個(gè)相應(yīng)的類中的代碼段如圖4-6所示：圖4-6 URL分配到各個(gè)相應(yīng)的類中的代碼計(jì)算平均值向量的過程，從前面定義的字符串?dāng)?shù)組*str中取出對應(yīng)的第j類中包含的URL行向量對應(yīng)的行號，將其取出，將j類中包含的所有URL行向量的對應(yīng)元素值相加再除以URL的個(gè)數(shù)算出分配后類j的平均向量的每個(gè)元素值，從而得出分配后每個(gè)類的平均向量，為下一次分配作準(zhǔn)備，其編程代碼實(shí)現(xiàn)如圖4-7：圖4-7 計(jì)算分配后各類的平均向量4.2.3 聚類結(jié)果顯示最后完成聚類，并進(jìn)行結(jié)果顯示，顯示的結(jié)果如圖4-8所示，因?yàn)檐浖谏巷@示窗口無法將分類全部顯示出來，只好進(jìn)行再次顯示，雙擊每一條分類，則進(jìn)行完全顯示，在二次結(jié)果顯示的窗口中單擊“詳細(xì)URL地址列表”則進(jìn)行對應(yīng)的詳細(xì)的URL地址顯示，其運(yùn)行結(jié)果及界面如圖4-8所示：圖4-8 K均值運(yùn)行結(jié)果顯示窗口我們看到第三行中分類后含的URL個(gè)數(shù)沒能完全顯示出來，雙擊此行則出現(xiàn)二次顯示窗口，如圖4-9：圖4-9 K均值二次顯示窗口在二次查看窗口中，我們?nèi)允侵荒芸捶诸惡?，每個(gè)類中包含的URL的對應(yīng)編號，而未能查看具體的URL地址，單擊“詳細(xì)URL列表”，則進(jìn)行URL編號和地址的詳細(xì)顯示，如圖4-10：圖4-10 K均值具體url顯示窗口4.3 Hamming聚類算法實(shí)現(xiàn)4.3.1 Hamming算法描述如前所述，URL-IP矩陣M的行向量M.,j反映了客戶對本站點(diǎn)的不同頁面的訪問情況，如果客戶對某些頁面的訪問情況相同或相似，那么，這些頁面理應(yīng)為相關(guān)頁面，可以聚為一類。聚類時(shí)，同樣先對URL-IP關(guān)聯(lián)矩陣 M進(jìn)行預(yù)處理，去掉所含元素值都為0的行向量，在本次設(shè)計(jì)中無考慮此情況，因?yàn)槿绻邢蛄恐禐?，則說明沒有任何用戶訪問此網(wǎng)頁，那就不在我們的考慮之內(nèi)，我們所研究的是用戶所訪問的網(wǎng)頁的聚類。對于Mi,j>0,可先令Mi,j=1，再根據(jù)hamming距離公式計(jì)算并構(gòu)造出行向量間的距離矩陣。在此矩陣中，表示第i個(gè)行向量和第j個(gè)行向量之間的Hamming距離，對角元素值為0.接下來根據(jù)閾值公式求URL-URL關(guān)聯(lián)矩陣的閾值：對于，如果<,那么就將第i個(gè)URL和所有滿足這個(gè)條件的第j個(gè)URL劃分為一個(gè)類。4.3.2 構(gòu)造行向量間的距離矩陣由于本次設(shè)計(jì)不考慮URL行向量值為0的情況，所以可以根據(jù)HamU_I矩陣通過Hamming距離公式直接構(gòu)造出URL行向量間的距離矩陣，其編程實(shí)現(xiàn)過程如圖4-11所示：圖4-11 構(gòu)造URL-URL關(guān)聯(lián)矩陣代碼4.3.3 求URL行向量間距離矩陣的閾值從已經(jīng)構(gòu)造好的行向量間距離矩陣中，根據(jù)閾值的計(jì)算公式，我們可以算出URL行向量矩陣的閾值，閾值是整個(gè)聚類過程的唯一，重要的參考指標(biāo)，所以說閾值取值情況將決定Hamming聚類的結(jié)果的精確與否。所以在閾值的求解上，我們將公式可調(diào)化，也就是說閾值的求值公式中的某些參數(shù)的值可以由用戶來進(jìn)行調(diào)整，使聚類的結(jié)果滿足用戶的最終需求，其編程中的實(shí)現(xiàn)過程如圖4-12所示：圖4-12 Hamming閾值求解代碼4.3.4 Hamming聚類算法核心代碼段由于Hamming算法是一個(gè)需要對分類中的每個(gè)值進(jìn)行對應(yīng)向量代號進(jìn)行循環(huán)再分類，其工作時(shí)間復(fù)雜度較高，因此，本次設(shè)計(jì)從i=0著手分出第一類，然后作一次數(shù)據(jù)優(yōu)化，去掉被其包含的子類。由于i=0對應(yīng)的行向量kcl0j所包含的元素個(gè)素是最多的，有hjm-1個(gè)，如果元素值kcl0j為1的數(shù)目多，則分出的第一類元素個(gè)數(shù)就比較多，可能包含的子類就更多，進(jìn)行的數(shù)據(jù)優(yōu)化的效果就越好。下面是求出第一類的代碼分析，如圖4-13所示：圖4-13 求出第一類的代碼求出第一個(gè)類后，我們對數(shù)據(jù)矩陣進(jìn)行優(yōu)化，我們把存在不屬于第一個(gè)類的行向量i作記號kclii=1，而行向量j上所含元素都在第一類中已存在的，我們說它完全包含于第一類，我們也作標(biāo)記kcljji=0;經(jīng)過數(shù)據(jù)優(yōu)化后，我們只對kclii值為1的行向量進(jìn)行分類，同時(shí)當(dāng)分出第二類時(shí)我們也作同樣的數(shù)據(jù)優(yōu)化，再次排除掉無效的行直到分類結(jié)束。下面是編程代碼的解析，如圖4-14所示：圖4-14 分出第一類后的數(shù)據(jù)優(yōu)化代碼中間分類及分類后的數(shù)據(jù)優(yōu)化代碼這里省略，原理和第一個(gè)類的分類過程是一樣的。4.3.5 Hamming聚類的結(jié)果顯示結(jié)果顯示與K均值的顯示界面及功能都基本相同，這里不再闡訴設(shè)計(jì)思想。顯示如圖4-15，圖4-16，圖4-17所示：圖4-15 Hamming聚類窗口圖4-16 Hamming聚類結(jié)果顯示窗口圖4-17 Hamming聚類二次顯示窗口4.4聚類結(jié)果分析4.4.1 聚類的精確度分析根據(jù)實(shí)現(xiàn)的結(jié)果，本次設(shè)計(jì)將用戶訪問的URL地址分為以下9個(gè)大類：（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)，自定義一個(gè)衡量聚類精確度的方法：設(shè)聚類的結(jié)果分為n類，去掉只含一個(gè)元素的類，誤分率大于50%的類和含大量元素的類（因?yàn)槿绻缓粋€(gè)元素也就沒有正確與否之說，更不用談什么精確度了，如果誤分率大于50%，則我們不會去利用這樣的分類結(jié)果，而含有大量元素的類，我們說這種類在本設(shè)計(jì)的兩種算法中都會出現(xiàn)，是不可避免的，特別是在數(shù)據(jù)量巨大時(shí)，由于這樣的類含的元素太多，肯定會包含以上所說的多種URL地址，這樣的情況下，我們也無法去解析它的精確度），剩下的分類數(shù)為N，我們把分析的對象定為含有一定數(shù)量元素的這樣一些類。設(shè)類i中共有y個(gè)URL，其中有x個(gè)URL與類中其它大部分元素是不同的，我們說這x個(gè)URL被錯(cuò)分到類i中，這樣我們定義一個(gè)精確度值=1-x/y,=x/y，而總的分類精確度下面我們進(jìn)行兩種聚類算法的精確度分析：1.Hamming聚類精確度計(jì)算：根據(jù)聚類結(jié)果顯示：當(dāng)輸入數(shù)據(jù)為“Ip_Url.txt”時(shí)，結(jié)果總共分為46類，其中去掉大量元素類7個(gè)，剩下可分析類39個(gè),下面列出各類的精確度（未寫出的都是全部正確的）：w=1/11;w=1/11;w=1/6;w=2/18;w=1/3;w=1/10;w=1/34;w=3/39;計(jì)算得出R97.4%2.K均值聚類精確度計(jì)算：根據(jù)聚類結(jié)果顯示：當(dāng)輸入數(shù)據(jù)為“Ip_Url.txt”時(shí)，與Hamming分類數(shù)一樣設(shè)為46類，其中去掉大量元素類和單元素類17個(gè)，剩下可分析類29個(gè),下面列出各類的精確度（未寫出的都是全部正確的）：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;計(jì)算得出R91.8%為了使比較更為直觀，我們將兩個(gè)算法精度曲線描繪出來，如下圖4-18分類精確度曲線所示： 圖4-18 Kmeans與Hamming聚類確精度對比曲線其中縱坐標(biāo)為每一分類中的分類精確度，最高為1，最小為0.5。前面定義精確度的時(shí)候說過，如果分類精確度小于0.5，也就是誤分率大于50%，那么這一分類我們認(rèn)為是不理想的，不會采納，所以排除在分析對象之外。橫坐標(biāo)為上面所對應(yīng)的可分析分類的類號，相互比較，我們清楚地看到在本設(shè)計(jì)相同的輸入中，當(dāng)分類的個(gè)數(shù)一樣時(shí)，Hamming聚類的精確度比K均值聚類的精確度要高，同時(shí)，我們也看到二者的精確度都在90%以上，這說明兩種聚類的算法都是有效的，都能夠較好地將具有相同或相似的URL聚在同一類。4.4.2 Hamming閾值對聚類結(jié)果的影響 前面我們提到Hamming閾值是分類過程中唯一也是最重要的衡量指標(biāo)，那么閾值的變化對整個(gè)聚類的結(jié)果會有什么樣的影響呢？下面跟據(jù)實(shí)驗(yàn)數(shù)據(jù)的對比和分析，我們將指出Hamming閾值的變化對聚類結(jié)果的具體影響。我們分3種情況，第一種為閾值與公式計(jì)算所得一樣不發(fā)生改變和調(diào)整;第二種為通過系統(tǒng)提供的閾值調(diào)整功能讓閾值變小;第三各為通過系統(tǒng)提供的閾值調(diào)整功能讓閾值變大. 下面比較三種情況下聚類的情況：閾值不變：此時(shí)分類數(shù)目為46，閾值為2.07301，閾值參數(shù)未作調(diào)整，如圖4-19所示：圖4-19 閾值不變時(shí)的Hamming聚類結(jié)果此時(shí)分析聚類的結(jié)果，去掉大量元素類7個(gè)，剩下可分析類39個(gè),下面給出可分析類的精確度曲線，如圖4-20所示：圖4-20 閾值不變時(shí)Hamming聚類精確度曲線2.閾值變大：通過對閾值參數(shù)N作調(diào)整使閾值變大，調(diào)整參數(shù)N為1.5，閾值為3.10952，分類數(shù)目43如圖-21所示：圖4-21 閾值變大后Hamming聚類的結(jié)果此時(shí)分析聚類的結(jié)果，去掉大量元素類7個(gè)，誤分率超過50%的少量元素類3個(gè)，剩下可分析類33個(gè),下面給出可分析類的精確度曲線，如圖4-22所示： 圖4-22 閾值變大后Hamming聚類的精確度曲線3.閾值變?。和ㄟ^調(diào)整閾值參數(shù)N使閾值變小，調(diào)整參數(shù)N為0.85，閾值為1.76206，分類的數(shù)目為85，如圖4-23所示：圖4-23 閾值變小后的Hamming聚類結(jié)果此時(shí)分析聚類的結(jié)果，去掉誤分率大于50%的少量元素類3個(gè)，大量元素類30個(gè)，剩下可分析類52個(gè)，下面給出可分析類的精確度曲線，如圖4-24所示： 圖4-24 閾值變小后Hamming聚類的精確度曲線通過對三種情況的分類精確度的分析，我們看到，當(dāng)閾值變大時(shí)，分類的數(shù)目減少了，這說明分類變得比較粗糙，因此有可能造成分類精確度較低。通過精確度曲線圖也證實(shí)了精確度比較差;而如果調(diào)小閾值，我們發(fā)現(xiàn)分類的數(shù)目變大，且幅度比較高，但是同時(shí)產(chǎn)生的大量元素類的數(shù)目也有較大的提高，這說明分類雖然多了，詳細(xì)了，但也使非利用類的數(shù)目變大（這是非利用類指的是大量元素類），可分析類的數(shù)目也有提高，而且從精確度曲線圖上，我們可以看出大部分分類的精確度都在90%以上，整條曲線比較平穩(wěn)，精確度較高，可以達(dá)到較為理想的聚類效果。下面我們用一個(gè)表較為直觀地顯示三者的對比結(jié)果，如表4-25所示：表4-1 閾值的變化對分類精確度的影響情況閾值變化總分類數(shù)變化可析類數(shù)變化大量元素類數(shù)誤分率高類數(shù)分類精確度變小85變大52變大30變大3較好不變463970一般變大433373較差4.4.3 分類數(shù)目變化對K均值聚類結(jié)果的影響由于K均值聚類是根據(jù)我們自定義的數(shù)目來進(jìn)行分類的，但是因?yàn)槲覀冸S機(jī)分配給每個(gè)類的初始量不一定就是不現(xiàn)于其它類的量，有可能在第一次分配時(shí)就使這一類為空，這樣就使分類無法正常進(jìn)行，于是在本設(shè)計(jì)中，如果某次分配后發(fā)現(xiàn)有空的類，則會把初始分量再次賦給它，等待下次的分配，其編程代碼在上文有說明，參看圖4-5。那么下面我們將根據(jù)實(shí)驗(yàn)得出的數(shù)據(jù)對分類數(shù)目進(jìn)行三種變化，從而分析分類數(shù)目變化對K均值聚類結(jié)果的影響。為了能和Hamming聚類結(jié)果進(jìn)行比較，K均值分類的數(shù)目將和上面Hamming聚類三種情況下分類的數(shù)目取相同的數(shù)據(jù)。分類數(shù)目不變：分類數(shù)目為46，如圖4-25所示：圖4-25 分類數(shù)目不變時(shí)的K均值聚類結(jié)果下面我們對分類的精確度進(jìn)行分析，去掉大量元素類1，單元素類13，誤分率較大類3，剩下可分析類29，其精確度曲線如圖4-26所示：圖4-26 分類數(shù)目不變時(shí)的K均值聚類精確度曲線分類數(shù)目變大：分類數(shù)目為85，如圖4-27所示：圖4-27 分類數(shù)目變大時(shí)的K均值聚類結(jié)果下面我們對分類的精確度進(jìn)行分析，去掉大量元素類1，單元素類32，誤分率較大類4，剩下可分析類43，其精確度曲線如圖4-28所示：圖4-28 分類數(shù)目變大時(shí)的K均值聚類精確度曲線3.分類數(shù)目變?。悍诸悢?shù)為43，如圖4-29所示：圖4-29 分類數(shù)目變小時(shí)的K均值聚類結(jié)果下面我們對分類的精確度進(jìn)行分析，去掉大量元素類1，單元素類14，誤分率較大類6，剩下可分析類22，其精確度曲線如圖4-30所示：圖4-30 分類數(shù)目變小時(shí)的K均值聚類精確度曲線通過三種情況的對比分析，我們可以看到，當(dāng)分類數(shù)目變大時(shí)單元素類大量增加，但是分類的精確度確是有所提高，分類精確度曲線出現(xiàn)的都較陡的坡度，這說明很少有連續(xù)的誤分類，只有個(gè)別誤分類穿插出現(xiàn);而當(dāng)分類數(shù)目變小時(shí)，精確度并不是有很大的變化，但是從坡度上我們可以看出坡度都較緩，這說明會有大量的連續(xù)的誤分類，所以其實(shí)上當(dāng)分類數(shù)變小時(shí)精確度有所下降。下面用表格較為直觀地進(jìn)行說明，如表4-2所示：表4-2 分類數(shù)目的變化對分類精確度的影響分類數(shù)目變化單元素類數(shù)大量元素類數(shù)可分析類數(shù)誤分率高類數(shù)分類精確度43變小14無明顯變化1無變化22減小6增大降代46不變131293一般85變大32大量增多1無變化43增多4變化不大增高4.4.4 兩種聚類方法的對比總結(jié)通過以上對兩種聚類方法的結(jié)果進(jìn)行詳細(xì)的對比和分析，我們看到，在相同分類數(shù)的情況下，Hamming聚類的精確度要比K均值的分類精確度高。但是兩種聚類的算法，在相應(yīng)的參數(shù)選擇好的情況下，如Hamming閾值的調(diào)整，和K均值的分類數(shù)目，如果參數(shù)選得好都可以達(dá)到較為滿意的聚類結(jié)果。此次通過兩種算法K均值算法和Hamming算法分別來對網(wǎng)頁進(jìn)行分類，其中Hamming算法的設(shè)計(jì)是參照宋擒豹 沈鈞毅關(guān)于Web日志高效多能挖掘算法中的Hamming聚類算法12.在本次實(shí)驗(yàn)中，對于原作者對Hamming閾值的計(jì)算公式進(jìn)行了調(diào)整。在實(shí)驗(yàn)過程中，根據(jù)實(shí)驗(yàn)的數(shù)據(jù)，若根據(jù)原來的Hamming閾值計(jì)算公式求閾值，會導(dǎo)致最后的分類數(shù)目極少，甚至只有一類。因此，在本次實(shí)驗(yàn)中，原作者所提的閾值公式12在本次設(shè)計(jì)中并不合適，在調(diào)適運(yùn)行過程中，本次設(shè)計(jì)對其公式進(jìn)行改進(jìn)最后使分類能夠順利進(jìn)行，而且效果也比較理想。此次驗(yàn)證性實(shí)驗(yàn)證時(shí)，Hamming算法中的閾值是要根據(jù)不同情況下的輸入進(jìn)行相應(yīng)的調(diào)節(jié)，才能使分類更加精準(zhǔn)有效，同時(shí)本次設(shè)計(jì)及實(shí)驗(yàn)結(jié)果也說明了兩種算法都是有效的聚類算法，都可以較理想地進(jìn)行聚類分析。致謝在這次畢業(yè)設(shè)計(jì)過程中，首先感謝白清源教授在算法上的詳細(xì)解釋，在算法資料上的提供，在論文格式及要求上的檢查和改正。感謝林鑫顯在系統(tǒng)實(shí)現(xiàn)過程的幫助,感謝身邊同學(xué)在設(shè)計(jì)過程中的鼓勵(lì)與幫助。參考文獻(xiàn)1 高新波.模糊聚類分析及其應(yīng)用.西安：西安電子科技大學(xué)出版社.2004：23-45.2 李恒峰，李國輝.基于內(nèi)容的音頻檢索與分類.計(jì)算機(jī)工程與應(yīng)用.2000.7.3（加）韓家煒，堪博 著，范明，孟小峰 譯.數(shù)據(jù)挖掘概念與技術(shù).北京：機(jī)械工業(yè)出版社.2007：18-90.4劉書香，盧才武.數(shù)據(jù)挖掘中的客戶聚類分析及其算法實(shí)現(xiàn).信息技術(shù).2004年1月，第28卷第1期，PP.4-10.5 尹松，周永叔，李陶深.數(shù)據(jù)聚