[發(fā)明專利]提取具有意義的頻出項(xiàng)目集的系統(tǒng)、方法以及程序

有效

• 申請(qǐng)?zhí)枺?/td>: 201110216914.8
• 申請(qǐng)日: 2011-07-29
• 公開(kāi)（公告）號(hào): CN102456068A
• 公開(kāi)（公告）日: 2012-05-16
• 發(fā)明（設(shè)計(jì)）人: 吉田一星
• 申請(qǐng)（專利權(quán)）人: 國(guó)際商業(yè)機(jī)器公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京市中咨律師事務(wù)所 11247
• 代理人: 于靜;楊曉光

技術(shù)領(lǐng)域

本發(fā)明涉及從存儲(chǔ)分別包含具有一個(gè)或多個(gè)項(xiàng)目的項(xiàng)目集的多個(gè)記錄的數(shù)據(jù)庫(kù)提取具有意義的頻出項(xiàng)目集，尤其涉及通過(guò)適當(dāng)次數(shù)的頻度計(jì)算且適當(dāng)?shù)拇鎯?chǔ)器的使用量高效地提取這樣的項(xiàng)目集的技術(shù)。

背景技術(shù)

以往，研究了從大量存儲(chǔ)的數(shù)據(jù)中提取有用的指示的數(shù)據(jù)挖掘。其中，檢測(cè)成為對(duì)象的多個(gè)記錄(例如已發(fā)布的收據(jù)的履歷)中頻繁出現(xiàn)的項(xiàng)目(例如商品)組的技術(shù)稱為頻出模式挖掘，提出了多種方法。在頻出模式挖掘中，將滿足“項(xiàng)目集的頻度≥預(yù)定閾值(稱為“最小支持”)”的項(xiàng)目集定義為頻出項(xiàng)目集，提取頻出項(xiàng)目集的集合。

但是，雖然項(xiàng)目集的出現(xiàn)頻度高，但項(xiàng)目間不一定具有較深的關(guān)系。例如，在包含出現(xiàn)頻度高的項(xiàng)目的項(xiàng)目集的情況下，項(xiàng)目間沒(méi)有關(guān)系但其項(xiàng)目集頻出的可能性高。在項(xiàng)目間具有較深關(guān)系的情況下，該頻出項(xiàng)目集是沒(méi)有意義的項(xiàng)目集。此外，最小支持的值由用戶賦予，但一般而言，已知對(duì)實(shí)用的最小支持的值生成大量數(shù)量的頻出項(xiàng)目集。

于是，存在如下現(xiàn)有技術(shù)：導(dǎo)入閉頻出集合的概念進(jìn)行定義，提取滿足該定義的閉頻出項(xiàng)目集(參照非專利文獻(xiàn)1)。在此，所謂項(xiàng)目集Y閉頻出，是指滿足“Y頻出且對(duì)任意的Y≠Y′，Y的頻度Y＞Y′的頻度”。此外，也存在如下現(xiàn)有技術(shù)：擴(kuò)大閉頻出集合的上述定義，提取滿足“Y頻出且對(duì)任意的Y≠Y′，(Y的頻度×δ)＞Y′的頻度”的項(xiàng)目集(參照非專利文獻(xiàn)2)。

如果提取閉頻出的項(xiàng)目，則與項(xiàng)目集整體具有相同出現(xiàn)頻度的項(xiàng)目集的部分集合不會(huì)作為頻出項(xiàng)目集無(wú)用地提取。例如，假設(shè)在超市POS數(shù)據(jù)中出現(xiàn)500次項(xiàng)目集Y₁＝{齒粉、面包}，項(xiàng)目Y₂＝{齒粉、面包、啤酒}也出現(xiàn)了500次。在此情況下，作為閉頻出的項(xiàng)目集提取的僅是項(xiàng)目集Y?₂。但是，對(duì)于閉頻出的項(xiàng)目集，雖然項(xiàng)目間具有很深的關(guān)系，但即使具有閉頻出的概念，也無(wú)法提取具有意義的頻出項(xiàng)目集。

于是，需要提取在項(xiàng)目間具有較深關(guān)系的項(xiàng)目集的技術(shù)。作為這樣的現(xiàn)有技術(shù)，存在非專利文獻(xiàn)3和非專利文獻(xiàn)4。非專利文獻(xiàn)3和非專利文獻(xiàn)4通過(guò)基于相互信息量、平均信息量的方法，嘗試在三個(gè)以上的項(xiàng)目之間提取具有關(guān)聯(lián)的項(xiàng)目集。

但是，提出非專利文獻(xiàn)3和非專利文獻(xiàn)4的方法以成對(duì)比較為基礎(chǔ)。因此，對(duì)于通過(guò)這些手法提取的項(xiàng)目集可以保證的僅僅是在項(xiàng)目集內(nèi)的任意兩個(gè)項(xiàng)目之間具有較深關(guān)聯(lián)。

例如，假設(shè)對(duì)呼叫中心的通話記錄適用上述手法，提取了項(xiàng)目集{操作系統(tǒng)A、瀏覽器B、異常結(jié)束}。在此情況下，對(duì){操作系統(tǒng)A、瀏覽器B}、{瀏覽器B、異常結(jié)束}、{操作系統(tǒng)A、異常結(jié)束}各自保證較高的相關(guān)性。但是，不保證“不是其他操作系統(tǒng)而在操作系統(tǒng)A上、不是其他應(yīng)用程序而是使用瀏覽器B發(fā)生了異常結(jié)束”。如下所示的專利文獻(xiàn)1作為公開(kāi)相關(guān)的規(guī)則提取手法的背景技術(shù)列舉。

專利文獻(xiàn)1：日本特開(kāi)平8-287106號(hào)公報(bào)

非專利文獻(xiàn)1：M.Boley?et?al.，“EfficientDiscovery?of?Interesting?Patterns?Based?on?Strong?Closedness”，Statistical?Analysis?and?Data?Mining，Volume?2，Issue?5&ash；6，Pages?346-360，December?2009

非專利文獻(xiàn)2：J.Cheng?et?al.，“Sigma-tolerance?closed?frequent?itemsets”，ICDM，Proceedings?of?the?Sixth?InternationalConference?on?Data?Mining，pages?139&#8211；148，2006

非專利文獻(xiàn)3：Y.Ke?et?al.，“Mining?q?uantitativecorrelated?patterns?using?an?information-theoretic?approach”，Proceedings?ofthe?12th?ACM?SIGKDD?international?conference?on?knowledge?discoveryand?data?mining，pages?227&#8211；236，August?2006