[發明專利]一種樹結構的挖掘系統及大型結構數據庫

在審

• 申請號: 201910966062.0
• 申請日: 2019-10-12
• 公開（公告）號: CN110765176A
• 公開（公告）日: 2020-02-07
• 發明（設計）人: 任薇;周揚
• 申請（專利權）人: 西南大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06K9/62
• 代理公司: 50230 重慶市信立達專利代理事務所(普通合伙)
• 代理人: 陳炳萍

本發明屬于數據挖掘技術領域，公開了一種樹結構的挖掘系統及大型結構數據庫。所述樹結構的挖掘系統包括：結構數據的預處理模塊、結構數據的挖掘模塊、規則的解釋和可視化模塊。所述結構數據的挖掘模塊包括：樹結構的擴展和生長模塊，樹結構的剪枝模塊。結構數據的預處理模塊，利用現在流行的樹(圖)的規范化技術來獲取結構數據和對結構數據預處理。結構數據的挖掘模塊，應用樹(圖)的擴展和生長技術、樹(圖)的剪枝技術等理論對結構數據挖掘，獲得相關的算法。規則的解釋和可視化模塊，采用統計分析技巧，結構數據挖掘原語，各種可視化技術，對規則進行評價，解釋和可視化。

技術領域

本發明屬于數據挖掘技術領域，尤其涉及一種樹結構的挖掘系統及大型結構數據庫。

背景技術

目前，最接近的現有技術：

作為數據挖掘的一個新的分支，結構數據挖掘的研究比一般的文本挖掘和Web挖掘的研究要晚，但近幾年已引起廣泛興趣。在國外，伊利諾伊大學香檳分校、加州大學洛杉磯分校、北卡羅來納大學、波士頓大學、澳大利亞南澳大利亞大學、德國慕尼黑大學、德國弗賴堡大學、德國馬格德堡大學、日本九州大學、希臘亞里斯多德大學等許多大學和研究所都有結構數據挖掘研究成果的報道。他們的研究目的主要是提高結構數據挖掘算法的執行效率，減少用戶需要管理和使用的頻繁子樹(圖)的數量，使得結構數據挖掘算法能夠應用于大型結構數據庫。而研究重點主要在以下三個方面：頻繁子樹(圖)的規范化、候選子樹(圖)的擴展和生長、樹(圖)的剪枝技術。

目前已提出的關于頻繁子樹的挖掘方法主要分為三類：①基于枚舉樹的算法(最多)，Zaki提出了基于枚舉樹的TreeMiner，在森林或者無根有序的樹結構數據庫中挖掘所有頻繁子樹，子樹保存了父結點與子結點的相互關系，該算法被用于構建XML數據的結構化分類器；Asai等人提出挖掘所有頻繁有根有序子樹的算法FREQT，并且提出了基于枚舉樹生長的挖掘所有頻繁有根無序子樹的算法；Y.Chi等人提出了有根無序樹的一個規范化模型，解決了多個有序樹對應同一個無序樹而帶來的樹同構問題，提出了基于枚舉樹生長的挖掘封閉和最大頻繁有根無序子樹的算法CMTreeMiner；MolFea是一個在統一的框架中集成層次遍歷搜索和解釋空間的數據庫，它在挖掘線性結構的模式中表現良好。②類Apriori算法，R.R.Muntz等人通過研究Free樹的索引技術得出了挖掘所有頻繁Free子樹的算法FreeTreeMiner for Free Trees；Ulrich Ruckert等人提出了挖掘滿足用戶指定約束的所有頻繁Free子樹的算法FreeTreeMiner for Graphs。③借鑒頻繁項挖掘中的FP－樹算法，構建了一種簡單存儲所有必需的信息的數據結構，這種數據結構用于頻繁子樹的挖掘，M.Dunham等人提出了挖掘最大頻繁子樹的算法PathJoin。PathJoin使用后剪枝技術，即在得到所有頻繁子樹后剪去不是最大的頻繁子樹。目前相關研究的焦點在頻繁子樹的規范化和封閉頻繁子樹的挖掘上。由于結構數據庫的海量，這些算法的挖掘效率還不夠高，頻繁子樹(圖)的數量通常隨樹(圖)的大小指數增長，這種情況在事務間高度相關的數據庫中尤為突出。

與國外相比，國內對數據挖掘和結構數據挖掘的研究都要稍晚，還沒有形成整體力量。目前，國內的結構數據挖掘的研究還處于起步和探索階段。結構數據的規范化技術、結構數據的擴展和生長技術、結構數據的剪枝技術的發展以及數據挖掘的發展使得結構數據挖掘成為可能并逐漸發展。但是大多數結構數據挖掘算法的執行效率并不高，給用戶的管理和使用上帶來了很大的不便。因此，提高結構數據挖掘算法的執行效率，減少用戶需要管理和使用的頻繁子樹(圖)的數量，使得挖掘算法能夠應用于大型結構數據庫，怎樣從結構數據庫中進行結構數據挖掘和發現知識作為近幾年結構數據挖掘的研究熱點和發展趨勢具有非常重要的學術意義和十分廣泛的實際意義。