Dokumentacja techniczna dotycząca algorytmu klastrowania Microsoft

Dotyczy: SQL Server 2019 i starsze usługi Analysis Services Azure Analysis Services Fabric/Power BI Premium

W tym artykule wyjaśniono implementację algorytmu klastrowania Microsoft, w tym parametry, których można użyć do kontrolowania zachowania modeli klastrowania. Artykuł zawiera również wskazówki dotyczące zwiększania wydajności podczas tworzenia i przetwarzania modeli klastrowania.

Aby uzyskać więcej informacji na temat używania modeli klastrowania, zobacz następujące artykuły:

• Zawartość modelu danych dla modeli klastrów (Analysis Services — eksploracja danych)

• Przykłady zapytań modelu klastrowania

implementacja algorytmu klastrowania Microsoft

Algorytm klastrowania Microsoft udostępnia dwie metody tworzenia klastrów i przypisywania punktów danych do klastrów. K-średnich jest metodą klastrowania twardego, co oznacza, że punkt danych może należeć tylko do jednego klastra, a algorytm oblicza pojedyncze prawdopodobieństwo członkostwa każdego punktu danych w tym klastrze. Maksymalizowanie oczekiwań (EM) to metoda klastrowania miękkiego , co oznacza, że punkt danych zawsze należy do wielu klastrów, a algorytm oblicza prawdopodobieństwo dla każdej kombinacji punktów danych i klastra.

Należy wybrać algorytm do użycia, ustawiając parametr CLUSTERING_METHOD . Domyślną metodą klastrowania jest skalowalne rozwiązanie EM.

Klastrowanie EM

W klastrowaniu EM algorytm iteracyjnie uściśli początkowy model klastra w celu dopasowania danych i określa prawdopodobieństwo, że punkt danych istnieje w klastrze. Algorytm kończy proces, gdy model probabilistyczny pasuje do danych. Funkcja używana do określania dopasowania to logarytmiczna funkcja wiarygodności danych przy danym modelu.

Jeśli proces generuje puste klastry lub członkostwo jednego lub większej liczby klastrów spadnie poniżej danego progu, algorytm ponownie przekierzy klastry o niskiej populacji w nowych punktach i ponownie uruchomi algorytm EM.

Wyniki metody klastrowania EM są probabilistyczne, co oznacza, że każdy punkt danych należy do wszystkich klastrów, ale każde przypisanie punktu danych do klastra ma inne prawdopodobieństwo. Ponieważ metoda umożliwia nakładanie się klastrów, suma elementów we wszystkich klastrach może przekraczać łączną liczbę elementów w zestawie treningowym. W wynikach modelu eksploracji danych wyniki wskazujące poziom wsparcia są korygowane, aby uwzględnić to nakładanie się.

Algorytm EM jest domyślnym algorytmem używanym w modelach klastrowania firmy Microsoft. Ten algorytm jest domyślny, ponieważ oferuje następujące korzyści w porównaniu z klastrowaniem metodą k-średnich:

• Wymaga co najwyżej jednego skanowania bazy danych.

• Działa pomimo ograniczonej pamięci RAM.

• Może używać kursora tylko do przodu.

• Przewyższa metody próbkowania.

Implementacja firmy Microsoft oferuje dwie opcje: skalowalne i nieskalowe EM. W skalowalnej wersji EM pierwsze 50 000 rekordów domyślnie inicjuje wstępne skanowanie. Jeśli ten krok zakończy się pomyślnie, model używa tylko tych danych. Jeśli model nie może zmieścić się przy użyciu 50 000 rekordów, algorytm odczytuje kolejne 50 000 rekordów.

W nieskalowalnym EM algorytm przetwarza cały zbiór danych niezależnie od jego rozmiaru. Ta metoda może tworzyć bardziej dokładne klastry, ale może mieć znaczące wymagania dotyczące pamięci. Ponieważ skalowalny algorytm EM działa na buforze lokalnym, iterowanie po danych jest szybsze, a algorytm lepiej wykorzystuje pamięć podręczną procesora niż nieskalowalny algorytm EM. Skalowalny algorytm EM jest trzy razy szybszy niż nieskalowalne EM, nawet wtedy, gdy wszystkie dane mieszczą się w pamięci operacyjnej. W większości przypadków poprawa wydajności nie prowadzi do obniżenia jakości kompletnego modelu.

Aby zapoznać się z raportem technicznym opisującym implementację EM w algorytmie grupowania firmy Microsoft, zobacz Scaling EM (Expectation Maximization) Clustering to Large Databases.

klastrowanie metodą k-średnich

Grupowanie K-średnich to dobrze znana metoda przypisywania członkostwa w klastrze poprzez minimalizowanie różnic między elementami w klastrze, jednocześnie maksymalizując odległość między klastrami. Termin „średnie” w metodzie k-średnich odnosi się do centroidu klastra, czyli punktu danych wybieranego arbitralnie, a następnie iteracyjnie udoskonalanego, aż będzie reprezentował rzeczywistą średnią wszystkich punktów danych w klastrze. „k” odnosi się do arbitralnie wybranej liczby punktów, które inicjują proces grupowania. Algorytm k-średnich oblicza kwadratowe odległości euklidesowe między rekordami danych a wektorem reprezentującym średnią klastra w klastrze i zbiega się do ostatecznego zbioru k klastrów, gdy ta suma osiągnie minimalną wartość.

Algorytm k-średnich przypisuje każdy punkt danych do dokładnie jednego klastra i nie pozwala na niepewność członkostwa. Wyrażasz członkostwo w klastrze jako odległość od centroidu.

Zazwyczaj algorytm k-średnich służy do tworzenia klastrów atrybutów ciągłych, gdzie obliczanie odległości do średniej jest proste. Jednak implementacja firmy Microsoft adaptuje metodę k-średnich do grupowania atrybutów dyskretnych za pomocą prawdopodobieństw. W przypadku atrybutów dyskretnych odległość punktu danych z określonego klastra jest obliczana w następujący sposób:

1 — P(punkt danych, klaster)

Algorytm k-średnich udostępnia dwie metody próbkowania zbioru danych: nieskalowalną metodę k-średnich, która ładuje cały zbiór danych i wykonuje jedno przejście klastrowania, oraz skalowalną metodę k-średnich, w której algorytm wykorzystuje pierwsze 50 000 rekordów i odczytuje kolejne rekordy tylko wtedy, gdy potrzebuje więcej danych, aby uzyskać dobre dopasowanie modelu do danych.

Aktualizacje algorytmu klastrowania firmy Microsoft w programie SQL Server 2008

W SQL Server 2008 domyślna konfiguracja algorytmu klastrowania Microsoft została zmieniona w celu użycia parametru wewnętrznegoNORMALIZATION = 1. Algorytm przeprowadza normalizację z wykorzystaniem statystyk z-score i zakłada, że dane mają rozkład normalny. Celem tej domyślnej zmiany zachowania jest zminimalizowanie wpływu atrybutów o dużej wielkości i wielu wartości odstających. Jednak normalizacja z-score może zmienić wyniki klastrowania w przypadku rozkładów, które nie mają rozkładu normalnego, takich jak rozkłady jednostajne. Aby zapobiec normalizacji i uzyskać takie samo zachowanie jak algorytm klastrowania K-średnich w SQL Server 2005, użyj okna dialogowego Ustawienia parametrów, aby dodać parametr niestandardowy NORMALIZATION i ustawić jego wartość na 0.

Dostosowywanie algorytmu klastrowania firmy Microsoft

Algorytm klastrowania Microsoft obsługuje kilka parametrów, które wpływają na zachowanie, wydajność i dokładność wynikowego modelu wyszukiwania.

Parametry algorytmu

W poniższej tabeli opisano parametry, których można użyć z algorytmem klastrowania Microsoft. Te parametry wpływają zarówno na wydajność, jak i dokładność wynikowego modelu eksploracji danych.

METODA KLASTERYZACJI
Określa metodę klastrowania dla algorytmu do użycia. Dostępne są następujące metody klastrowania:

Wartość domyślna to 1 (skalowalna wersja EM).

CLUSTER_COUNT
Określa przybliżoną liczbę klastrów do skompilowania przez algorytm. Jeśli algorytm nie może skompilować przybliżonej liczby klastrów z danych, tworzy jak najwięcej klastrów. Ustawienie wartości CLUSTER_COUNT na 0 powoduje, że algorytm używa heurystyki w celu najlepszego określenia liczby klastrów do skompilowania.

Wartość domyślna to 10.

CLUSTER_SEED
Określa numer inicjujący używany przez algorytm do losowego generowania klastrów na początkowym etapie tworzenia modelu.

Zmieniając tę liczbę, można zmienić sposób kompilowania początkowych klastrów, a następnie porównać modele utworzone przy użyciu różnych nasion. Jeśli zmienisz ziarno, ale klastry znajdowane przez algorytm nie zmienią się znacząco, możesz uznać model za stosunkowo stabilny.

Wartość domyślna to 0.

MINIMUM_SUPPORT
Określa minimalną liczbę przypadków wymaganych do utworzenia klastra. Jeśli liczba przypadków w klastrze jest niższa niż ta liczba, algorytm traktuje klaster jako pusty i odrzuca go. Jeśli ustawisz tę liczbę za wysoką, możesz przegapić prawidłowe klastry.

Wartość domyślna to 1.

MODELOWANIE_KARDYNALNOŚCI
Określa liczbę przykładowych modeli, które algorytm tworzy podczas procesu klastrowania.

Zmniejszenie liczby modeli kandydatów może poprawić wydajność na ryzyko braku niektórych dobrych modeli kandydatów.

Wartość domyślna to 10.

TOLERANCJA_ZATRZYMANIA
Określa wartość używaną przez algorytm do określenia, kiedy osiągana jest zbieżność, a algorytm kończy tworzenie modelu. Zbieżność jest osiągana, gdy ogólna zmiana prawdopodobieństwa klastra jest mniejsza niż stosunek parametru STOPPING_TOLERANCE podzielonego przez rozmiar modelu.

Wartość domyślna to 10.

rozmiar próbki
Określa liczbę przypadków, których algorytm używa w każdym przekazaniu, jeśli parametr CLUSTERING_METHOD jest ustawiony na jedną ze skalowalnych metod klastrowania. Ustawienie parametru SAMPLE_SIZE na 0 powoduje, że cały zestaw danych jest klastrowany w jednym przebiegu, co może powodować problemy z pamięcią i wydajnością.

Wartość domyślna to 50000.

MAKSYMALNE_ATTRYBUTY_WEJŚCIOWE
Określa maksymalną liczbę atrybutów wejściowych, które algorytm może obsłużyć, zanim wywoła wybór funkcji. Ustawienie tej wartości na 0 określa, że nie ma maksymalnej liczby atrybutów.

Zwiększenie liczby atrybutów może znacznie obniżyć wydajność.

Wartość domyślna to 255.

MAXIMUM_STATES
Określa maksymalną liczbę stanów atrybutów, które obsługuje algorytm. Jeśli atrybut ma więcej stanów niż maksimum, algorytm używa najpopularniejszych stanów i ignoruje pozostałe stany.

Zwiększenie liczby stanów może znacznie obniżyć wydajność.

Wartość domyślna to 100.

Flagi modelarskie

Algorytm obsługuje następujące flagi modelowania. Zdefiniuj flagi modelowania podczas tworzenia struktury górniczej lub modelu górnictwa. Flagi modelowania określają sposób obsługi wartości w każdej kolumnie podczas analizy.

Requirements

Model klastrowania musi zawierać kolumnę klucza i kolumny wejściowe. Można również zdefiniować kolumny wejściowe jako przewidywalne. Kolumny ustawione jako Tylko przewidywanie nie są używane do tworzenia klastrów. Rozkład tych wartości w klastrach jest obliczany po skompilowanych klastrach.

Kolumny wejściowe i przewidywalne

Algorytm klastrowania Microsoft obsługuje kolumny wejściowe i przewidywalne kolumny wymienione w poniższej tabeli. Aby uzyskać więcej informacji o tym, co oznaczają typy zawartości w przypadku użycia w modelu wyszukiwania, zobacz Typy zawartości (wyszukiwanie danych).

Zobacz także

Algorytm klastrowania firmy Microsoft
Przykłady zapytań modelu klastrowania
Zawartość modelu danych dla modeli klastrów (Analysis Services — eksploracja danych)