Zanieczyczczenie Giniego

REKLAMA

Kwalifikacja INF.03. Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych. Część 3. Programowanie aplikacji internetowych. Podręcznik do nauki zawodu technik informatyk i technik programista
−15%38,16 zł
C++. Algorytmy i struktury danych
129,00 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ż

Metoda z zastosowaniem przepływu blokującego – algorytm wyznaczający maksymalny przepływ w sieci przepływowej. W algorytmie tym przepływ zwiększany jest iteracyjnie, w każdej iteracji wyznaczony przepływ jest powiększany o przepływ blokujący w warstwowej sieci residualnej.

→ Czytaj całość

Symulowane wyżarzanie – jedna z technik projektowania algorytmów heurystycznych (metaheurystyka). Cechą charakterystyczną tej metody jest występowanie parametru sterującego zwanego temperaturą, który maleje w trakcie wykonywania algorytmu. Im wyższą wartość ma ten parametr, tym bardziej chaotyczne mogą być zmiany. Podejście to jest inspirowane zjawiskami obserwowanymi w metalurgii – im większa temperatura metalu, tym bardziej jest on plastyczny.

Jest to metoda iteracyjna: najpierw losowane jest pewne rozwiązanie, a następnie jest ono w kolejnych krokach modyfikowane. Jeśli w danym kroku uzyskamy rozwiązanie lepsze, wybieramy je zawsze. Istotną cechą symulowanego wyżarzania jest jednak to, że z pewnym prawdopodobieństwem może być również zaakceptowane rozwiązanie gorsze (ma to na celu umożliwienie wyjście z maksimum lokalnego).

Prawdopodobieństwo przyjęcia gorszego rozwiązania wyrażone jest wzorem e(f(X)−f(X'))/T (rozkład Boltzmanna), gdzie X jest poprzednim rozwiązaniem, X' nowym rozwiązaniem, a f funkcją oceny jakości – im wyższa wartość f(X), tym lepsze rozwiązanie. Ze wzoru można zauważyć, że prawdopodobieństwo przyjęcia gorszego rozwiązania spada wraz ze spadkiem temperatury i wzrostem różnicy jakości obu rozwiązań.

→ Czytaj całość

Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.

Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.

→ Czytaj całość
Polityka prywatnościKontakt