Suche nach Refinements für verschiedene Attributtypen optimieren

[michael-rapp]

Bisher wird stets der selbe Code für die Suche nach Refinements genutzt, unabhängig davon, um welche Art Attribut es sich handelt. Zukünftig sollte es möglich sein, für einzelne Attributtypen spezielle Implementierungen zu verwenden, die für den jeweiligen Fall werden können. D.h., dass folgende Aspekte überarbeitet werden müssen:

• Statt mit mit der Klasse FeatureVector nur eine Datenstruktur für die Speicherung von Featurewerten bereitzustellen, müssen auf die unterschiedlichen Attributtypen zugeschnittene Datenstrukturen angeboten werden, die von einer gemeinsamen Basisklasse IFeatureVector erben:
  • NumericalFeatureVector für die Speicherung numerischer Featurewerte in sortierter Reihenfolge
  • NominalFeatureVector für die Speicherung nominaler Featurewerte in Bins
  • BinaryFeatureVector für die Speicherung nominaler Featurewerte mit zwei möglichen Werten
  • OrdinalFeatureVector für die Speicherung ordinaler Featurewerte in sortierten Bins
  • EqualFeatureVector falls alle Werte für ein Feature identisch sind (kann durch Filtern anderer Klassen passieren)
• Die folgenden Unterklassen von IFeatureType müssen Methoden implementieren, um die Werte für ein bestimmtes Feature aus einer Featurematrix auszulesen und, je nach Typ, eine der oben genannten Datenstrukturen zu erzeugen:
  • NumericalFeatureType erzeugt einen NumericalFeatureVector oder EqualFeatureVector
  • NominalFeatureType erzeugt einen NominalFeatureVector, BinaryFeatureVector oder EqualFeatureVector
  • OrdinalFeatureType erzeugt einen OrdinalFeatureVector, BinaryFeatureVector oder EqualFeatureVector
• In der Klasse ExactThresholds muss ein IFeatureVector über die neuen Funktionen der KlasseIFeatureType erzeugt werden. Da nun unterschiedliche Datenstrukturen vorliegen können, müssen Funktionen zur Filterung der Feature-Werte auf Basis eines Refinement und gleichzeitige Anpassung der CoverageMask, bzw. zur Filterung auf Basis der CoverageMask zu jeder Unterklasse von IFeatureVector hinzugefügt werden:
  • NumericalFeatureVector:
    • Erstellt eine View auf den originalen Vector oder einen EqualFeatureVector bei Filterung nach Refinement
    • Erstellt eine neue Datenstruktur oder einen EqualFeatureVector bei Filterung nach CoverageMask
  • NominalFeatureVector:
    • Erstellt eine View auf den originalen Vector (eventuell als BinaryFeatureVector) mit angepasster Auswahl der Bins oder einen EqualFeatureVector bei Filterung nach Refinement
    • Erstellt eine neue Datenstruktur, einen BinaryFeatureVector oder einen EqualFeatureVector bei Filterung nach CoverageMask
  • BinaryFeatureVector:
    • Erstellt einen EqualFeatureVector bei Filterung nach Refinement
    • Erstellt eine neue Datenstruktur oder einen EqualFeatureVector bei Filterung nach CoverageMask
  • OrdinalFeatureVector:
    • Erstellt eine View auf den originalen Vector mit angepasster Auswahl der Bins oder einen EqualFeatureVector bei Filterung nach Refinement
    • Erstellt eine neue Datenstruktur oder einen EqualFeatureVector bei Filterung nach CoverageMask
  • EqualFeatureVector erfordert nicht dass neue Vektoren erzeugt werden
• Statt eine einzige Implementierung vom Typ IRuleRefinement für alle Arten von Attributen zu verwenden, müssen auf die unterschiedlichen Attributtypen zugeschnittene Implementierungen verwendet werden, die von einem IFeatureVector per Visitor-Pattern aufgerufen werden.
  • Suche nach Refinements auf Basis eines NumericalFeatureVector
  • Suche nach Refinements auf Basis eines NominalFeatureVector
  • Suche nach Refinements auf Basis eines BinaryFeatureVector
  • Suche nach Refinements auf Basis eines OrdinalFeatureVector
  • Suche nach Refinements auf Basis eines EqualFeatureVector sollte nie ein Ergebnis liefern

Anschließend sollte der Code für die approximative Suche nach Refinements auf die selben Datenstrukturen und Mechanismen umgestellt werden, um den Code zu vereinheitlichen. Dies soll jedoch nicht Teil dieses Issues sein und wird stattdessen in #770 beschrieben.

[michael-rapp]

Benchmarks

Comparison of runtimes between the implementation in this branch (after) and the main branch (before). In both cases, BOOMER's default configuration and a 10 fold-cross validation was used.

dataset	labels	feature type	feature sparsity	runtime before (in sec)	runtime after (in sec)	speedup
20ng	20	numerical	96.81	15	14	1.07
bibtex	159	nominal	96.26	20	17	1.18
birds	19	numerical	38.64	8	7	1.14
cal500	174	numerical	0.15	40	42	0.95
corel5k	374	nominal	98.35	30	30	1.00
delicious	983	nominal	96.34	364	359	1.01
emotions	6	numerical	0.33	6	6	1.00
enron	53	nominal	91.6	3	3	1.00
eukaryote-go	22	numerical	99.86	4	4	1.00
eukaryote-pse-aac	22	numerical	43.37	62	65	0.95
eurlex-sm	201	numerical	95.26	138	141	0.98
image	5	numerical	0.22	24	24	1.00
imdb	28	nominal	98.06	155	145	1.07
langlog	75	numerical	81.38	4	4	1.00
medical	45	numerical	99.32	2	2	1.00
ohsumed	23	numerical	96.03	12	12	1.00
reuters-k500	103	nominal	98.41	13	13	1.00
scene	6	numerical	1.15	31	29	1.07
slashdot	22	numerical	99.46	2	2	1.00
tmc2007	22	nominal	99.79	26	26	1.00
yeast	14	numerical	0	31	30	1.03

The training times of the new implementation are competitive to those of the original one. In many cases, the new implementation is slightly faster. In other cases, it is just as fast as the original implementation. In three cases, the new implementation is (insignificantly) slower.