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 页。