Kolejnym tematem jest algorytm będący preludium do uczenia maszynowego, dziedziny, która robi teraz wielkie "bum" na rynku. Poznajcie "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 "MACHINE LEARNING'U"!

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 też mamy szczątkowe informacje. Na przykładzie człowieka możemy nie znać jego twarzy, ale 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óbujcie dać wiarę, że właśnie w ten sposób Netflix wie jakie filmy Wam 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 przewidzenie 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? Hmmm...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. No i tak dalej, i tym podobne...

KOD ŹRÓDŁOWY

Na postawienie kropki nad i, macie 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();
	}
}

REKORD "POINT"

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

	public int distanceTo(Point point) {
		int x = this.x - point.x;
		int y = this.y - point.y;
		int doubledX = x*x;
		int doubledY = y*y;
		double distance = Math.sqrt(doubledX + doubledY);

		return (int)Math.round(distance);
	}
}

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() {
		this(new Point(0, 0));
	}

	public Item(Point position) {
		this.position = position;
	}

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

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

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

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

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

	public Point getPosition() {
		return position;
	}
}

KLASA "ITEMS"

import java. util.ArrayList;

public class Items extends ArrayList<Item> {
	public Items() {
		add(new Item(new Point(2, 2), "Pomarańcza"));
		add(new Item(new Point(6, 2), "Pomarańcza"));
		add(new Item(new Point(4, 5), "Pomarańcza"));
		add(new Item(new Point(12, 12), "Grejpfrut"));
		add(new Item(new Point(10, 10)));
	}
}

KLASA "ITEMTYPESCORES"

import java. util.*;

public class ItemTypeScores extends HashMap<String, Integer> {
	public ItemTypeScores(ArrayList<Item> closestItems) {
		putScores(closestItems);
	}

	public String typeWithHighestScore() {
		Item item = new Item();
		int highestScore = 0;

		for (Map.Entry<String, Integer> entry : entrySet()) {
			int value = entry.getValue();
			
			if(value > highestScore) {
				highestScore = value;

				item.setType(entry.getKey());
			}
		}

		return item.getType();
	}

	private void putScores(ArrayList<Item> closestItems) {
		for (Item item : closestItems) {
			String type = item.getType();
			int count = containsKey(type) ? get(type) + 1 : 1;

			put(type, count);
		}
	}
}

KLASA "CLOSESTITEMS"

import java. io.PrintStream;
import java. util.ArrayList;
import java. util.Comparator;

public class ClosestItems extends ArrayList<Item> {
	public ClosestItems(ArrayList<Item> items) {
		super(items);
		removeIf(Item::typeIsUnknown);
	}

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

	public void sortByDistanceRelativelyToUnknownItem(Item unknownItem) {
		Point unknownItemPosition = unknownItem.getPosition();

		sort((Comparator.comparingInt(o -> o.getPosition().distanceTo(unknownItemPosition))));
	}

	public void printDistancesToUnknownItem(Item unknownItem) {
		PrintStream ps = System.out;
		Point unknownItemPosition = unknownItem.getPosition();

		ps.println("Odległości: ");
		forEach(e -> ps.println(e.getPosition().distanceTo(unknownItemPosition)));
	}
}

KLASA "KNN"

import java. io.PrintStream;

public class KNN {
	private final Items items = new Items();
	private final ClosestItems closestItems = new ClosestItems(items);
	private final PrintStream printStream = System.out;

	public KNN() {
		Item unknownItem = items.get(4);

		items.forEach(printStream::println);
		sortClosestItems(unknownItem);
		excludeClosestItems(3);
		identifyObject(closestItems, unknownItem);
		items.forEach(printStream::println);
	}

	private void sortClosestItems(Item unknownItem) {
		closestItems.sortByDistanceRelativelyToUnknownItem(unknownItem);
		closestItems.printDistancesToUnknownItem(unknownItem);
		printStream.println("Posortowani wg odległości: ");
		closestItems.forEach(printStream::println);
	}

	private void excludeClosestItems(int neighbors) {
		closestItems.removeElementsWithIndexHigherThanGiven(neighbors);
		printStream.println("Pozostali sąsiedzi: ");
		closestItems.forEach(printStream::println);
	}

	private void identifyObject(ClosestItems closestItems, Item unknownItem) {
		ItemTypeScores typeScores = new ItemTypeScores(closestItems);
		String typeWithHighestScore = typeScores.typeWithHighestScore();

		printStream.println("WYNIKI TYPÓW: " + typeScores);
		printStream.println("Zidentyfikowano typ! Jest to " + typeWithHighestScore);
		unknownItem.setType(typeWithHighestScore);
	}
}

K najbliższych sąsiadów rozbiłem na czynniki pierwsze. Mamy ten sam rekord dla punktu w dwuwymiarowym układzie współrzędnych, co w jednym z poprzednich przykładów. Tam jest tylko jedna metoda kalkująca długość odcinka od tego punktu do drugiego podanego w parametrze oraz przesłonięcie metody "toString" celem zdefiniowania i wyświetlenia informacji o współrzędnych w momencie przypisania referencji obiektu w miejsce metody "print" i "println".

Drugie 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. Poza tym, dodałem przesłonięcie tej samej metody "toString" wraz z drobną modyfikacją łańcucha (kiedy typ jest nieznany, wstaw znaki zapytania) oraz "gettery" i "settery", czyli nic niewymagającego tłumaczeń.

Dalej mamy klasę pochodną od "ArrayList", która sterczy tylko w celu odseparowania dodawania elementów od całej reszty kodu. Powiem tylko o tym ostatnim elemencie, który wprowadziłem 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.

"ItemTypeScores" ma za zadanie przechowywać wyniki odnośnie liczebności wykrytych rodzajów obiektów. Konstruktor potrzebuje listy najbliżej stojących przedmiotów, aby później w prywatnej metodzie przypisywać liczniki do każdego klucza (w postaci łańcucha znaków obiektu) i liczyć liczbę znalezionych sztuk. Operator trójargumentowy pilnuje, aby liczyć elementy danego typu w sposób prawidłowy. Jeżeli słownik nie posiada klucza, to jest on 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. Klasa dziedziczy od słownika "HashMap".

Na tym podział się nie kończy. Dla najbliższych przedmiotów także dodałem osobny plik źródłowy w postaci klasy "ClosestItems". W jej konstruktorze (prócz "super" odwołującego się do konstruktora bazowego) znajdziecie wywołanie "removeIf", które wykasuje w try miga wszystkie obiekty o nieznanym pochodzeniu. A 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 macie trzy publiczne metody. Pierwsza 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), druga sortuje elementy w liście według odległości od obcego obiektu w kolejności rosnącej, a trzecia po prostu wypisuje wyniki na ekranie terminala.

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 wtłaczamy tę pierwszą oraz to samo "PrintStream" dla tego samego celu: uprościć wywołania "println-owe". Treść konstruktora jest już dużo bardziej bogata. Lokalna zmienna oznacza wydobycie z listy elementów "tego nieznanego", bo zostanie użyty jako parametr kilku metod jednocześnie. Pierwsza z nich definiuje treść dla sortowania najbliżej stojących elementów wokół nieznanego obiektu. Tak naprawdę to interesuje nas jedynie wywołanie pierwszej metody, gdyż reszta jest tylko wypisywaniem rezultatów. Druga metoda wyklucza z listy obiekty przekraczające indeks w kolejności od liczby podanej w parametrze (wyjaśnienie wyżej). Metoda na samym dole, 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).

Weźcie 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. w sytuacji kiedy 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 alfa, 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