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

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

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

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

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