# Rozdział 4 Grupowanie - analiza skupień

## 4.1 Podział macierzy danych na klasy

Definicja 4.1 Podział macierzy danych \(X\) na \(k\) klas wyznaczony jest przez podział indeksów wierszy na rozłączne zbiory \(I_1,I_2,\dots,I_k\). Wyznaczone są w ten sposób podmacierze \[ X_{[j]}= \begin{bmatrix} X_{i_1} \\ X_{i_2} \\ \vdots \\ X_{i_{n_j}} \end{bmatrix} \] gdzie \[ I_j=\left\{ i_1,i_2,\dots,i_{n_j} \right\} \]

Macierz \(X\) można zapisać:1 \[ X= \begin{bmatrix} X_{[1]} \\ X_{[2]} \\ \vdots \\ X_{[k]} \end{bmatrix} \]

Definicja 4.2 Centroidem \(G_j\) \(j\)_tej klasy podziału \(\mathcal{P}\) nazywamy środek ciężkości \(X_{[j]}\): \[ G_j=g\left(X_{[j]}\right) \] Macierz \[ G_{\mathcal{P}} = \begin{bmatrix} G_1^{n_1} \\ G_1^{n_2} \\ \vdots \\ G_1^{n_k} \end{bmatrix} \]
nazywamy macierzą centroidów podziału \(\mathcal{P}\)
Lemat 4.1 Niech \(G_1,G_2,\dots,G_k\) będą centroidami podziału, \(G=g(X)\).
1. \(G\) jest wypukłą kombinacją \(G_j\): \[ G=\sum_{i=1}^k p_jG_j,\,\, p_j=\frac{n_j}{n},\,\,\sum_{i=1}^kp_j=1 \] 2. \(G\) jest środkiem ciężkości \(G_{\mathcal{P}}\).

Dobry podział charakteryzuje się dwiema cechami:

1. Dane w podmacierzach \(X_{[1]}, X_{[2]}, \dots ,X_{[k]}\) są maksymalnie zwarte2
2. Centroidy podziału są maksymalnie odległe3

Realizacją postulatu 1. jest aby bezwładności \(J\left(X_{[j]}\right)\) były małe, zaś postulatu 2. - aby bezwładność \(J\left(G_{\mathcal{P}}\right)\) była jak największa.
Zazwyczaj trudno jest zrealizować jednocześnie tak dwa sprzeczne cele. Okaże się, że (twierdzenie 4.1) wystarczy realizować jeden z tych postulatów

Definicja 4.3 Bezwładność wewnątrzklasowa podziału \(\mathcal{P}\) jest liczbą \[ J_W\left(\mathcal{P}\right)=\sum_{j=1}^k p_j J\left(X_{[j]}\right) \] Bezwładność międzyklasowa podziału \(\mathcal{P}\) jest liczbą \(J_M\left(\mathcal{P}\right) = J\left(G_{\mathcal{P}}\right)\)
Twierdzenie 4.1 Twierdzenie Pitagorasa dla podziału Dla każdego podziału \(\mathcal{P}\) \[ J(X)=J_W\left(\mathcal{P}\right)+J_M\left(\mathcal{P}\right) \]
Wniosek 4.1 \(J_W\left(\mathcal{P}\right)\) maleje wtedy i tylko wtedy gdy \(J_M\left(\mathcal{P}\right)\) rośnie
Definicja 4.4 Porządek między podziałami \[ \mathcal{P}\succ\mathcal{Q} \iff J_M\left(\mathcal{P}\right) > J_M\left(\mathcal{Q}\right)\\ \mathcal{P}\succeq\mathcal{Q} \iff J_M\left(\mathcal{P}\right) \geq J_M\left(\mathcal{Q}\right) \]
Propozycja 4.1 \[ J_M\left(\mathcal{P}\right)=\sum_{j=1}^k p_j||G_j-G||^2\\ J_W\left(\mathcal{P}\right)=\frac{1}{n} \sum_{j=1}^k \sum_{i \in I_j}||X_i-G_j||^2 \]

### 4.1.1 Przykład

#### 4.1.1.1 Użyteczne funkcje w \(\mathbf{R}\)

    SrodekCiezkosci <- function(dane){
      g <- apply(dane,MARGIN = 2,mean)
      return(list(g = g,n = nrow(dane)))
    }

    srodki_ciezkosci <- function(dane, podzial){
    require(dplyr)
     k <- length(levels(podzial))
     nc <- ncol(dane)
     gg <- numeric(k*(nc+1))
     gg <- array(gg,dim=c(k,nc+1))
     gg <- as.data.frame(gg)
     colnames(gg) <- c(colnames(dane),"n")

     for (i in 1:k) {
       dane %>%
       as.data.frame()  %>%
       filter(podzial == i) %>%
       SrodekCiezkosci() -> gg_rob
       gg[i,1:nc] <- gg_rob$g
       gg[i,(nc+1)] <- gg_rob$n
     }
     return(gg)
    }

    JM <- function(dane, podzial){
      gg <- srodki_ciezkosci(dane, podzial)
      g <- SrodekCiezkosci(dane)$g
      jm <- 0
      for (j in 1: (ncol(gg)-1))
          jm <- jm + gg$n %*%(gg[,j]-g[j])^2
      jm <- as.numeric(jm/nrow(dane))
      return(jm)
    }

#### 4.1.1.2 Dane

    ##   X1 X2
    ## 1  1  1
    ## 2  2  2
    ## 3  3  3
    ## 4  3  4
    ## 5  4  3
    ## 6  5  2

    ggplot(X,aes(X1,X2)) + geom_point(size=3)

#### 4.1.1.3 Porównanie podziałów

    ##   X1 X2 P1 P2 P3
    ## 1  1  1  2  1  1
    ## 2  2  2  2  2  1
    ## 3  3  3  2  1  2
    ## 4  3  4  2  2  2
    ## 5  4  3  1  2  2
    ## 6  5  2  1  1  2

    p1_plot <- ggplot(XP,aes(X1,X2)) + geom_point(size=3,aes(color=P1))
    p2_plot <- ggplot(XP,aes(X1,X2)) + geom_point(size=3,aes(color=P2))
    p3_plot <- ggplot(XP,aes(X1,X2)) + geom_point(size=3,aes(color=P3))
    grid.arrange(p1_plot,p2_plot,p3_plot,nrow=2)

Rys. 4.1: Trzy podziały tych samych danych

Środki ciężkości

    data.frame(
      Podzial=c("P1 K1","P1 K2","P2 K1","P2 K2","P3 K1","P3 K2"),
      rbind(
        srodki_ciezkosci(X,P1),
        srodki_ciezkosci(X,P2),
        srodki_ciezkosci(X,P3)
      )
    )

    ##   Podzial   X1  X2 n
    ## 1   P1 K1 4.50 2.5 2
    ## 2   P1 K2 2.25 2.5 4
    ## 3   P2 K1 3.00 2.0 3
    ## 4   P2 K2 3.00 3.0 3
    ## 5   P3 K1 1.50 1.5 2
    ## 6   P3 K2 3.75 3.0 4

Bezwładność międzyklasowa i wewnątrzklasowa

    jm1 <- JM(X,P1)
    jm2 <- JM(X,P2)
    jm3 <- JM(X,P3)
    (J <- sum(diag(cov(X))))

    ## [1] 3.1

    bzwl <- rbind(
      c(jm1,J-jm1),
      c(jm2,J-jm2),
      c(jm3,J-jm3)
    )
    colnames(bzwl) <- c("JM","JW")
    rownames(bzwl) <- c("P1","P2","P3")
    bzwl

    ##       JM    JW
    ## P1 1.125 1.975
    ## P2 0.250 2.850
    ## P3 1.625 1.475

> \(P3\succ P1 \succ P2\)

## 4.2 Podział Woronoja

Definicja 4.5 Podziałem Woronoja przestrzeni \(\mathbf{R}^p\) o centrach \(C_1,C_2,\dots,C_k\) jest rodzina podzbiorów \(\mathbf{R}^p\): \[ W_j^* = \left\{ P \in \mathbf{R}^p : \; ||P-C_j||=min \{||P-C_r||, \; r=1,2,\dots,k \} \right\} \]

Rys. 4.2: Mapa Tokio z podziałem Woronoja. Centrami są stacje kolejowe. Kolor zależy od odległości od stacji Shinjuku - centralnej stacji w Tokio (biały krzyżyk)

Źródło: https://chichacha.netlify.com/2018/11/10/voronoi-diagram-with-ggvoronoi-package-with-train-station-data/

Zbiory \(W_j^*\) nie są rozłączne (mają wspólne granice). Można je skonstruować tak, aby uzyskały rozłączność: \[ W_j=W_j^*-\bigcup_{r=1}^{j-1}W_r^* \]

Definicja 4.6 Podziałem Woronoja macierzy danych \(X\) o centrach \(C_1,C_2,\dots,C_k\) jest rodzina macierzy \(X_{[j]}\) taka, że \[ I_j = \left\{i: X_i \in W_j \right\} \]
Twierdzenie 4.2 Niech \(\mathcal{P}\) będzie podziałem macierzy \(X\) na \(k\) klas \(X_{[1]},X_{[2]},\dots,X_{[k]}\), \(g(X_{[j]})=G_j \, (j=1,2,\dots,k)\) - centroidami podziału \(\mathcal{P}\). Niech \(\mathcal{Q}\) będzie podziałem Woronoja o centrach \(G_1,G_2,\dots,G_k\). Wtedy \(\mathcal{Q} \succeq \mathcal{P}\).

### 4.2.1 Przykład (cd)

Korzystając z twierdzenia 4.2 znajdziemy dla każdego z podziałów \(P1,P2,P3\) maksymalnie najlepszy podział

#### 4.2.1.1 Użyteczne funkcje w \(\mathbf{R}\)

    deuc <- function(x,y){ # odleglosc euklidesowa
      sum((x-y)^2)
    }

    odSc <- function(x,sc){ #odleglosc x od centroidów sc
      apply(sc,1,function(y) deuc(x,y))
    }

    prox <- function(x,sc){ # podaje numer centroidu najblizszego punktowi x
      which.min(odSc(x,sc))
    }

    proxV <- function(dane,sc){# podaje numery centroidow najblizszych punktom danych dane
      as.factor(apply(dane,1,function(x) prox(x,sc)))
    }

    proxVpod <- function(dane,podzial){# podaje numery klas najblizszych punktom danych dane
      nc <- ncol(dane)
      sc <- srodki_ciezkosci(dane,podzial)[,1:nc]
      proxV(dane,sc)
    }

    proxWyn <- function(dane,podzial){# sprawdza czy nowy podzial lepszy od starego
      w <- proxVpod(dane,podzial)
      rowne <- all.equal.factor(podzial,w)
      return(list(stare=podzial,nowe=w,rowne=rowne))
    }

#### 4.2.1.2 Poprawianie podziałów

    (P11 <- proxWyn(X,P1))

    ## $stare
    ## [1] 2 2 2 2 1 1
    ## Levels: 1 2
    ##
    ## $nowe
    ## [1] 2 2 2 2 1 1
    ## Levels: 1 2
    ##
    ## $rowne
    ## [1] TRUE

> Podział \(P1\) jest podziałem Woronoja

    (P21 <- proxWyn(X,P2))

    ## $stare
    ## [1] 1 2 1 2 2 1
    ## Levels: 1 2
    ##
    ## $nowe
    ## [1] 1 1 2 2 2 1
    ## Levels: 1 2
    ##
    ## $rowne
    ## [1] "2 string mismatches"

    (P22 <- proxWyn(X,P21$nowe))

    ## $stare
    ## [1] 1 1 2 2 2 1
    ## Levels: 1 2
    ##
    ## $nowe
    ## [1] 1 1 2 2 2 2
    ## Levels: 1 2
    ##
    ## $rowne
    ## [1] "1 string mismatch"

    (P23 <- proxWyn(X,P22$nowe))

    ## $stare
    ## [1] 1 1 2 2 2 2
    ## Levels: 1 2
    ##
    ## $nowe
    ## [1] 1 1 2 2 2 2
    ## Levels: 1 2
    ##
    ## $rowne
    ## [1] TRUE

Podział \(P22\$nowe=112222\) jest lepszy podziału \(P2=121221\) i jest równy podziałowi \(P3\). Z tego wynika, że \(P3\) jest podziałem Woronoja. Nie wiadomo, czy są inne podziały Woronoja dla tych danych

    p1_plot <- ggplot(XP,aes(X1,X2)) + geom_point(size=3,aes(color=P1)) + labs(caption="JM=1.125")
    p3_plot <- ggplot(XP,aes(X1,X2)) + geom_point(size=3,aes(color=P3))+ labs(caption="JM=1.625")
    grid.arrange(p1_plot,p3_plot,nrow=2)

Rys. 4.3: Podziały Woronoja dla danych X

Z tych dwóch podziałów Woronoja podział \(P3\) jest lepszy.

1. po odpowiednim przestawieniu wierszy↩

2. Dane wewnątrz klas są do siebie podobne↩

3. Klasy są do siebie niepodobne↩