Zanieczyczczenie Giniego

REKLAMA

English 4 IT. Praktyczny kurs języka angielskiego dla specjalistów IT i nie tylko
−40%29,94 zł
Algorytmy, struktury danych i techniki programowania. Wydanie VI
−40%35,40 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: 0 Tak Nie
Liczba głosów: 0.

Dodano: 4 lutego 2022 19:59, ostatnia edycja: 5 lutego 2022 16:23.

REKLAMA

Zobacz też

Algorytm genetycznymetaheurystyka inspirowana biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.

→ Czytaj całość
Sortowanie bąbelkowe (ang. bubble sort) – prosty algorytm sortowania polegający na porównywaniu za sobą sąsiednich elementów. Złożoności czasowa algorytmu wynosi O(n2).
→ Czytaj całość

Sortowanie przez wstawianie (ang. insertion sort) – prosty algorytm sortowania polegający na wstawianiu kolejnych elementów ciągu we właściwe miejsca. Złożoności czasowa algorytmu wynosi O(n2). Jest to algorytm realizujący metodę przyrostową.

→ Czytaj całość
Polityka prywatnościKontakt