Personal tools
You are here: Home Data Mining MVminer
Document Actions

MVminer

by François Rioult last modified 2008-11-26 17:14

MVminer est un extracteur de motifs delta-libres et de leurs fermetures. La distribution fournie inclut également les outils de pré-traitement.

Les outils mis ici à disposition sont des prototypes de recherche. Ils fonctionnent si vous les utilisez comme précisé ci-dessous. Il y a des détections primaires d'erreur, mais si ça ne marche quand même pas, c'est sûrement de votre faute... Vérifiez la syntaxe des lignes de commande, le format de vos données. Les demandes exotiques ne sont pas garanties.

Description

MVminer extrait la collection des motifs delta-libres [1] depuis une base de données transactionnelle, et est robuste en présence de valeurs manquantes [2].
Les données d'entrée sont lues depuis un fichier texte contenant une ligne par transaction. Une ligne est une succession de numéro d'items (le zéro est interdit), précédé d'un moins '-' si l'item est manquant. Les transactions avec valeur manquante doivent être regroupées en fin de fichier. Les lignes commençant par un dièse '#' sont ignorées mais renvoyées vers la sortie. Les lignes vides sont considérées comme des transactions vides.
La version fournie ici code les items et les transactions sur deux octets. Pour des dimensions supérieures, me contacter.

$ cat sample.bin
# Exemple jouet de données transactionnelle sample.bin
1 3 5
2 3 5
1 3 5
2 4 6
2 3 6
2 3 6
1 4 7
2 4 7

La sortie est constituée de lignes décrivant les motifs delta-libres. La première partie de la ligne indique le motif. Après la virgule ',' sont indiqués les items qui complètent la fermeture, précédés d'un '_' si c'est la première fois qu'ils y apparaissent. Entre parenthèses, on trouve le nombre d'exceptions. Enfin, après ':', le support.

$ mvminer -h
-a val minsup absolu, 1 transaction(s) par défaut
-c silent mode
-d val valeur de delta (nb de transactions), 0 par défaut.
-h affiche l'aide.
-i nomfich fichier de données.
-n nomfich fichier d'items ignorés.
-o nomfich fichier de résultat.
-p val minsup en %, 1 transaction(s) par défaut
-s val minsup [0,1], 1 transactions par défaut.
Ex. mvminer -i data -o data.out -s 0.1 -d 2
(extraction depuis data, résultats dans data.out,
support minimal 10 %, delta = 2 transactions.)

$ mvminer -i sample.bin -a 2 -d 0
 $ mvminer -i sample.bin -a 2 -d 1
# Exemple jouet de données transactionnelles sample.bin
# MVminer depuis sample.bin, 8 lignes, 7 colonnes.
# minsup = 2, delta = 0.
, :8
1 , :3
2 , :5
3 , :5
4 , :3
5 , _3 :3
6 , _2 :3
7 , _4 :2
1 3 , _5 :2
1 5 , 3 :2
2 3 , :3
2 4 , :2
3 6 , 2 :2
# Exemple jouet de données transactionnelles sample.bin
# MVminer depuis sample.bin, 8 lignes, 7 colonnes.
# minsup = 2, delta = 1.
, :8
1 , _3(1) _5(1) :3
2 , :5
3 , :5
4 , _2(1) _7(1) :3
5 , _1(1) _3 :3
6 , _2 _3(1) :3
7 , _1(1) _2(1) _4 :2
2 3 , _6(1) :3




Binarisation

Les données au format attribut valeur doivent être binarisées. Nous fournissons ici les utilitaires nécessaires à cette étape, ainsi qu'à celle de traduction inverse pour l'analyse des résultats de MVminer.
L'exemple ci-dessus provient de la base attribut valeur suivante :

$ cat sample
# Exemple jouet de données attribut-valeur sample
droite moins 0.1
gauche moins 0.3
droite moins 0.2
gauche plus 0.5
gauche moins 0.6
gauche moins 0.45
droite plus 0.95
gauche plus 0.8

L'utilitaire mvdico permet de répertorier les valuations des attributs, et de segmenter les valeurs numériques. Il utilise pour cela un fichier de configuration des attributs. Par exemple, en désignant par X1, X2, X3, les attributs de la base exemple, le fichier sample.atr de configuration est le suivant :

$ cat sample.atr
0 X1
0 X2
3 X3

La première valeur indique zéro '0' pour un attribut ayant des valeurs discrètes, comme X1 et X2, ou le nombre de segments que l'on veut obtenir à partir des valeurs numériques. mvdico produit alors la sortie suivante :

$ mvdico sample sample.atr > sample.dico
$ cat sample.dico
#X1
droite
gauche
#X2
moins
plus
#X3
0.3
0.6
0.95

On retrouve le nom de chaque attribut, suivi de la liste de ses valeurs, ou des bornes supérieures des intervalles de discrétisation. L'utilitaire mvsegment analyse les données et convertit les valeurs des attributs en items. Il fournit également un fichier de traduction pour convertir les résultats de MVminer.

$ mvsegment -i sample -o sample.bin -d sample.dico -t sample.trad
$ cat sample.bin
# binarisation du fichier sample
# Exemple jouet de données attribut-valeur sample
1 3 5
2 3 5
1 3 5
2 4 6
2 3 6
2 3 6
1 4 7
2 4 7
$ cat sample.trad
#0
1 X1:droite
2 X1:gauche
#1
3 X2:moins
4 X2:plus
#2
5 X3<=0.3
6 X3<=0.6
7 X3<=0.95

Les résultats de MVminer sont traduits à l'aide de l'utilitaire mvtraduc :

$ mvminer -i sample.bin -a 2 -d 1 | mvtraduc sample.trad 
# binarisation du fichier sample
# Exemple jouet de données attribut-valeur sample
# Extraction depuis sample.bin, 8 lignes, 7 colonnes.
# minsup = 2, delta = 1.
, :8
X1:droite , _X2:moins(1) _X3<=0.3(1) :3
X1:gauche , :5
X2:moins , :5
X2:plus , _X1:gauche(1) _X3<=0.95(1) :3
X3<=0.3 , _X1:droite(1) _X2:moins :3
X3<=0.6 , _X1:gauche _X2:moins(1) :3
X3<=0.95 , _X1:droite(1) _X1:gauche(1) _X2:plus :2
X1:gauche X2:moins , _X3<=0.6(1) :3

On constate que la règle X1:droite => _X2:moins(1) && _X3<=0.3(1) est présente 3 fois, à une exception près pour _X2:moins et _X3<=0.3.

Motifs fermés

Pour obtenir la liste des motifs fermés, il faut utiliser MVclose. Il s'agit simplement d'une version de MVminer qui fusionne le libre et les items qui l'accompagnent pour n'afficher que la fermeture. Le format de sortie présente successivement les concepts, i.e. l'association du fermé d'attributs puis de transaction, séparés par le caractère ':'.

$ mvclose -i sample.bin -a 2
1 : 1 3 7
2 : 2 4 5 6 8
3 : 1 2 3 5 6
4 : 4 7 8
3 5 : 1 2 3
2 6 : 4 5 6
4 7 : 7 8
1 3 5 : 1 3
1 3 5 : 1 3
2 3 : 2 5 6
2 4 : 4 8
2 3 6 : 5 6

Il y a cependant beaucoup de doublons, et il faut piper la sortie dans sort -u

$ mvclose -i sample.bin -a 2 | sort -u 
1 : 1 3 7
1 3 5 : 1 3
2 : 2 4 5 6 8
2 3 : 2 5 6
2 3 6 : 5 6
2 4 : 4 8
2 6 : 4 5 6
3 : 1 2 3 5 6
3 5 : 1 2 3
4 : 4 7 8
4 7 : 7 8

mvtraduc peut finalement afficher les concepts sous la forme attribut valeur :

$ mvclose -i sample.bin -a 2 | sort -u | ./traduc sample.trad
X1:droite : 1 3 7
X1:droite X2:moins X3<=0.3 : 1 3
X1:gauche : 2 4 5 6 8
X1:gauche X2:moins : 2 5 6
X1:gauche X2:moins X3<=0.6 : 5 6
X1:gauche X2:plus : 4 8
X1:gauche X3<=0.6 : 4 5 6
X2:moins : 1 2 3 5 6
X2:moins X3<=0.3 : 1 2 3
X2:plus : 4 7 8
X2:plus X3<=0.95 : 7 8

Téléchargement - Installation

MVminer est utilisable sur toute plateforme supportant les outils de développement GNU (automake, g++), c'est-à-dire Linux, Unix, MacInstosh, Windows, etc.

Pour utiliser MVminer, suivez les étapes suivantes :
  • Télécharger le fichier de distribution mvminersolo-2.1.tar.gz
  • Extraire l'archive à l'aide de la commande
    tar xvfz mvminersolo-2.1.tar.gz
  • Aller dans le dossier mvminersolo-2.1
  • Si vous souhaitez installer la distribution dans un répertoire local, par exemple pour moi /users/ens/frioult/lib, taper les commandes
    ./configure --prefix=/users/ens/frioult/lib
    make
    make install
  • N'oubliez pas d'ajouter le chemin d'accès à la librairie dans votre PATH (dans le fichier .bashrc ajouter la ligne
    export PATH=$PATH:/users/ens/frioult/lib/bin
  • Si vous possédez les droits d'administration de votre machine, vous pouvez installer la distribution dans le répertoire par défaut avec les commandes ./configure (sans --prefixe) puis make et enfin make install.

Références

  • [1] J.-F. Boulicaut and A. Bykowski and C. Rigotti, Free-sets : a condensed representation of boolean data for the approximation of frequency queries, Data Mining and Knowledge Discovery journal, Kluwer Academics Publishers, p. 5-22, 2003.
  • [2] F. Rioult and B. Crémilleux, Condensed representations in presence of missing values 5th International Symposium on Intelligent Data Analysis (IDA'03), LNCS 2810, p. 578-588, 2003.
« June 2011 »
Su Mo Tu We Th Fr Sa
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30
 

Powered by Plone, the Open Source Content Management System

This site conforms to the following standards: