Apriori算法挖掘XML文檔

Question

我想通過Apriori算法從XML文檔中挖掘關聯規則。這樣做有兩種常用方法：1）將XML映射到關係格式並應用經典的Apriori，2）直接挖掘XML。我想使用後者，但有幾個問題。

研究後，我發現兩個不完整的解決方案：

這post在SO提供用於產生k項集

這paper在於提出了通過XQuery的一個模擬的Apriori的溶液（所提供的代碼是不完整）

請讓我知道你的想法和建議，我該如何做到這一點（兩種方法）？

更新：

根據所提到的文件的另一個版本，該數據集是這樣的：

<transactions> 
<transaction id="1"> 
<items> 
<item>a</item> 
<item>d</item> 
<item>e</item> 
</items> 
</transaction> 

<transaction id="2"> 
<items> 
<item>b</item> 
<item>c</item> 
<item>d</item> 
</items> 
</transaction> 

<transaction id="3"> 
<items> 
<item>a</item> 
<item>c</item> 
</items> 
</transaction> 

<transaction id="4"> 
<items> 
<item>b</item> 
<item>c</item> 
<item>d</item> 
</items> 
</transaction> 

<transaction id="5"> 
<items> 
<item>a</item> 
<item>b</item> 
</items> 
</transaction> 

</transactions> 

然後，功能如下

define function join(element $X, element $Y) returns element { 
let $items := (for $item in $Y 
where every $i in $X satisfies 
$i != $item 
return $item) 
return $X union $items 
} 

define function commonIts(element $X, element $Y) returns 
element { 
for $item in $X 
where some $i in $Y satisfies $i = $item 
return $item 
} 

define function removeIts(element $X, element $Y) returns 
element { 
for $item in $X 
where every $i in $Y satisfies $i != $item 
return $item 
} 

define function candidateGen(element $l) returns element { 
for $freqSet1 in $l 
let $items1 := $freqSet1//items/* 
for $freqSet2 in $l 
let $items2 := $freqSet2//items/* 
where $freqSet2 >> $freqSet1 and 
count($items1)+1 = count($items1 union $items2) 
and prune(join($items1,$items2), $l) 
return <items> 
{join($items1,$items2)} 
</items> 
} 

define function prune(element $X, element $Y) returns boolean 
{ 
every $item in $X satisfies 
some $items in $Y//items satisfies 
count(commonIts(removeIts($X,$item),$items/*)) 
= count($X) - 1 
} 

define function removeDuplicate(element $C) returns element 
{ 
for $itemset1 in $C 
let $items1 := $itemset1/* 
let $items :=(for $itemset2 in $C 
let $items2 := $itemset2/* 
where $itemset2>>$itemset1 and 
count($items1) = 
count(commonIts($items1, $items2)) 
return $items2) 
where count($items) = 0 
return $itemset1 
} 

define function getLargeItemsets(element $C, element $minsup, 
element $total, element $src) returns element { 
for $items in $C 
let $trans := (for $tran in $src 
where every $item1 in $items/* satisfies 
some $item2 in $tran/* 
satisfies $item1 = $item2 
return $tran) 
let $sup := (count($trans) * 1.00) div $total 
where $sup >= $minsup 
return <largeItemset> {$items} 
<support> {$sup} </support> 
</largeItemset> 
} 

define function apriori(element $l, element $L, element $minsup, 
element $total, element $src) returns element { 
let $C := removeDuplicate(candidateGen($l)) 
let $l := getLargeItemsets($C, $minsup, $total, $src) 
let $L := $l union $L 
return if (empty($l)) then 
$L 
else 
apriori($l, $L, $minsup, $total, $src) 
} 

let $src := document(「/transactions.xml」)//items 
let $minsup := 0.4 
let $items := (for $item in $src/* 
where $itemset = $item 
let $total := count($src) * 1.00 
let $C := distinct-values($src/*) 
let $l :=(for $itemset in $C 
return $item) 
let $sup := (count($items) * 1.00) div $total 
where $sup >= $minsup 
return <largeItemset> 
<items> {$itemset} </items> 
<support> {$sup} </support> 
</largeItemset>) 
let $L := $l 
return <largeItemsets> { apriori($l, $L,$minsup, $total, $src) } 
</largeItemsets> 

並計算規則文件，他們引入了這個表達式：

let $minconf := 1.00 
let $src := document(「/large.xml」)//largeItemset 
for $itemset1 in $src 
let $items1 := $itemset1/items/* 
for $itemset2 in $src 
let $items2 := $itemset2/items/* 
where count($items1) > count($items2) and 
count(commonIts($items1, $items2)) = 
count($items2) and $itemset1/support div 
$itemset2/support >= $minconf 
return <rule support =「{$itemset1/support}」 
confidence = 「{($itemset1/support*1.0) div 
($itemset2/support*1.0)}」> 
<antecedent> {$items2} </antecedent> 
<consequent> 
{removeItems($items1,$items2)} 
</consequent> 
</rule> 

現在，我面臨的最大挑戰是將這些功能集成在一起工作。

Answer 1

第一種方法會快很多。將數據僅預處理一次（處理XML代價很高），轉換成非常適合您算法的輸入格式！

關於查找源代碼的問題在這裏是焦點話題。嘗試解決這個問題，回過頭來提一些涉及您編寫的代碼的特定問題，並嘗試以簡潔的格式展示它們，以便以自包含的QA樣式很好地回答問題。

另請注意，上述嘗試使用Xquery實現Apriori時缺少一些構成Apriori算法貢獻的必要的必要的優化。對於一個真正可用的Apriori實現，您需要使用優化的數據結構將，您不能在XQuery中實現此目的。嘗試在一些經典數據集上運行此實現，並且它將只是死亡。使用Apriori進行擴展已經足夠困難，但使用XQuery來實現它卻是瘋狂之路 - 一個關鍵的挑戰就是保持內存使用率低，即使在C中！