Negative Sequential Pattern Mining
負向循序性樣式探勘 (Negative Sequential Pattern Mining)

  傳統的循序性樣式探勘著重於資料庫中出現的項目集所形成的序列關係,然而由未出現項目集所形成的序列關係可能也蘊藏許多重要的資訊。未出現項目集也被稱為負向項目集,包含至少一個負向項目集的循序性樣式則稱為負向循序性樣式,而相較之下傳統的循序性樣式則稱為正向循序性樣式(如圖)。藉由探勘出此種包含出現與未出現項目集的循序性樣式,我們可以獲得更多應用。我們著重在漸進式資料庫中探勘出正向與負向循序性樣式,並且賦予負向循序性樣式一個新的定義,使負向循序性樣式的發生頻率需多於對應正向循序性樣式的一定倍數,藉此說明循序性樣式中的負向項目集的必要性與非必要性。同時我們利用漸進式循序性樣式探勘中的特殊樹狀資料結構,加上不同的走訪方式,以增加探勘時的效率。

Mining Progressive Positive and Negative Sequential Patterns Simultaneously

  正向循序性樣式探勘著重於出現的項目,而負向循序性樣式探勘傾向於找出發生與未發生項目之間的關係。僅有少數的研究與負向循序性樣式探勘有關,而且在每一個研究中,對於負向循序性樣式的定義都不一致。以往使用在正向循序性樣式上的支持度閾值也一直被套用在負向循序性樣式上,使得較有趣的樣式不容易被找出。除此之外,正向循序性樣式探勘已經發展出漸增式循序性樣式探勘與漸進式循序性樣式探勘,而負向循序性樣式探勘卻仍只於靜態資料庫上執行。漸進式循序性樣式探勘會在資料庫中發掘最新的循序性樣式,而最新的樣式能夠提供更有價值的資訊。然而,以往的漸進式循序性樣式探勘演算法包含一些多餘的處理程序,並存在著可以加快效率的空間。

  在本研究中,我們意旨在結合負向循序性樣式探勘與漸進式循序性樣式探勘,並同時提出Propone演算法以達成有效率的探勘。我們提高正向漸進式循序性樣式的探勘速度,並且賦予負向循序性樣式一個新的定義,藉此找出更具意義與有趣的樣式。我們也另外提出一個剪枝策略和其他方法來減少候選負向循序性樣式的數量與計算時間。藉由修改以往的演算法並以其與Propone比較過後,實驗結果顯示Propone的效能優於其他演算法。

 Back