基于劃分的聚類算法.研究與應(yīng)用

《基于劃分的聚類算法.研究與應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、大連理工大學(xué)碩士學(xué)位論文1緒論1．1研究背景及意義數(shù)據(jù)挖掘(DataMining)就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識(shí)的過(guò)程。還有很多和這一術(shù)語(yǔ)相近似的術(shù)語(yǔ)，如從數(shù)據(jù)庫(kù)中發(fā)現(xiàn)知識(shí)(I①D)ll】、數(shù)據(jù)分析、數(shù)據(jù)融合(DataFusion)以及決策支持等。隨著網(wǎng)絡(luò)上Web頁(yè)面的激增，以及文本數(shù)據(jù)庫(kù)對(duì)各種形式文本統(tǒng)一管理和存儲(chǔ)，僅僅依靠手工來(lái)對(duì)這些文本資源進(jìn)行處理是不可能的。人們迫切需要有計(jì)算機(jī)自動(dòng)地對(duì)這些大規(guī)模的文本集合進(jìn)行有效

2、的處理和分析，包括分類、聚類、自動(dòng)摘要等等。聚類分析【l】是數(shù)據(jù)挖掘的一項(xiàng)重要功能。聚類(Clustering)就是將物理或抽象的集合分組成為由相似的對(duì)象組成的多個(gè)類的過(guò)程，使得每一類內(nèi)的數(shù)據(jù)盡可能相似而不同組內(nèi)的數(shù)據(jù)盡可能不NE21。在許多應(yīng)用中可以把一個(gè)簇中的數(shù)據(jù)對(duì)象當(dāng)作一個(gè)整體來(lái)對(duì)待。聚類是人類一項(xiàng)最基本的認(rèn)識(shí)活動(dòng)。通過(guò)適當(dāng)聚類，事物才便于研究，事物的內(nèi)部規(guī)律才可能為人類所掌握。從技術(shù)角度講，聚類的主要目的是將數(shù)據(jù)空間中的數(shù)據(jù)點(diǎn)劃分到若干個(gè)類中，其中將距離相近的數(shù)據(jù)點(diǎn)劃分到相同的類中，而將距離較遠(yuǎn)的數(shù)

3、據(jù)點(diǎn)劃分到不同的類中。它是在無(wú)監(jiān)督的情況下根據(jù)一定的相似性或距離計(jì)算函數(shù)自動(dòng)的將數(shù)據(jù)集分成若干類。因此，在很多應(yīng)用中，聚類分析作為一種數(shù)據(jù)預(yù)處理過(guò)程，是進(jìn)一步分析和處理數(shù)據(jù)的基礎(chǔ)。作為數(shù)據(jù)挖掘的功能，聚類分析可以作為一個(gè)獲得數(shù)據(jù)分布情況、觀察每個(gè)類的特征和對(duì)特定類迸一步分析的獨(dú)立工具。通過(guò)聚類，能夠識(shí)別密集和稀疏的區(qū)域，發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的相互關(guān)系等。隨著Intemet以及各種文本管理系統(tǒng)中可用文本的不斷增多，將文本幾個(gè)余弦分割成若干類別，為諸多面向文本的智能系統(tǒng)提供了支持。雖然聚類分析也

4、可以起到分類的作用，但是它和大多數(shù)分類方法不同；大多數(shù)分類方法都是演繹的，即人們事先確定某種事物分類的準(zhǔn)則或各類的標(biāo)準(zhǔn)，分類的過(guò)程就是比較分類的要素與各類別標(biāo)準(zhǔn)，然后將各要素劃歸于各類別中。確定事物分類準(zhǔn)則或各類別的標(biāo)準(zhǔn)或多或少帶有主觀的色彩。在某些分類問(wèn)題中，幾乎沒(méi)有相關(guān)數(shù)據(jù)的先驗(yàn)信息(如統(tǒng)計(jì)模型)可用，而且用戶又要求盡可能少地對(duì)數(shù)據(jù)的可能性進(jìn)行假設(shè)。而聚類分析將若干無(wú)標(biāo)記的數(shù)據(jù)點(diǎn)聚合成有意義的簇的過(guò)程是由數(shù)據(jù)驅(qū)動(dòng)12】的，因此特別適合用于挖掘有上述條件限制的數(shù)據(jù)點(diǎn)之間的內(nèi)在關(guān)系。聚類分析是歸納的，不需要

5、事先確定基于劃分的聚類算法研究與應(yīng)用分類的準(zhǔn)則，不知道它們的分類，甚至連分成幾類也不知道。它通過(guò)一些計(jì)算來(lái)把對(duì)象進(jìn)行合理的分離，使得同一類的對(duì)象比較接近，不同類的對(duì)象相差較多，這是無(wú)指導(dǎo)的學(xué)習(xí)。它既可以作為一個(gè)單獨(dú)的工具以發(fā)現(xiàn)數(shù)據(jù)庫(kù)中數(shù)據(jù)分布的一些深入信息，也可以作為其它數(shù)據(jù)挖掘分析算法的一個(gè)預(yù)處理步驟。本文算法的應(yīng)用背景為實(shí)驗(yàn)室給大連市公安局做的大連市公安局網(wǎng)上作戰(zhàn)系統(tǒng)一刑事審訊決策支持子系統(tǒng)項(xiàng)目。大連市公安局刑事審訊決策支持系統(tǒng)為大連市公安局提供的一套系統(tǒng)。該系統(tǒng)的一個(gè)需求模塊是對(duì)案例事件進(jìn)行管理，對(duì)同

6、類犯罪的案例進(jìn)行匯總，并對(duì)新加入的分到相應(yīng)的類別中，同時(shí)還要求方便工作人員查看某類犯罪類別的重要特征。由于公安局的刑事案例是以純文本的形式存在的，是不在網(wǎng)上公布的內(nèi)部文本數(shù)據(jù)庫(kù)信息，所以針對(duì)此類需求，我們需要實(shí)現(xiàn)一種基于劃分的聚類算法，對(duì)其中的違法犯罪數(shù)據(jù)庫(kù)庫(kù)經(jīng)行數(shù)據(jù)挖掘，對(duì)犯罪的人員進(jìn)行聚類，對(duì)犯罪人員的各種狀態(tài)進(jìn)行聚類，挖掘出犯罪類型的詳細(xì)特征，方便工作人員的查看。1．2國(guó)內(nèi)外研究現(xiàn)狀1989年8月在美國(guó)底特律召開的第11屆人工智能聯(lián)合會(huì)議的專題討論會(huì)上首次出現(xiàn)KDD(KnowledgeDiscover

7、yinDatabases)這個(gè)概念。隨后在1991年、1993年和1994年都舉行過(guò)KDD專題討論會(huì)，匯集來(lái)自各個(gè)領(lǐng)域的研究人員和應(yīng)用開發(fā)者，集中討論數(shù)據(jù)統(tǒng)計(jì)、海量數(shù)據(jù)分析算法、知識(shí)表示、知識(shí)運(yùn)用等問(wèn)題【3】。到了1995年，在美國(guó)計(jì)算機(jī)年會(huì)(AssociationforComputingMachinery)上，提出了數(shù)據(jù)挖掘的概念。同年在加拿大召開了第一屆知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘國(guó)際學(xué)術(shù)會(huì)議。IEEE的KnowledgeandDataEngineering會(huì)刊率先在1993年出版了KDD技術(shù)?？?，并行計(jì)算、計(jì)算

8、機(jī)網(wǎng)絡(luò)和信息工程等其他領(lǐng)域的國(guó)際學(xué)會(huì)、學(xué)刊也把數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)列為專題和?？懻摗＝陙?lái)有關(guān)KDD的國(guó)際研討會(huì)已經(jīng)召開了多次，規(guī)模由原來(lái)的專題討論會(huì)發(fā)展到國(guó)際學(xué)術(shù)大會(huì)，研究重點(diǎn)也逐漸從發(fā)現(xiàn)方法轉(zhuǎn)向系統(tǒng)應(yīng)用，注重多種發(fā)現(xiàn)策略和技術(shù)的集成，以及多種學(xué)科之間的相互滲透。1998年在美國(guó)紐約舉行的第四屆知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘國(guó)際學(xué)術(shù)會(huì)議上有30多家軟件公司展示了數(shù)據(jù)挖掘軟件產(chǎn)品，不少軟件已經(jīng)在北美和歐洲的國(guó)家得到應(yīng)用。IB