我想通过Apriori算法从XML文档中挖掘关联规则。这样做有两种常用方法:1)将XML映射到关系格式并应用经典的Apriori,2)直接挖掘XML。我想使用后者,但有几个问题。Apriori算法挖掘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>
现在,我面临的最大挑战是将这些功能集成在一起工作。
不幸的是,你的问题不适合SO,因为它主要要求完整的代码来解决某些算法问题。我建议你自己尝试使用XQuery来编写这种算法,如果你没有“将这些功能集成在一起”,你就回过头来问自己,正如你自己所说的那样。 – dirkk
我正在研究,但是由于我是XQuery中的新成员,因此找到函数的不同部分和详细信息时有点困惑和复杂。 – Eilia