數(shù)據(jù)特征化技術(shù)研究.pdf

1、數(shù)據(jù)特征化在數(shù)據(jù)管理領(lǐng)域和數(shù)據(jù)挖掘領(lǐng)域具有重要的用途。數(shù)據(jù)特征化旨在保留數(shù)據(jù)特征的情況下減小原始數(shù)據(jù)的規(guī)模。根據(jù)不同的數(shù)據(jù)類型和應(yīng)用背景,數(shù)據(jù)特征化技術(shù)主要分為:數(shù)值型數(shù)值數(shù)據(jù)特征化,關(guān)系型數(shù)據(jù)特征化和(半)結(jié)構(gòu)化數(shù)據(jù)特征化三大類。數(shù)值型數(shù)據(jù)特征化主要被數(shù)據(jù)庫(流)管理系統(tǒng)中的查詢引擎用于選擇度估算或者近似查詢處理,其主要包括直方圖技術(shù)和小波技術(shù);關(guān)系型數(shù)據(jù)特征化主要應(yīng)用于數(shù)據(jù)庫歸檔和數(shù)據(jù)瀏覽領(lǐng)域(如在手持設(shè)備上瀏覽大型的數(shù)據(jù)表),其使

2、用基于語義的表匯總技術(shù);現(xiàn)實世界的大量對象被建模成圖模型,實際應(yīng)用中的圖模型往往是巨大的(具有成千上萬甚至上百萬的節(jié)點和邊),去理解被編碼在這些(巨大的)圖中的信息需要使用圖匯總技術(shù)。
　　這些數(shù)據(jù)的特征化問題具有相同的共性:其目標是縮減數(shù)據(jù)規(guī)模且盡可能的保留數(shù)據(jù)原有特征,數(shù)據(jù)的特征均由給定的函數(shù)來度量。如何使得特征化數(shù)據(jù)的度量函數(shù)取得最優(yōu)值從而提高匯總數(shù)據(jù)的質(zhì)量,如何提高數(shù)據(jù)特征化算法的時間和空間效率以及如何在特定應(yīng)用背景下調(diào)整

3、通用的數(shù)據(jù)特征化算法是數(shù)據(jù)特征化問題面臨的主要挑戰(zhàn)。
　　L2范數(shù)誤差度量是基于統(tǒng)計分布中任意數(shù)據(jù)點是等概率被訪問的假設(shè),然而,在實際應(yīng)用中該假設(shè)往往不成立。例如:數(shù)據(jù)庫中的數(shù)據(jù)通常會出現(xiàn)帕累托法則的現(xiàn)象:20％的數(shù)據(jù)具有80%的訪問量。那么構(gòu)造基于工作負荷的直方圖能夠使得查詢優(yōu)化模塊獲得更準確的選擇度估算值。另一方面,最優(yōu)直方圖構(gòu)造算法的時間開銷通常為多項式級的。在時間敏感的數(shù)據(jù)庫系統(tǒng)中(例如實時環(huán)境下)為了將算法的時間開銷降至

4、線性時間,可考慮犧牲直方圖的估算質(zhì)量來換取算法時間效率上的提高,這樣的直方圖稱作近似直方圖。
　　現(xiàn)有的小波概要構(gòu)造算法均只關(guān)注如何確定被保留小波系數(shù)卻忽略如何有效地處理被拋棄(未被保留的)小波系數(shù)(只是簡單將未被選擇的小波系數(shù)當作0來處理)。經(jīng)過分析與證明發(fā)現(xiàn):合理地處理被拋棄的小波系數(shù)對改進近似數(shù)據(jù)集質(zhì)量和提高估算精度起著同樣重要的作用。針對L2范數(shù)誤差度量和MinMax絕對值度量的小波概要的被拋棄小波系數(shù)缺省值計算方法需要被

5、研究。
　　現(xiàn)有的表語義匯總技術(shù)將表的語義匯總作為K匿名進行處理,這樣的解決方法會導(dǎo)致語義匯總表的質(zhì)量下降,且存在轉(zhuǎn)換開銷大、算法框架復(fù)雜和不易擴展到高維屬性等缺點。通過將表語義匯總建模成多維層次空間聚類問題進行求解能有效克服上述缺點。
　　將原始圖中節(jié)點分配到多個分組并根據(jù)原始邊來確立分組間關(guān)系,這樣得到的圖稱作匯總圖。匯總圖的規(guī)模可以由用戶設(shè)定,用戶可以通過瀏覽小規(guī)模的匯總圖來獲得原始圖的相關(guān)信息。然而,現(xiàn)有算法存在匯總

6、圖規(guī)模設(shè)定受限問題。為了解決該問題,可引入節(jié)點的屬性值概念分層來增加圖匯總過程中節(jié)點分組的靈活性:不僅可以合并同值的節(jié)點還可合并具有相似值的節(jié)點。除了關(guān)注匯總過程中邊的信息損失外,節(jié)點的語義信息損失也需要被關(guān)注。改進的方法將圖匯總問題建模成多目標規(guī)劃問題,并通過分層序列法和基于分級的統(tǒng)一評價函數(shù)兩種不同策略來解決該問題。
　　圖規(guī)模巨大時,普通的基于聚類的圖語義匯總算法存在著算法時間開銷大的問題。如何快速地對大規(guī)模圖進行語義匯總是