www-ai.cs.tu-dortmund.de/LEHRE/VORLESUNGEN/KDD/SS09/3DMVkNN.pdf
Vorlesung Wissensentdeckung - Klassifikation und Regression: nächste Nachbarn
Dimension furchtbar spärlich.
N 1 p ist bei 100 Beispielen und p = 10 nur 1001/10 = 5
√ 10.
Wenn 100 Beispiele bei p = 1 einen dichten Raum ergeben, muss man für die selbe Dichte bei p = 10 schon 10010 Beispiele [...] Einzelähnlichkeiten:
Sim( ~x1, ~x2) = 1 p
p∑ j=1
sim(x1,j , x2,j)
Vielleicht sind einige Attribute wichtiger als andere?
Sim( ~x1, ~x2) =
∑p j=1wjsim(x1,j , x2,j)∑p
j=1wj
Vielleicht ist der quadratische [...] Modellselektion
Fluch der hohen Dimension bei kNN
Die Dichte der Beispiele ist proportional zu N 1 p .
Schon bei p = 10 brauchen wir 80% der möglichen Werte jedes Attributs Xi, um wenigstens 10% der Daten in …