基于最小生成樹(shù)的聚類分析方法研究.pdf

1、數(shù)據(jù)挖掘（Data Mining）是當(dāng)前國(guó)際上數(shù)據(jù)庫(kù)技術(shù)和信息決策最前沿的研究領(lǐng)域之一，從多個(gè)學(xué)科汲取營(yíng)養(yǎng)。聚類分析是數(shù)據(jù)挖掘里一個(gè)重要的研究方向，對(duì)其進(jìn)行深入研究在理論基礎(chǔ)和實(shí)際應(yīng)用上都有重要價(jià)值。聚類分析方法已經(jīng)經(jīng)過(guò)了幾十年的發(fā)展，期間研究人員都在嘗試用不同的方法來(lái)處理聚類問(wèn)題。在眾多提出的方法里，最小生成樹(shù)聚類算法是其中一種典型的方法。但是，現(xiàn)有的該類方法仍舊存在不足，這就要求對(duì)已有的聚類分析技術(shù)進(jìn)行改進(jìn)，提出一種新的聚類理論和方

2、法。
　　本文通過(guò)研究分析，首先在Prim和Kruskal最小生成樹(shù)算法的基礎(chǔ)上，構(gòu)造一種新的最小生成樹(shù)算法QMST（Quick Minimum Spanning Tree），該方法巧妙地將數(shù)據(jù)集分成上界、下界和臨時(shí)數(shù)據(jù)集三部分，大幅度地降低所需處理的數(shù)據(jù)規(guī)模，能夠快速地構(gòu)造出最小生成樹(shù)，所需時(shí)間優(yōu)于Prim和Kruskal。同時(shí)，在處理高維數(shù)據(jù)集時(shí)，依據(jù)屬性差異度原理，引入降維策略，使得QMST在構(gòu)造高維數(shù)據(jù)集的最小生成樹(shù)時(shí)依舊

3、保持快速的特性。接下來(lái)，通過(guò)分析現(xiàn)有的最小生成樹(shù)聚類算法，結(jié)合基于劃分和基于密度的聚類思想，提出一種基于最小生成樹(shù)的快速自適應(yīng)聚類分析方法QSAK-MST（Quick Self-adaptive K-means–Minimum Spanning Tree），該方法通過(guò)QMST快速地構(gòu)造出數(shù)據(jù)集的最小生成樹(shù)，同時(shí)不依賴參數(shù)選取，即事先無(wú)需進(jìn)行參數(shù)設(shè)定，而是比較簇的緊湊度大小，使用分裂準(zhǔn)則對(duì)生成樹(shù)進(jìn)行迭代分裂，自適應(yīng)地產(chǎn)生初始聚類中心和初始

4、簇，接著使用K-均值的核心思想，根據(jù)前階段產(chǎn)生的初始聚類中心和初始簇，采用最小化平方誤差函數(shù)，根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象分配到最相似的簇，更新簇均值，重復(fù)這個(gè)過(guò)程，直到函數(shù)收斂或者達(dá)到設(shè)定的迭代次數(shù)上限。通過(guò)這一局部調(diào)整的過(guò)程，能夠有效地緩解在分割最小生成樹(shù)以及對(duì)高維數(shù)據(jù)進(jìn)行降維處理所帶來(lái)的誤差，從而進(jìn)一步地提高聚類結(jié)果的精度。QSAK-MST解決了事先需要設(shè)置參數(shù)的難題以及大幅度地降低了構(gòu)造最小生成樹(shù)需要耗費(fèi)的時(shí)間，不僅提高了聚類