聚類分析是模式識(shí)別與數(shù)據(jù)挖掘等諸多領(lǐng)域的重要技術(shù)之一。然而,由于簇的大小、形狀、分布各異,目前已有的聚類算法,包括劃分式、層次式、基于密度峰值和基于最小生成樹(shù)等方法都無(wú)法令人滿意。大量研究發(fā)現(xiàn),相比均值中心和密度中心,使用代表點(diǎn)作為聚類中心的方法具有較好的性能,該方法受噪聲、離群點(diǎn)和簇的形狀的影響較小。另外,最小生成樹(shù)的形狀并不會(huì)隨簇邊界的變化而變化,因此,基于最小生成樹(shù)的聚類算法能解決對(duì)簇的形狀和噪聲敏感的問(wèn)題。本文重點(diǎn)解決了如何在最小生成樹(shù)上搜索代表點(diǎn),計(jì)算類間距離,以及簇的合并準(zhǔn)則,并構(gòu)建了基于最小生成樹(shù)的快速聚類算法。本文從在當(dāng)前研究現(xiàn)狀的基礎(chǔ)上,主要進(jìn)行了以下工作:(1)提出了一種基于最小生成樹(shù)樹(shù)形重心的類間距離度量方法。該方法的提出主要基于以下幾個(gè)原因:首先,傳統(tǒng)的基于最小生成樹(shù)的聚類算法,對(duì)最小生成樹(shù)的幾何形狀利用率不高;其次,使用歐幾里德距離的度量方法對(duì)類別的形狀分布敏感;最后,傳統(tǒng)的基于代表點(diǎn)的類別中心選取方法的時(shí)間復(fù)雜度較高。最小生成樹(shù)的樹(shù)形重心作為代表點(diǎn)能夠充分利用其幾何形狀,測(cè)地距離可以適應(yīng)多種形狀的簇。通過(guò)樹(shù)鏈剖分技術(shù)和二分算法快速地合并簇,從而大大降低計(jì)算代表...

【文章頁(yè)數(shù)】：67 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 引言
    1.2 國(guó)內(nèi)外研究現(xiàn)狀
    1.3 本文主要工作
    1.4 論文研究及章節(jié)安排
第2章 現(xiàn)有聚類算法及相關(guān)理論知識(shí)
    2.1 劃分式聚類算法
        2.1.1 K-means算法
        2.1.2 K-medoids算法
    2.2 基于密度的聚類算法
    2.3 層次式聚類算法
        2.3.1 CURE層次聚類算法
        2.3.2 Chameleon層次聚類算法
    2.4 最小生成樹(shù)聚類算法
        2.4.1 樸素分裂式最小生成樹(shù)聚類算法
        2.4.2 SAM算法
        2.4.3 其他最小生成樹(shù)聚類算法
    2.5 本章小結(jié)
第3章 一種基于最小生成樹(shù)樹(shù)形重心的類間距離度量方法
    3.1 相似度度量方法及類別中心選取
        3.1.1 歐幾里德距離及其推廣
        3.1.2 其他經(jīng)典相似度度量
        3.1.3 測(cè)地距離度量
        3.1.4 類別中心及代表點(diǎn)法
    3.2 最小生成樹(shù)樹(shù)形重心
    3.3 基于最小生成樹(shù)樹(shù)形重心的類間距離度量方法
    3.4 本章小結(jié)
第4章 一種基于限制廣度優(yōu)先搜索的預(yù)聚類方法
    4.1 廣度優(yōu)先搜索算法
    4.2 一種基于限制廣度優(yōu)先搜索的預(yù)聚類算法
    4.3 本章小結(jié)
第5章 一種基于割邊約束條件的多階段層次聚類方法
    5.1 階段Ⅱ:基于割邊約束的小類合并過(guò)程
    5.2 階段Ⅲ:最終聚類
    5.3 完整算法
    5.4 整體算法時(shí)間復(fù)雜度分析
    5.5 本章小結(jié)
第6章 算法對(duì)比實(shí)驗(yàn)
    6.1 聚類評(píng)價(jià)指標(biāo)
    6.2 實(shí)驗(yàn)環(huán)境介紹
    6.3 人工數(shù)據(jù)集實(shí)驗(yàn)結(jié)果
    6.4 UCI真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果
    6.5 算法運(yùn)行時(shí)間對(duì)比
    6.6 本章小結(jié)
第7章 全文總結(jié)與展望
    7.1 本文工作總結(jié)
    7.2 研究展望
參考文獻(xiàn)
攻讀碩士學(xué)位期間的相關(guān)成果
致謝



本文編號(hào)：4019193