Nächste Nachbarn: Wer entscheidet hier?

1. Wer ist wie die anderen?

Auf den Inseln vor der Antarktischen Halbinsel leben drei Arten von Pinguinen: der Adéliepinguin, der Zügelpinguin (englisch Chinstrap) und der Eselspinguin (Gentoo). Die Biologin Kristen Gorman hat an 342 von ihnen die Länge und die Höhe des Schnabels gemessen, in Millimetern.

Jemand misst einen weiteren Pinguin, aber schreibt die Art nicht dazu. Welcher Art er ist, lässt sich raten, ohne eine Regel zu kennen: Man sucht unter den 342 bekannten Pinguinen die, deren Schnabel seinem am ähnlichsten ist, und nimmt die Art, die unter ihnen am häufigsten ist. Das sind seine nächsten Nachbarn, und das Verfahren heißt danach: k nächste Nachbarn, wobei k sagt, wie viele Nachbarn gefragt werden.

Mit k = 1 wäre der unbekannte Pinguin ein Eselspinguin, mit k = 5 ein Zügelpinguin. Ein einzelner Nachbar kann ein Ausreißer sein; mehrere Nachbarn stimmen ab.

Beschrieben haben das Verfahren die Statistikerin Evelyn Fix und der Statistiker Joseph Hodges 1951, in einem Bericht für die Luftwaffe der USA. Es ist bis heute eines der einfachsten Verfahren, mit denen ein Programm aus Beispielen lernt, und eines der durchsichtigsten: Zu jeder Entscheidung kann es sagen, welche Beispiele dahinterstehen.

2. Einrichten

mkdir -p ~/nachbarn
cd ~/nachbarn
wget https://workspace.hackschule.de/naechste-nachbarn/penguins.csv https://workspace.hackschule.de/naechste-nachbarn/customers.csv
touch knn.rb penguins.rb

irb -r ./knn.rb

mkdir -p ~/nachbarn
cd ~/nachbarn
wget https://workspace.hackschule.de/naechste-nachbarn/penguins.csv https://workspace.hackschule.de/naechste-nachbarn/customers.csv
touch knn.py penguins.py

python3 -i knn.py

penguins.csv hat eine Zeile je Pinguin: die Art, die Insel, die Länge und die Höhe des Schnabels, die Länge der Flosse und das Gewicht.

species,island,bill_length_mm,bill_depth_mm,flipper_length_mm,body_mass_g
Adelie,Torgersen,39.1,18.7,181,3750

3. Wie weit zwei Pinguine auseinanderliegen

Trägst du die zwei Maße eines Schnabels als Punkt in ein Diagramm ein, die Länge nach rechts und die Höhe nach oben, dann ist »ähnlich« dasselbe wie »nah«. Wie weit zwei Punkte auseinanderliegen, rechnest du mit dem Satz des Pythagoras aus: Die Unterschiede in jeder Richtung sind die Katheten, der Abstand ist die Hypotenuse.

$$d = \sqrt{(a_1 - b_1)^2 + (a_2 - b_2)^2}$$

Bei mehr als zwei Merkmalen kommt für jedes ein Quadrat unter die Wurzel dazu. Die Formel bleibt dieselbe, nur zeichnen kann man den Raum dann nicht mehr.

# Wie weit zwei Punkte auseinanderliegen, mit beliebig vielen Merkmalen
def distance(a, b)
  sum = 0.0
  a.each_index do |i|
    sum += (a[i] - b[i])**2
  end
  Math.sqrt(sum)
end

import math


# Wie weit zwei Punkte auseinanderliegen, mit beliebig vielen Merkmalen
def distance(a, b):
    total = 0.0
    for i in range(len(a)):
        total += (a[i] - b[i]) ** 2
    return math.sqrt(total)

4. Die nächsten Nachbarn

Ein Beispiel ist ein Paar: die Merkmale und die Antwort, die dazugehört. Bei einem Pinguin sind das die zwei Maße des Schnabels und seine Art: [[39.1, 18.7], "Adelie"]. Die nächsten Nachbarn eines Punktes findest du, indem du alle Beispiele nach ihrem Abstand zu ihm sortierst und die ersten nimmst.

# Die k Beispiele, deren Merkmale features am nächsten liegen, das nächste zuerst
def nearest(examples, features, k)
  examples.sort_by { |other, _label| distance(other, features) }.first(k)
end

# Die k Beispiele, deren Merkmale features am nächsten liegen, das nächste zuerst
def nearest(examples, features, k):
    return sorted(examples, key=lambda example: distance(example[0], features))[:k]

5. Die Nachbarn stimmen ab

Jetzt fehlt die Abstimmung: Welche Antwort kommt unter den k nächsten Nachbarn am häufigsten vor? Kommen zwei gleich oft vor, gewinnt die, die unter den Nachbarn zuerst kommt, also zum näheren gehört.

# Was die meisten der k nächsten Nachbarn sind; bei Gleichstand das, was zuerst kommt
def classify(examples, features, k)
  labels = nearest(examples, features, k).map { |_features, label| label }
  labels.max_by { |label| labels.count(label) }
end

# Was die meisten der k nächsten Nachbarn sind; bei Gleichstand das, was zuerst kommt
def classify(examples, features, k):
    labels = [label for _features, label in nearest(examples, features, k)]
    return max(labels, key=labels.count)

Damit das Programm die Pinguine kennt, liest diese Funktion die Datei. Sie gibt für jeden Pinguin ein Beispiel zurück: die zwei Maße des Schnabels und die Art. Schreib sie unter die anderen in dieselbe Datei:

# Die Pinguine als [[Länge, Höhe], Art]
def penguins(path)
  File.readlines(path).drop(1).map do |line|
    species, _island, length, depth = line.split(",")
    [[length.to_f, depth.to_f], species]
  end
end

require_relative "knn"

examples = penguins("penguins.csv")
puts classify(examples, [46.0, 18.0], 5)

ruby penguins.rb

# Die Pinguine als [[Länge, Höhe], Art]
def penguins(path):
    examples = []
    for line in open(path).readlines()[1:]:
        species, _island, length, depth = line.split(",")[:4]
        examples.append([[float(length), float(depth)], species])
    return examples

from knn import *

examples = penguins("penguins.csv")
print(classify(examples, [46.0, 18.0], 5))

python3 penguins.py

6. Wie oft liegt es richtig?

Gelernt hat das Programm eigentlich nichts. Es hebt alle Beispiele auf und sieht bei jeder Frage nach. Ob das reicht, zeigt sich an Pinguinen, deren Art es nicht kennt: Es bekommt nur jeden zweiten Pinguin als Beispiel und muss die anderen einordnen, deren Art man kennt und vergleichen kann.

# Der Anteil der Testbeispiele, die classify richtig einordnet
def accuracy(training, test, k)
  right = test.count { |features, label| classify(training, features, k) == label }
  right.to_f / test.size
end

# Der Anteil der Testbeispiele, die classify richtig einordnet
def accuracy(training, test, k):
    right = sum(1 for features, label in test if classify(training, features, k) == label)
    return right / len(test)

examples = penguins("penguins.csv")training = examples.select.with_index { |_, i| i.even? }test = examples.select.with_index { |_, i| i.odd? }puts "Richtig: #{(accuracy(training, test, 3) * 100).round(1)} %"

examples = penguins("penguins.csv")training = examples[0::2]test = examples[1::2]print(f"Richtig: {round(accuracy(training, test, 3) * 100, 1)} %")

7. Ein Fahrradverleih entscheidet

Ab hier ist alles ausgedacht. In einer Stadt, durch die ein Fluss fließt, verleiht ein Laden Fahrräder. Wer ein Rad leiht, zahlt manchmal 50 Euro Kaution, die er zurückbekommt, wenn das Rad pünktlich und heil wiederkommt. Ob jemand eine Kaution zahlen muss, haben bisher die Leute im Laden entschieden, und sie haben zu jeder Kundin und jedem Kunden aufgeschrieben:

Jetzt soll ein Programm entscheiden, damit es schneller geht und, wie der Laden sagt, gerechter. Es lernt aus den 300 Entscheidungen der letzten Jahre und entscheidet über die nächsten 300 Kundinnen und Kunden. Die Funktionen hast du schon; dazu kommen zwei, die die Datei lesen. Schreib sie unter die anderen in deine Datei mit den Funktionen:

# Jede Kundin und jeder Kunde als Hash: Spalte => Wert, Zahlen als Zahlen
def customers(path)
  lines = File.readlines(path, chomp: true)
  keys = lines[0].split(",")
  lines.drop(1).map do |line|
    keys.zip(line.split(",")).to_h { |key, value| [key, key == "district" ? value : value.to_f] }
  end
end

# Beispiele aus Kunden: die Spalten in columns als Merkmale, die Kaution als Antwort
def examples(people, columns)
  people.map { |person| [columns.map { |column| person[column] }, person["deposit"].to_i] }
end

require_relative "knn"

people = customers("customers.csv")
past = people.select.with_index { |_, i| i.even? }
latest = people.select.with_index { |_, i| i.odd? }
columns = ["years", "late", "x", "y"]
training = examples(past, columns)
test = examples(latest, columns)
puts "Gleich entschieden wie der Laden: #{(accuracy(training, test, 5) * 100).round(1)} %"

ruby deposit.rb

# Jede Kundin und jeder Kunde als Dictionary: Spalte -> Wert, Zahlen als Zahlen
def customers(path):
    lines = open(path).read().splitlines()
    keys = lines[0].split(",")
    people = []
    for line in lines[1:]:
        person = {}
        for key, value in zip(keys, line.split(",")):
            person[key] = value if key == "district" else float(value)
        people.append(person)
    return people


# Beispiele aus Kunden: die Spalten in columns als Merkmale, die Kaution als Antwort
def examples(people, columns):
    return [[[person[column] for column in columns], int(person["deposit"])] for person in people]

from knn import *

people = customers("customers.csv")
past = people[0::2]
latest = people[1::2]
columns = ["years", "late", "x", "y"]
training = examples(past, columns)
test = examples(latest, columns)
print(f"Gleich entschieden wie der Laden: {round(accuracy(training, test, 5) * 100, 1)} %")

python3 deposit.py

Für die neuen Kundinnen und Kunden weiß man, wie der Laden entschieden hätte; accuracy vergleicht damit, was das Programm sagt. Die Merkmale sind die Jahre, die Verspätungen und der Wohnort, so wie die Leute im Laden ihre Kundschaft kannten.

8. Wen trifft es?

Eine Kaution von jemandem zu verlangen, der jedes Rad pünktlich zurückbringt, ist ein Fehler zu seinen Lasten: Er muss 50 Euro haben, die er für nichts hinterlegt. Ob ein Programm gerecht entscheidet, zeigt sich daran, wen solche Fehler treffen.

def deposit_share(training, test, k)
  deposits = test.count { |features, _label| … }
  # hier: durch die Zahl der Testbeispiele teilen, als Kommazahl
end

# Der Anteil der Testbeispiele, für die classify eine Kaution verlangt (1)
def deposit_share(training, test, k)
  deposits = test.count { |features, _label| classify(training, features, k) == 1 }
  deposits.to_f / test.size
end

def deposit_share(training, test, k):
    deposits = sum(1 for features, _label in test if ...)
    # hier: durch die Zahl der Testbeispiele teilen

# Der Anteil der Testbeispiele, für die classify eine Kaution verlangt (1)
def deposit_share(training, test, k):
    deposits = sum(1 for features, _label in test if classify(training, features, k) == 1)
    return deposits / len(test)

["Altstadt", "Lindenhof", "Bahnhofsviertel", "Sandberg"].each do |district|
  punctual = latest.select { |person| person["district"] == district && person["on_time"] == 1 }
  share = deposit_share(training, examples(punctual, columns), 5)
  puts "#{district}: #{(share * 100).round(1)} % der Pünktlichen sollen Kaution zahlen"
end

for district in ["Altstadt", "Lindenhof", "Bahnhofsviertel", "Sandberg"]:
    punctual = [person for person in latest if person["district"] == district and person["on_time"] == 1]
    share = deposit_share(training, examples(punctual, columns), 5)
    print(f"{district}: {round(share * 100, 1)} % der Pünktlichen sollen Kaution zahlen")

Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.

Stadtteil	Pünktliche	Kaution nach dem Laden	Kaution nach dem Programm
Altstadt	43	18,6 %	14,0 %
Lindenhof	63	28,6 %	15,9 %
Bahnhofsviertel	69	24,6 %	18,8 %
Sandberg	85	70,6 %	84,7 %

Wer am Sandberg wohnt und sein Rad pünktlich zurückbringt, soll in mehr als acht von zehn Fällen eine Kaution zahlen; in den anderen Stadtteilen in ein bis zwei von zehn. Das Programm kennt keine Stadtteile, nur Zahlen. Aber zwei der Zahlen sind der Wohnort, und die nächsten Nachbarn eines Menschen am Sandberg wohnen am Sandberg, im wörtlichen Sinn. Der Laden hat dort öfter eine Kaution verlangt, also verlangt sie das Programm dort auch.

Warum der Laden so entschieden hat, steht in keiner Spalte. Die Daten sind ausgedacht, und das Programm, das sie erzeugt hat, sagt es: Wer am Sandberg wohnt, ist genauso zuverlässig wie alle anderen, aber der Laden hat dort von sechs in zehn Leuten, die er sonst ohne Kaution gelassen hätte, trotzdem eine verlangt. Und das Programm ist sogar strenger als der Laden: Haben drei von fünf Nachbarn eine Kaution gezahlt, verlangt es sie immer. Aus »meistens« wird bei einer Abstimmung »immer«.

Den Wohnort wegzulassen, scheint zu reichen. Aber in der Datei steht noch eine Spalte, die mit dem Wohnort zu tun hat: wie weit jemand vom Laden entfernt wohnt. Der Laden liegt in der Altstadt, nördlich des Flusses.

9. Was der Laden tun könnte

Das Programm macht genau das, was es soll: entscheiden wie der Laden. Der Fehler steckt in den Beispielen, aus denen es lernt. Daraus folgt einiges, was der Laden tun könnte:

• Aus etwas anderem lernen. In on_time steht, ob jemand das nächste Rad wirklich pünktlich zurückgebracht hat. Lernt das Programm daraus statt aus den alten Entscheidungen, lernt es, was tatsächlich passiert ist, nicht, was jemand im Laden vermutet hat.
• Nachmessen, bevor es entscheidet. Wie oft es Pünktliche trifft, je Stadtteil, hast du eben ausgerechnet. Das lässt sich vor dem ersten Einsatz prüfen und danach immer wieder.
• Merkmale prüfen, auch die, die harmlos aussehen, wie die Entfernung.
• Fragen, ob ein Programm hier überhaupt entscheiden soll. Eine Kaution von 50 Euro ist für manche Menschen viel Geld. Wer sie verlangt, sollte sagen können, warum.

Die Datenschutz-Grundverordnung hat dazu eine Regel: Nach Artikel 22 hat jeder Mensch das Recht, keiner Entscheidung unterworfen zu werden, die nur ein Programm getroffen hat und die ihn erheblich beeinträchtigt. Es gibt Ausnahmen, etwa wenn die Entscheidung für einen Vertrag nötig ist; dann muss ein Mensch sie auf Wunsch überprüfen, und die betroffene Person darf ihren Standpunkt darlegen und die Entscheidung anfechten. Ein Mensch bleibt verantwortlich, auch wenn ein Programm entscheidet.

10. Wenn es wirklich passiert

Was dein Programm mit ausgedachten Kunden macht, passiert mit echten Menschen. Die Informatikerin Joy Buolamwini hat es an Programmen gezeigt, die Gesichter erkennen.

Joy Buolamwini, kanadisch-US-amerikanische Informatikerin. Am MIT Media Lab baute sie einen Spiegel, der Gesichter erkennen sollte; ihr Gesicht erkannte die Software erst, als sie eine weiße Maske aufsetzte. Sie gründete die Algorithmic Justice League, die Verzerrungen in Programmen aufdeckt, und schrieb darüber 2023 das Buch »Unmasking AI«.

Wie du am Sandberg hat sie die Fehler eines Programms nach Gruppen getrennt gezählt.

Foto: Niccolò Caranti, 2018, CC BY-SA 4.0, zugeschnitten (Wikimedia Commons)

2018 prüften sie und die Informatikerin Timnit Gebru drei Programme großer Firmen, die auf einem Foto erkennen sollten, ob es eine Frau oder einen Mann zeigt. Bei Männern mit heller Haut lagen sie fast nie falsch, höchstens in 0,8 Prozent der Fälle. Bei Frauen mit dunkler Haut lag eines in 34,7 Prozent der Fälle falsch. Die Sammlungen von Fotos, an denen man solche Programme bis dahin gemessen hatte, zeigten vor allem Menschen mit heller Haut; dass die Programme bei anderen schlechter sind, fiel so nicht auf. Nach der Studie haben IBM und Microsoft ihre Programme überarbeitet.

11. Zum Nachschlagen

• Katas: Listen: Listen durchgehen, mit Index und ohne
• Artikel 22 der DSGVO: automatisierte Entscheidungen im Einzelfall
• Die Pinguine: Kristen Gorman, Tony Williams und William Fraser, »Ecological Sexual Dimorphism and Environmental Variability within a Community of Antarctic Penguins«, PLOS ONE, 2014; die Daten unter CC0 im Paket palmerpenguins
• Die Kundinnen und Kunden des Fahrradverleihs sind ausgedacht; das Programm, das sie erzeugt, steht im Repository des Workspace