Grupowanie danych wielowymiarowych — Clustering high-dimensional data

Grupowanie danych wielowymiarowych to analiza skupień danych zawierających od kilkudziesięciu do wielu tysięcy wymiarów . Takie wysokowymiarowe przestrzenie danych są często spotykane w dziedzinach takich jak medycyna , gdzie technologia mikromacierzy DNA może generować wiele pomiarów na raz, oraz grupowanie dokumentów tekstowych , gdzie w przypadku użycia wektora częstotliwości słów liczba wymiarów jest równa wielkość słownictwa .

Problemy

W przypadku klastrowania danych wielowymiarowych należy rozwiązać cztery problemy:

  • Wiele wymiarów jest trudnych do przemyślenia, niemożliwych do wizualizacji, a ze względu na wykładniczy wzrost liczby możliwych wartości z każdym wymiarem, pełne wyliczenie wszystkich podprzestrzeni staje się niewykonalne wraz ze wzrostem wymiarowości. Ten problem jest znany jako przekleństwo wymiarowości .
  • Pojęcie odległości staje się mniej precyzyjne wraz ze wzrostem liczby wymiarów, ponieważ odległość między dowolnymi dwoma punktami w danym zbiorze danych jest zbieżna. W szczególności rozróżnianie najbliższego i najdalszego punktu staje się bez znaczenia:
  • Klaster jest przeznaczony do grupowania powiązanych obiektów na podstawie obserwacji wartości ich atrybutów. Jednak biorąc pod uwagę dużą liczbę atrybutów, niektóre atrybuty zwykle nie będą miały znaczenia dla danego klastra. Na przykład w badaniach przesiewowych noworodków klaster próbek może identyfikować noworodki, które mają podobne wartości krwi, co może prowadzić do wglądu w znaczenie niektórych wartości krwi dla choroby. Ale w przypadku różnych chorób różne wartości krwi mogą tworzyć klaster, a inne wartości mogą być nieskorelowane. Jest to znane jako lokalny problem istotności cech : różne klastry mogą znajdować się w różnych podprzestrzeniach, więc globalne filtrowanie atrybutów nie jest wystarczające.
  • Biorąc pod uwagę dużą liczbę atrybutów, prawdopodobnie niektóre atrybuty są skorelowane . Stąd klastry mogą istnieć w dowolnie zorientowanych podprzestrzeniach afinicznych .

Ostatnie badania wskazują, że problemy z dyskryminacją pojawiają się tylko wtedy, gdy istnieje duża liczba nieistotnych wymiarów, a podejście polegające na współdzieleniu najbliższego sąsiada może poprawić wyniki.

Podejścia

Podejścia do grupowania w równoległych do osi lub arbitralnie zorientowanych podprzestrzeniach afinicznych różnią się tym, jak interpretują ogólny cel, jakim jest znajdowanie klastrów w danych o wysokiej wymiarowości. Ogólnie odmiennym podejściem jest znajdowanie klastrów na podstawie wzorca w macierzy danych, często nazywanej biklastrowaniem , która jest techniką często stosowaną w bioinformatyce .

Grupowanie podprzestrzenispace

Przykładowa przestrzeń 2D z klastrami podprzestrzennymi

Sąsiedni obraz przedstawia jedynie dwuwymiarową przestrzeń, w której można zidentyfikować wiele gromad. W podprzestrzeniach jednowymiarowych można znaleźć klastry (w podprzestrzeni ) oraz , , (w podprzestrzeni ). nie może być uważany za klaster w dwuwymiarowej (pod)przestrzeni, ponieważ jest zbyt słabo rozłożony na osi. W dwóch wymiarach można zidentyfikować dwa klastry i .

Problem grupowania podprzestrzeni wynika z faktu, że istnieją różne podprzestrzenie przestrzeni o wymiarach. Jeżeli podprzestrzenie nie są równoległe do osi, możliwa jest nieskończona liczba podprzestrzeni. Dlatego algorytmy grupowania podprzestrzennego wykorzystują pewien rodzaj heurystyki, aby zachować wykonalność obliczeniową, ryzykując uzyskanie gorszych wyników. Na przykład, własność zamykania w dół (por. reguły asocjacji ) może być użyta do zbudowania podprzestrzeni w wyższych wymiarach tylko przez połączenie podprzestrzeni o niższych wymiarach, ponieważ każda podprzestrzeń T zawierająca klaster spowoduje, że pełna przestrzeń S również będzie zawierała to klaster (tj. S ⊆ T), podejście przyjęte przez większość tradycyjnych algorytmów, takich jak CLIQUE, SUBCLU . Możliwe jest również zdefiniowanie podprzestrzeni przy użyciu różnych stopni istotności dla każdego wymiaru, podejście przyjęte przez iMWK-Means, EBK-Modes i CBK-Modes.

Przewidywane grupowanie

Przewidywane klastrowanie ma na celu przypisanie każdego punktu do unikalnego klastra, ale klastry mogą istnieć w różnych podprzestrzeniach. Ogólnym podejściem jest użycie specjalnej funkcji odległości wraz ze zwykłym algorytmem grupowania .

Na przykład algorytm PreDeCon sprawdza, które atrybuty wydają się obsługiwać grupowanie dla każdego punktu, i dostosowuje funkcję odległości tak, aby wymiary o małej wariancji były wzmacniane w funkcji odległości. Na powyższym rysunku klaster można znaleźć przy użyciu DBSCAN z funkcją odległości, która kładzie mniejszy nacisk na oś - i tym samym wyolbrzymia małą różnicę w osi wystarczająco do zgrupowania punktów w klaster.

PROCLUS stosuje podobne podejście z grupowaniem k-medoid . Odgaduje się medoidy początkowe, a dla każdego medoidu wyznacza się podprzestrzeń objętą atrybutami o małej wariancji. Punkty są przypisywane do najbliższego medoidu, biorąc pod uwagę tylko podprzestrzeń tego medoidu przy określaniu odległości. Algorytm postępuje następnie jak zwykły algorytm PAM .

Jeśli funkcja odległości waży atrybuty w inny sposób, ale nigdy z 0 (a zatem nigdy nie usuwa nieistotnych atrybutów), algorytm nazywa się „miękkim” algorytmem grupowania .

Grupowanie oparte na projekcji

Grupowanie oparte na projekcji opiera się na nieliniowej projekcji danych wielowymiarowych w przestrzeni dwuwymiarowej. Typowe metody projekcji, takie jak rozproszone t stochastyczne osadzanie sąsiadów (t-SNE) lub wizualizator pobierania sąsiadów (NerV) są używane do wyraźnego rzutowania danych na dwa wymiary, z pominięciem podprzestrzeni wyższego wymiaru niż dwa i zachowywanie tylko odpowiednich sąsiedztw w wielowymiarowych dane. W następnym kroku obliczany jest wykres Delaunaya między rzutowanymi punktami, a każdy wierzchołek między dwoma rzutowanymi punktami jest ważony odległością między odpowiednimi wysokowymiarowymi punktami danych. Następnie najkrótsza ścieżka między każdą parą punktów jest obliczana przy użyciu algorytmu Dijkstry . Najkrótsze ścieżki są następnie wykorzystywane w procesie grupowania, który obejmuje dwie opcje w zależności od typu struktury w danych wielowymiarowych. O tym logicznym wyborze można się zdecydować, patrząc na mapę topograficzną struktur wielowymiarowych. W analizie porównawczej 34 porównywalnych metod grupowania klasteryzacja oparta na projekcji była jedynym algorytmem, który zawsze był w stanie znaleźć wysokowymiarową odległość lub strukturę opartą na gęstości zestawu danych. Klastrowanie oparte na projekcjach jest dostępne w pakiecie R o otwartym kodzie źródłowym „ProjectionBasedClustering” w CRAN.

Podejścia hybrydowe

Nie wszystkie algorytmy próbują znaleźć unikalne przypisanie klastra dla każdego punktu lub wszystkich klastrów we wszystkich podprzestrzeniach; wielu zgadza się na wynik pomiędzy, gdzie znajduje się pewna liczba prawdopodobnie nakładających się, ale niekoniecznie wyczerpujących zestawów klastrów. Przykładem jest FIRES, który w swoim podstawowym podejściu jest algorytmem grupowania podprzestrzennego, ale używa heurystyki zbyt agresywnej, aby wiarygodnie utworzyć wszystkie klastry podprzestrzenne. Innym podejściem hybrydowym jest włączenie pętli „człowieka do algorytmu”: wiedza specjalistyczna w dziedzinie ludzkiej domeny może pomóc zredukować wykładniczą przestrzeń poszukiwań poprzez heurystyczną selekcję próbek. Może to być korzystne w dziedzinie zdrowia, gdzie np. lekarze mają do czynienia z wielowymiarowymi opisami stanu pacjenta i pomiarami powodzenia pewnych terapii. Ważnym pytaniem w takich danych jest porównanie i korelacja stanów pacjentów i wyników terapii wraz z kombinacjami wymiarów. Liczba wymiarów jest często bardzo duża, w związku z czym należy je zmapować do mniejszej liczby odpowiednich wymiarów, aby były bardziej podatne na analizę ekspercką. Dzieje się tak, ponieważ nieistotne, zbędne i sprzeczne wymiary mogą negatywnie wpływać na skuteczność i wydajność całego procesu analitycznego.

Grupowanie korelacji

Inny typ podprzestrzeni jest rozważany w klastrowaniu korelacji (eksploracja danych) .

Oprogramowanie

  • ELKI zawiera różne algorytmy klastrowania podprzestrzeni i korelacji
  • FCPS zawiera ponad pięćdziesiąt algorytmów klastrowania

Bibliografia

  1. ^ B Kriegel HP ; Kröger, P.; Zimek A. (2009). „Klastrowanie danych wielowymiarowych”. Transakcje ACM dotyczące wykrywania wiedzy z danych . 3 : 1-58. doi : 10.1145/1497577.1497578 .
  2. ^ Houle, ME; Kriegel, HP ; Kröger, P.; Schubert, E.; Zimek A. (2010). Czy odległości dzielone od sąsiadów mogą pokonać klątwę wymiarowości? (PDF) . Zarządzanie naukowymi i statystycznymi bazami danych. Notatki z wykładów z informatyki. 6187 . str. 482. doi : 10.1007/978-3-642-13818-8_34 . Numer ISBN 978-3-642-13817-1.
  3. ^ Agrawal, R.; Gehrke, J.; Gunopulos, D.; Raghavan, P. (2005). „Automatyczne klastrowanie podprzestrzenne danych wielkowymiarowych”. Eksploracja danych i odkrywanie wiedzy . 11 : 5-33. CiteSeerX  10.1.1.131.5152 . doi : 10.1007/s10618-005-1396-1 .
  4. ^ Kailing, K.; Kriegel, HP ; Kröger, P. (2004). Klastry podprzestrzenne połączone z gęstością dla danych wielkowymiarowych . Materiały z Międzynarodowej Konferencji SIAM 2004 poświęconej eksploracji danych. s.  246 . doi : 10.1137/1.9781611972740.23 . Numer ISBN 978-0-89871-568-2.
  5. ^ De Amorim, RC; Mirkin, B. (2012). „Metryka Minkowskiego, ważenie cech i inicjalizacja klastrów anomalnych w grupowaniu K-średnich”. Rozpoznawanie wzorców . 45 (3): 1061. doi : 10.1016/j.patcog.2011.08.012 .
  6. ^ Carbonera, Joel Luis; Abel, Mara (listopad 2014). Algorytm grupowania podprzestrzeni oparty na entropii dla danych kategorialnych . 2014 IEEE 26th International Conference on Tools with Artificial Intelligence . IEEE. doi : 10.1109/ictai.2014.48 . Numer ISBN 9781479965724.
  7. ^ Carbonera, Joel Luis; Abel, Mara (2015). Tryby CBK: Algorytm oparty na korelacji do kategorycznego grupowania danych . Materiały XVII Międzynarodowej Konferencji Systemów Informatycznych w Przedsiębiorstwie . SCITEPRESS - Publikacje Naukowe i Technologiczne. doi : 10.5220/0005367106030608 . Numer ISBN 9789897580963.
  8. ^ Böhm, C.; Kailing, K.; Kriegel, H.-P. ; Kröger, P. (2004). Klastry połączone gęstością z lokalnymi preferencjami podprzestrzennymi (PDF) . Czwarta Międzynarodowa Konferencja IEEE na temat eksploracji danych (ICDM'04). str. 27. doi : 10.1109/ICDM.2004.10087 . Numer ISBN 0-7695-2142-8.
  9. ^ Aggarwal, CC; Wilk, JL; Yu, PS; Procopiuc, C.; Park, JS (1999). „Szybkie algorytmy przewidywanego grupowania”. Rekord ACM SIGMOD . 28 (2): 61. CiteSeerX  10.1.1.681.7363 . doi : 10.1145/304181.304188 .
  10. ^ a b c Thrun, MC, & Ultsch, A. : Używanie klastrów opartych na projekcji do znajdowania klastrów opartych na odległości i gęstości w danych wielkowymiarowych, J. Classif., s. 1-33, doi: 10.1007/s00357-020- 09373-2 .
  11. ^ Van der Maaten, L. i Hinton, G .: Wizualizacja danych za pomocą t-SNE, Journal of Machine Learning Research, tom. 9 (11), s. 2579-2605. 2008.
  12. ^ Venna, J., Peltonen, J., Nybo, K., Aidos, H. i Kaski, S.: Perspektywa wyszukiwania informacji do nieliniowej redukcji wymiarowości do wizualizacji danych, The Journal of Machine Learning Research, tom. 11 , s. 451-490. 2010.
  13. ^ Delaunay, B .: Sur la sphere vide, Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, t. 7 (793-800), s. 1-2. 1934.
  14. ^ Dijkstra, EW: Uwaga na temat dwóch problemów związanych z wykresami, Numerische mathematik, tom. 1 (1), s. 269-271. 1959.
  15. ^ Thrun, MC i Ultsch, A .: Odkrywanie wysokowymiarowych struktur projekcji z metod redukcji wymiarów, MethodsX, tom. 7, s. 101093, doi: 10.1016/j.mex.20200.101093,2020 .
  16. ^ "CRAN — klastrowanie oparte na projekcji pakietów" .
  17. ^ Kriegel, H .; Kröger, P.; Renz, M.; Wurst, S. (2005). Ogólne ramy efektywnego klastrowania podprzestrzennego danych wielkowymiarowych (PDF) . Piąta Międzynarodowa Konferencja IEEE na temat eksploracji danych (ICDM'05). str. 250. doi : 10.1109/ICDM.2005.5 . Numer ISBN 0-7695-2278-5.
  18. ^ Hund, M.; Böhm, D.; Sturm, W.; Sedlmair, M.; Schreck, T.; Keim, Waszyngton; Majnaric, L.; Holzinger, A. (2016). „Analityka wizualna do eksploracji koncepcji w podprzestrzeniach grup pacjentów: Zrozumienie złożonych zbiorów danych za pomocą Doctor-in-the-loop” . Informatyka mózgu . 3 (4): 233–247. doi : 10.1007/s40708-016-0043-5 . PMC  5106406 . PMID  27747817 .
  19. ^ Thrun, MC i Stier, Q .: Pakiet podstawowych algorytmów klastrowania, SoftwareX, tom. 13(C), s. 100642, doi: 10.1016/j.softx.2020.100642, 2021 .