R 中的数据挖掘算法/频繁模式挖掘/arulesNBMiner

引言

本章将讨论在频繁项集挖掘中使用的一种技术。在许多情况下，人们对集合中两个或多个项目的共现感兴趣。确定哪些项目共现很重要，因为关联规则可以从频繁项集中提取 [1]。一个典型的应用示例是超市，在那里发现购买肉和啤酒的顾客也倾向于购买煤炭。因此，一个频繁项集将是肉-啤酒-煤炭，而关联规则将是，一般来说，购买肉和啤酒的顾客更有可能购买煤炭。

许多工作都处理了频繁项集挖掘的问题。它们中的大多数都表明了 min_support 阈值的需求，它是数据中的项集最小频率，通常由矿工用户定义。此外，这些研究的目标是挖掘满足 min_support 的完整频繁项集 [2]。应用最小支持导致了几个很少讨论或验证的假设。一个假设是项目在数据库中按照可能未知但稳定的过程出现，并且项目在数据库中以大致相似的频率出现。然而，在现实世界中，交易数据具有高度倾斜的频率分布，大多数项目出现频率较低，而只有其中一些项目出现频率较高。在发生这种现象的数据库中，有趣的模式无法找到，因为一些关联项目过于罕见，无法满足用户指定的最小支持 [3]。

一些算法（如 TFP）的开发方式使得用户无需确定 min_support。但是，他需要告知项集的最小大小 (min_l) 以及他希望挖掘的项集数量 (k)。此外，TFP 算法只挖掘频繁闭合项集。[2]。同样，用户有一个参数 (min_l) 应该在挖掘数据之前指定，这是一个微妙的决定。

因此，本章介绍了一种算法，该算法在 R 包中实现，并使用一个简单的随机模型（负二项式模型或 NB 模型）来估计最小支持，利用生成交易数据的过程的知识，并允许高度倾斜的频率分布。该包的名称是 arulesNBMiner，它是深度优先搜索算法的 Java 实现，用于挖掘 NB-精确规则的 NB-频繁项集 [4]。该算法利用其自身数据结构中包含的信息来估计最小支持。然后，它使用精度限制来估计每个 k-项集的 min_support，加上它以不同的最小支持计算的一个扩展。

待讨论的技术

算法

Function NBSelect$\left(l,\ L,\ n,\ {\tilde {k}},\ {\tilde {a}}',\ \pi \right)$
1. rmax = max(c.count) in L
2. rrescale = sum(c.count) in L
3. for each tuple [c,c.count] ∈ L do nobs [c.count]++
4. do
5. ${\text{precision}}={\frac {(1-\vert l\vert )P[R_{1}\geq p\;\vert \;k={\tilde {k}},\;a=r_{\text{rescale}}\cdot {\tilde {a}}']}{\sum _{r=p}^{r_{\text{max}}}n_{ob}s[r]}}$
6. while (precision ≥ π ∧ (p−−) > 0)
7. return {c| [c,c.count] ∈ L ∧ c.count > p}
where
l = the pattern for which candidate items are selected
L = a data structure which holds count information for items which co-occur with pattern l; 
we use tuples c, c.count , where c represents a candidate  item and c.count the count.
n = the total number of available items
${\tilde {k}}{\text{ and }}{\tilde {a}}'$ = estimated parameters for the data set
π = user-specified precision threshold

实现（使用模块和包的描述）

使用 NBMiner 的第一步是安装 NBMiner 包。此包具有三个依赖包：arules (https://cran.r-project.org.cn/web/packages/arules/index.html)，它提供了表示、操作和分析交易数据和模式（频繁项集和关联规则）的基础设施；Matrix (https://cran.r-project.org.cn/web/packages/Matrix/index.html)，它是一类和方法，用于使用 Lapack 和 SuiteSparse 处理密集和稀疏矩阵以及对它们的操作；以及 lettice (https://cran.r-project.org.cn/web/packages/lattice/index.html)，它是在贝尔实验室开发的一种用于数据可视化的框架。此外，用户必须在计算机上安装 Sun Java(TM) Development Kit (JDK) 6，因为 NBMiner 使用一个名为 rJava 的包，它是 JDK 的一部分。这必须安装在用户操作系统中。

依赖包的安装可以在 R 环境中使用函数“install.packages(“包名”)”执行。NBMiner 包的名称是 arulesNBMiner。

install.packages(“arulesNBMiner”)	

用户安装完必要的包后，必须加载它们。这可以使用函数“library(包名)”完成。

library(arulesNBMiner)	

但是，在展示如何使用 NBMiner 包之前，有必要展示如何加载数据。这里，我们使用 csv 格式的数据。在这种格式中，每行都是一笔交易，如下例所示

就业	教育	婚姻状况	职业	性别	帐户
私有	大学	分居	服务	女性	美国
私有	助理	未婚	运输	男性	牙买加
私有	高中毕业	离婚	文员	男性	美国
私有	学士学位	民事	维修	男性	美国
私有	大学	民事	行政	男性	美国
私有	高中毕业	民事	服务	男性	美国

在 R 环境中使用函数“read.table()”，我们可以加载数据。此函数创建一个“data.frame”对象。其语法为

object name<-read.table(“filename”, header=TRUE/FALSE,sep=”,”)

参数 header 指示数据是否有标题，而 sep 指示用于分隔元素的字符。之后，用户必须将此数据帧对象转换为交易对象。为此，他可以使用函数“as()”。其语法为

object name<-as(data frame object,”transactions”)

重要的是要注意，用户必须在使用带有参数 transaction 的 as 函数之前加载 NBMiner 包。此外，还有一种其他数据格式，一些 R 函数可以读取并将其转换为交易对象。用户可以使用二进制格式，如下例所示

1	1	0	0	0	1	0	0	0
1	0	1	0	0	0	1	0	0
1	0	0	1	0	0	0	1	0
1	0	0	0	1	0	0	0	1
1	1	0	0	0	0	0	0	1
1	0	0	1	0	0	0	0	1
1	0	0	0	1	0	0	0	1

这里，每行代表一笔交易，每列代表数据库中的一个词语。数字 1 表示该词语在该交易中存在，而 0 表示不存在。要读取此数据，用户可以首先使用函数“scan()”。它创建一个向量对象，其语法为

object name<-scan(“file name”,sep=”,”)

之后，有必要将向量对象转换为矩阵对象。这是使用函数“dim()”完成的。其语法为

dim(vector object)<-c(dim1,dim2) 

Dim1 和 Dim2 是用户想要创建的矩阵的维度。如果用户愿意，他可以使用函数“dimnames()”为矩阵的每一行和每一列命名。其语法为

dimnames(matrix object)<-list(pridim=c(names),segdim=c(names))

其中 pridim 是一个包含第一维名称的向量，而 segdim 是一个包含第二维名称的向量。最后，此对象可以使用函数“as()”转换为交易对象。其语法为

object name<-as(matrix object,”ItemMatrix”)

用户加载完包和数据后，有必要使用 NBMiner 的函数“NBMinerParameters()”创建参数对象。此函数读取数据并从中提取一些参数，这些参数将在下一步中使用。此函数的语法为

object name<-NBMinerParameters(data object, pi=#, theta=#, maxlen=#, minlen=#, trim=#, verb=TRUE/FALSE, plot=TRUE/FALSE, rules=TRUE/FALSE)
where: 
# = numbers
data object = the data as an object of class transaction
pi = precision threshold
theta = pruning parameter
maxlen = maximal number of items in found itemsets (default = 5)
minlen = minimum number of items in found itemsets (default = 1)
trim = fraction of incidences to trim off the tail of the frequency distribution of the data
verbose = use verbose output for the estimation procedure
plot = plot the model
rules = mine NB-precise rules instead of NB-frequent itemsets

用户执行此过程后，他就可以运行算法来挖掘他的数据。为此，将使用名为“NBMiner()”的函数。其语法为

object name<-NBMiner(data object, parameter=object parameter, control = list(verb=TRUE, debug=FALSE))

如果用户在创建参数对象时使用选项 rules=TRUE，则算法将挖掘 NB-精确规则。否则，相同的算法将挖掘 NB-频繁项集。

最后，我们总结了使用 NBMiner 包执行挖掘任务所需的命令，使用上面提到的第一个数据结构，如下所示

library(package name)
object name<-read.table(“filename”, header=TRUE/FALSE,sep=”,”)
object name<-as(data frame object,”transaction”)
object name<-NBMinerParameters(data object, pi=#, theta=#, maxlen=#, minlen=#, trim=#, verb=TRUE/FALSE, plot=TRUE/FALSE, rules=TRUE/FALSE)
object name<-NBMiner(data object, parameter=object parameter, control = list(verb=TRUE, debug=FALSE

可视化

要可视化“data.frame”对象中包含的数据信息，只需使用对象名称。这里，我们使用table作为对象名称

table = read.table("data",sep=",",header=TRUE)
table

#	就业	教育	婚姻状况	职业	性别	帐户
1	私有	大学	分居	服务	女性	美国
2	私有	助理	未婚	运输	男性	牙买加
3	私有	高中毕业	离婚	文员	男性	美国
4	私有	学士学位	民事	维修	男性	美国
5	私有	大学	民事	行政	男性	美国
6	私有	Hsgrad	民事	服务	美国

但是，当在“transactions”格式中使用相同的原理时，我们只有由“as()”函数生成的交易数量和项目

tableT = as(table,"transactions")
tableT
 transactions in sparse format with
 6 transactions (rows) and
 18 items (columns)

使用“inspect()”函数可视化转换为“transactions”格式的结果

inspect(tableT)

#	items	transactionID
1	{Employment=Private,Education=College,Marital=Separated,Occupation=Service,Sex=Female,Accounts=USA}	1
2	{Employment=Private,Education=Associate,Marital=Unmarried,Occupation=Transport,Sex=Male,Accounts=Jamaica}	2
(...)

要总结“transaction”格式中的数据信息，请使用“summary()”。

summary(tableT)
transactions as itemMatrix in sparse format with
6 rows (elements/itemsets/transactions) and
18 columns (items) and a density of 0.3333333 
most frequent items:
Employment=Private    Sex=Male    Accounts=USA 
        6                5            5 
Marital=Civil    Education=College  (Other) 
        3                2            15 
element (itemset/transaction) length distribution:
sizes
6 
6 
  Min.    1st Qu.  Median  Mean   3rd Qu.   Max. 
     6       6       6       6       6       6 
includes extended item information - examples:
       labels			variables    	levels
1  	Employment=Private 	Employment   	Private
2 	Education=Associate  	Education 	Associate
3  	Education=Bachelor  	Education  	Bachelor
includes extended transaction information - examples:
transaction		ID
1            		1
2             		2
3             		3

要查看转换为事务格式时生成的项目的标签，请使用“itemInfo()”

itemInfo(tableT)
	labels  		variables		levels
1	Employment=Private 	Employment      	Private
2    	Education=Associate  	Education    		Associate
3     	Education=Bachelor  	Education     		Bachelor
4	Education=College  	Education      		College
5	Education=HSgrad  	Education       	HSgrad
6	Marital=Civil    	Marital        		Civil
7	Marital=Divorced 	Marital     		Divorced
8	Marital=Separated    	Marital    		Separated
9	Marital=Unmarried    	Marital    		Unmarried
10   	Occupation=Clerical 	Occupation     		Clerical
11  	Occupation=Executive 	Occupation    		Executive
12	Occupation=Repair 	Occupation       	Repair
13    	Occupation=Service 	Occupation      	Service
14	Occupation=Transport 	Occupation    		Transport
15	Sex=Female       	Sex       		Female
16	Sex=Male        	Sex         		Male
17	Accounts=Jamaica   	Accounts      		Jamaica
18	Accounts=USA   		Accounts 		USA

使用“labels()”仅查看项目和交易的标签

labels(tableT)
$items
[1]	"Employment=Private"	"Education=Associate"		"Education=Bachelor"   
[4]	"Education=College"     "Education=HSgrad"      	"Marital=Civil"        
[7]	"Marital=Divorced"      "Marital=Separated"  		"Marital=Unmarried"    
[10]	"Occupation=Clerical"   "Occupation=Executive"  	"Occupation=Repair"    
[13]	"Occupation=Service"    "Occupation=Transport"  	"Sex=Female"           
[16]	"Sex=Male"              "Accounts=Jamaica"      	"Accounts=USA"
$transactionID
[1] "1" "2" "3" "4" "5" "6"

要查看NB挖掘结果，请使用上面提到的针对“transactions”数据的相同命令

paramA <- NBMinerParameters(tableT, trim = 0.01, pi = 0.999, theta = 0.8, rules = TRUE, plot = FALSE, verbose = FALSE, minlen=3, maxlen=5)
tableNB <- NBMiner(tableT, parameter = paramA, control = list(verb = FALSE, debug=FALSE))
inspect(head(tableNB))
	lhs                     		rhs		                precision
1	{Education=HSgrad, Sex=Male}       	=> {Employment=Private}    	0.9991467
2	{Sex=Male, Accounts=USA} 		=> {Marital=Civil}		0.9999421
3	{Sex=Male, Accounts=USA} 		=> {Education=HSgrad}      	0.9977636
4	{Education=College, Accounts=USA} 	=> {Employment=Private}		0.9982934
5	{Marital=Civil, Accounts=USA} 		=> {Sex=Male}              	0.9999752
6	{Employment=Private, Sex=Male}		=> {Accounts=USA}		0.9999948

其中“lhs”是规则的前提，而“rhs”是规则的结果。

我们还可以使用“image()”函数在空间中显示数据分布

image(tableNB)

文件：ImageFunction.png

案例研究

场景

它包含由Graham Williams（Rattle的开发者）创建的，并随Rattle一起提供的合成数据。引用Rattle文档：“它包括2,000个虚构的客户，他们已接受审计，可能是为了核查他们申报的退税金额是否符合规定。对于每种情况，都会记录结果（纳税人的申报是否需要调整），以及由此产生的任何调整金额。”

输入数据不再存在，无法下载

可在 http://cs.anu.edu.au/Student/comp3420/mining/audit.csv 上获取。

执行

table = read.table("audit.csv",sep=",",header=TRUE)
tableT = as(table,"transactions")
paramA = NBMinerParameters(tableT, trim = 0.01, pi = 0.999, theta = 0.8, rules = TRUE, plot = FALSE, verbose = FALSE, minlen=3, maxlen=5)
transNB = NBMiner(tableT, parameter = paramA, control = list(verb = FALSE, debug=FALSE))

输出

transNB
set of 18158 rules 

tableNB = as(transNB,"data.frame")
write.table(tableNB,file="auditNB.csv",sep=",")

分析

rules	consequent	precedent A	precedent B	precedent C	precedent D
92	Accounts=China	Employment=PSState	Education=Master	Occupation=Professional
4721	Accounts=China	Employment=PSState	Education=Master
4762	Accounts=China	Employment=PSState	Occupation=Professional
4857	Accounts=China	Education=Master	Marital=Civil	Occupation=Professional	Sex=Male
5871	Accounts=China	Education=Master	Occupation=Professional
6131	Accounts=China	Marital=Civil	Occupation=Professional
10269	Accounts=China	Education=Master	Occupation=Professional	Sex=Male
10386	Accounts=China	Education=Master	Marital=Civil	Occupation=Professional
14791	Accounts=China	Marital=Civil	Occupation=Professional	Sex=Male

根据以上数据，我们可以注意到，当婚姻状态为“民事”且“职业”为“专业”时，我们有一个“中国”账户。

参考资料

• [1] Mohammed j. Zaki 和 Wagner Meira Jr. 数据挖掘算法基础。第11章 - 项目集挖掘，74-93
• [2] Jianyong Wang、Jiawei Han、Ying Lu 和 Petre Tzvetkov。TFP：一种用于挖掘 Top-K 频繁闭合项目集的有效算法。IEEE 知识与数据工程汇刊，17(5):652-665，2005 年 5 月
• [3] Michael Hahsler。从交易数据中挖掘关联的基于模型的频率约束。数据挖掘与知识发现，13(2):137-166，2006 年 9 月。
• [4]http://cran.fiocruz.br/web/packages/arulesNBMiner/index.html