子空間聚類算法解析ppt課件.ppt

《子空間聚類算法解析ppt課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、研究背景和意義在過去的幾十年里，隨著科學(xué)技術(shù)的進(jìn)步，數(shù)據(jù)采集及存貯能力得到了快速發(fā)展，很多學(xué)科都出現(xiàn)了信息爆炸的現(xiàn)象，研究人員需要面對越來越龐大的觀測數(shù)據(jù)。因此，數(shù)據(jù)挖掘技術(shù)受到大家的廣泛關(guān)注。數(shù)據(jù)挖掘（DataMining，DM）一般是指從數(shù)據(jù)庫的大量數(shù)據(jù)中，自動搜索隱藏于其中有著特定價值和規(guī)律的信息的過程。此外，數(shù)據(jù)挖掘也是一種決策支持過程，基于人工智能、機(jī)器學(xué)習(xí)、模式識別、統(tǒng)計(jì)學(xué)、可視化等技術(shù)，分析各種類型的數(shù)據(jù)，做出歸納性的推理，從中挖掘出潛在模式，幫助各個領(lǐng)域的專家及研究人員做出正確的決策和判斷數(shù)據(jù)挖掘的主要過程包括數(shù)據(jù)準(zhǔn)備、信息挖掘、結(jié)果表達(dá)和解釋三個處理階段數(shù)

2、據(jù)準(zhǔn)備是指從相關(guān)的數(shù)據(jù)源中選取所需的數(shù)據(jù)樣本，將其整合成用于數(shù)據(jù)分析的樣本集；信息挖掘是指利用各種數(shù)據(jù)挖掘算法將所得的樣本集中包含的規(guī)律信息或潛在模式挖掘出來；結(jié)果表達(dá)和解釋是指盡可能以用戶可理解的方式將找出的規(guī)律或模式表示出來新的問題和挑戰(zhàn)首先，數(shù)據(jù)的規(guī)模越來越大的，也就是所謂的大規(guī)模數(shù)據(jù)（Large-ScaleData）的問題其次，數(shù)據(jù)的特征不斷增加，導(dǎo)致數(shù)據(jù)維數(shù)的增加，出現(xiàn)了數(shù)據(jù)密度稀疏和“維數(shù)災(zāi)難”等現(xiàn)象，導(dǎo)致出現(xiàn)如下的問題1)很難定義準(zhǔn)確的距離度量函數(shù)。2)算法的空間復(fù)雜度和時間復(fù)雜度急劇上升。隨著數(shù)據(jù)維數(shù)的漸增，導(dǎo)致各種數(shù)據(jù)挖掘算法的性能出現(xiàn)明顯下降，難以解決實(shí)

3、際問題中的實(shí)時性問題；3)數(shù)據(jù)簇之間或數(shù)據(jù)類之間的差異無法判斷。由于高維空間中存在大量冗余的特征，使得在整個特征空間中，各個樣本點(diǎn)之間的距離幾乎是相等的。最后，數(shù)據(jù)挖掘越來越強(qiáng)調(diào)多學(xué)科的交叉，不僅需要靈活運(yùn)用統(tǒng)計(jì)學(xué)、計(jì)算機(jī)、數(shù)學(xué)等建模技術(shù)，還需要具有生物學(xué)、腦科學(xué)、證券金融等學(xué)科的知識背景針對于這些問題，人們提出了大規(guī)模數(shù)據(jù)的數(shù)據(jù)流（DataStream）分析方法；針對高維數(shù)據(jù)的特征加權(quán)（FeatureWeighting）和特征選擇（FeatureSelection）方法；同時，生物信息學(xué)（Bioinformatics）等交叉學(xué)科也成為目前數(shù)據(jù)挖掘領(lǐng)域的研究重點(diǎn)子空間聚類算

4、法一般來說，樣本之間的差異往往是由若干個關(guān)鍵的特征所引起的，如果能恰當(dāng)?shù)恼页鲞@些重要特征，對建立合理的聚類或分類模型將起到積極的作用。這樣不僅可以減少模型的建立時間，提高模型預(yù)測的準(zhǔn)確率，還能有效地提高數(shù)據(jù)挖掘算法的魯棒性和適應(yīng)性。因此，我們希望可以針對數(shù)據(jù)的高維特征，對其各個特征的重要性進(jìn)行加權(quán)，或者挑選出最重要的特征子集，減少或消除冗余特征以及不相關(guān)特征的影響，最大限度地保留和利用原始數(shù)據(jù)中的關(guān)鍵特征，在這個想法的基礎(chǔ)上我們提出了子空間聚類。子空間聚類算法是指把數(shù)據(jù)的原始特征空間分割為不同的特征子集，從不同的子空間角度考察各個數(shù)據(jù)簇聚類劃分的意義，同時在聚類過程中為每個

5、數(shù)據(jù)簇尋找到相應(yīng)的特征子空間。子空間聚類算法子空間聚類算法實(shí)際上是將傳統(tǒng)的特征選擇技術(shù)和聚類算法進(jìn)行結(jié)合，在對數(shù)據(jù)樣本聚類劃分的過程中，得到各個數(shù)據(jù)簇對應(yīng)的特征子集或者特征權(quán)重。根據(jù)目前的研究結(jié)果，子空間聚類可以分為硬子空間聚類和軟子空間聚類兩種形式。更具體而言，根據(jù)搜索方式的不同，硬子空間聚類方法又可分為自底向上的子空間搜索算法和自頂向下的子空間搜索算法兩種；對于軟子空間聚類方法而言，根據(jù)特征加權(quán)不確定性表示方式的不同，可以分為模糊加權(quán)軟子空間聚類和熵加權(quán)軟子空間聚類兩種自底向上子空間聚類算法自底向上子空間聚類算法一般是基于網(wǎng)格密度，采用自底向上搜索策略進(jìn)行的子空間聚類算

6、法。它先將原始特征空間分成若干個網(wǎng)格，再以落到某網(wǎng)格中樣本點(diǎn)的概率表示該子空間的密度情況。對于密度超過一定閾值的子空間作為密集單元進(jìn)行保留，而對非密集的子空間進(jìn)行舍棄。經(jīng)典的自底向上子空間聚類方法有最早的靜態(tài)網(wǎng)格聚類算法CLIQUE、利用熵理論作為密度度量的ENCLUS方法，以及后來提出的通過動態(tài)查找策略，得到更加穩(wěn)定劃分結(jié)果的子空間聚類算法：MAFIA和DOC等CLIQUE算法在高維（多屬性）空間中進(jìn)行聚類，一般的聚類算法要求有一個降維的預(yù)處理過程，典型的做法是：（1）由用戶指定其中的若干重要屬性，從而達(dá)到維度的降低；（2）通過屬性約簡，將一些不重要的屬性去掉，經(jīng)常采用的

7、方法有主成分分析法和粗糙集方法；（3）將數(shù)據(jù)空間通過不同維度的線性組合變換到一個低維空間中，使得不同點(diǎn)間的間隔在兩個空間中近似相同。但是這些方法都存在一定的缺陷，對于前兩種方法有丟失有趣的結(jié)構(gòu)或模式的可能。對于第三種方法因?yàn)檫M(jìn)行了屬性的組合，打亂了與原空間的對應(yīng)關(guān)系，使得產(chǎn)生的聚類結(jié)果很難解釋。CLIQUE算法采用了基于網(wǎng)格和密度的方法。首先對每個屬性進(jìn)行等分，整個數(shù)據(jù)空間就被分成一個超長方體集合，對每個單元進(jìn)行數(shù)據(jù)點(diǎn)計(jì)數(shù)，大于某個閾值的單元稱這稠密單元，然后對稠密單元進(jìn)行連接就構(gòu)成類。不同于其它方法，它可以自動地