多關(guān)系數(shù)據(jù)聚類算法及其應(yīng)用研究.pdf

1、隨著信息技術(shù)的發(fā)展，各行各業(yè)在實(shí)際應(yīng)用中都產(chǎn)生了大量的數(shù)據(jù)，為了能在這些海量數(shù)據(jù)中發(fā)現(xiàn)對(duì)其所屬領(lǐng)域有用的信息和知識(shí)，作為知識(shí)發(fā)現(xiàn)的一個(gè)重要過程，數(shù)據(jù)挖掘技術(shù)研究得到了廣泛的關(guān)注。而作為數(shù)據(jù)挖掘的一種方法，聚類分析技術(shù)也自然成為了數(shù)據(jù)挖掘領(lǐng)域中一個(gè)非?；钴S的研究課題。聚類分析作為非監(jiān)督的機(jī)器學(xué)習(xí)算法，將對(duì)象集合按照相似度分為多個(gè)類別（簇），使得同一類別中的對(duì)象間相似度較大，而不同類別中的對(duì)象間相似度較小。聚類分析可用于發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，

2、并通過觀察每個(gè)聚簇的特點(diǎn)，對(duì)某些特定的聚簇做進(jìn)一步的分析，還可作為其他算法的預(yù)處理步驟，使其在生成的聚簇上做進(jìn)一步的處理。
　　大多數(shù)聚類算法僅適用于存儲(chǔ)于單關(guān)系表中的數(shù)據(jù)，而在許多實(shí)際應(yīng)用中，結(jié)構(gòu)化數(shù)據(jù)多存放于關(guān)系數(shù)據(jù)庫的多個(gè)關(guān)系表中，雖然可通過連接或聚合操作將多張關(guān)系表合并為一張單表，但這種處理方式不僅會(huì)產(chǎn)生高維數(shù)據(jù)，而且整合后數(shù)據(jù)點(diǎn)可能會(huì)分布在不同維的子空間中，導(dǎo)致位于不同維的數(shù)據(jù)對(duì)象間距離相等，失去距離度量的意義；還很難體

3、現(xiàn)不同表間的聯(lián)系對(duì)聚類造成的影響。多關(guān)系數(shù)據(jù)聚類正是面向該應(yīng)用需求而產(chǎn)生的。然而關(guān)于多關(guān)系數(shù)據(jù)聚類算法的研究在面對(duì)對(duì)象間存在一對(duì)多的聯(lián)系、表間對(duì)應(yīng)信息不完全使得各目標(biāo)對(duì)象可能由不同階數(shù)的信息描述，多關(guān)系數(shù)據(jù)集中各關(guān)系表間的聯(lián)系存在回路等問題時(shí)，尚未給出有效的解決方案。另外一個(gè)完整的聚類分析過程在聚類結(jié)束后，仍需評(píng)價(jià)聚類結(jié)果的質(zhì)量，確定結(jié)果是否符合數(shù)據(jù)的內(nèi)在分布特性，即驗(yàn)證聚類結(jié)果的有效性；并且利用合理有效的方法分析解釋該結(jié)果，以有助于為

4、數(shù)據(jù)分析人員提供決策支持。
　　因此針對(duì)多關(guān)系數(shù)據(jù)聚類算法以及聚類結(jié)果評(píng)價(jià)、解釋方法中存在的主要問題，本文展開了以下幾個(gè)方面的研究工作。
　?。?）針對(duì)多關(guān)系數(shù)據(jù)聚類中利用統(tǒng)計(jì)方法提取一對(duì)多聯(lián)系對(duì)應(yīng)的信息會(huì)忽略數(shù)據(jù)的原始特征、不同關(guān)系表間的聯(lián)系出現(xiàn)的回路可能導(dǎo)致信息重復(fù)利用的問題，研究有效的層次多關(guān)系聚類算法。首先引起數(shù)據(jù)集中存在上述問題是由表間聯(lián)系的種類不同而引起的，而 IDEF1x模型中描述的聯(lián)系可用于解釋其原因，因此基

5、于該模型研究多關(guān)系數(shù)據(jù)聚類的層次框架，然后研究框架中不同種類的聯(lián)系對(duì)聚類結(jié)果傳遞的影響，以及整合多個(gè)子節(jié)點(diǎn)聚類結(jié)果的方法，并提出新的多關(guān)系數(shù)據(jù)聚類算法，以實(shí)現(xiàn)最終有效輔助目標(biāo)對(duì)象聚類的目的。
　?。?）針對(duì)多關(guān)系聚類中目標(biāo)對(duì)象可能由不同階數(shù)信息描述的問題，研究盡量不損失數(shù)據(jù)信息的多關(guān)系聚類算法。仍以基于 IDEF1x的關(guān)聯(lián)層次模型作為多關(guān)系聚類的基礎(chǔ)框架，并將描述信息不完整的目標(biāo)對(duì)象視為不確定數(shù)據(jù)。首先基于Kripke結(jié)構(gòu)構(gòu)建多關(guān)

6、系不確定數(shù)據(jù)模型以刻畫數(shù)據(jù)描述信息的完整性；并基于概率約束區(qū)域進(jìn)一步描述其不確定性，然后定義不確定數(shù)據(jù)間的距離度量方法，最后提出基于概率約束區(qū)域的多關(guān)系數(shù)據(jù)聚類算法，使得在不破壞原始數(shù)據(jù)特征的前提下，保證多關(guān)系聚類的有效性。
　?。?）傳統(tǒng)的聚類評(píng)價(jià)方法幾乎均根據(jù)評(píng)價(jià)指標(biāo)的值分析聚類結(jié)果的有效性，使其具有一定的局限性。因此著眼于聚類過程，提出有效的聚類結(jié)果所對(duì)應(yīng)的聚類過程應(yīng)滿足的狀態(tài)性質(zhì)，并基于程序圖以及遷移系統(tǒng)對(duì)聚類過程進(jìn)行抽象

7、建模；然后基于模型檢測(cè)算法將判斷聚類結(jié)果的有效性問題轉(zhuǎn)換為利用模型檢測(cè)技術(shù)驗(yàn)證描述聚類過程的模型是否滿足給定性質(zhì)的問題，使得該算法不僅能夠直接指出聚類結(jié)果是否有效，若結(jié)果不理想，還能根據(jù)反例分析過程指出是由哪次迭代導(dǎo)致的問題。即試圖構(gòu)建聚類分析與模型檢測(cè)技術(shù)間的橋梁。
　?。?）常見的聚類結(jié)果解釋方法如分析屬性值的分布特征、數(shù)據(jù)的分布情況等，缺少對(duì)聚簇間基于各屬性差異的定量度量，而這種差異恰能體現(xiàn)屬性對(duì)聚類結(jié)果的影響程度，并可進(jìn)一