TRIPS 樹探勘演算法的改進

Abstract

在處理大量資料時，將會需要一些特別的技巧來從資料中獲得比較有用的資訊，資料探勘（Data mining）便是一項從大量資料中尋找出隱藏在這些資料裡有用、相關資訊的技巧。在目前許多對於資料探勘的研究上，進展的方向也從探勘頻繁出現的物件集合逐漸朝向更加複雜的結構進行探勘，例如樹結構（tree）或圖（graph）等。 在本文中，我們所提到的這個探勘頻繁子樹的問題，在過去已經被證實了可用於許多廣範圍的應用上，像是生物資訊（bioinformatics）、XML處理、計算語言學（computational linguistics）和web使用率探勘上。TRIPS是一個從樹資料庫中探勘子樹的新演算法，這個演算法比起一些過去的演算法還快，並且可以很廣泛的用於針對嵌入或歸納子樹，而子樹可以是有標記、無標記、有序、無序等。本文中主要會針對TRIPS演算法對於嵌入、有序子樹和嵌入、無序子樹上提出改進的做法，在實驗結果上也可以看到我們的做法在速度上所獲得的提升。 在本文中，我們會先稍微介紹樹探勘演算法的概要與應用，然後說明介紹相關的基礎定義，再來詳細介紹一些有關的樹探勘演算法，並且之後會針對Shirsh Tatikonda提出的TRIPS [1] 演算法，提出我們改進的地方，以及在實驗上所驗證出來的結果。