Zanieczyczczenie Giniego

REKLAMA

Web accessibility. Wprowadzenie do dostępności cyfrowej
−40%47,40 zł
Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
29,90 zł

Zanieczyszczenie Giniego (ang. Gini Impurity) – miara niejednorodności danego zbioru wyrażająca się wzorem:

$$G = ∑↙{n} p_n (1-p_n),$$

gdzie pn jest prawdopodobieństwem przynależności elementu do klasy n, czyli liczbą elementów danej klasy podzieloną przez liczbę elementów całego zbioru. Jeśli wszystkie elementy zbioru należą do tej samej klasy, zanieczyszczenie Giniego jest równe 0.

Zanieczyszczenia Giniego nie należy mylić ze współczynnikiem Giniego. Są to miary służące do wyrażania zupełnie innych rzeczy. Współczynnik Giniego określa nierównomierność rozkładu i jest wykorzystywany między innymi do liczbowego wyrażania nierówności w dochodach danego społeczeństwa.

Przykład

Niech będzie dany zbiór {a, a, a, a, a, a, b, b, b, c}. Zbiór ten zawiera dziesięć elementów: sześć należy do klasy a, trzy do klasy b i jeden do klasy c. Prawdopodobieństwa przynależności elementów do kolejnych klas wynoszą zatem kolejno:

  • 0,6 dla klasy a
  • 0,3 dla klasy b
  • 0,1 dla klasy c
Zanieczyszczenie wynosi w takim razie: 0,6 * 0,4 + 0,3 * 0,7 + 0,1 * 0,9 = 0,24 + 0,21 + 0,09 = 0,54.

Zastosowanie

Wskaźnik zanieczyszczenia Giniego jest wykorzystywany do oceny, na ile dobrze jakiś sposób podziału zbioru wejściowego (np. węzeł w drzewie decyzyjnym) separuje poszczególne klasy. Po podziale danego zbioru, łączne zanieczyszczenie uzyskanych podzbiorów wyraża się za pomocą średniej ważonej ich zanieczyszczeń, gdzie waga jest liczbą elementów w podzbiorze.

Przedstawmy to na prostym przykładzie. Załóżmy, że mamy pięć urządzeń:

  • urządzenie 1 – cena: 1000 zł, klasa energetyczna B,
  • urządzenie 2 – cena: 1100 zł, klasa energetyczna B,
  • urządzenie 3 – cena: 1200 zł, klasa energetyczna A,
  • urządzenie 4 – cena: 1300 zł, klasa energetyczna B,
  • urządzenie 5 – cena: 1400 zł, klasa energetyczna A.

Przyjmijmy, że chcemy ustalić próg cenowy, który oddzieliłby urządzenia wyższej klasy energetycznej od niższej. Idealny podział nie jest możliwy, ale za pomocą zanieczyszczenia Giniego możemy określić, który spośród czterech możliwych podziałów daje najbardziej jednolite podzbiory.

  • Dla progu wynoszącego 1050 zł otrzymamy podzbiór jednoelementowy {B} o wskaźniku zanieczyszczenia równym 0 i podzbiór czteroelementowy {B, A, B, A} o wskaźniku równym 1/2. Ich średnia ważona to (1 * 0 + 4 * (1/2)) / 5 = 2 / 5 = 0,4.
  • Dla progu wynoszącego 1150 zł otrzymamy podzbiór dwuelementowy {B, B} o wskaźniku zanieczyszczenia równym 0 i podzbiór trójelementowy {A, B, A} o wskaźniku równym 4/9. Ich średnia ważona to (2 * 0 + 3 * (4/9)) / 5 = 4 / 15 ≈ 0,27.
  • Dla progu wynoszącego 1250 zł otrzymamy podzbiór trójelementowy {B, B, A} o wskaźniku zanieczyszczenia równym 4/9 i podzbiór dwuelementowy {B, A} o wskaźniku równym 0,5. Ich średnia ważona to (3 * (4/9) + 2 * (1/2)) / 5 = 7 / 15 ≈ 0,47.
  • Dla progu wynoszącego 1350 zł otrzymamy podzbiór czteroelementowy {B, B, A, B} o wskaźniku zanieczyszczenia równym 3/8 i podzbiór jednoelementowy {A} o wskaźniku równym 0. Ich średnia ważona to (4 * (3/8) + 1 * 0) / 5 = 3 / 10 = 0,3.

Widzimy więc, że optymalnym progiem jest 1150 zł.

Bibliografia

Ocena: +1 Tak Nie
Liczba głosów: 1.

Dodano: 4 lutego 2022 19:59, ostatnia edycja: 20 września 2022 19:04.

REKLAMA

Zobacz też

Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.

Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).

→ Czytaj całość

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ Czytaj całość

Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.

→ Czytaj całość
Polityka prywatnościKontakt