天津大學(xué)碩士學(xué)位論文基于粒子群的聚類算法改進(jìn)及其在訪問(wèn)模式中的應(yīng)用研究姓名：陳君彥申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：信息管理與信息系統(tǒng)指導(dǎo)教師：張慧穎20070101 ,中文摘要從大

天津大學(xué)

碩士學(xué)位論文

基于粒子群的聚類算法改進(jìn)及其在訪問(wèn)模式中的應(yīng)用研究

姓名：陳君彥

申請(qǐng)學(xué)位級(jí)別：碩士

專業(yè)：信息管理與信息系統(tǒng)

指導(dǎo)教師：張慧穎

20070101

中文摘要

從大量顧客日志數(shù)據(jù)中挖掘有意義的用戶訪問(wèn)模式及相關(guān)的潛在顧客群，是目前數(shù)據(jù)挖掘技術(shù)在Ｉｎｔｅｒｎｅｔ上的重要應(yīng)用之一，挖掘用戶訪問(wèn)網(wǎng)站的模式，可以使網(wǎng)站建設(shè)者清楚地了解自己網(wǎng)站不同用戶的興趣和整個(gè)網(wǎng)站頁(yè)面的訪問(wèn)情況，并可進(jìn)一步優(yōu)化網(wǎng)站的組織結(jié)構(gòu)或建立自適應(yīng)網(wǎng)站，從而從中發(fā)現(xiàn)商機(jī)并方便不同用戶的訪問(wèn)。由于現(xiàn)實(shí)需求的急迫，越來(lái)越多的研究者將目光對(duì)準(zhǔn)了這個(gè)領(lǐng)域，使得Ｗｅｂ訪問(wèn)模式挖掘技術(shù)得到很快的發(fā)展，本論文正是在這樣的背景下對(duì)用戶訪問(wèn)模式聚類算法進(jìn)行了研究。

本文通過(guò)分析Ｗｅｂ數(shù)據(jù)特點(diǎn)及現(xiàn)有聚類算法，得出用戶訪問(wèn)模式聚類的特點(diǎn)，提出將粒子群優(yōu)化算法與Ｋ－均值相結(jié)合應(yīng)用于Ｗｅｂ訪問(wèn)模式聚類的可能。

通過(guò)分析Ｋ－均值算法與粒子群優(yōu)化算法（ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ），對(duì)現(xiàn)有的幾種基于粒子群的Ｋ．均值聚類算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，并根據(jù)粒子群算法在數(shù)據(jù)分析應(yīng)用中的不足，提出了一種基于隨機(jī)搜索方向的Ｋ．均值與粒子群算法結(jié)合的聚類算法ＲＶＰＳＯ－Ｋ，它能夠通過(guò)改變粒子軌跡提高粒子本身的搜索能力，從而可能盡快地找到全局最優(yōu)解。經(jīng)Ｉｒｉｓ、Ｚｏｏ、Ｗｉｎｅ數(shù)據(jù)集對(duì)Ｋ．均值算法、粒子群算法及相關(guān)的４種改進(jìn)算法進(jìn)行測(cè)試，結(jié)果表明，ＲＶＰＳＯ－Ｋ算法聚類能力較強(qiáng)，收斂性較好。

ＲＶＰＳＯ。Ｋ算法應(yīng)用于用戶訪問(wèn)模式時(shí)，本文詳細(xì)地分析了預(yù)處理階段的各項(xiàng)任務(wù)，構(gòu)造了本文算法所適用的ＵｓｅｒｌＤ—ＵＲＬ關(guān)聯(lián)矩陣，對(duì)聚類中心代表含義進(jìn)行了說(shuō)明，提出設(shè)定不同的閾值的概念來(lái)解決用戶后續(xù)推薦問(wèn)題，從而提高調(diào)控推薦網(wǎng)頁(yè)的數(shù)量的靈活性，滿足不同的推薦需求。實(shí)驗(yàn)結(jié)果表明，在大量及高維度的用戶數(shù)據(jù)情況下，與其他改進(jìn)算法對(duì)比，ＲＶＰＳＯ－Ｋ算法具有較強(qiáng)的搜索能力和較好穩(wěn)定性，且精度較好，速度有明顯提升。關(guān)鍵詞：粒子群算法Ｋ．均值聚類分析Ｗｅｂ訪問(wèn)模式

ＡＢＳＴＲＡＣＴ

ＩｔｉｓｏｎｅｏｆｔｈｅｍｏｓｔｉｍｐｏｒｔａｎｔａｐｐｌｉｃａｔｉｏｎｓｉｎｐｒｅｓｅｎｔｄａｔａｍｉｎｉｎｇｔｏｈａｖｅｔｈｅａｂｉｌｉｔｙｔｏｄｉｓｃｏｖｅｒｕｓｅｆｕｌＷｅｂＵｓａｇｅＰａｔｔｅｒｎｓａｎｄｐｏｔｅｎｔｉａｌｃｕｓｔｏｍｅｒｓｆｒｏｍｌａｒｇｅｖｏｌｕｍｅｓｏｆｕｓｅｒａｃｃｅｓｓｌｏｇｓ．ＴｈｅＷｅｂＵｓａｇｅＭｉｎｉｎｇ

ｕｓｅｒｓｃａｎｍａｋｅｔｈｅｗｅｂｓｉｔｅ’Ｓｃｒｅａｔｏｒｓａｃｃｅｓｓｕｎｄｅｒｓｔａｎｄｔｈｅｄｉｆｆｅｒｅｎｔｉｎｔｅｒｅｓｔｓｏｆｔｈｅｉｒ

ｗｅｂｓｉｔｅ．Ｔｈｅｙｃａｎａｎｄｔｈｅｏｖｅｒａｌｌｓｉｔｕａｔｉｏｎｏｆｔｈｅｉｒｏｒａｌｓｏｏｒｇａｎｉｚｅｔｈｅｌｏｇｉｃｓｔｒｕｃｔｕｒｅｏｆｔｈｅｗｅｂｐａｇｅ

ｏｕｔｓｅｔｕｐａｓｅｌｆ－ａｄａｐｔｉｖｅＷｅｂｓｉｔｅ，ｔｈｕｓｄｉｇｇｉｎｇ

ｕｓｅｒ．Ｂｅｃａｕｓｅｔｈｅｒｅｉｓａｂｕｓｉｎｅｓｓｏｐｐｏｒｔｕｎｉｔｉｅｓａｎｄｆａｃｉｌｉｔａｔｉｎｇｅａｃｈａｒｅａｎ

ａｎｈｉｇｈｄｅｍａｎｄｆｏｒＷｅｂｕｓａｇｅｍｉｎｉｎｇ，ｔｈｅｒｅｉｍｃｒｅａｓｉｎｇｅｘｐｏｎｅｎｔｉａｌ

ｏｎｎｕｍｂｅｒｏｆｒｅｓｅａｒｃｈｅｒｓ．ＴｈｅｒｅｆｏｒｅＷｅｂＵｓａｇｅＭｉｎｉｎｇｉｓｄｅｖｅｌｏｐｉｎｇａｔｒａｔｅ．ＴｈｉｓｄｉｓｓｅｒｔａｔｉｏｎｍａｉｎｌｙｓｔｕｄｉｅｓｔｈｅｃｌｕｓｔｅｒｉｎｇｏｆＷｅｂＵｓａｇｅＰａｔｔｅｒｎｓ

ｓｉｔｕａｔｉｏｎｓ．ｔｈｅｓｅ

Ｔｈｅ

ｃｈａｒａｃｔｅｒｃｈａｒａｃｔｅｒｏｆｔｈｅｃｌｕｓｔｅｒｉｎｇｏｆＷｅｂＵｓａｇｅＰａｔｔｅｒｎＷａＳｇｉｖｅｎｂｙＷｅｂｄａｔａａｎｄｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓ．Ｔｈｅｎ，ｔｈｅｃｏｍｂｉｎａｔｉｏｎ

ｏｎｏｆＰａｒｔｉｃｌｅＳｗａｒｍＩｎｔｅｌｌｉｇｅｎｃｅ（ＰＳＯ）ａｎｄＫ－ｍｅａｎｓｉｓｐｒｏｐｏｓｅｄｔｏｂｅａｐｐｌｉｅｄｔｈｅＷｅｂＵｓａｇｅＭｉｎｉｎｇ．

ＴｈｅｅｆｆｅｃｔｉｖｅｍｅｔｈｏｄｗａｓｅｘｔｒａｃｔｅｄｂｙｅｘｐｅｒｉｍｅｎｔｓｔｏｔｅｓｔｓｏｍｅｋｉｎｄｓｏｆｅｘｉｓｔｉｎｇａｍｅｌｉｏｒａｔｉｏｎｏｆＫ—ｍｅａＢｓｂａｓｅｄ

ｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄ，ＲＶＰＳＯ—ＫｏｎＰＳＯｂｙａｎａｌｙｓｉｎｇＫ－ｍｅａｎｓａｎｄＰＳＯ．ＡｎｅｗｅｘｐａｔｉａｔｅｄｂａｓｅｄｏｎＷａＳｔｈｅｒａｎｄｏｍｒｅｓｅａｒｃｈｃｏｍｂｉｎｉｎｇＫ—ｍｅａｎｓａｎｄＰＳＯａｃｃｏｒｄｉｎｇｔｈｅｉｎｓｕｆｆｉｃｉｅｎｃｙｏｆＰＳＯｉｎｔｈｅｄａｔａａｎａｌｙｓｉｓ．Ｔｈｅｓｅａｒｃｈｉｎｇａｂｉｌｉｔｙｏｆｔｈｅｉｎｄｉｖｉｄｕａｌｐａｒｔｉｃｌｅｗａｓｅｎｈａｎｃｅｄｂｙｃｈａｎｇｅｔｈｅｆｌｙｉｎｇｔｒａｊｅｃｔｏｒｙｏｆｔｈｅｐａｒｔｉｃｌｅ，ｔｈｕｓｔｈｅｏｐｔｉｍｕｍｗｏｕｌｄｂｅｆｏｕｎｄｉｎ

ｏｎａｒｅｌａｔｉｖｅｌｙｓｈｏｒｔａｍｏｕｎｔｏｆｔｉｍｅ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓｗｅｒｇｃｏｎｄｕｃｔｅｄ

ｗｈｉｃｈｓｈｏｗｓｔｈａｔｔｈｅＲＶＰＳＯ—ＫｉｓａＩｒｉｓ，ＷｉｎｅａｎｄＧｌａｓｓｄａｔａｓｅｔｓ，ｏｆｂｅｔｔｅｒｃｏｎｖｅｒｇｅｎｃｅａｎｄｂｅｔｔｅｒｃｌｕｓｔｅｒｉｎｇａｂｉｌｉｔｙｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｏｔｈｅｒ４ｒｅｌａｔｅｄｍｅｔｈｏｄｓ．

ＩｎｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆｔｈｅＷｅｂＵｓａｇｅＰａｔｔｅｒｎ，ｔｈｅｍｏｓｔｐｏｐｕｌａｒｍｅｔｈｏｄｏｆｄａｔａｐｒｅｐｒｏｃｅｓｓｉｎｇｗｅｒｅｃａｒｒｉｅｄｏｕｔａｎｄ

ＴｈｅｍｅａｎｉｎｇｏｆｔｈｅｃｌｕｓｔｅｒｉｎｇａＵｓｅｒｌＤ－ＵＲＬｒｅｌｅｖａｎｔｍａｔｒｉｘｗａｓｃｏｎｓｔｒｕｃｔｅｄ．ｗａｓｅｘｐｌａｉｎｅｄｃｅｎｔｅｒａｎｄａｄｉｆｆｅｒｅｎｔｔｈｒｅｓｈｏｌｄｗａｓｐｒｏｐｏｓｅｄｔｏｂｅｉｍｐｌｅｍｅｎｔｅｄ，ｔｈｅｒｅｆｏｒｅｔｈｅａｇｉｌｉｔｙｏｆｔｈｅｒｅｃｏｍｍｅｎｄｅｄｗｅｂｗａｓｉｍｐｒｏｖｅｄｔＯｓａｔｉｓｆｙｄｉｓｔｉｎｃｔｒｅｑｕｉｒｅｍｅｎｔｓ．ＴｈｅｅｘｐｅｒｉｍｅｎｔｓａｒｅｉｍｐｌｅｍｅｎｔｅｄｏｎＷｅｂｌｏｇｄａｔａａｆｔｅｒｐｒｅｐｒｏｃｅｓｓｉｎｇ，ｓｈｏｗｉｎｇｔｈａｔｔｈｅＲＶＰＳＯ—Ｋｈａｓｓｔｒｏｎｇｅｒｓｅａｒｃｈｉｎｇａｂｉｌｉｔｙ，ｂｅｔｔｅｒｓｔａｂｉｌｉｔｙａｎｄｈｉｇｈｅｒｐｒｅｃｉｓｉｏｎｃｏｍｐａｒｅｄｗｉｔｈｒｅｌａｔｅｄｍｅｔｈｏｄｓ．

ＫＥＹＷＯＲＤＳ：ＰＳＯ；Ｋ—ｍｅａｎｓ；Ｃｌｕｓｔｅｒｉｎｇ；ＷｅｂＵｓａｇｅＰａｔｔｅｒｎ；

獨(dú)創(chuàng)性聲明

本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作和取得的研究成果，除了文孛特別加以標(biāo)注和致謝之處矯，論文中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果，也不包含為獲得鑫鲞盤鱟或其他教育機(jī)構(gòu)的學(xué)位域證書(shū)焉使照過(guò)的材料。與我一囝工作的露志對(duì)本研究所傲的錳何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示了謝意。

學(xué)位論文作者簽名：髓；忍鳥(niǎo)簽字目期：砷’年ｆ月糾同

學(xué)位論文版權(quán)使用授權(quán)書(shū)

本學(xué)位論文作者完全了解叁鲞蕉堂有關(guān)保留、使用學(xué)位論文的規(guī)定。特授權(quán)叁洼基堂可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，并采用影印、縮印或掃描等復(fù)制手段保存、匯編璦供查閱和借闋。同意學(xué)校向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤。

（保密的學(xué)位論文在解密螽適用本授權(quán)說(shuō)蹋）

學(xué)位論文作者簽名：蘆。另島

簽字同期：磚審年ｆ月凡７日導(dǎo)師簽名：旅棼純簽字日期：私口７年，月ｚｊ日

第一章緒論

第一章緒論

１．１選題背景與研究意義

近年來(lái)，Ｉｎｔｅｍｅｔ的快速普及和迅猛發(fā)展使得各種信息可以以非常低的成本在網(wǎng)絡(luò)上獲得，使得其成為一個(gè)巨大的、分布廣泛的和全球性的信息服務(wù)中心以及人們獲得信息的重要媒介。但隨著網(wǎng)絡(luò)應(yīng)用的不斷深入，各種新型應(yīng)用向計(jì)算機(jī)網(wǎng)絡(luò)提出了新的挑戰(zhàn)。對(duì)于訪問(wèn)者而言，從海量的網(wǎng)絡(luò)信息中尋找有用的知識(shí)，早已成為迫切需求。對(duì)于網(wǎng)站設(shè)計(jì)運(yùn)營(yíng)人員來(lái)說(shuō)，Ｗｅｂ站點(diǎn)的規(guī)模和復(fù)雜程度的增加使得站點(diǎn)設(shè)計(jì)、網(wǎng)絡(luò)運(yùn)行和維護(hù)工作，變得越來(lái)越困難，需要運(yùn)用自動(dòng)輔助設(shè)計(jì)工具為客戶提供快捷、高效的網(wǎng)絡(luò)鏈接。在這樣的市場(chǎng)需求下，出現(xiàn)了基于Ｗｅｂ的個(gè)性化信息服務(wù)。

早期的基于Ｗｅｂ的個(gè)性化信息服務(wù)主要是新聞、股票、目錄推薦等內(nèi)容組成。隨著電子商務(wù)的發(fā)展，個(gè)性化信息服務(wù)應(yīng)用于網(wǎng)上產(chǎn)品推薦和營(yíng)銷，例如Ａｍａｚｏｎ書(shū)店、當(dāng)當(dāng)網(wǎng)站、Ｄｅｌｌ計(jì)算機(jī)公司，都已獲得了巨大成功。其原因就是它們能滿足不同客戶的需求，便捷了與顧客的聯(lián)系方式，創(chuàng)造出前所未有的經(jīng)營(yíng)方式，大大降低了公司的運(yùn)營(yíng)成本。隨著Ｗｅｂ領(lǐng)域技術(shù)的不斷完善和發(fā)展，個(gè)性化信息服務(wù)將滲透到用戶的許多個(gè)人業(yè)務(wù)處理范疇。Ｗｅｂ信息將擴(kuò)展為真正的個(gè)人信息，并幫助用戶理解和管理這些信息，這種新的服務(wù)將成為一種深入到用戶個(gè)體生活工作各個(gè)層面的普及性輔助工具。

目前，這種個(gè)性化服務(wù)主要體現(xiàn)在Ｗｅｂ定制服務(wù)、推薦系統(tǒng)以及自適應(yīng)站點(diǎn)智能服務(wù)上，而解決這方面需求的有力工具就是面向Ｗｅｂ的挖掘技術(shù)。

Ｗｅｂ挖掘是從數(shù)據(jù)挖掘發(fā)展起來(lái)的，是在大量的非結(jié)構(gòu)化、異構(gòu)的Ｗｅｂ信息資源中抽取感興趣的、潛在的模式和隱含信息，也是將數(shù)據(jù)挖掘技術(shù)和理論應(yīng)用于互聯(lián)網(wǎng)資源的一個(gè)新興研究領(lǐng)域，涉及機(jī)器學(xué)習(xí)、模式識(shí)別、人工智能、統(tǒng)計(jì)學(xué)、計(jì)算機(jī)語(yǔ)言學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)、信息學(xué)等多個(gè)領(lǐng)域。Ｗｅｂ所處理的對(duì)象包括靜態(tài)網(wǎng)頁(yè)、Ｗｅｂ數(shù)據(jù)庫(kù)、Ｗｅｂ結(jié)構(gòu)、用戶使用記錄等信息。Ｗｅｂ挖掘當(dāng)前研究主要有三種分類，Ｗｅｂ內(nèi)容挖掘、Ｗｅｂ結(jié)構(gòu)挖掘以及Ｗｅｂ訪問(wèn)模式挖掘（Ｗｅｂ使用挖掘）。

Ｗｅｂ訪問(wèn)模式挖掘是Ｗｅｂ數(shù)據(jù)挖掘的一個(gè)主要分支，也是Ｗｅｂ個(gè)性化的一個(gè)重要組成部分。它旨在將數(shù)據(jù)挖掘技術(shù)應(yīng)用于Ｗｅｂ服務(wù)器日志文件，通過(guò)分

第一章緒論

日志文件，發(fā)現(xiàn)用戶訪問(wèn)特征，頁(yè)面被訪問(wèn)的規(guī)律，設(shè)計(jì)者的領(lǐng)域知識(shí)等，進(jìn)而研究如何使網(wǎng)站結(jié)構(gòu)設(shè)計(jì)更加合理化，如何使網(wǎng)站更加吸引訪問(wèn)者以及如何從中發(fā)掘更多商業(yè)機(jī)會(huì)。大型的Ｗｅｂ站點(diǎn)每天可以有數(shù)以百兆字節(jié)的Ｗｅｂ日志記錄，研究Ｗｅｂ日志數(shù)據(jù)庫(kù)可獲得有關(guān)Ｗｅｂ動(dòng)態(tài)的豐富信息。

在Ｗｅｂ訪問(wèn)模式挖掘中，現(xiàn)階段較為常見(jiàn)的應(yīng)用分析技術(shù)包括：聚類分析、關(guān)聯(lián)規(guī)則、序列模式、分類等。Ｗｅｂ訪問(wèn)模式挖掘中的聚類分析包括頁(yè)面聚類和用戶聚類。用戶聚類是把具有相似瀏覽模式的用戶分成可用于電子商務(wù)應(yīng)用的市場(chǎng)分片和或其它個(gè)性化服務(wù)，然后依據(jù)當(dāng)前用戶所在的用戶組為其進(jìn)行推薦。因此，基于Ｗｅｂ用戶聚類的數(shù)據(jù)挖掘?qū)τ陔娮由虅?wù)中的市場(chǎng)決策和向用戶提供個(gè)性化服務(wù)是非常有幫助的。

另一方面，基于人工智能的群集智能算法是一種新型的模擬進(jìn)化算法和迭代的并行優(yōu)化算法。在解決連續(xù)優(yōu)化問(wèn)題和復(fù)雜的組合優(yōu)化問(wèn)題方面，與傳統(tǒng)啟發(fā)式優(yōu)化算法相比都具有明顯的優(yōu)越性。并且如何將它的優(yōu)點(diǎn)和傳統(tǒng)算法的優(yōu)點(diǎn)相結(jié)合，構(gòu)造出有特色有實(shí)用價(jià)值的混合算法是當(dāng)前算法改進(jìn)的一個(gè)重要方向。

本文將就用戶在Ｗｅｂ訪問(wèn)模式聚類問(wèn)題進(jìn)行研究，尤其對(duì)群智能中的粒子群算法在Ｗｅｂ用戶聚類中的應(yīng)用進(jìn)行研究。

１．２Ｗｅｂ數(shù)據(jù)挖掘研究現(xiàn)狀

Ｗｅｂ數(shù)據(jù)挖掘是從數(shù)據(jù)挖掘發(fā)展過(guò)來(lái)的，與熟知的數(shù)據(jù)挖掘定義類似，我們可將Ｗｅｂ挖掘定義為：從大量的、不完全的、有噪聲的針對(duì)包括Ｗｅｂ頁(yè)面內(nèi)容的、頁(yè)面之間的結(jié)構(gòu)、用戶訪問(wèn)信息、電子商務(wù)信息等在內(nèi)的各種Ｗｅｂ數(shù)據(jù)，提取隱含的、未知的、潛在有用的信息和知識(shí)的過(guò)程。在Ｗｅｂ挖掘中所處理的數(shù)據(jù)可以來(lái)源于服務(wù)器、客戶端或者代理服務(wù)器，也可以來(lái)自其他相關(guān)的數(shù)據(jù)源。Ｗｅｂ所處理的對(duì)象包括靜態(tài)網(wǎng)頁(yè)、Ｗｅｂ數(shù)據(jù)庫(kù)、Ｗｅｂ結(jié)構(gòu)、用戶使用記錄等信息。

１．２．１Ｗｒｅｂ數(shù)據(jù)特點(diǎn)

Ｗｅｂ挖掘與傳統(tǒng)的數(shù)據(jù)挖掘定義相類似，但是還有許多獨(dú)特之處。Ｗｅｂ對(duì)有效的資源和知識(shí)發(fā)現(xiàn)具有極大的挑戰(zhàn)性，Ｗｅｂ挖掘的特性及面臨的問(wèn)題具體表現(xiàn)在：

１．龐大的數(shù)據(jù)

由于Ｗｅｂ為消息在全球范圍發(fā)布和傳播提供了機(jī)會(huì)，它允許任何人在任何地方任何時(shí)間傳播和獲取信息，使得Ｗｅｂ上的信息與日俱增，爆炸性增長(zhǎng)。據(jù)

第一章緒論

２００６年上半年的中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告調(diào)查顯示，網(wǎng)民人數(shù)、上網(wǎng)計(jì)算機(jī)數(shù)分別達(dá)到了１．２３億人、５４５０萬(wàn)臺(tái)，與去年同期相比分別增長(zhǎng)了１９．４％和１９．５％；中國(guó)域名總數(shù)為２，９５０，５００個(gè)，其中ＣＮ下注冊(cè)的域名達(dá)到１，１９０，６１７個(gè)，與去年同期相比，增長(zhǎng)了９１．３％；中國(guó)網(wǎng)站總數(shù)達(dá)到了７８８，４００個(gè)。

２．半結(jié)構(gòu)化數(shù)據(jù)

Ｗｅｂ頁(yè)面的復(fù)雜性遠(yuǎn)比任何傳統(tǒng)的文本文檔復(fù)雜得多。Ｗｅｂ頁(yè)面缺乏同一的結(jié)構(gòu)，Ｗｅｂ上的大量文檔無(wú)法按某一排列次序加以組織，它沒(méi)有分類索引，也沒(méi)有特定的模型描述，每一個(gè)站點(diǎn)的數(shù)據(jù)都各自獨(dú)立設(shè)計(jì)，并且數(shù)據(jù)本身具有自述性和動(dòng)態(tài)可變性。因而，Ｗｅｂ上的數(shù)據(jù)雖具有一定的結(jié)構(gòu)性，但因其自述層次的存在，從而是一種非完全結(jié)構(gòu)化的數(shù)據(jù)，這也被稱之為半結(jié)構(gòu)化數(shù)據(jù)。

３．異構(gòu)性

從數(shù)據(jù)庫(kù)研究的角度出發(fā)．，Ｗｅｂ網(wǎng)站上的信息也可以看作一個(gè)數(shù)據(jù)庫(kù)，一個(gè)更大、更復(fù)雜的數(shù)據(jù)庫(kù)。Ｗｅｂ上的每一個(gè)站點(diǎn)就是?個(gè)數(shù)據(jù)源，每個(gè)數(shù)據(jù)源都是異構(gòu)的，這就構(gòu)成了一個(gè)巨大的異構(gòu)數(shù)據(jù)庫(kù)環(huán)境。

４．動(dòng)態(tài)性

Ｗｅｂ不僅以極快的速度增長(zhǎng)，而且其信息還在不斷地發(fā)生著更新。新聞、公司廣告、股票市場(chǎng)、Ｗｅｂ服務(wù)中心等都在不斷的更新著各自的頁(yè)面。鏈接信息和訪問(wèn)記錄也在頻繁更新之中。

１．２．２Ｗｅｂ數(shù)據(jù)挖掘分類

由于Ｗｅｂ具有這些與傳統(tǒng)數(shù)據(jù)挖掘不同的特點(diǎn)，使得要從這些分散的、異構(gòu)的、沒(méi)有統(tǒng)一管理的海量信息中快速、準(zhǔn)確地獲取信息也成為Ｗｅｂ挖掘所要解決的一個(gè)難點(diǎn)，也使得用于Ｗｅｂ的數(shù)據(jù)挖掘技術(shù)不能照搬用于數(shù)據(jù)庫(kù)的數(shù)據(jù)挖掘技術(shù)。所以，開(kāi)發(fā)新的Ｗｅｂ挖掘技術(shù)這一課題成為目前國(guó)內(nèi)外的研究熱點(diǎn)。目前ｗｅｂ挖掘主要分為三類：Ｗｅｂ內(nèi)容挖掘（ＷｅｂＣｏｎｍｎｔＭｉｎｉｎｇ）、Ｗｅｂ結(jié)構(gòu)挖掘（ＷｅｂＳｔｍｃｔｕｒｅＭｉｎｉｎｇ）和Ｗｅｂ訪問(wèn)模式挖掘（Ｗｅｂ使用挖掘，ＷｅｂＵｓａｇｅＭｉｎｉｎｇ）。

Ｗｅｂ內(nèi)容挖掘主要包括文本挖掘和多媒體挖掘兩類，其對(duì)象包括文本、圖像、音頻、視頻和其他各種類型的數(shù)據(jù)。Ｗｅｂ文本挖掘可以對(duì)Ｗｅｂ上大量文檔集合的內(nèi)容進(jìn)行關(guān)聯(lián)分析、總結(jié)、分類、聚類以及利用Ｗｅｂ文檔進(jìn)行趨勢(shì)預(yù)測(cè)等，是Ｗｅｂ挖掘中比較重要的技術(shù)領(lǐng)域。Ｗｅｂ上多媒體挖掘主要是利用多媒體提取工具進(jìn)行特征提取，然后對(duì)這些特征進(jìn)行關(guān)聯(lián)規(guī)則或者分類的挖掘操作。多媒體數(shù)據(jù)挖掘包括對(duì)圖像、視頻和聲音的挖掘。Ｗｅｂ結(jié)構(gòu)挖掘是挖掘Ｗｅｂ潛在的鏈接結(jié)構(gòu)模式，主要是通過(guò)對(duì)Ｗｅｂ站點(diǎn)的

第一章緒論

結(jié)構(gòu)進(jìn)行分析、變形和歸納，將Ｗｅｂ頁(yè)面進(jìn)行分類，以利于信息的搜索。這種模式可以用于網(wǎng)頁(yè)歸類，薺且可以由此獲得有關(guān)不同網(wǎng)頁(yè)間相似度及關(guān)聯(lián)度的信息。結(jié)構(gòu)挖掘有助于用戶找到相關(guān)主體的權(quán)威站點(diǎn)，并且可以指向眾多權(quán)威站點(diǎn)相關(guān)主題的站點(diǎn)。當(dāng)前的Ｗｅｂ結(jié)構(gòu)挖掘的研究分為兩個(gè)方向【３】：一般的訪問(wèn)模式追蹤，即通過(guò)分析使用記錄來(lái)了解用戶的訪問(wèn)模式和傾向，以改進(jìn)站點(diǎn)的組織結(jié)構(gòu)；個(gè)性化的使用記錄追蹤，即分析單個(gè)用戶的偏好，根據(jù)不同用戶的訪問(wèn)模式為每個(gè)用戶提供定制的站點(diǎn)。

Ｗｅｂ訪問(wèn)模式挖掘是對(duì)用戶訪問(wèn)Ｗｅｂ時(shí)在服務(wù)器上留下的訪問(wèn)數(shù)據(jù)進(jìn)行挖掘，來(lái)發(fā)現(xiàn)用戶訪問(wèn)Ｗｅｂ頁(yè)面的模式。這些數(shù)據(jù)包括：Ｗｅｂ服務(wù)器日志記錄、代理服務(wù)器的日志記錄、客戶端的日志記錄、用戶簡(jiǎn)介、注冊(cè)信息等，因此訪問(wèn)模式挖掘主要是Ｗｅｂ日志的挖掘。Ｗｅｂ日志分為Ｓｅｒｖｅｒ

ＣｏｏｋｉｅＬｏｇｓ，ＥｒｒｏｒＬｏｇｓ和Ｌｏｇｓ，日志記錄了網(wǎng)頁(yè)被使用的信息，如ＩＰ地址、訪問(wèn)時(shí)間、哪一頁(yè)、字節(jié)大小等，因此對(duì)用戶訪問(wèn)Ｗｅｂ站點(diǎn)的存取方式進(jìn)行挖掘可以實(shí)現(xiàn)用戶聚類、頁(yè)面聚類和發(fā)現(xiàn)頻繁訪問(wèn)路徑，可以發(fā)現(xiàn)用戶訪問(wèn)站點(diǎn)的瀏覽模式、頁(yè)面的訪問(wèn)頻率等信息，進(jìn)而可以改善網(wǎng)站設(shè)計(jì)和為用戶提供個(gè)性化服務(wù)。

１．３結(jié)構(gòu)安排及創(chuàng)新點(diǎn)

本論文的章節(jié)安排如下：

第一章簡(jiǎn)要說(shuō)明了文章的選題背景及意義，介紹了Ｗｅｂ數(shù)據(jù)挖掘的研究現(xiàn)狀，最后概括本文結(jié)構(gòu)安排及創(chuàng)新點(diǎn)。

第二章介紹了數(shù)據(jù)挖掘技術(shù)的理論及相關(guān)應(yīng)用，總結(jié)了關(guān)聯(lián)規(guī)則、序列模式、分類和聚類等基本理論，同時(shí)對(duì)進(jìn)化計(jì)算中的群智能算法進(jìn)行了概述。通過(guò)分析Ｗｅｂ數(shù)據(jù)特點(diǎn)及現(xiàn)有聚類算法，得出用戶訪問(wèn)模式聚類的特點(diǎn)，分析了現(xiàn)有Ｗｅｂ訪問(wèn)模式聚類算法的不足之處。提出將粒子群優(yōu)化算法與艮均值相結(jié)合應(yīng)用于Ｗｅｂ訪問(wèn)模式聚類的可能。

第三章首先概述粒子群相關(guān)內(nèi)容，包括：粒子群優(yōu)化算法的基本原理、算法的數(shù)學(xué)描述、算法程序?qū)崿F(xiàn)流程等，其中探討了相關(guān)參數(shù)設(shè)置。同時(shí)，把粒子群的聚類思想與Ｋ．均值算法相結(jié)合，提出了基于搜索方向改進(jìn)的ＲＶＰＳＯ．Ｋ算法，并詳細(xì)論述了該算法的實(shí)現(xiàn)原理和流程。并采用ＵＣＩ機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Ｉｒｉｓ、Ｚｏｏ、Ｗｉｎｅ數(shù)據(jù)集合對(duì)Ｋ．均值算法、粒子群算法及相關(guān)的４種改進(jìn)算法進(jìn)行實(shí)驗(yàn)，結(jié)果表明，ＲＶＰＳＯ．Ｋ算法精度最高，收斂性較好。

第四章首先對(duì)Ｗｅｂ訪問(wèn)模式的理論研究及應(yīng)用進(jìn)行了說(shuō)明。該章主要實(shí)現(xiàn)了在用戶訪問(wèn)模式（Ｗｅｂ日志挖掘）聚類中的應(yīng)用：描述了實(shí)驗(yàn)數(shù)據(jù)來(lái)源及預(yù)處理４

第一章緒論

方法，定義了ＵｓｅｄＤ。ＵＲＬ關(guān)聯(lián)矩陣，對(duì)本文提出的ＲＶＰＳＯ．Ｋ算法在用戶訪問(wèn)模式聚類進(jìn)行了實(shí)現(xiàn)，同時(shí)給出了相關(guān)的定義和詳細(xì)的算法流程圖。實(shí)驗(yàn)結(jié)果表明，在大量及高維度的用戶數(shù)據(jù)情況下，與其他改進(jìn)算法對(duì)比，ＲＶＰＳＯ．Ｋ算法的精度最高。該算法不僅可用于用戶模式聚類，也可廣泛用于其他應(yīng)用領(lǐng)域。

第五章為論文的結(jié)束部分，對(duì)論文進(jìn)行了總結(jié)，指出了存在的不足以及進(jìn)一步的研究方向。

本文的創(chuàng)新點(diǎn)主要包括以下幾點(diǎn)：

１．通過(guò)對(duì)傳統(tǒng)粒子群算法的分析及對(duì)Ｋ．均值與粒子群結(jié)合的相關(guān)改進(jìn)聚類算法的驗(yàn)證，提出基于速度改進(jìn)的ＲＶＰＳＯ．Ｋ算法，這一改進(jìn)解決了粒子群全局最優(yōu)位置不是位于初始粒子位置與一個(gè)局部最優(yōu)位置之間情況下，且許多粒子都在同樣方向上搜索時(shí)，對(duì)全局最優(yōu)解區(qū)域形成搜尋盲區(qū)的問(wèn)題，能夠通過(guò)改變粒子軌跡提高粒子本身的搜索能力，從而可能盡快地找到全局最優(yōu)解。該算法具有較強(qiáng)的搜索能力和較好穩(wěn)定性，且精度較好，速度有明顯提升。

２．在本文提出的ＲＶＰＳＯ－Ｋ算法基礎(chǔ)上，將其應(yīng)用于Ｗｅｂ訪問(wèn)模式挖掘的用戶聚類中。通過(guò)實(shí)驗(yàn)對(duì)聚類算法進(jìn)行測(cè)試與分析，表明該算法較其他幾種粒子群與Ｋ．均值結(jié)合算法，能夠很好的提高聚類的準(zhǔn)確率指標(biāo)。

３．在Ｗｅｂ日志挖掘的用戶訪問(wèn)模式聚類中，對(duì)聚類中心代表含義進(jìn)行了說(shuō)明，提出設(shè)定不同的閾值的概念來(lái)解決用戶后續(xù)推薦問(wèn)題，從而提高調(diào)控推薦網(wǎng)頁(yè)的數(shù)量的靈活性，滿足不同的推薦需求。

第二章相關(guān)技術(shù)及理論介紹

第二章相關(guān)技術(shù)及理論介紹

２．１數(shù)據(jù)挖掘相關(guān)技術(shù)及理論介紹

２．１．１關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則挖掘通過(guò)統(tǒng)計(jì)方法歸納、提取有價(jià)值的ｉｏｔｈｅｎ規(guī)則。Ａｇｒａｗａｌ等人于１９９３年首先提出了挖掘顧客交易數(shù)據(jù)庫(kù)中項(xiàng)集間的關(guān)聯(lián)規(guī)則問(wèn)題…，以后關(guān)聯(lián)規(guī)則的挖掘問(wèn)題的大量研究包括對(duì)原有的算法進(jìn)行優(yōu)化以提高算法挖掘規(guī)則的效率，對(duì)關(guān)聯(lián)規(guī)則的應(yīng)用進(jìn)行推廣等。在零售業(yè)中，關(guān)聯(lián)規(guī)則挖掘技術(shù)可以發(fā)掘商品之間的在銷售過(guò)程中相互關(guān)聯(lián)關(guān)系，利用這些相關(guān)性，就可以更好的組織站點(diǎn)的內(nèi)容和結(jié)構(gòu)，為用戶推薦相關(guān)的商品，實(shí)施更有效的市場(chǎng)策略，從而得到了廣泛的應(yīng)用。比如利用頁(yè)面之間的這種相關(guān)性可以進(jìn)行交叉銷售，從而提高銷售量。

基本定義：設(shè)Ｉ＝｛ｉｌ，ｉ２，．．．，ｉｎ）是二進(jìn)制文字的集合，其中的元素稱為項(xiàng)（ｉｔｅｍ）。記Ｄ為交易（ｔｒａｎｓａｅｔｉｏｎ）Ｔ的集合，這里交易Ｔ是項(xiàng)的集合，并且Ｔ酉。對(duì)應(yīng)每一個(gè)交易有唯一的標(biāo)識(shí)，如交易號(hào)，記作ＴＩＤ。設(shè)Ｘ是一個(gè)Ｉ中項(xiàng)的集合，如果

’

Ｘ＿＿ｃＴ，那么稱交易Ｔ包含Ｘ。

一個(gè)關(guān)聯(lián)規(guī)則是形如ＸｊＹ的蘊(yùn)涵式，這里ＸｃＩ，Ｙｃｉ，并且ＸｎＹ＝①。規(guī)則ＸｊＹ在交易數(shù)據(jù)庫(kù)Ｄ中的支持度（ｓｕｐｐｏｒｔ）是交易集中包含ｘ和Ｙ的交易數(shù)與所有交易數(shù)之比，記為ｓｕｐｐｏｒｔ（Ｘ＝＞Ｙ），即：

ｓｕｐｐｏｒｔ（Ｘｊ驢Ｉ｛Ｔ：ＸｕＹ匕Ｔ，ＴｅＤ｝Ｉ／ＩＤｌ

規(guī)則ｘｊＹ在交易集中的置信度（ｃｏｎｆｉｄｅｎｃｅ）是指包含Ｘ和Ｙ的交易數(shù)與包含Ｘ的交易數(shù)之比，記為ｃｏｎｆｉｄｅｎｃｅ（Ｘ≥Ｙ），即

ｃｏｎｆｉｄｅｎｃｅ（Ｘ：＝＞Ｙ）＝Ｉ｛Ｔ：ＸｗＹ＿ｃＴ，ＴｅＤ｝Ｉ／Ｉ｛Ｔ：ＸｃＴ，ＴｅＤ｝Ｉ

給定一個(gè)交易集Ｄ，挖掘關(guān)聯(lián)規(guī)則問(wèn)題就是產(chǎn)生支持度和置信度分別大于用戶給定的最小支持度（ｍｉｎｓｕｐｐ）和最小置信度（ｍｉｎｃｏｎｆ）ｌ拘關(guān)聯(lián)規(guī)則。【Ｉ】

關(guān)聯(lián)規(guī)則挖掘用來(lái)尋找給定數(shù)據(jù)集中項(xiàng)之間的有趣聯(lián)系。關(guān)聯(lián)規(guī)則的挖掘過(guò)程一般分兩步進(jìn)行，其中，第二步比較簡(jiǎn)單，挖掘關(guān)聯(lián)規(guī)則的總體性能主要由第一步?jīng)Q定：

１．找出所有的頻繁項(xiàng)集。根據(jù)定義，這些項(xiàng)集出現(xiàn)的頻率至少和預(yù)定義的最小支持計(jì)數(shù)一樣。

２．由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則：根據(jù)定義，這些規(guī)則必須滿足最小支持度６