Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

1609 lines (1233 sloc) 33.311 kb
#LyX 1.6.5 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\begin_preamble
\setcounter{page}{0}
\end_preamble
\use_default_options true
\language dutch
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize a4paper
\use_geometry false
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\secnumdepth 1
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\author ""
\author ""
\end_header
\begin_body
\begin_layout Title
Project data mining voor informatica
\end_layout
\begin_layout Author
Wim Leers
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\shape italic
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\begin_inset Newline newline
\end_inset
\end_layout
\begin_layout Date
Universiteit Hasselt
\begin_inset Newline newline
\end_inset
Academiejaar 2009-2010
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
thispagestyle{empty}
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Newpage clearpage
\end_inset
\begin_inset CommandInset toc
LatexCommand tableofcontents
\end_inset
\begin_inset Newpage clearpage
\end_inset
\end_layout
\begin_layout Section
Aanpak implementatie
\end_layout
\begin_layout Standard
Ik heb er voor gekozen om het project in de programmeertaal C++ te schrijven,
omdat ook de running time van de implementatie van belang is.
Daarbij heb ik niet de typische STL-containers (
\family typewriter
vector
\family default
,
\family typewriter
map
\family default
en
\family typewriter
set
\family default
) gebruikt, maar heb ik de container types van Qt gebruikt (
\family typewriter
QList
\family default
,
\family typewriter
QHash
\family default
en
\family typewriter
QSet
\family default
) omdat deze veel beter gedocumenteerd zijn.
Ook voorziet Qt een zeer handig
\family typewriter
foreach
\family default
keyword, waarmee je eenvoudig kan itereren over de items in de containers,
zodat je niet iedere keer opnieuw dezelfde paar regels code moet herhalen.
\end_layout
\begin_layout Standard
Bovendien heb ik ook het signal/slot mechanisme van Qt aangewend om geparste
transacties door te geven vanuit de parser naar de klasse die deze transacties
verwerkt.
Het signal/slot mechanisme is een veralgemening van het principe van de
callback functie.
Zoals wel algemeen bekend is, zijn C++ callbacks (dus naar een method van
een object) een absolute hel, en ook dit werd vereenvoudigd dankzij het
gebruik van Qt.
\end_layout
\begin_layout Standard
Om de performance te maximaliseren en geheugengebruik te minimaliseren,
heb ik ervoor gekozen om telkens zo min mogelijk data door te geven.
Zo wordt bijvoorbeeld voor iedere combinatie van een item name (ook wel
attribute name genoemd) en een quantity, een unieke item ID gegenereerd.
In alle berekeningen wordt enkel naar de item ID gekeken.
De mapping van item ID naar item name en quantity wordt bij het parsen
van de data set opgeslagen en pas bij het tonen van de resultaten weer
gebruikt.
\end_layout
\begin_layout Standard
Om andere discrete datatypes te ondersteunen moet enkel de opgeslagen waarde
voor de mapping aangepast worden: in plaats van item ID naar item name
en quantity bijvoorbeeld item ID naar string.
Continuë data zou eerst gediscreteerd moeten worden, waarna hetzelfde van
toepassing is.
\end_layout
\begin_layout Standard
Tevens wordt van zo minimalistisch mogelijke datatypes gebruik gemaakt,
zo wordt een item ID in een 16-bit unsigned integer opgeslagen om geheugengebru
ik nog verder te minimaliseren.
Het gevolg is wel dat slechts 65535 verschillende items ondersteund worden.
Dit kan aangepast worden in
\family typewriter
typedefs.h
\family default
— waar alle gebruikte data types gedefinieerd worden — door te veranderen
naar een 32-bit of zelfs 64-bit unsigned integer.
\end_layout
\begin_layout Standard
Daarnaast heb ik ook handig gebruik gemaakt van
\family typewriter
qDebug()
\family default
, waarmee je debug output kan definiëren die automatisch weggecompileerd
wordt wanneer je een release build maakt.
Om custom data types te kunnen weergeven d.m.v.
\family typewriter
qDebug()
\family default
moesten er overeenkomstige streaming output operators gedefinieerd worden
en dit heb ik dan ook gedaan.
Ook deze worden niet meegecompileerd in het geval van een release build
d.m.v.
defines.
\end_layout
\begin_layout Section
Algoritmes
\end_layout
\begin_layout Standard
Voor het minen van frequent itemsets heb ik gekozen voor het FP-growth algoritme.
Voor het minen van quantitative association rules heb ik het Apriori algoritme
gebruikt.
Voor regels van type A (zoals in de opgave gedefinieerd) zijn er geen verdere
aanpassingen nodig dankzij het feit dat ik iedere combinatie van item name
en quantity een unieke item ID geef en enkel hiermee verder reken.
\end_layout
\begin_layout Standard
Voor regels van type B en C wordt één en hetzelfde algoritme gebruikt.
De gevonden frequent itemsets voor regels van type A worden gemerged indien
hun namen overeenkomen en hun quantities een aaneengesloten reeks getallen
vormen (dus: een interval).
Uit deze gemergde frequente itemsets worden vervolgens association rules
gemined, met precies dezelfde code als voor regels van type A.
\begin_inset Newline newline
\end_inset
Ik vond het persoonlijk een stuk duidelijker (en accurater) om intervallen
te tonen van het type
\begin_inset Formula $[x,y]|x,y\in\mathbb{N}$
\end_inset
in plaats van het type
\begin_inset Formula $\{]0,x],[x,\infty[\}|x\in\mathbb{N}$
\end_inset
(wat een voorstelling is die synoniem is met wat in de opgave beschreven
staat).
Een neveneffect is natuurlijk dat de berekeningen voor regels van types
B en C hetzelfde zijn.
Het is nog steeds perfect mogelijk om regels van type B en C zoals in de
opgave te
\emph on
interpreteren
\emph default
uit de intervallen, maar zo kan tenminste de foutenmarge/ruwheid van schatting
zelf gekozen worden.
\end_layout
\begin_layout Subsubsection*
FP-growth-tiny
\end_layout
\begin_layout Standard
Tijdens het schrijven van het verslag, weken nadat ik mijn FP-tree implementatie
had voltooid, stuitte ik toevallig op de paper
\emph on
A Space Optimization for FP-Growth, Eray Özkural and Cevdet Aykanat, Department
of Computer Engineering, Bilkent University 06800 Ankara, Turkey
\emph default
, waarin zij een geoptimaliseerde versie van FP-growth voorstellen, die
ze FP-growth-tiny hebben gedoopt.
In plaats van complexe operaties uit te voeren op bomen, halen zij gewoon
paden uit de boom, stellen deze voor als transacties, en voegen deze in
in een nieuwe boom.
Dit is een stuk minder complex en daardoor sneller.
Dit is
\emph on
precies
\emph default
hoe ik het geïmplementeerd had! Ik vond het een triviale en logische optimalisa
tie, die de implementatie zelfs vereenvoudigde.
Daarom vermeld ik overal
\begin_inset Quotes eld
\end_inset
FP-growth
\begin_inset Quotes erd
\end_inset
, omdat ik niet realiseerde dat ik het algoritme zodanig anders had geïmplemente
erd.
\end_layout
\begin_layout Standard
Ik ben nog verder gegaan dan hen: zij slaan hun
\emph on
symbolen
\emph default
(die ik
\emph on
item names
\emph default
noem) op in iedere node, terwijl ik enkel een 16-bit int opsla (wat ik
een
\emph on
item ID
\emph default
noem).
In hun conclusie vermelden ze dat ze 2.4 keer minder geheugen nodig hebben
en 28.5% keer sneller zijn dan het originele FP-growth algoritme.
Hopelijk is dat voor mijn implementatie dan ook het geval — het geheugengebruik
zou zelfs nog beter moeten zijn.
\end_layout
\begin_layout Section
Structuur
\end_layout
\begin_layout Standard
De structuur zou voor zich moeten spreken:
\end_layout
\begin_layout Itemize
\family typewriter
typedefs.h
\family default
&
\family typewriter
typedefs.cpp
\family default
: definiëren van data types die gebruikt worden in de code.
Door veelvuldig gebruik van custom data types, kan de compiler ook meer
fouten opvangen dan wanneer overal
\family typewriter
int
\family default
s gebruikt zouden worden.
\end_layout
\begin_layout Itemize
\family typewriter
arffparser.h
\family default
&
\family typewriter
arffparser.cpp
\family default
: de zelf geschreven ARFF parser, die zeer beperkt is: enkel numerical attribute
s worden ondersteund.
Placeholder values (vraagtekens) worden o Er zijn twee public methods:
\family typewriter
parseItemProperties()
\family default
en
\family typewriter
parseTransactions()
\family default
.
\begin_inset Newline newline
\end_inset
\family typewriter
parseItemProperties()
\family default
parset enkel de eigenschappen van ieder item: het genereert unieke
\family typewriter
ItemID
\family default
s in de volgorde dat unieke items worden tegen gekomen en returnet de
\family typewriter
ItemName
\family default
,
\family typewriter
Quantity
\family default
en
\family typewriter
SupportCount
\family default
voor alle
\family typewriter
Item
\family default
s.
Dit is nodig opdat het FP-growth algoritme het inserten van transacties
in de FP-tree kan optimaliseren.
\begin_inset Newline newline
\end_inset
\family typewriter
parseTransactions()
\family default
parset eenvoudigweg alle transacties en roept een callback functie aan
die er iets mee doet — in dit geval worden de transacties in een FP-tree
geïnsert.
\end_layout
\begin_layout Itemize
\family typewriter
fpnode.h
\family default
&
\family typewriter
fpnode.cpp
\family default
: een enkele node in een FP-tree wordt voorgesteld door instanties van de
\family typewriter
FPNode
\family default
klasse.
Er is een pointer naar de parent
\family typewriter
FPNode
\family default
, een
\family typewriter
ItemID
\family default
, een
\family typewriter
SupportCount
\family default
en een hash met
\family typewriter
ItemID
\family default
s als keys en
\family typewriter
FPNode
\family default
pointers als values om naar de kinderen van iedere
\family typewriter
FPNode
\family default
te wijzen.
\end_layout
\begin_layout Itemize
\family typewriter
fptree.h
\family default
&
\family typewriter
fptree.cpp
\family default
: de
\family typewriter
FPTree
\family default
klasse implementeert een FP-tree zoals in het boek staat uitgelegd en voorziet
enkele hulpfuncties.
De uitzondering is hoe prefix paths aangepakt worden: in plaats van rechtstreek
s met nodes uit de tree te werken, wordt voor ieder prefix path een lijst
van
\family typewriter
Item
\family default
s aangemaakt.
Ieder
\family typewriter
Item
\family default
bevat de
\family typewriter
ItemID
\family default
en de
\begin_inset Quotes eld
\end_inset
netto
\begin_inset Quotes erd
\end_inset
\family typewriter
SupportCount
\family default
(de
\family typewriter
SupportCount
\family default
van de node waarvan vertrokken werd).
Ieder prefix path kan dus als een transactie beschouwd worden die gewoon
in een nieuwe tree kan ingevoegd worden, waarbij de support informatie
correct overgenomen wordt.
Op die manier moest geen complexe logica ingebouwd worden voor het verwijderen
van
\family typewriter
FPNode
\family default
s uit de
\family typewriter
FPTree
\family default
.
\end_layout
\begin_layout Itemize
\family typewriter
fpgrowth.h
\family default
&
\family typewriter
fpgrowth.cpp
\family default
: het FP-growth algoritme zelf wordt geïmplemeneerd in deze
\family typewriter
FPGrowth
\family default
klasse.
Voor het parsen van de dataset wordt uiteraard de
\family typewriter
ARFFParser
\family default
klasse gebruikt.
Dit is exact geïmplementeerd zoals in het boek beschreven staat, inclusief
de opsplitsing in verschillende fases:
\end_layout
\begin_deeper
\begin_layout Itemize
Preprocessing fase 1 parset de item names, quantities en support counts.
De eerste twee worden nu al geparset om in de volgende stappen minder geheugen
te moeten gebruiken (zie eerder).
De laatste wordt berekend om transacties te kunnen optimaliseren voordat
ze in de
\family typewriter
FPTree
\family default
ingevoegd worden.
\end_layout
\begin_layout Itemize
Preprocessing fase 2 parset de transacties en kan hierbij voor ieder Item
in de
\family typewriter
Transaction
\family default
twee 16-bit integers volstaan (een
\family typewriter
ItemID
\family default
en een
\family typewriter
SupportCount
\family default
).
Voor iedere geparsete
\family typewriter
Transaction
\family default
wordt het
\family typewriter
ARFFParser::parsedTransaction(Transaction)
\family default
signal geëmit, opgevangen in het
\family typewriter
FPGrowth::parsedTransaction(Transaction)
\family default
slot en geoptimaliseerd door
\family typewriter
FPGrowth::optimizeTransaction()
\family default
alvorens ingevoegd te worden in de
\family typewriter
FPTree
\family default
.
\begin_inset Newline newline
\end_inset
\family typewriter
FPGrowth::optimizeTransaction()
\family default
verwijdert items uit de transactie met te weinig support en herrangschikt
items binnen de transactie zodat die met de meeste support vooraan staan.
Items met dezelfde support worden steeds op dezelfde manier gerangschikt
om de density van de FP-tree te maximaliseren.
\end_layout
\begin_layout Itemize
Calculating fase 1 genereert de frequent itemsets exact volgens het algoritme
in het boek.
\end_layout
\begin_layout Itemize
Calculating fase 2 berekent de
\family typewriter
SupportCount
\family default
s van iedere gevonden frequent itemset.
Dit gaat zeer snel, omdat ieder item in een frequent itemset nog zijn
\begin_inset Quotes eld
\end_inset
netto
\begin_inset Quotes erd
\end_inset
\family typewriter
SupportCount
\family default
met zich meedraagt.
Dus moet enkel het minimum van deze netto
\family typewriter
SupportCount
\family default
s berekend worden, en dit is dan de
\family typewriter
SupportCount
\family default
voor de frequent itemset.
\end_layout
\end_deeper
\begin_layout Itemize
\family typewriter
ruleminer.h
\family default
&
\family typewriter
ruleminer.cpp
\family default
: deze klasse bevat enkel static methods, omdat de enige
\emph on
state
\emph default
die doorgegeven moet worden, de
\family typewriter
minimumConfidence
\family default
is.
Rules van types A worden bijna exact gemined zoals in het boek beschreven
staat.
De uitzondering is mijn implementatie van het ap-genrules algoritme, wat
volgens mij een fout bevat zoals het in het boek beschreven staat, of op
z'n minst een grove onduidelijkheid.
\begin_inset Newline newline
\end_inset
Algoritme 6.2 op pagina 351 in het boek genereert 1-item consequenten en
geeft deze door aan
\family typewriter
ap-genrules
\family default
(algoritme 6.3 op pagina 352 in het boek).
\family typewriter
ap-genrules
\family default
probeert echter niet om antecedenten voor deze 1-item consequenten te genereren
, maar kijkt meteen of het mogelijk is om nog grotere consequenten te genereren,
en indien dat het geval is, berekent het de antecedenten voor die grotere
consequenten en evalueert vervolgens de gegenereerde regel a.d.h.v.
zijn confidence.
De fout is dus volgens mij dat ook voor 1-item consequenten er antecedenten
moeten gegenereerd worden.
Als je de algoritmes 6.2 en 6.3 exact implementeert, is dat foutief.
Je moet algoritme 6.3 lichtjes aanpassen: genereer eerst antecedenten voor
de ontvangen consequenten, verwijder de consequenten die te weinig confidence
hebben, en
\emph on
dan pas
\emph default
moet er gekeken worden of nog grotere consequenten gegenereerd kunnen worden
(als er al nog consequenten over zijn met voldoende confidence).
\begin_inset Newline newline
\end_inset
Voor deze aanpassing werden niet alle rules gevonden die gevonden moesten
worden, erna wel.
Dus nogmaals, het is ofwel een fout in het algoritme die we worden veronderstel
d te ondervinden bij de implementatie, ofwel een zeer onduidelijke notatie.
\end_layout
\begin_layout Itemize
\family typewriter
intervaltransformer.h
\family default
&
\family typewriter
intervaltransformer.cpp
\family default
: de bedoeling van deze klasse is om gegeven frequente itemsets zoals hierboven
(dus met een
\family typewriter
ItemID
\family default
voor iedere combinatie van een
\family typewriter
ItemName
\family default
en
\family typewriter
Quantity
\family default
) te transformeren naar frequente itemsets die geschikt zijn voor interval-gebas
eerde quantative association rules (of zoals het in de opgave staat: regels
van type B en C).
De resulterende frequente itemsets kunen rechtstreeks aan
\family typewriter
RuleMiner
\family default
meegegeven worden en zo zullen de regels van type B en C gevonden worden.
Een nauwkeurigere beschrijving:
\end_layout
\begin_deeper
\begin_layout Itemize
verwijder de frequente itemsets van grootte 1 omdat deze niet kunnen resulteren
in regels
\end_layout
\begin_layout Itemize
zoek alle unieke item name combinaties (per frequente itemset) en houd pointers
naar alle frequente itemsets die aan deze combinatie voldoen
\end_layout
\begin_layout Itemize
genereer iedere mogelijke combinatie voor iedere verzameling van frequente
itemsets met dezelfde item names
\end_layout
\begin_layout Itemize
merge alle frequente itemset combinaties (waarbij de quantities en support
counts onthouden worden zodat we deze kunnen valideren in de volgende stap)
\end_layout
\begin_layout Itemize
behoud enkel gemergde frequent itemsets waarvan de intervallen aansluitend
zijn
\end_layout
\begin_layout Itemize
genereer een item ID voor ieder item in een van de gevonden frequent itemsets
en sla de mapping naar item name en quantities (kleinste en grootste van
het interval) op
\end_layout
\end_deeper
\begin_layout Itemize
\family typewriter
main.cpp
\family default
: controleert het aantal ontvangen argumeenten, maakt een
\family typewriter
FPGrowth
\family default
object aan, doorloopt de 4 fases van
\family typewriter
FPGrowth
\family default
(waarbij telkens de tijdsduur gemeten wordt), maakt vervolgens gebruik
van de
\family typewriter
RuleMiner
\family default
klasse en print ten slotte de gevonden regels uit.
\end_layout
\begin_layout Itemize
\family typewriter
DMP.pro
\family default
: een Qt project file, waarmee eenvoudig cross-platform gebuild kan worden
\end_layout
\begin_layout Section
Tijds- en plaatscomplexiteit
\end_layout
\begin_layout Standard
Ik ga de tijds- en plaatscomplexiteit bekijken per fase:
\end_layout
\begin_layout Standard
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
|- PREPROCESSING
\end_layout
\begin_layout Plain Layout
|- Preprocessing stage 1: parsing item names, quantities and support counts.
\end_layout
\begin_layout Plain Layout
|- Duration: 906 ms.
\end_layout
\begin_layout Plain Layout
|- Preprocessing stage 2: parsing transactions and building an FP-tree.
\end_layout
\begin_layout Plain Layout
|- Duration: 1846 ms.
\end_layout
\begin_layout Plain Layout
|- CALCULATING
\end_layout
\begin_layout Plain Layout
|- Calculating stage 1: frequent itemset generation.
\end_layout
\begin_layout Plain Layout
|- Duration: 1 ms.
\end_layout
\begin_layout Plain Layout
|- Calculating stage 2: calculate support for frequent itemsets.
\end_layout
\begin_layout Plain Layout
|- Duration: 0 ms.
\end_layout
\begin_layout Plain Layout
|- Calculating stage 3: rule generation
\end_layout
\begin_layout Plain Layout
|- Duration: 0 ms.
\end_layout
\begin_layout Plain Layout
|- Calculating stage 4: transform frequent itemsets for interval rule
generation
\end_layout
\begin_layout Plain Layout
|- Duration: 1 ms.
\end_layout
\begin_layout Plain Layout
|- Calculating stage 5: interval rule generation
\end_layout
\begin_layout Plain Layout
|- Duration: 0 ms.
\end_layout
\begin_layout Plain Layout
ACTUAL PROCESSING TIME: 1848 ms (excludes preprocesing stage 1)
\end_layout
\begin_layout Plain Layout
TOTAL PROCESSING TIME: 2754 ms (all stages)
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Gegeven volgende variabelen:
\begin_inset Formula \begin{eqnarray*}
T & = & aantal\, transacties\\
t_{avg} & = & gemiddelde\, lengte\, van\, transactie\,(dus\, gemiddeld\, aantal\, items\, per\, transactie)\\
t_{max} & = & maximale\, lengte\, transactie\\
I & = & aantal\, unieke\, items\\
F_{max} & = & aantal\, maximale\, frequent\, itemsets\\
C & = & aantal\, unieke\, combinaties\, van\, item\, names\, in\, maximale\, frequent\, itemsets\\
F_{merged} & = & aantal\, gemergede\, frequent\, itemsets\,(voor\, intervallen)\\
F_{contiguous} & = & aantal\, gemergede\, frequent\, itemsets\, waarvan\, de\, intervallen\, aansluiten\end{eqnarray*}
\end_inset
\end_layout
\begin_layout Itemize
preprocessing
\end_layout
\begin_deeper
\begin_layout Itemize
preprocessing stage 1:
\end_layout
\begin_deeper
\begin_layout Itemize
TC:
\begin_inset Formula $O(T\times t_{avg})$
\end_inset
, want alle transacties worden gelezen en voor iedere transactie alle unieke
items worden eruit gefilterd
\end_layout
\begin_layout Itemize
PC: van ieder uniek item worden de details bijgehouden, dus
\begin_inset Formula $O(I)$
\end_inset
, wat enkel zeer hoog is indien alle items uniek zijn, maar dan is de data
sowieso niet geschikt voor data mining.
\end_layout
\end_deeper
\begin_layout Itemize
preprocessing stage 2:
\end_layout
\begin_deeper
\begin_layout Itemize
TC:
\begin_inset Formula $O(T\times t_{avg}\log t_{avg}\times\log t_{avg})$
\end_inset
, want alle transacties worden gelezen, iedere transactie wordt geoptimaliseerd
waarbij de grootste kost het sorteren van de support counts van de items
binnen die transactie is d.m.v.
quicksort (average case:
\begin_inset Formula $O(t_{avg}\log t_{avg})$
\end_inset
) en ten slotte wordt de geoptimaliseerde transactie ingevoegd in de FP-tree,
wat voor een dense tree
\begin_inset Formula $O(\log t_{avg})$
\end_inset
kost, maar in het slechtere geval
\begin_inset Formula $O(t_{avg})$
\end_inset
kan kosten.
\end_layout
\begin_layout Itemize
PC: de grootte van de FP-tree is
\begin_inset Formula $O(t_{max})$
\end_inset
in het geval dat alle transacties zeer gelijkaardig zijn (best case) of
\begin_inset Formula $O(T\times t_{max})$
\end_inset
als iedere transactie allemaal unieke items heeft (worst case).
Gemiddeld zal het ongeveer
\begin_inset Formula $O(\log T\times t_{avg})$
\end_inset
zijn (average case).
\end_layout
\end_deeper
\end_deeper
\begin_layout Itemize
calculating: merk op dat in preprocessing stage 2 de grootte van de gebouwde
FP-tree sterk afhangt van de minimum support en dus ook van de dataset.
Als de resulterende boom zeer dense is, dan zullen de calculating stages
zeer snel doorlopen kunnen worden.
\end_layout
\begin_deeper
\begin_layout Itemize
calculating stage 1:
\end_layout
\begin_deeper
\begin_layout Itemize
TC: is ongeveer
\begin_inset Formula $O(t_{avg}\,^{5}\times t_{avg}\log t_{avg})$
\end_inset
, want—details achterwege latende—er wordt over ieder uniek item in de huidige
boom (of dat nu de originele FP-tree is of een conditional FP-tree) geïtereerd
(
\begin_inset Formula $O(t_{avg})$
\end_inset
), de prefix paths worden berekend (
\begin_inset Formula $O(t_{avg}\,^{2})$
\end_inset
en vervolgens gefilterd (
\begin_inset Formula $O(t_{avg})$
\end_inset
), waarna een CFP-tree met het resultaat wordt opgebouwd (
\begin_inset Formula $O(t_{avg}\log t_{avg}\times\log t_{avg})$
\end_inset
).
\end_layout
\begin_layout Itemize
PC:
\begin_inset Formula $O(F_{max})$
\end_inset
, want dat is net het resultaat.
Omdat tijdens de berekeningen een steeds kleinere boom wordt gegenereerd
voor een grotere frequent itemset, en die boom moet blijven bestaan tot
de berekening voor de grotere frequent itemset voltooid is, zijn er dus
in het slechtste geval zoveel bomen tegelijk in het geheugen als de langste
frequent itemset.
De exacte grootte van die bomen is onvoorspelbaar, maar feit is dat het
aantal nodes per boom monotoon vermindert net zoals de lengte van de frequent
itemset monotoon toeneemt.
\end_layout
\end_deeper
\begin_layout Itemize
calculating stage 2:
\end_layout
\begin_deeper
\begin_layout Itemize
TC:
\begin_inset Formula $O(F_{max}\times t_{avg})$
\end_inset
, want er moet over alle items in alle gevonden frequent itemsets geïtereerd
worden om de support counts van de frequent itemsets te berekenen
\end_layout
\begin_layout Itemize
PC:
\begin_inset Formula $O(F_{max})$
\end_inset
, want er wordt één support count berekend per frequent itemset
\end_layout
\end_deeper
\begin_layout Itemize
calculating stage 3: standaard Apriori
\end_layout
\begin_layout Itemize
calculating stage 4:
\end_layout
\begin_deeper
\begin_layout Itemize
TC:
\begin_inset Formula $O(F_{max}\times t_{avg}+C\times t_{avg}\,^{3}+C^{2}\times t_{avg}\,^{2}+F_{merged}\times t_{avg}\,^{2}+F_{contiguous}\times t_{avg})$
\end_inset
, want eerst worden frequent itemsets met dezelfde item names gezocht (
\begin_inset Formula $O(F_{max}\times t_{avg})$
\end_inset
), hierna worden alle mogelijke combinaties gegenereerd (
\begin_inset Formula $O(C\times t_{avg}\,^{3})$
\end_inset
), waarna voor de combinaties waarvoor overeenkomstige frequent itemsets
gevonden zijn, gemergede frequent itemsets gegenereerd worden (
\begin_inset Formula $O(C^{2}\times t_{avg}\,^{2})$
\end_inset
), dan worden aaneensluitende intervallen gefilterd uit deze gemergede frequent
itemsets (
\begin_inset Formula $O(F_{merged}\times t_{avg}\,^{2})$
\end_inset
) en ten slotte wordt een nieuwe item ID mapping gegenereerd (
\begin_inset Formula $O(F_{contiguous}\times t_{avg})$
\end_inset
).
\end_layout
\begin_layout Itemize
PC:
\begin_inset Formula $O(C\times F_{max}\times t_{avg}+F_{merged}+F_{contiguous})$
\end_inset
, voor uitleg: zie uitleg voor TC
\end_layout
\end_deeper
\begin_layout Itemize
calculating stage 5: standaard Apriori
\end_layout
\end_deeper
\begin_layout Section
Tests
\end_layout
\begin_layout Itemize
Met de gegeven dataset (van 109 transacties, met minimum support 10% en
minimum confidence 90%), wordt het correct resultaat gevonden
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
ACTUAL PROCESSING TIME: 3 ms (excludes preprocesing stage 1)
\end_layout
\begin_layout Plain Layout
TOTAL PROCESSING TIME: 4 ms (all stages)
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
Rules of type A:
\end_layout
\begin_layout Plain Layout
{BoughtI4=2, BoughtI5=5} => {BoughtI3=9} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI3=9, BoughtI5=5} => {BoughtI4=2} (conf=0.916667)
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
Rules of types B & C:
\end_layout
\begin_layout Plain Layout
None.
\end_layout
\end_inset
\end_layout
\begin_layout Itemize
Als diezelfde dataset duizendmaal gekopieerd wordt, wordt natuurlijk hetzelfde
gevonden, maar duren de berekeningen langer:
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
ACTUAL PROCESSING TIME: 1782 ms (excludes preprocesing stage 1)
\end_layout
\begin_layout Plain Layout
TOTAL PROCESSING TIME: 2692 ms (all stages)
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
Rules of type A:
\end_layout
\begin_layout Plain Layout
{BoughtI4=2, BoughtI5=5} => {BoughtI3=9} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI3=9, BoughtI5=5} => {BoughtI4=2} (conf=0.916667)
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
Rules of types B & C:
\end_layout
\begin_layout Plain Layout
None.
\end_layout
\end_inset
\end_layout
\begin_layout Itemize
Ten slotte, een eigen dataset voor het testen van regels van types B en
C (eveneens met minimum support 10% en minimum confidence 90%):
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
@relation basket1
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
@attribute BoughtI1 numeric
\end_layout
\begin_layout Plain Layout
@attribute BoughtI2 numeric
\end_layout
\begin_layout Plain Layout
@data
\end_layout
\begin_layout Plain Layout
5,2
\end_layout
\begin_layout Plain Layout
6,1
\end_layout
\begin_layout Plain Layout
8,4
\end_layout
\begin_layout Plain Layout
9,5
\end_layout
\begin_layout Plain Layout
\end_layout
\end_inset
geeft het volgende resultaat:
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
ACTUAL PROCESSING TIME: 1 ms (excludes preprocesing stage 1)
\end_layout
\begin_layout Plain Layout
TOTAL PROCESSING TIME: 1 ms (all stages)
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
Rules of type A:
\end_layout
\begin_layout Plain Layout
{BoughtI2=2} => {BoughtI1=5} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI1=5} => {BoughtI2=2} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI2=1} => {BoughtI1=6} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI1=6} => {BoughtI2=1} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI2=4} => {BoughtI1=8} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI1=8} => {BoughtI2=4} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI2=5} => {BoughtI1=9} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI1=9} => {BoughtI2=5} (conf=1)
\end_layout
\begin_layout Plain Layout
\end_layout
\begin_layout Plain Layout
Rules of types B & C:
\end_layout
\begin_layout Plain Layout
{BoughtI2 in [1,2]} => {BoughtI1 in [5,6]} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI1 in [5,6]} => {BoughtI2 in [1,2]} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI2 in [4,5]} => {BoughtI1 in [8,9]} (conf=1)
\end_layout
\begin_layout Plain Layout
{BoughtI1 in [8,9]} => {BoughtI2 in [4,5]} (conf=1)
\end_layout
\end_inset
\end_layout
\begin_layout Section
Builden
\end_layout
\begin_layout Standard
Er zijn twee build modes: release en debug.
debug mode genereert een hoop output en gaat hoogstwaarschijnlijk irrelevant
zijn bij de evaluatie.
Om te builden is Qt vereist.
Ik heb gewerkt met Qt 4.5, maar het zou evenzeer moeten werken met oudere
en nieuwere versies, aangezien enkel basisfunctionaliteit wordt gebruikt.
\end_layout
\begin_layout Standard
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
qmake DMP.pro
\end_layout
\begin_layout Plain Layout
make release
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Op Mac OS X zal het
\family typewriter
qmake
\family default
commando standaard een XCode project genereren i.p.v.
een
\family typewriter
Makefile
\family default
.
Als je toch een
\family typewriter
Makefile
\family default
wilt genereren, gebruik dan het volgende commando:
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
qmake DMP.pro -spec macx-g++
\end_layout
\end_inset
\end_layout
\begin_layout Section
Gebruik
\end_layout
\begin_layout Standard
Het gebruik is zoals te verwachten:
\end_layout
\begin_layout Standard
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
DMP <inputfile> <minsup> <minconf>
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Concreet wordt dat:
\begin_inset listings
inline false
status open
\begin_layout Plain Layout
DMP dataset.arff 0.1 0.9
\end_layout
\end_inset
\end_layout
\begin_layout Standard
De
\family typewriter
minsup
\family default
parameter dient dus een float te zijn en hetzelfde geldt voor de
\family typewriter
minconf
\family default
parameter.
\end_layout
\end_body
\end_document
Jump to Line
Something went wrong with that request. Please try again.