Sugerowani znajomi - algorytm

Projekt akademicki, do wyboru mam zarówno użycie gotowej biblioteki i zapoznanie się z nią, jak i również spróbowanie samemu podejścia do implementacji algorytmu. Celem ćwiczenia jest stworzenie mechanizmu podobnego jak na Facebooku czy Linkedinie, czyli sugerowani znajomi. Wersja łatwa to oparcie się po prostu na liczbie wspólnych znajomych, wersja nieco bardziej rozbudowana to dorzucenie innych zmiennych jak wspólne zainteresowania, miejsce zamieszkania, miejsce pracy, szkoła. Po wstępnym researchu widze 3 opcję:

• algorytm k nearest neighbors - wydaje się tutaj odpowiedni? Zaimplementowanie go nawet od 0 nie wydaje się też mega skomplikowane
• http://surpriselib.com/ - wolałbym coś w Javie, aczkolwiek jakieś tam podstawy Pythona mam a więcej chyba nie trzeba by uruchomić bibliotekę
• Hadoop MapReduce

Generalnie ten problem dałoby się załatwić skończoną liczbą ifów, aczkolwiek z chęcią spróbowałbym sił w algorytmice, tak więc najbardziej skłaniam się ku opcji pierwszej. Nie jestem pewien jednak czy to odpowiedni algorytm do tego zadania, dlatego też z chęcią poznam inne opcje.

K-nearest może być ok, ale ogólnie to to jest problem grafowy, a k-nearest jest bardziej problemem przestrzennym. To co potrzebujesz to policzenie ile jest różnych dróg do wierzchołków, które są w odległości 2 ścieżek od zadanego wierzchołka. Następnie sortujesz po tej metryce i wyświetlasz N najlepszych wyników. Po prawdzie to można ogarnąć 1 zapytaniem SQLowym bez bazy grafowej. W bazach grafowych to jest jeszcze prostsze. Ogólnie to jak masz już taki graf, to głupim DFSem/BFSem z odcięciem po 2 skoku można to zrobić. Około 1h roboty.

A może użyć np. CPM https://en.wikipedia.org/wiki/Clique_percolation_method do wygenerowania "grup" i sugerować znajomych właśnie z takich grup do których należy zadany wierzchołek?

W sumie KNN może faktycznie nie być najlepszym pomysłem, chyba że go nie do końca rozumiem?

• biorę użytkownika i jakieś dwie metryki które go opisują, niech będzie np. jego stosunek w skali 1 do 5 do sztuki i do sportu
• nanoszę to na płaszczyzne euklidesową, gdzie X to sztuka, Y do sport, a dane każdego użytkownika przedstawiam jako punkty na tej płaszczyźnie
• dla wybranego użytkownika szukam najbliższych sąsiadów, czyli po prostu k innych punktów które są najbliżej

Czy wybrane kategorie które osadzam na X i Y mają znaczenie, może to być cokolwiek np. X to stosunek do wędkarstwa, gdzie Y opisuję czy dany użytkownik popiera zakaz aborcji? Czy trzeba to jednak jakoś sensownie grupować? Np.parując jakieś skrajne poglądy.
No i sam fakt, że wchodzi w grę jakiś rating jest w sumie mało trafiony, biorąc pod uwage kryteria jak miejsce pracy, miejsce zamieszkania, skończona uczelnia, czy ulubiona potrawa, ciągle obracamy się w bardziej 0/1 stwierdzeniach a nie jakieś mierzalnej opinii.

No chyba, że źle coś rozumiem i jednak da się ten algorytm podciągnąć pod moj problem. Nie żebym się uparł koniecznie na KNN, grafy były w sumie drugim na co napotkałem i skoro tak sugerujecie to sprawdzę Wasze propozycję, chciałbym się po prostu upewnić co do swojego poprzedniego przypuszczenia, szczególnie że prowadzący zajęcia od razu uznał, że KNN nada się tutaj jak znalazł po tym jak wspomniałem o tym algorytmie ;)

#Edit:
Jeszcze co do grafów, nie bardzo mogę sobie to wyobrazić - każdy z wierzchołków to użytkownik, bezpośrednio połączone wierzchołki to jego znajomi? Czyli powiedzmy, że szukamy sugerowanych znajomych dla użytkownika A, bezpośrednie połączenia (wewnętrzny czerwony okrąg) to jego obecni znajomi, a sugerowani znajomi to Ci z wewnątrz drugiego czerwonego kręgu?

Ifami by to mozna nawet zrobić, tylko miejsce zamieszkania to bys musial sie pobawic w robienie mapy w klasie czy strukturze a jak ktos mieszka na wy... znaczy odludziu to może być czasochłonne. Chyba, że tylko z tej samej miejscowości, no to prościzna.

Myśle, że może Cię zainteresować hasło collaborative filtering: https://realpython.com/build-recommendation-engine-collaborative-filtering/