基于聚集約束條件的不確定數(shù)據清洗與Top-k查詢.pdf

1、隨著技術的進步和人們對數(shù)據采集和處理技術理解的不斷深入，不確定性數(shù)據（uncertain data）得到了廣泛的重視。在許多現(xiàn)實的應用中，例如經濟、軍事、金融、電信等領域，數(shù)據的不確定性普遍存在，對不確定數(shù)據進行處理顯得尤為重要。對不確定數(shù)據進行研究和處理過程中，經常遇到的也是最難解決的就是可能世界實例“空間爆炸”問題，由于不確定數(shù)據的特殊性，同等規(guī)模的不確定數(shù)據庫較傳統(tǒng)確定數(shù)據庫處理的復雜度和困難程度要大得多。本文主要研究了基于聚集約

2、束的不確定數(shù)據清洗與 Top-k查詢，在研究過程中發(fā)現(xiàn)，無論不確定數(shù)據清洗還是查詢，都存在判斷可能世界實例是否滿足聚集約束條件的過程，當不確定數(shù)據集元組個數(shù)較多時，會面臨可能世界實例“爆炸”的問題。
　　本文針對不確定數(shù)據清洗和查詢問題，對基于聚集約束條件的不確定數(shù)據清洗與Top-k查詢進行了研究，主要研究工作體現(xiàn)在以下兩點：
　　1.分析了基于聚集約束對不確定數(shù)據進行清洗面臨的主要問題，并建立了完善的數(shù)學模型，將清洗問題轉

3、化成了一個非線性最優(yōu)化問題。根據本文研究的問題中，不確定數(shù)據元組值是離散的數(shù)值這一特點，在現(xiàn)有改進的非?？焖倌M退火（MVFSA）算法基礎上，通過重新設計算法的隨機擾動方式，提出了針對本文特定問題的MVFSA算法。實驗結果表明，本文提出的MVFSA算法較傳統(tǒng)的SA算法在清洗得到的結果質量和算法的效率上都有較大的提高。
　　2.針對基于聚集約束進行 Top-k查詢過程中，可能世界實例多，難以逐一判斷是否滿足約束這一問題，提出了一種基