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

在審

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

1.一種樹結構的挖掘系統，其特征在于，所述樹結構的挖掘系統包括：結構數據的預處理模塊、結構數據的挖掘模塊、規則的解釋和可視化模塊；

所述結構數據的挖掘模塊包括：樹結構的擴展和生長模塊，樹結構的剪枝模塊；

結構數據的預處理模塊，利用現在流行的樹的規范化技術獲取結構數據和對結構數據預處理；

結構數據的挖掘模塊，應用樹的擴展和生長技術、樹的剪枝技術理論對結構數據挖掘，獲得相關的算法；

規則的解釋和可視化模塊，采用統計分析技巧，結構數據挖掘原語，各種可視化技術，對規則進行評價，解釋和可視化。

2.如權利要求1所述的樹結構的挖掘系統，其特征在于，所述結構數據的預處理模塊對樹結構規范化和預處理，包括樹結構的定義和標記、有根無序樹的深度優先編碼、樹結構的規范化。

3.如權利要求1所述的樹結構的挖掘系統，其特征在于，結構數據的挖掘模塊對樹結構擴展和生長，包括封閉頻繁子樹和最大頻繁子樹的概念和性質、樹結構的最右路徑擴展、擴展表的得到和增長、非封閉頻繁子樹的生長。

4.如權利要求1所述的樹結構的挖掘系統，其特征在于，結構數據的挖掘模塊對樹結構剪枝，包括非頻繁樹的超樹的剪枝。

5.一種如權利要求1所述的樹結構的挖掘系統的構建方法，其特征在于，所述樹結構的挖掘系統的構建方法為：

利用現在流行的樹的規范化技術來獲取結構數據和對結構數據的預處理；應用樹的擴展和生長技術、樹的剪枝技術等理論對結構數據挖掘進行研究，獲得相關的算法；采用統計分析技巧，結構數據挖掘原語，各種可視化技術，對規則進行評價，解釋和可視化。

6.如權利要求5所述的樹結構的挖掘系統的構建方法，其特征在于，所述樹結構的挖掘系統的構建方法還包括：樹的編碼、生成候選子樹、覆蓋模式挖掘；

所述樹的編碼的具體技術實現為：

(1)采用寬度孩子數編碼，用寬度優先算法來遍歷樹；寬度孩子數編碼在字符串編碼的基礎上記錄了樹中每個結點的索引以及其孩子結點的索引，進而將計算候選子樹支持度操作的時間復雜度降到了O(n)；

(2)在寬度孩子數編碼中，樹中的每個結點用三元組(ind(v)，ran(v)，flg(v))三元組表示，其中ind(v)表示結點v在樹的寬度優先序列中的位置，c_ran(v)表示結點v的孩子的索引范圍，flg(v)表示結點v的標簽；

(3)按照寬度優先遍歷得到的三元組序列就是寬度孩子數編碼序列；對于樹中具有兄弟關系的結點按照其標簽flg(v)的字典順序進行排序；

所述生成候選子樹的具體技術實現為：通過最大前綴編碼相同的樹拓撲結構，生成候選子樹的集合；

所述覆蓋模式挖掘的具體技術實現為：采用頻繁子序列挖掘中的δ-覆蓋概念，對候選子樹進行進一步挖掘。