R 中的資料探勘演算法/序列挖掘/SPADE
頻繁序列挖掘用於發現一組在物件之間共享的模式，這些物件之間具有特定順序。例如，一家零售商店可能擁有一個交易資料庫，該資料庫指定每個客戶在一段時間內購買了哪些產品。在這種情況下，商店可以使用頻繁序列挖掘來發現 40% 的購買了《指環王》第一卷的人在一個月後回來購買了第二卷。此類資訊可用於支援定向廣告活動或推薦系統。
另一個可以使用頻繁序列挖掘的應用領域是資訊檢索系統中的 Web 點選日誌分析，在這種情況下，系統性能可以透過分析使用者在搜尋或瀏覽特定資訊時所經歷的互動序列來改進。當我們考慮到工業搜尋引擎以查詢日誌形式獲得的海量資料時，這種用法就變得尤為明顯。據報道，僅 Google 在 2008 年 12 月就回答了 54.2 億次查詢（Telecom Paper，2009 年）
在生物學中，頻繁序列挖掘可用於提取隱藏在 DNA 序列中的資訊。由於遺傳突變和進化（Li 等人，2007 年），生物學中的序列資料庫通常龐大且複雜。例如，頻繁序列挖掘可用於提取可能決定遺傳狀況發展的模式。
序列 α 是事件的有序列表 <a1,a2,...,am>。事件是非空無序的專案集 ai ⊆ i1,i2,...,ik。序列 α = <a1,a2,...,am> 是 β = < b1, b2,...,bn > 的子序列，當且僅當存在 i1,i2,...,im 使得 1 ≤ i1 < i2 < ... < im ≤ n 且 a1 ⊆ bi1，a2 ⊆ bi2 且 am ⊆ bim。給定一個序列資料庫 D = s1,s2,...,sn，序列 α 的支援度是 D 中包含 α 作為子序列的序列數量。如果 α 的支援度大於閾值 minsup，則 α 是頻繁序列（Peng 和 Liao，2009 年）。
頻繁序列挖掘的一種演算法是 SPADE（使用等價類的順序模式發現）演算法。它使用垂直 id-list 資料庫格式，其中我們將每個序列與其出現的物件列表相關聯。然後，可以使用 id-list 上的交集有效地找到頻繁序列。該方法還減少了資料庫掃描次數，從而也減少了執行時間。
SPADE 的第一步是計算 1-序列的頻率，即只有一個專案的序列。這是在一次資料庫掃描中完成的。第二步包括計算 2-序列。這是透過將垂直表示轉換為記憶體中的水平表示來完成的，並使用二維矩陣計算每對專案的序列數量。因此，此步驟也可以在一次掃描中執行。
然後可以透過使用它們的 id-list 連線 (n-1) 序列來形成後續的 n-序列。id-list 的大小是專案出現的序列數量。如果此數字大於 minsup，則該序列是頻繁的。當不再能找到頻繁序列時，演算法停止。該演算法可以使用廣度優先搜尋或深度優先搜尋方法來查詢新序列（Zaki，2001 年）
第一步是安裝 arulesSequences 包（Buchta 和 Hahsler，2010 年）。
> install.packages("arules")
> install.packages("arulesSequences")
為了說明 CSPADE 的使用方法，我們將使用 arulesSequence 包中可以找到的示例檔案。此檔案列在下面
$ cat /usr/local/lib/R/site-library/arulesSequences/misc/zaki.txt 1 10 2 C D 1 15 3 A B C 1 20 3 A B F 1 25 4 A C D F 2 15 3 A B F 2 20 1 E 3 10 3 A B F 4 10 3 D G H 4 20 2 B F 4 25 3 A G H
zaki.txt 檔案中的每一行都是一個事件。第一列是序列 ID，即此事件所屬的序列。第二列是事件時間戳，即事件發生的時刻。第三列是事件中專案的數量 n，後面跟著 n 個額外的列，每列對應一個專案。
首先，我們需要載入必要的包
> library(Matrix) > library(arules) > library(arulesSequences)
要讀取 zaki.txt 檔案，請發出以下命令
> x <- read_baskets(con = system.file("misc", "zaki.txt", package = "arulesSequences"), info = c("sequenceID","eventID","SIZE"))
> as(x, "data.frame")
items sequenceID eventID SIZE
1 {C,D} 1 10 2
2 {A,B,C} 1 15 3
3 {A,B,F} 1 20 3
4 {A,C,D,F} 1 25 4
5 {A,B,F} 2 15 3
6 {E} 2 20 1
7 {A,B,F} 3 10 3
8 {D,G,H} 4 10 3
9 {B,F} 4 20 2
10 {A,G,H} 4 25 3
接下來，我們執行 CSPADE 演算法
> s1 <- cspade(x, parameter = list(support = 0.4), control = list(verbose = TRUE))
請注意，我們使用 zaki 物件中包含的資料執行了 cpade 演算法。我們將支援引數設定為 0.4，並指示演算法顯示詳細輸出。
演算法輸出將如下所示
preprocessing ... 1 partition(s), 0 MB [0.046s] mining transactions ... 0 MB [0.022s] reading sequences ... [0.07s] total elapsed time: 0.138s
我們可以使用命令 summary 和 as 來檢視結果
cspade> summary(s1)
set of 18 sequences with
most frequent items:
A B F D (Other)
11 10 10 8 28
most frequent elements:
{A} {D} {B} {F} {B,F} (Other)
8 8 4 4 4 3
element (sequence) size distribution:
sizes
1 2 3
8 7 3
sequence length distribution:
lengths
1 2 3 4
4 8 5 1
summary of quality measures:
support
Min. :0.5000
1st Qu.:0.5000
Median :0.5000
Mean :0.6528
3rd Qu.:0.7500
Max. :1.0000
mining info:
data ntransactions nsequences support
x 10 4 0.4
cspade> as(s1, "data.frame")
sequence support
1 <{A}> 1.00
2 <{B}> 1.00
3 <{D}> 0.50
4 <{F}> 1.00
5 <{A,F}> 0.75
6 <{B,F}> 1.00
7 <{D},{F}> 0.50
8 <{D},{B,F}> 0.50
9 <{A,B,F}> 0.75
10 <{A,B}> 0.75
11 <{D},{B}> 0.50
12 <{B},{A}> 0.50
13 <{D},{A}> 0.50
14 <{F},{A}> 0.50
15 <{D},{F},{A}> 0.50
16 <{B,F},{A}> 0.50
17 <{D},{B,F},{A}> 0.50
18 <{D},{B},{A}> 0.50
此輸出顯示 (1) 最頻繁的孤立專案的列表 (A、B、..)，(2) 在事件中出現的專案的最頻繁集的列表（稱為元素），(3) 專案集大小的分佈，(4) 序列中事件數量的分佈（稱為序列長度），(5) 最小值、最大值、平均值和中位數支援值，以及 (6) 按其支援值排序的已挖掘頻繁序列集。
在本案例研究中，我們分析了 CSPADE 演算法在標籤推薦問題中的應用。標籤是在 Web 2.0 環境下使用者為專案分配的關鍵詞。標籤推薦系統用於向用戶推薦新標籤，旨在增強其瀏覽體驗並豐富專案描述。本案例研究中使用的資料集是從 Delicious 收集的，使用其公共時間線，該時間線顯示了系統所有使用者在給定時間段內的書籤。執行了 SPADE 演算法，並將在下面的討論中介紹一些結果。
本案例研究中使用的資料集是從 Delicious 收集的，時間為 2009 年 10 月。我們定期收集 Delicious 公共時間線，該時間線顯示了系統所有使用者的書籤。每個書籤包含一個使用者、被書籤的 URL 以及使用者選擇用來描述 URL 的一組標籤。
我們展示了一些書籤示例
gmenezes http://www.traderslog.com/forum/ 5 education investment forex CFD trading gmenezes http://bikebins.com/index.html 6 pannier bike bicycle cycling bikes commuting osvaldo http://www.noycefdn.org/ecrwresources.php 6 literacy math foundation education webdesign professionaldevelopment
在此示例中，使用者 gmenezes 已將 URL http://www.traderslog.com/forum/ 設為書籤，並使用 5 個標籤來描述其內容：education investment forex CFD trading。
公共時間線以時間順序顯示系統書籤，因此我們可以獲得特定使用者的書籤序列。我們可以使用這些序列作為 CSPADE 演算法的輸入。在這種情況下，每個書籤都是一個事件，每個標籤都是一個專案。換句話說，我們將挖掘時間模式，目的是生成規則，這些規則可以透過利用群體智慧來預測特定使用者的有用標籤。
在將演算法應用於資料之前，我們必須對原始資料進行一些預處理。首先，我們提取了一個樣本，該樣本包含 31,289 個順序書籤。接下來，我們執行資料清理和重複項刪除。最後，我們得到了 7,559 個順序書籤。我們將每個使用者的書籤分組為序列，並將每個單獨的書籤分組為事件。例如，上面的例子產生
1 1 5 education investment forex CFD trading 1 2 6 pannier bike bicycle cycling bikes commuting 2 1 6 literacy math foundation education webdesign professionaldevelopment
可以使用的資料集可以從 這裡 下載。
我們在實驗中使用了上面描述的資料集。要執行演算法，我們首先執行 read_baskets() 從磁碟將資料集檔案載入為時間交易資料。請注意，我們需要載入所需的庫（如上所述）。
n <- read_baskets(con = system.file("misc", "delicious.sequence", package = "arulesSequences"), info = c("sequenceID","eventID","SIZE"))
我們可以使用命令 summary() 檢視資料統計資訊
> summary(n)
transactions as itemMatrix in sparse format with
7559 rows (elements/itemsets/transactions) and
7496 columns (items) and a density of 0.0004482878
most frequent items:
design tools blog webdesign inspiration (Other)
469 301 233 229 220 23949
element (itemset/transaction) length distribution:
sizes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2283 1432 1172 825 560 343 230 273 171 100 60 34 25 14 5 5
17 18 19 20
5 7 8 7
Min. 1st Qu. Median Mean 3rd Qu. Max.
1.00 1.00 3.00 3.36 4.00 20.00
includes extended item information - examples:
labels
1 |
2 -
3 ,
includes extended transaction information - examples:
sequenceID eventID SIZE
1 1 1 2
2 2 1 5
3 3 1 3
接下來，我們執行 cspade() 來生成規則。我們將支援度設定為 0.002 以獲得更多模式。
s1 <- cspade(n, parameter = list(support = 0.002), control = list(verbose = TRUE))
在本資料集中使用更高的支援級別不會生成任何規則，並可能導致非直觀的錯誤。例如，如果將支援度設定為 0.1，系統將輸出
> s1 <- cspade(n, parameter = list(support = 0.1), control = list(verbose = TRUE)) parameter specification: support : 0.1 maxsize : 10 maxlen : 10 algorithmic control: bfstype : FALSE verbose : TRUE summary : FALSE preprocessing ... 1 partition(s), 0.18 MB [0.05s] mining transactions ... can't open data file: No such file or directory Error in cspade(n, parameter = list(support = 0.1), control = list(verbose = TRUE)) : system invocation failed
我們可以透過發出命令 as() 來檢視生成的規則。
as(s1, "data.frame")
(...)
845 <{webdesign},{design}> 0.004675877
846 <{inspiration,webdesign},{design}> 0.001912859
847 <{design,webdesign},{design}> 0.004250797
848 <{design,typography},{design}> 0.002337938
849 <{design,tools},{design}> 0.002337938
850 <{inspiration},{inspiration},{design}> 0.001912859
851 <{inspiration},{design},{design}> 0.002125399
852 <{design,inspiration},{design}> 0.004675877
853 <{design},{inspiration},{design}> 0.001912859
854 <{inspiration,art},{design}> 0.001912859
855 <{design,inspiration},{inspiration},{design}> 0.001912859
856 <{design},{design,inspiration},{design}> 0.001912859
857 <{design},{design},{design}> 0.004250797
858 <{design,blog},{design}> 0.002337938
859 <{design,art},{design}> 0.002550478
860 <{design},{design},{design},{design}> 0.002337938
861 <{design},{design,blog}> 0.001912859
862 <{design,art,blog}> 0.001912859
863 <{design},{design,art}> 0.002763018
864 <{art},{design,art}> 0.002125399
865 <{culture,art}> 0.001912859
866 <{css},{css}> 0.001912859
867 <{design},{css}> 0.002125399
868 <{blog,blogs}> 0.003400638
869 <{blog,blogging}> 0.001912859
(...)
要檢視完整的規則集，請從 這裡 下載。
我們觀察到 CSPADE 從使用者行為中找到了許多瑣碎的序列。例如，它找到了許多單一序列，例如 <{design}>、<{ajax}>、<{css}> 等。這些單一序列確實經常使用，但在特定應用（標籤推薦）中可能沒有用。
此外，還發現了其他瑣碎的序列，例如 <{design}.{design}> 和 <{webdesign},{design}>。這些序列表明相同的使用者往往會隨後書籤相同主題的頁面。但是，也發現了一些有趣的模式。我們可以引用 <{library},{books}>、<{javascript},{ajax}> 和 <{video},{youtube}>。
我們還可以觀察到，許多頻繁模式與 design、art 和 web_development 相關。正如 這裡 所示，這些標籤也是整個 Delicious 系統中最受歡迎的標籤。
- ^ Buchta, C.、Hahsler, M.，2010 年。“arulesSequences：挖掘頻繁序列”。R 包版本 0.1-11。 http://CRAN.R-project.org/package=arulesSequences
- ^ Li, K.-C.、Chang, D.-J.、Rouchka, E. C.、Chen, Y. Y.，2007 年。“使用合理的神經網路進行生物序列挖掘及其在內含子/外顯子邊界預測中的應用”。在：CIBCB。IEEE，第 165-169 頁。
- ^ Peng, W.-C.、Liao, Z.-X.，2009 年。“跨多個序列資料庫挖掘順序模式”。Data Knowl. Eng. 68（10），1014-1033。
- ^ 電信論文，2009 年 1 月。“Google 查詢量”。
- ^ Zaki, M. J.，2001 年。“Spade：一種用於挖掘頻繁序列的有效演算法”。在：機器學習。第 42 卷。第 31-60 頁。