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 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. 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 = estimated parameters for the data set π = user-specified precision threshold
![{\displaystyle {\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]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b05107c6229f4742559e14d40ff068b6d74f7c08)
使用 NBMiner 的第一步是安裝 NBMiner 包。此包具有三個依賴包：arules (http://cran.r-project.org/web/packages/arules/index.html)，它提供了表示、操作和分析交易資料和模式（頻繁項集和關聯規則）的基礎設施；Matrix (http://cran.r-project.org/web/packages/Matrix/index.html)，它是一類和方法，用於使用 Lapack 和 SuiteSparse 處理密集和稀疏矩陣以及對它們的操作；以及 lettice (http://cran.r-project.org/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)
它包含由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