聚類算法的研究與應(yīng)用.pdf

1、隨著計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)的快速發(fā)展，人們生產(chǎn)、收集數(shù)據(jù)的能力不斷提高，商業(yè)管理、政府部門、科研機(jī)構(gòu)與工程技術(shù)等領(lǐng)域的數(shù)據(jù)量以前所未有的速度海量增長。面對海量數(shù)據(jù)，如何從這些大規(guī)模數(shù)據(jù)中找到數(shù)據(jù)之間的模式，以提取信息、建立知識資源，從而避免“數(shù)據(jù)豐富而知識匱乏”的局面，已經(jīng)成為一個(gè)迫切需要解決的課題。 基于數(shù)據(jù)庫的知識發(fā)現(xiàn)(Knowledge Discovery in Database，簡稱KDD)是指從大量數(shù)據(jù)中提取有效的、新穎的

2、、潛在有用的和最終可被理解的模式的非平凡過程。它是一個(gè)反復(fù)迭代的人機(jī)交互處理過程，該過程需要經(jīng)歷多個(gè)步驟，主要包括數(shù)據(jù)整理、數(shù)據(jù)挖掘(Data Mining)和結(jié)果的解釋評估。其中數(shù)據(jù)挖掘是整個(gè)KDD過程中最核心的步驟，數(shù)據(jù)挖掘的目的就是運(yùn)用特定的數(shù)據(jù)挖掘算法，從數(shù)據(jù)庫中提取用戶感興趣的知識，并以一定的方式表示出來，如樹、表、規(guī)則、圖等。 聚類分析是數(shù)據(jù)挖掘的最主要的功能之一，聚類就是將數(shù)據(jù)對象分組為多個(gè)類或簇，在同一個(gè)簇中的對

3、象之間具有較高的相似度，而不同簇中的對象差別較大。聚類分析是一個(gè)很活躍的研究領(lǐng)域，是用以發(fā)現(xiàn)數(shù)據(jù)分布和模式的一類重要技術(shù)：聚類算法廣泛應(yīng)用于模式識別、數(shù)據(jù)分析、圖像處理、數(shù)據(jù)挖掘、決策支持和市場營銷等研究領(lǐng)域。本文將重點(diǎn)研究聚類分析中的若干關(guān)鍵技術(shù)和算法。 在第一章中，首先就數(shù)據(jù)挖掘進(jìn)行概述，主要討論數(shù)據(jù)挖掘的產(chǎn)生、發(fā)展以及數(shù)據(jù)挖掘算法所實(shí)現(xiàn)的各種功能，主要包括：類／概念描述、關(guān)聯(lián)規(guī)則、分類與回歸、聚類分析、序列與時(shí)序分析以及孤

4、立點(diǎn)分析等。最后給出了本文研究的主要內(nèi)容和組織結(jié)構(gòu)。 在第二章中，首先介紹了聚類分析的定義，聚類算法的基本要求，以及聚類算法中用到的主要數(shù)據(jù)類型；然后討論聚類分析的各種算法：基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法以及基于模型的方法；最后對聚類算法的應(yīng)用領(lǐng)域進(jìn)行了探討。 在第三章中，簡要介紹了半監(jiān)督聚類分析的概念、研究目的，以及現(xiàn)有算法的分類。 在第四章中，首先系統(tǒng)介紹了PAM聚類算法，分析

5、該聚類算法的關(guān)鍵技術(shù)和主要思想；然后在原有算法基礎(chǔ)上，本文給出了一種改進(jìn)算法：對屬于K-中心點(diǎn)算法的PAM算法的進(jìn)行效率改進(jìn)，提出了一種新的利用三角不等式消除、部分距離搜索等策略的快速PAM聚類算法，在保證聚類準(zhǔn)確率的同時(shí)提高了聚類效率；拓展了原有算法的聚類能力。實(shí)驗(yàn)結(jié)果表明，相對于基本PAM聚類算法，在保持相同聚類效果的情況下，本文提出的快速PAM聚類新算法能夠減少70％～90％的乘法計(jì)算量；并可節(jié)省約1/3以上的計(jì)算時(shí)間。第五章對論