有序決策系統(tǒng)的知識更新理論及其高效算法.pdf

1、數(shù)據(jù)挖掘的主要任務(wù)是從數(shù)據(jù)中發(fā)現(xiàn)有用知識。粒計算是一種新興的知識發(fā)現(xiàn)范式，已經(jīng)被廣泛地應(yīng)用到數(shù)據(jù)挖掘研究中。粗糙集理論是一種重要的粒計算理論。它的基本觀點是任一粗糙概念可以被兩個清晰概念刻畫。這對清晰概念被稱為上、下近似集。因此，近似集計算是利用粗糙集理論進行問題求解的一個關(guān)鍵步驟。近年來，日益復(fù)雜的數(shù)據(jù)環(huán)境（動態(tài)數(shù)據(jù)、復(fù)合數(shù)據(jù)等等）對近似集計算效率帶來了巨大的挑戰(zhàn)，加速近似集計算已經(jīng)引起了許多學(xué)者的關(guān)注。
　　人們在日常生活中存

2、在著各種各樣的偏好，因此，從實際問題中抽象的信息系統(tǒng)往往存在具有偏好屬性域的屬性（在決策分析研究中，這類屬性稱為指標(biāo)）。然而，經(jīng)典粗糙集理論不能直接用來處理具有偏好屬性域的信息。為此，Greco等用一個優(yōu)勢關(guān)系代替經(jīng)典粗糙集理論中的不可區(qū)分關(guān)系，從而提出了優(yōu)勢關(guān)系粗糙集方法。該方法能夠有效地應(yīng)用于多指標(biāo)分類或多指標(biāo)決策分析等相關(guān)問題求解。加速優(yōu)勢關(guān)系粗糙集方法近似集計算有助于提高這類問題求解的效率。因此，本文以優(yōu)勢關(guān)系粗糙集方法為研究對

3、象，分析動態(tài)信息系統(tǒng)中對象集、屬性值和屬性集的變化對近似集的影響，利用增量更新策略，通過局部更新過時的相關(guān)結(jié)果來避免不必要的重復(fù)計算，來實現(xiàn)高效地更新近似集的目的。為了便于解決涉及復(fù)合數(shù)據(jù)的多指標(biāo)分類問題或多指標(biāo)決策分析問題，本文基于容差關(guān)系和優(yōu)勢關(guān)系建立了一種新的粗糙集模型，并提出了該模型的近似集增量更新方法。為了采用并行技術(shù)實現(xiàn)高效地計算優(yōu)勢關(guān)系粗糙集方法近似集的目的，本文提出了一種適用于計算優(yōu)勢關(guān)系粗糙集方法近似集的并行策略，并且

4、設(shè)計了相關(guān)的并行算法等。本文的主要研究成果如下:
　　(1)針對有序決策系統(tǒng)中對象集的動態(tài)變化，提出了添加（刪除）一個對象時動態(tài)維護優(yōu)勢關(guān)系粗糙集中近似集的方法，設(shè)計了論域中添加（刪除）一個對象后更新優(yōu)勢關(guān)系粗糙集中近似集的增量算法。實驗評估反映了增量算法明顯地提高了對象集變化時更新優(yōu)勢關(guān)系粗糙集的近似集的效率。
　　(2)針對動態(tài)信息系統(tǒng)中局部的屬性值變化，提出了屬性值變化時動態(tài)維護優(yōu)勢關(guān)系粗糙集中近似集的方法以及設(shè)計了相

5、應(yīng)的增量算法。采用一個數(shù)值化算例說明了屬性值變化時增量更新優(yōu)勢關(guān)系粗糙集中近似集的可行性。通過實驗評估發(fā)現(xiàn)屬性值變化率小于一個閾值時利用增量算法更新優(yōu)勢關(guān)系粗糙集的近似集能夠有效地減少計算時間。
　　(3)對于動態(tài)信息系統(tǒng)中屬性集的變化，提出了同時添加（刪除）多個條件屬性時動態(tài)維護優(yōu)勢關(guān)系粗糙集方法中近似集的方法。在此基礎(chǔ)上，設(shè)計了相應(yīng)的增量算法。通過實驗評估發(fā)現(xiàn)同時添加（刪除）多個條件屬性時運用增量算法更新優(yōu)勢關(guān)系粗糙集的近似集

6、能夠有效地提高計算效率，并且增量算法的性能與數(shù)據(jù)集的屬性數(shù)和對象數(shù)密切相關(guān)。
　　(4)為了能夠應(yīng)用粗糙集方法對涉及多類型數(shù)據(jù)的分類問題進行求解，建立了一種基于容差和優(yōu)勢關(guān)系的復(fù)合粗糙集模型。同時，提出了添加（刪除）多個對象時動態(tài)維護該模型近似集的方法和設(shè)計了相應(yīng)的增量算法。實驗驗證了添加（刪除）對象時更新近似集使用增量算法都能夠提高計算效率。
　　(5)為了采用并行技術(shù)加速優(yōu)勢關(guān)系粗糙集的近似集計算，給出了優(yōu)勢關(guān)系粗糙集近