K najbliższych sąsiadów. Teoria i kod źródłowy

Kolejnym tematem jest algorytm będący preludium do uczenia maszynowego, dziedziny, która robi teraz wielkie "bum" na rynku 💣. Poznaj "K najbliższych sąsiadów", zagadnienie identyfikacji nowych obiektów na podstawie sąsiedztwa z innymi obiektami (i nie tylko) 🗣!

K NAJBLIŻSZYCH SĄSIADÓW WSTĘPEM DO UCZENIA MASZYNOWEGO!

Nazwa jest całkiem popularna i jak raz poznałem "K nearest neighbours" na studiach inżynierskich, tak z biegiem czasu dociera do moich uszu coraz częściej. Chodzi tutaj o dylemat powstający w momencie potrzeby zidentyfikowania obiektu, o którym nie wiemy niczego lub mamy szczątkowe informacje. Na przykładzie człowieka możemy nie znać jego twarzy, natomiast możemy powiedzieć o jego płci, wzroście, w jakim jest wieku czy jakie są jego upodobania. W uczeniu maszynowym nazywa się takie informacje "cechami" i na podstawie takich cech, program może podjąć próbę przypisania obcej osoby do którejś z grup społecznych. Podałem jedno z co najmniej KILKUDZIESIĘCIU przykładowych zastosowań do czego może nam się przydać ten algorytm 😯. Spróbuj dać wiarę, że właśnie w ten sposób Netflix wie jakie filmy Ci zarekomendować jako następne do obejrzenia ⭐!

Problem: zidentyfikowanie nieznanego obiektu i przypisanie go do odpowiedniej grupy już znanych obiektów na podstawie podanych kryteriów LUB predykcja przyszłości / odpowiedzi etc. na podstawie podanych kryteriów

K najbliższych sąsiadów może się nadać tak naprawdę do dwóch rzeczy. Nauka określa je klasyfikacją oraz regresją. Klasyfikacja to przyporządkowanie nieznanego obiektu do jednej z grup znanych obiektów, a z regresją mamy do czynienia wtedy, kiedy chcemy przewidzieć czyiś ruch w niedalekiej przyszłości np. kurs dolara USD za dwa dni, ulubione filmy użytkownika według jego ruchu w serwisie (często nazywane jako "Proponowane" albo "Sugerowane") i tym podobne ✅. W obu zastosowaniach żeby algorytm mógł pomóc, musi mieć zestaw danych wejściowych czyli pisząc poprawnie, zestaw cech. I tu dopiero zaczyna się karuzela 🌀!

Aby nie otrzymać na wyjściu żadnych głupot, algorytm musi otrzymać precyzyjnie przemyślany duży zestaw informacji 🌐. Sztuką nie jest ilość, ale jakość, choć im więcej dobrze dobranych informacji, tym większa efektywność rezultatów 📈. Najważniejszy jest dobór odpowiednich cech i to w obu zastosowaniach. Weźmy ponownie człowieka bez wiedzy o jego tożsamości. Co może być najważniejsze w klasyfikacji człowieka? To zależy od zastosowania. W przypadku grupy fanów jakiejś serii filmów, to kluczowe okażą się jego zainteresowania kinematograficzne. Kiedy w grę wchodzi udział w grze zespołowej, możemy brać pod uwagę jego wzrost. A co do wysokości emerytury, lata przepracowane w charakterze doświadczenia komercyjnego. I tak dalej, i tym podobne...

KOD ŹRÓDŁOWY

Na postawienie kropki nad i, masz ode mnie standardowo kod źródłowy w języku Java ukazujący prostolinijne działanie algorytmu K najbliższych sąsiadów:

KLASA "MAIN"

public class Main {
	public static void main(String[] args) {
		new KNN();
	}
}

K najbliższych sąsiadów rozbiłem na czynniki pierwsze. W metodzie "main" mamy tworzenie instancji klasy, której tłumaczenie zostawiłem na sam koniec, bo stanowi połączenie wszystkich klocków w jedną całość 🧩.

REKORD "POINT"

public record Point(int x, int y) {
	@Override
	public String toString() {
		return "(" + x + ", " + y + ")";
	}

	public double getDistanceTo(Point point) {
		if(point == null) {
			return Double.MAX_VALUE;
		}

		var x = this.x - point.x;
		var y = this.y - point.y;
		var squaredX = x*x;
		var squaredY = y*y;

		return Math.sqrt(squaredX + squaredY);
	}
}

Powyżej mamy rekord (klasę danych) dla punktu w dwuwymiarowym układzie współrzędnych. Tam jest tylko jedna metoda kalkująca długość odcinka od tego punktu, do drugiego podanego w parametrze. W przypadku, gdy parametr przyjmuje wartość "null", ma zwracać wartość maksymalną, jaką może zmieścić typ "double" ("Double.MAX_VALUE"). To jest po to, żeby odsuwać bzdurne wartości na sam koniec. Oprócz tego, jest przesłonięcie metody "toString" celem zdefiniowania wyświetlenia informacji o współrzędnych w momencie przypisania referencji obiektu w miejsce metod "print" i "println".

KLASA "ITEM"

public class Item {
	private final StringBuilder type = new StringBuilder();
	private final Point position;

	public Item(Point position, String type) {
		this(position);
		setType(type);
	}

	public Item(Point position) {
		this.position = position != null ? position : new Point(0, 0);
	}

	@Override
	public String toString() {
		var type = this.type.isEmpty() ? "???" : this.type.toString();

		return "Typ obiektu: " + type + ", pozycja: " + getPosition();
	}

	public void setType(String type) {
		if(type != null) {
			this.type.replace(0, this.type.length(), type);
		}
	}

	public String getType() {
		return type.toString();
	}

	public boolean typeIsUnknown() {
		return type.isEmpty();
	}

	public double getDistanceTo(Item item) {
		return position != null && item != null ? position.getDistanceTo(item.getPosition()) : 0;
	}

	public Point getPosition() {
		return position;
	}
}

Drugi plik źródłowy w kolejności, to klasa "Item". "Item" ma w sobie dwie dane składowe: obiekt "StringBuilder" (również z tego samego powodu opisanego poprzednio) oraz pozycję w układzie dwuwymiarowym. Mamy także przeciążone konstruktory. Pierwszy z nich potrzebuje nazwy oraz pozycji. To jest postać domyślna. Drugi z nich to wariant dla obiektu nieznanego pochodzenia, o którym wiemy tylko tyle gdzie się znajduje.

Dodałem też przesłonięcie tej samej metody "toString" wraz z drobną modyfikacją łańcucha (kiedy typ jest nieznany, to ma wstawić znaki zapytania) oraz metody przypisujące oraz pobierające odpowiednie dane (tzw. "gettery" i "settery"), czyli nic niewymagającego tłumaczeń, za wyjątkiem "getDistanceTo" - dodałem ją, żeby skrócić ten ciąg przedostawania się do metody wyznaczającej odległość do punktu 〰️.

KLASA "ITEMS"

import java. util.ArrayList;

public class Items extends ArrayList {
	private static final String ORANGE_ITEM_TYPE = "Pomarańcza";
	private static final String GRAPEFRUIT_ITEM_TYPE = "Grejpfrut";

	public Items() {
		add(new Item(new Point(2, 2), ORANGE_ITEM_TYPE));
		add(new Item(new Point(6, 2), ORANGE_ITEM_TYPE));
		add(new Item(new Point(4, 5), ORANGE_ITEM_TYPE));
		add(new Item(new Point(12, 12), GRAPEFRUIT_ITEM_TYPE));
		add(new Item(new Point(10, 10)));
	}

	public Optional getFirstItemWithUnknownTypeIfPossible() {
		return stream().filter(Item::typeIsUnknown).findFirst();
	}
}

Dalej mamy klasę pochodną dziedziczącą od "ArrayList" ("Items"), która występuje tylko w celu odseparowania dodawania elementów od całej reszty kodu, w ramach dobrych praktyk 👍. U góry wprowadziłem dwie stałe jako rodzaje obiektów tych już zidentyfikowanych. W konstruktorze dodajemy sobie elementy wśród których, ten ostatni jest jako ten "obcy" i który nasz algorytm spróbuje zidentyfikować patrząc na sąsiadujące obiekty. Dlatego on wyjątkowo nie ma przypisanego typu.

Dużo ciekawsza może być dla Ciebie metoda "getFirstItemWithUnknownTypeIfPossible" - tutaj skorzystałem z dobrodziejstwa programowania funkcyjnego i wstawiłem taki oto ciąg wywołań (wyciągnę go może, żeby było wiadomo o co biega):

stream().filter(Item::typeIsUnknown).findFirst();

On jednym zdaniem pobiera pierwszy znaleziony element (przedmiot), który nie ma zdefiniowanego typu (metoda "typeIsUnknown" zwraca wartość prawdziwą). "stream" pobiera sekwencję elementów, "filter" zwraca nową listę po przefiltrowaniu wszystkich elementów według tzw. "predykatu" (metody określającej kryterium na podstawie którego dany element ma przyjąć lub odrzucić), a "findFirst" próbuje pobrać pierwszy element w kolejności (stąd zwraca dokładnie typ "Optional"). Jednym słowem, to jest "opakowanie" zmiennej danego typu, która może przyjąć wartość "null" i ma stanowić zabezpieczenie przed zgłoszeniem wyjątku "NullPointerException", gdy program spróbuje coś zrobić na tej referencji 🔒.

KLASA "ITEMTYPESCORES"

import java. util.*;

public class ItemTypeScores extends HashMap {
	public ItemTypeScores(ArrayList items) {
		if(items != null) {
			items.forEach(this::addItem);
		}
	}

	public String getTypeWithHighestNumberOfUnits() {
		var entry = entrySet().stream().max(Comparator.comparingInt(Entry::getValue));

		return entry.isPresent() ? entry.get().getKey() : "NULL";
	}

	private void addItem(Item item) {
		if(item == null) {
			return;
		}

		var itemType = item.getType();
		var numberOfItemsOfType = containsKey(itemType) ? get(itemType) + 1 : 1;

		put(itemType, numberOfItemsOfType);
	}
}

Klasa "ItemTypeScores" ma za zadanie przechowywać wyniki odnośnie liczebności wykrytych rodzajów obiektów. Konstruktor wstawia na dzień dobry listę najbliżej stojących przedmiotów w sposób dostosowany do słownika. W metodzie "addItem" (o dostępie prywatnym) elementy są przypisywane według klucza (w postaci łańcucha znaków typu przedmiotu) i każdorazowo "doliczane" do odpowiedniego typu. Operator trójargumentowy pilnuje, aby doliczać elementy danego typu w sposób prawidłowy ✅. Jeżeli słownik nie posiada klucza, to dany typ jest dopisywany z początkową wartością 1, a w przeciwnym wypadku, inkrementuje.

Druga metoda już o dostępie publicznym zwraca typ o najwyższym wyniku. Przyda się to w momencie nadawania typu obcemu elementowi 👍. Mamy znowu ciąg metod (tylko nieco szerszy 😜):

entrySet().stream().max(Comparator.comparingInt(Entry::getValue));

który w kolejności: pobiera zbiór par klucz-wartość ("entrySet"), pobiera sekwencję elementów ("stream") i zwraca ten o maksymalnej wartości ("max"), który w tym wypadku oznacza "rekordzistę" w zliczonych obiektach jednego typu ☺️. Uff 😁...Żeby jeszcze bardziej umilić sobie życie, porównuję liczby używając metody statycznej "comparingInt" z klasy "Comparator". "Entry::getValue" oznacza pobranie liczby zliczonych obiektów jednego typu - technicznie rzecz ujmując, to jest referencja do metody.

KLASA "CLOSESTITEMS"

import java. util.*;

public class ClosestItems extends ArrayList {
	public ClosestItems(ArrayList items) {
		super(items != null ? items.stream().filter(element -> !element.typeIsUnknown()).toList() : new ArrayList<>());
	}

	public void removeElementsWithIndexHigherThan(int index) {
		subList(index, size()).clear();
	}

	public void sortByDistanceToItemIfPossible(Item item) {
		if(item != null) {
			sort(Comparator.nullsLast(Comparator.comparingDouble(element -> element.getDistanceTo(item))));
		}
	}
}

Idźmy dalej. Dla najbliższych przedmiotów także dodałem osobny plik źródłowy w postaci klasy "ClosestItems". W jej konstruktorze (w wywołaniu "super" odwołującego się do konstruktora bazowego) jest pobieranie elementów z listy z parametru i dodanie ich tutaj. Dbamy o przefiltrowanie wyników z pominięciem tych o nieznanym typie ❎. Czynimy tak dlatego, że to będzie pula obiektów dla przyporządkowywania obiektu obcego, więc siłą rzeczy nie możemy mieć żadnych obcych osobników 😆.

Dalej są dwie publiczne metody. Pierwsza od góry ("removeElementsWithIndexHigherThan") usuwa nam obiekty o indeksie większym od zadanego w parametrze (służy to do ograniczenia liczebności do podanej liczby jako sąsiadów, gdyż w metodzie inicjującej K najbliższych sąsiadów, polegamy na ograniczonej liczbie danych). Metoda "subList" zwraca fragment listy według podanego kryterium, a potem wywołujemy "clear" i tak czyścimy niechciane elementy 🤭.

Druga ("sortByDistanceToItemIfPossible") sortuje elementy w liście według odległości od obcego obiektu w kolejności rosnącej. To kolejny ciąg instrukcji, który może budzić grozę wśród niektórych 👻, lecz tutaj programowanie funkcyjne naprawdę warto opanować w Javie, bo można w ten sposób sobie fajnie uprościć kod 😎. "sort" sortuje...chyba jasne 😆. Dalej stosuję komparator "nullsLast", żeby odsunąć wartości "null" na ostatnie miejsca w kolejności (czyli w zasadzie to robi to samo, co ja zrobiłem w metodzie "getDistanceTo", w rekordzie "Point", gdy tam jest wartość "null" 😁). Potem tak naprawdę sortuję rosnąco, tylko tym razem stosując "comparingDouble" (bo metoda obliczająca dystans pomiędzy dwoma punktami zwraca typ "double") i sięgam po tę samą metodę ("getDistanceTo") ✨.

KLASA "RESULTSPRINTER"

import java. io.PrintStream;
import java. util.*;
import java. util.function.Function;

public class ResultsPrinter {
	private final PrintStream printStream = System.out;

	public  void printAllElementsOf(List list, String message, Function function) {
		printLine(message);

		if(list != null && function != null) {
			list.forEach(element -> printStream.println(function.apply(element)));
		}
	}

	public  void printAllElementsOf(List list, String message) {
		printLine(message);
		printAllElementsOf(list);
	}

	public  void printAllElementsOf(List list) {
		if(list != null) {
			list.forEach(printStream::println);
		}
	}

	public  void printAllElementsOf(Map map, String message) {
		printLine(message + map);
	}

	public  void printElement(T type, String message) {
		printLine(message + type);
	}

	private void printLine(String message) {
		printStream.println(message);
	}
}

Ta klasa jest absolutnie poboczna i nie ma związku z jakąkolwiek częścią działania K najbliższych sąsiadów ℹ️. "ResultsPrinter" jedynie służy do wypisywania wyników podczas funkcjonowania aplikacji - dałem ją tylko dla celów dydaktycznych 😄. Jedna finalna dana składowa jest tylko do zwiększenia komfortu w pisaniu "println". Żeby uczynić wszystkie metody "podstawialnymi" pod różne przypadki, umieściłem dużo typów generycznych, które bardzo się przydały ✊. Jak spojrzysz na metodę "printAllElementsOf", to zobaczysz kolejny rzadziej spotykany element - "Function"!

"Function" w języku Java ma dokładnie takie samo zastosowanie, co niejakie "Func" w języku C# - to jest możliwość wstawienia instrukcji w miejsce parametru, które musi na wyjściu zwrócić wartość odpowiedniego typu (to jest zawsze ostatni parametr wewnątrz nawiasów kątowych). Jest jeden przypadek użycia tej wersji przeciążenia metody, jednak spróbuj go sam(a) znaleźć 😁!

KLASA "KNN"

public class KNN {
	private final Items items = new Items();
	private final ClosestItems closestItems = new ClosestItems(items);
	private final ResultsPrinter resultsPrinter = new ResultsPrinter();

	private static final int NUMBER_OF_NEIGHBORS = 3;

	public KNN() {
		var optionalUnknownItem = items.getFirstItemWithUnknownTypeIfPossible();

		if(optionalUnknownItem.isEmpty()) {
			return;
		}

		var unknownItem = optionalUnknownItem.get();

		resultsPrinter.printAllElementsOf(items);

		closestItems.sortByDistanceToItemIfPossible(unknownItem);

		resultsPrinter.printAllElementsOf(closestItems, "Odległości: ", element -> String.valueOf(element.getDistanceTo(unknownItem)));
		resultsPrinter.printAllElementsOf(closestItems, "Posortowani wg odległości: ");

		closestItems.removeElementsWithIndexHigherThan(NUMBER_OF_NEIGHBORS);

		resultsPrinter.printAllElementsOf(closestItems, "Pozostali sąsiedzi: ");

		identifyItemIfPossible(unknownItem);

		resultsPrinter.printAllElementsOf(items);
	}

	private void identifyItemIfPossible(Item item) {
		if(item == null || !item.typeIsUnknown()) {
			return;
		}

		var itemTypeScores = new ItemTypeScores(closestItems);

		item.setType(itemTypeScores.getTypeWithHighestNumberOfUnits());
		resultsPrinter.printAllElementsOf(itemTypeScores, "WYNIKI TYPÓW: ");
		resultsPrinter.printElement(item, "Zidentyfikowano typ! Jest to: ");
	}
}

Tak oto przechodzimy do "serca" aplikacji - KNN to ostatnia część potrzebująca wyjaśnień.

Trzy finalne dane składowe określają kolejno listę elementów WSZYSTKICH, listę najbliższych elementów, do której dodajemy elementy tej pierwszej oraz instancję klasy do wywołań "println-owych" 🙂. Niżej mamy zdefiniowaną stałą do określania ile sąsiednich elementów bierzemy pod uwagę w momencie ustalania typu dla obcego obiektu ("NUMBER_OF_NEIGHBORS") 👽.

Treść konstruktora jest już dużo bardziej bogata. Najpierw pobieramy element do identyfikacji. Lokalna zmienna ma za zadanie posiadać element nieznany wydobyty z listy, bo zostanie użyty jako parametr dla kilku różnych metod. Znów jest użycie typu "Optional", aby dopasować go do typu wartości zwracanej przez metodę "getFirstItemWithUnknownTypeIfPossible". 

Po upewnieniu się, że znaleziono jakiś element nieznanego pochodzenia, jest przypisanie "wypakowanej" referencji do kolejnej zmiennej lokalnej ("get"), a później to już same wywołania. Instrukcje pochodzące od "resultsPrinter" oddzieliłem wersem odstępu, aby w razie potrzeby, wiedzieć co możesz usunąć, jeśli nie potrzebujesz wypisywania wyników w ekranie terminala ℹ️.

Pierwszą konkretną operacją jest sortowanie według najbliżej stojących elementów wokół nieznanego obiektu ("sortByDistanceToItemIfPossible"). Druga operacja ("removeElementsWithIndexHigherThan") wyklucza z listy obiekty przekraczające indeks w kolejności od liczby podanej w parametrze (wyjaśnienie wyżej). Metoda na samym dole wydzielona jako jedyna ("identifyItemIfPossible"), dokonuje klasyfikacji obiektu na podstawie wyników liczebności poszczególnych typów. Po wykonaniu instrukcji, obiekt zostaje zidentyfikowany tylko i wyłącznie na podstawie liczby sąsiadujących obiektów (tych najbliższych). Na tym etapie jest zakończenie działania programu 🏁.

Weź pod uwagę bardzo istotną sprawę ⚠️! Pokazałem BARDZO prosty przykład dokonujący identyfikacji obiektu na podstawie tylko jednej cechy jaką jest odległość euklidesowa. Żeby takie K najbliższych sąsiadów dawało jakiś użytek, to tych cech musiałoby być co najmniej kilkanaście 😱! Ponadto odległość euklidesowa nie zawsze może przynieść oczekiwany rezultat np. sytuacja, gdy jakiś nasz znajomy spełnia wszystkie cechy do konkretnego przypisania, a jedyne co go wykreśla, to zbyt duża odległość. Warto wtedy pochylić się nad podobieństwem cosinusowym, które to określa stopień przynależności na podstawie cosinusa kąta, a nie długości odcinka 🔼.

To by było tyle. Dzięki za uwagę i to na razie będzie stanowiło przystanek w redagowaniu o algorytmice ✋. Sprawdzimy jakie będzie zainteresowanie publiczności (i czy w ogóle) 🙂.

PODOBNE ARTYKUŁY

• Programowanie dynamiczne w algorytmice. Siatka podproblemów
• Problem NP-zupełny w algorytmice
• Problem pokrycia zbioru. Teoria i kod źródłowy