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

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

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

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



本文編號：4019193