Bottom-Up Hill-Climbing

[Malou]

Problem solved
Hallo allerseits,

Bin gerade am lernen und habe eine Frage bezüglich Foliensatz 'subgroup discovery' Folie 31:

Und zwar steht hier, dass att1=1 nicht anhand von bottom-up hill-climbing lernbar ist. Ich verstehe nicht warum, denn wenn ich das Algorithmus Find-S durchführe, finde ich Problemlos genau diese Hypothese. Und Find-S soll doch einen Bottom-Up Hill-Climbing Algorithmus laut Definition sein oder?

Vielleicht ist auch was in meine Vorgehensweise falsch, hier mal meine Gedanken:

Wir fangen mit der speziellste Regel an, sprich

Code: Alles auswählen

if att1=1 and att1=0 and att2=1 and att2=0 and att3=0 and att3=1 then +

.
Beim ersten Beispiel fallen die Bedingungen weg, die das Beispiel nicht abdecken, also bleibt folgende Regel übrig:

Code: Alles auswählen

if att1=1 and att2=1 and att3=1 then +

Beim zweiten Beispiel wird die zwei letzten Bedingungen weggelassen, da sie das neue Beispiel nicht abdecken, was uns zu folgender Regel führt:

Code: Alles auswählen

if att1=1 then +

Diese Regel wird nicht weiter generalisiert, da nur noch negative Beispiele auftauchen.
Am Ende des Algorithmus bleibt also nur noch diese Regel übrig und in der Folie wird gesagt, dass diese nicht lernbar ist...

Ich glaube, dass ich meine eigene Frage selbst beantworten kann, poste es aber trotzdem hier, falls es jemanden helfen kann
Das Beispiel in der Folie gilt ja nur für Batch Learning, wo alle Beispiele gleichzeitig betrachtet wird. Es wird also zuerst eine Regel gefunden, die genau ein Beispiel abdeckt, wie folgende:

Code: Alles auswählen

if att1=1 and att2=1 and att3=1 then +

Dann wird versucht, eine Bedingung zu entfernen und jeweils betrachtet, ob mehr positive Beispiele abgedeckt werden.

• Wenn die erste Bedingung entfernt wird, werden genau gleich viele positive Beispiele abgedeckt, sprich nur das erste.
• Wenn die zweite Bedingung entfernt wird, wird auch nur das erste Beispiel abgedeckt
• Und für die dritte Bedingung gilt dasselbe

Irgendeine Bedingung wird also zufällig ausgewählt und entfernt, was auch die erste betreffen kann, also att1=1. Daher kann ein Bottom-Up Algorithmus im Batch Learning die Bedingung att=1 tatsächlich nicht lernen.

Bin glücklich, dass es ein Forum gibt, wo ich meine Fragen stellen und selbst beantworten kann!

Also danke d120 Community!

Malou