www-ai.cs.tu-dortmund.de/LEHRE/SEMINARE/SS09/AKTARBEITENDESDM/FOLIEN/vortragItemSetsCompress.pdf
Item Sets that Compress - Arno Siebes Jilles Vreeken Matthijs van Leeuwen
0 0 111 110 0 10 0 → n2 n1 n1 n4 n3 n1 n2 n1
10/39
Minimum Despription Length 2/3
Beispielcode ist optimal für W’keit(n1)= 1/2, W’keit(n2)=1/4, W’keit(n3)=1/8,W’keit (n4)=1/8
Shannon Entropie
Wähle Länge [...] I2}{I1, I2, I3}{I1, I2, I3, I4}}
3/39
Das Ziel
Normalerweise: Finden von frequent item sets
Problem: Redundanzen der Item Sets {{I1}{I1, I2}, ...}
Ziel: Kompression der Datenbank db
4/39
Die Idee
Item Sets sind [...] Item Sets: {{I1 : 3} {I1, I2 : 2}{I1, I2, I3 : 2}︸ ︷︷ ︸{I1, I2, I3, I4 : 1}}
Closed Item Sets:{{I1 : 3}{I1, I2, I3 : 2}{I1, I2, I3, I4 : 1}}
6/39
Kompression
7/39
Kompression
Reduktion des Speicherbedarfs …