k- mediane grupare - k-medians clustering
În statistici , clusterizarea k- medians este un algoritm de analiză cluster . Este o variație a grupării k- înseamnă că în loc să calculăm media pentru fiecare cluster pentru a-i determina centroul, se calculează în schimb mediana . Acest lucru are ca efect reducerea la minimum a erorilor asupra tuturor clusterelor în raport cu metrica distanței cu 1 normă , spre deosebire de metrica pătrată a distanței cu 2 norme (ceea ce înseamnă k ).
Aceasta se referă direct la problema k -mediană în raport cu norma 1, care este problema găsirii k centrelor astfel încât grupurile formate de acestea să fie cele mai compacte. În mod oficial, având în vedere un set de puncte de date x , k centrele c i trebuie alese astfel încât să minimizeze suma distanțelor de la fiecare x la cel mai apropiat c i .
Funcția de criteriu formulată în acest mod este uneori un criteriu mai bun decât cel utilizat în algoritmul de grupare k- înseamnă , în care se utilizează suma distanțelor pătrate. Suma distanțelor este utilizată pe scară largă în aplicații precum locația facilității .
Algoritmul propus folosește iterația în stil Lloyd care alternează între un pas de așteptare (E) și maximizare (M), făcând din acesta un algoritm de așteptare-maximizare . În pasul E, toate obiectele sunt atribuite celei mai apropiate mediane. În pasul M, medianele sunt recalculate utilizând mediana în fiecare dimensiune.
Medianele și medoizii
Mediana este calculată în fiecare dimensiune în formularea Manhattan-distanță a problemei k- mediani, astfel încât atributele individuale vor proveni din setul de date. Acest lucru face algoritmul mai fiabil pentru seturi de date discrete sau chiar binare. În schimb, utilizarea mijloacelor sau a medianelor la distanță euclidiană nu va produce neapărat atribute individuale din setul de date. Chiar și cu formularea la distanță Manhattan, atributele individuale pot proveni din instanțe diferite din setul de date; astfel, mediana rezultată poate să nu fie un membru al setului de date de intrare.
Acest algoritm este adesea confundat cu algoritmul k -medoids . Cu toate acestea, un medoid trebuie să fie o instanță reală din setul de date, în timp ce pentru mediana multivariată la distanță Manhattan aceasta este valabilă doar pentru valorile unui singur atribut. Mediana reală poate fi astfel o combinație de instanțe multiple. De exemplu, având în vedere vectorii (0,1), (1,0) și (2,2), mediana distanței Manhattan este (1,1), care nu există în datele originale și, prin urmare, nu poate fi o medoid.
Software
- ELKI include diverse variante de k-mijloace, inclusiv k-mediane.
- Kmtrianii FORTRAN
- GNU R include k-mediane în pachetul „flexclust”.
- Stata kmedians