基于局部信息的全局數據挖掘研究
2008-12-31 00:00:00王金龍徐從富耿雪玉
計算機應用研究 2008年7期
摘 要：重點綜述了基于局部信息的全局數據挖掘方法。根據數據挖掘的過程，將該問題的研究劃分成三個階段，即利用粒度數據表示進行挖掘、利用局部信息改善全局挖掘的效率和利用局部模式結果獲得全局數據理解，并對每個階段進行了分類論述。最后總結了全文并指明了未來的研究方向。
關鍵詞：數據挖掘;全局模型;局部模式;粒度計算
中圖分類號：TP311 文獻標志碼：A
文章編號：1001-3695(2008)07-1936-04
Study on global data mining based on local information
WANG Jinlong1，XU Congfu2a，GENG Xueyu2b
(1.School of Computer Engineering， Qingdao Technological University， Qingdao Shandong 266033， China；2.a.College of Computer Science，b.Institute of Geotechnical Engineering Research， Zhejiang University， Hangzhou 310027， China)
Abstract:This paper investigated data mining through combining global model constructing and local pattern mining， especially studied global data mining based on local information. On the basis of the process of data mining，it divided this problem into three phases， including improving the efficiency of mining using granular representation， improving the interpretation of local mining using global model， improving the efficiency and accuracy of global mining. And the paper reviewed these three problems respectively. Finally， the paper summarized and also pointed out some future works.
Key words:data mining;global model；local pattern；granular computing
人類在思考、解決問題時，往往根據實際需要或是先從總體進行初步分析，然后再深入研究各部分的具體情況，即先整體后部分；或是先研究各部分的情況，再進行綜合，即先部分后整體；或是交替使用上述兩種方法，根據具體問題，時而從總體上把握問題，時而深入研究某一部分的具體情況。盡管數據挖掘的功能各不相同，待發現的模式類型也有所不同，但在所獲得的知識表示上主要包括全局模型和局部模式兩大類[1]。
傳統上，數據挖掘的文獻主要分為對這兩種知識表達形式的獲取和表示[2，3]。
1)全局模型對數據集進行全局性總結
它對測量空間的每一點進行描述。在這類問題中，其挖掘和處理的主要目的是基于數據產生過程描述數據或構造數據生成模型，最后得到對整個數據的理解。這是一種全局性的數據挖掘。如圖1所示，從大橢圓形虛線框到“學習”，再到“模型”的過程即為全局模型學習。
2)模式結構僅對變量變化空間作出局部性描述
在圖1中，局部挖掘僅對變量空間的一個有限區域進行描述。所使用的主要技術為基于數據的快速計數。這類問題最突出的例子是關聯規則挖掘[4]和頻繁模式發現[5]。這類方法一般瞄準發現頻繁出現的模式和項集，每個得到的模式及其頻率僅反映部分數據特性，每個模式可獨立反映數據的局部意義。通過將所獲模式放到一起，能夠獲得對數據集的整體理解。
1 基于局部信息的全局數據挖掘
本質上全局和局部挖掘都嘗試獲得對已有信息的理解，進而歸納相關知識或對未知數據進行推理。基于全局模型的挖掘自不必說，貝葉斯網絡等概率圖模型學習是機器學習的重要內容，利用其進行分類和預測的方法非常多；在局部模式挖掘中，利用所獲得的頻繁模式進行分類[6，7]、基于頻繁模式的聚類[8，9]、基于頻繁模式輔助構造概率圖模型等[10，11]也是數據挖掘中的重要主題。雖然全局和局部挖掘方法最終目的相同，但因這兩種方法立足點不同，各有優缺點。從整體上對數據進行挖掘所獲取的全局信息比較容易理解，且易于使用，但在維數較高時，這種圖模型的構造效率較低，影響了算法的推廣性；與全局模型不同，局部模式發現在用戶給定閾值的情況下獲取局部信息，在挖掘過程中，一些數據結構和數據特性的使用可以提高很多算法的效率，處理高維數據，但這種挖掘方法常依賴于用戶所設參數，在給定參數較小時，往往得到大量局部模式，影響了理解，使得所獲知識不易使用。
在數據挖掘方面，若能將上述兩種方法進行綜合，利用其各自的優勢設計有效算法正在成為當前研究的重點和難點問題。本文主要研究了基于局部信息的全局數據挖掘，通過局部信息的使用一方面獲取算法效率的提高，另一方面通過局部信息的綜合能夠獲得理解性更強的模型。在全局數據挖掘中，將局部信息的使用總結為如下三類：
a)數據表示。數據的合理表示是數據挖掘的基礎，充分利用局部信息能夠有效提高挖掘的效率。基于數據粒表示的挖掘充分利用了粒度思想中全局和局部相結合的思想，通過將數據進行有效劃分和總結，能夠設計更加有效的挖掘算法。
b)挖掘過程。在挖掘過程中，局部信息的使用能夠顯著改善全局挖掘效率，提高算法的擴展性。
c)挖掘結果。在所挖掘的局部模式上，利用全局方法進行模式的綜合和壓縮，顯著減少了模式的數量，提高了知識的表達和使用。
2 基于數據粒度表示的挖掘
在一般的局部數據挖掘中，模式信息主要通過對數據集的反復掃描獲得。該處理過程往往將數據集作為一個不可分隔的整體，將數據集的所有屬性作為有意義的名稱進行考慮，從而獲得屬性之間的關聯關系。
Lin[12]利用粒度思想，將數據表的行列翻轉，將數據表中的元組作為其基本元素，而屬性值被認為是標記這些元素的名稱（粒，granule），從而將關系表及其模型轉換為面向機器可處理的關系模型。該方法以更接近機器的方式進行信息處理，同時能夠根據計算的不同需要，將數據拆分或合并進行處理，加快了搜索和計算的速度。
基于這種數據粒化及模型轉變的方法，人們可將一些經典的數據挖掘方法，如關聯規則、決策規則等簡化為集合操作的形式，從而比較容易地進行規則發現和局部模式挖掘[12~14]。
這種將數據進行不同劃分，在不同粒度世界進行分析的方法更加符合人類思考問題的方式。這正是粒度計算[15，16]（granular computing，GrC）的基本思想。粒度計算就是對人類這種能力的一種形式化表達。粒度計算中最基本的概念是粒度。粒度是一個論域的子集、類或簇[17]。
利用等價類的思想，可定義數據表中的粒，將數據整體進行適當劃分，在計算時，根據所定義的粒進行基于集合的運算，從而加快了計算效率。該過程如圖2所示。
3 基于局部模式的全局模型挖掘
在全局挖掘過程中，適當結合數據的局部模式特性，不僅能簡化模型構造的復雜度，且能獲得更加有效的全局表示。
貝葉斯網絡學習的復雜性與屬性變量個數密切相關，當數據維數非常高時，其學習在很多情況下不可行。研究者已將頻繁項集用于稀疏數據的全局模型模擬問題[3，18~20]。2004年，卡內基梅隆大學的Anna Goldenberg和其導師Andrew Moore探討了在稀疏及高維數據時（如在基因分析和社會網絡分析），如何利用頻繁集的局部信息有效進行貝葉斯網絡結構搜索的方法，在BDeu[21]評分函數下學習了貝葉斯網絡。該方法不僅在效率上獲得了顯著提升，并且與爬山法（hillclimbing）[22]相比，獲得了更加準確的結果。2005年，作者將其改進方法用于合作者網絡的理解[23]，獲得了較好的結果。應用于稀疏數據的主要原因是在這種數據集中，數據同時發生的頻率很低，在多數情況下，屬性兩兩同時出現的發生頻率接近0。因此，反映局部模式的頻繁項集能夠反映整個數據集的大量重要信息，使得頻繁項集在稀疏數據的全局模擬中成為可能，加快了學習的速度。其學習和挖掘過程如圖3所示。
另外，針對序列數據的處理，Mannila等人[24]在2000年提出了序列數據的全局性偏序算法，以一個單一的偏序來描述一個序列數據庫中的所有時間順序關系。其挖掘的過程利用了平凡偏序模式和一般偏序的混合模型來生成數據，用EM算法[25]來獲得其中參數。為了降低模型構造的復雜性，作者對局部信息進行了限制，只考慮了seriesparallel[26]的偏序模型。
在當前很多實際數據中，數據的維數和復雜性越來越高，而全局模型的求解因為搜索空間的限制，在準確性和效率上的矛盾越來越突出。這就要求在很多實際問題中引入數據局部特性或加入一些限制，在獲得用戶所需結果的前提下提高效率。該方面的研究正在引起數據挖掘和機器學習領域的高度重視。
4 基于局部模式的全局信息獲取
傳統的局部模式發現方法常得到大量模式信息，為了減少這些模式信息的數量，同時又保證所獲得模式的質量，可利用全局思想對其進行總結，從而減少模式數量，減輕用戶理解的負擔。基于此，一些新的模式及其挖掘方法被相繼提出，根據挖掘中所用壓縮技術的不同，主要分為無損壓縮和有損壓縮兩大類。
無損壓縮最典型的方法是閉合模式的挖掘。該模式挖掘方法能夠在信息可以完全恢復的前提下有效減小頻繁模式數量，但在很多情況下，所獲得的模式數量仍然過高。最大模式[27]和K最大閉合模式[28]兩種模式挖掘方法能夠獲取更少的模式信息，但其在挖掘時信息損失較大，信息不能恢復，從而會損失很多用戶感興趣的信息，而且因其對數據分布較為敏感，最后的模式信息往往不能有效反映數據。
無論是閉合模式還是最大模式，它們都是在傳統模式挖掘的框架下盡量減少模式數量，但其所獲得的結果無法在準確性和可用性之間達到較好折中，影響了結果的理解和使用。若能從全局角度將局部模式進行總結，在準確性能夠得到有效控制的前提下顯著減少模式數量，將會得到更加直觀和有效的結果。這種方法不僅能夠簡化局部模式的表達，甚至在一定程度上能夠獲得對整個數據集的全局概括。這個過程既可在挖掘過程中進行，也可以直接應用在挖掘結果的后處理上，如圖4所示。
在此框架下，很多研究者進行了深入的研究。2004年，Afrati等人[29]提出了模式近似和壓縮的概念，嘗試用k個模式對所獲得的大量頻繁模式進行總結、勾畫模式的輪廓。該方法利用k個總結模式來對頻繁模式進行覆蓋，獲得對輸入模式的近似總結，使得結果易于表達和使用。為解決文獻[29]在模式壓縮中未考慮項集支持度信息的問題，Yan等人[30]在生成模型的框架下提出了基于項集輪廓對閉合頻繁項集進行壓縮的方法。該方法能夠控制誤差范圍，近似恢復每個項集的支持度，不但壓縮了模式，同時獲得了有意義的近似結果。
另一種方法嘗試在給定誤差范圍內利用聚類技術將頻繁模式進行分組，選擇代表模式，用其對模式進行壓縮。2002年，Pei等人[31]基于支持度對模式進行劃分，在每個劃分的組中選取最有代表性的模式，精簡了模式的表達。
2005年，Xin等人[32]對所獲得的閉合模式進行了壓縮，將頻繁模式進行聚類，然后為每個簇選擇一個代表模式。所獲得的代表模式能夠描述其他相關模式的表達式和支持度，從而描述整個簇。
上述兩種方法都從減少所獲得頻繁項集數量的角度進行模式壓縮。與此不同，Siebes等人[33]嘗試直接描述項集對原始數據集的壓縮能力（最好的頻繁項集能對數據集進行最好壓縮），在最小描述長度原則下[34]，利用啟發式算法獲得了能夠壓縮數據集的頻繁項集。
在序列模式挖掘方面，2005年，GarrigaCasas[35]針對閉合序列模式數量較多的問題，研究了對其進行總結的后處理方法，通過對模式的融合，獲得了閉合偏序模型（closed partial order），可以更加直觀和有效地表達結果。針對該方法僅對已獲得的模式進行分析、效率較低的問題，2006年Pei等人[36]設計了直接挖掘原始數據以獲得頻繁閉合偏序的方法，得到了效率和擴展性更高的算法。
5 結束語
經過數十年的研究，數據挖掘已成為一門理論日趨成熟、應用日趨廣泛的學科。全局和局部相結合的數據挖掘研究正在成為數據挖掘研究的熱點問題。雖然該問題的研究已取得較大進展，但仍有許多問題有待解決。當前，對于將全局模型和局部模式相結合進行挖掘的研究起步不久，還有大量的理論研究和應用工作需要進行，主要概括如下：a）粒度計算提供了全局和局部相集成的處理方法，利用該方法能夠進行更加有效的數據挖掘。同時，該問題還需要更加深入的理論研究。如何將現有的多種具體粒度方法融入同一框架及如何進行更加有效的推理計算等都是目前研究的熱點和難點問題。b）在挖掘的過程中，如何更好地集成局部模式信息以優化全局模型構造是當前機器學習和數據挖掘領域的難點問題。另一方面，先驗模型的引入能夠有效改進全局模型構造，基于圖模型的構造過程，從理論上研究將局部信息集成到全局模型構造中的方法。c)挖掘結果的全局表示減少了模式的數量，便于用戶理解。針對序列數據，如何利用生成模型的方法來研究模式的壓縮問題，從而獲取更加準確和快速的結果也正在引起研究者的高度關注。
參考文獻：
［1］ HAND D， MANNILA H， SMYTH P. Principles of data mining[M]. [S.l.]: MIT Press， 2001.
[2]MANNILA H.Local and global methods in data mining:basic techniques and open problems[C]//Proc of the 29th International Colloquium on Automata， Languages and Programming.Malaga，Spain:SpringerVerlag，2002:57-68.
[3]HOLLMEN J，SEPPANEN J K，MANNILA H.Mixture models and frequent sets:combining global and local methods for 01 data[C]//Proc of SIAM International Conference on Data Mining.San Francisco，CA:[s.n.]，2003.
[4]AGRAWAL R，IMIELINSKI T， SWAMI A. Mining association rules between sets of items in large databases[C]//Proc of ACM SIGMOD International Conference on Management of Data.Washington DC:ACM Press，1993:207-216.
[5]AGRAWAL R，SRIKANT R.Fast algorithms for mining association rules in large databases[C]//Proc of the 20th International Conference on Very Large Data Bases.Santiago de Chile:Morgan Kaufmann Publishers，1994:487-499.
[6]LIU B，HSU W，MA Y M.Integrating classification and association rule mining[C]//Proc of the 4th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:AAAI Press，1998:80-86.
[7]CHENG H， YAN X F， HAN J W， et al. Discriminative frequent pattern analysis for effective classification[C]//Proc of the 23th International Conference on Data Engineering.Istanbul， Turkey: IEEE Computer Society，2007:716725.
[8]AGRAWAL R，GEHRKE J， GUNOPULOS D，et al.Automatic subspace clustering of high dimensional data for data mining applications[C]//Proc of CM SIGMOD International Conference on Management of Data.Seattle， Washington DC:ACM Press， 1998:94105.
[9]CHENG C H，FU A W，ZHANG Y.Entropybased subspace clustering for mining numerical data[C]//Proc of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Diego， California:ACM Press，1999:84-93.
[10]GOLDENBERG A，MOORE A.Tractable learning of large Bayes net structures from sparse data[C]//Proc of the 21th International Conference on Machine learning.Banff， Alberta:ACM Press， 2004.
[11]WANG C，PARTHASARATHY S. Learning approximate MRFS from large transaction data[C]//Proc of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases.Berlin:SpringerVerlag，2006: 641-649.
[12]LIN T Y.Data mining and machine oriented modeling:a granular computing approach[J].Applied Intelligence，2000，13(2):113124.
[13]LIN T Y， LOUIE E. Data mining using granular computing: fast algorithms for finding association rules[C]//Proc ofData Mining， Rough Sets and Granular Computing.2002:23-45.
[14]LIN T Y.Mining associations by linear inequalities[C]//Proc of the 4th IEEE International Conference on Data Mining.Brighton:IEEE Computer Society，2004:154161.
[15]LIN T Y. Granular computing[R].[S.l.]:Announcement of the BISC Special Interest Group on Granular Computing，1997.
[16]ZADEH L A. Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J].Fuzzy Sets and Systems，1997，90(2):111127.
[17]YAO Y Y. Granular computing: basic issues and possible solutions[C]//Proc of International Joint Conference on Information Sciences.2000:186189.
[18]MANNILA H，TOIVONEN H. Multiple uses of frequent sets and condensed representations (extended abstract)[C]//Proc of the 2nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Portland， Oregon:AAAI Press，1996:189194.
[19]CHICKERING D M， HECHEMAN D. Fast learning from sparse data[C]//Proc of the 15th Conference on Uncertainty in Artificial Intelligence.Stockholm， Sweden: Morgan Kaufmann， 1999:109115.
[20]PAVLOV D， MANNILA H， SMYTH P.Beyond independence:probabilistic models for query approximation on binary transaction data[J].IEEE Trans on Knowledge and Data Engineering，2003，15(6):14091421.
[21]HECHERMAN D， GEIGER D， CHICKERING D M.Learning Bayesian networks:the combination of knowledge and statistical data[J].Machine Learning，1995，20(3):197-243.
[22]COOPER G F，HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data[J].Machine Learning，1992，9(4):309-347.
[23]GOLDENBERG A，MOORE A. Bayes net graphs to understand coauthorship networks[C]//Proc of the 3rd International Workshop on Link Discovery.Chicago， Illinois:ACM Press，2005:1-8.
[24]MANNILA H，MEEK C.Global partial orders from sequential data[C]//Proc of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Boston， Massachusetts:ACM Press，2000:161168.
[25]DEMPSTER A P， LAIRD N M， RUBIN D B. Maximum likelihood from incomplete data via the em algorithm[J].Journal of the Royal Statistical Society:Series B(Methodological)，1979，39(1):1-38.
[26]VALDES J，TARJAN R E， LAWLER E L. The recognition of series parallel digraphs[C]//Proc of Annual ACM Symposium on Theory of Computing， Pages.Atlanta， Georgia:ACM Press，1979:112.
[27]BAYARDO R J. Efficiently mining long patterns from databases[C]//Proc of ACM SIGMOD International Conference on Management of Data.Seattle， Washington DC:ACM Press，1998: 85-93.
[28]WANG J Y， LU Y， TZVETKOV P.TFP:an efficient algorithm for mining topk frequent closed itemsets[J].IEEE Trans on Knowledge and Data Engineering，2005，17(5):652-664.
[29]AFRATI F，GIONIS A，MANNILA H.Approximating a collection of frequent sets[C]//Proc of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Seattle:ACM Press，2004:1219.
[30]YAN X F，CHENG H，HAN J W，et al.Summarizing itemset patterns: a profilebased approach[C]//Proc of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.Chicago， Illinois:ACM Press， 2005: 314-323.
[31]PEI J， DONG G Z， ZOU W，et al.On computing condensed frequent pattern bases[C]//Proc of the 2nd IEEE International Conference on Data Mining.Maebashi City， Japan: IEEE Press， 2002:378.
[32]XIN D， HAN J W， YAN X F，et al.Mining compressed frequentpattern sets[C]//Proc of the 31th International Conference on Very Large Data Bases.Trondheim， Norway: VLDB Endowment，2005:709720.
[33]SIEBES A， VREEKEN J， LEEUWEN M V. Item sets that compress[C]//Proc of SIAM International Conference on Data Mining.Bethesda:[s.n.]，2006.
[34]GRUNWALD P. Advances in minimum description length，chapter minimum description length tutorial[M].[S.l.]:MIT Press，2005.
[35]CASASGARRIGA G. Summarizing sequential data with closed partial orders[C]//Proc of SIAM International Conference on Data Mining.Newport Beach， California:[s.n.]， 2005.
[36]PEI J， LIU J， WANG K，et al.Discovering frequent closed partial orders from strings[J].IEEE Trans on Knowledge and Data Engineering，2006，18(11): 14671481.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
