Koncepcja klasyfikatora opartego na programowaniu

ekspresji genów i logice rozmytej

Jacek Kluska

Politechnika Rzeszowska

2011

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

1 / 52

Problem klasyfikacji danych

Dane: zbiór rekordów danych (przykładów, obserwacji, ...):

{(

x

1

, y

1

)

,

. . . ,

(

x

Q

, y

Q

)

} ⊂

X

× {

c

1

,

. . . , c

m

}

,

X

⊂

R

n

.

Problem: Znaleźć model (klasyfikator) przydzielający c

i

dla x

i

∈

R

n

.

// Regresja:

//

{(

x

1

, y

1

)

,

. . . ,

(

x

Q

, y

Q

)

} ⊂

R

n

×

R.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

2 / 52

Wstęp - metody klasyfikacji danych

DT

pojedyncze, wzmacniane, lasy drzew
(ID3, Quinlan 1979; CART, Breiman 1984; C4.5/C5 Quinlan 1993, ...)

kNN,

SVM,

ANN

MLP,
PNN,
RBF,
LVQ,
GMDH,

Na¨ıve Bayes,

Metoda k-średnich,

Rodziny klasyfikatrów,

GEP.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

3 / 52

Programowanie ekspresji genów (GEP) - fenotyp

Ferreira C., Gene Expression Programming. Mathematical Modeling
by an Artificial Intelligence (2nd Edition), Ser. Studies in
Computational Intelligence 21, Springer Verlag, 2006.
Idea: drzewo wyrażenia

p

(

a

+

b

) (

c

−

d

)

- fenotyp

// fenotyp - zespół dostrzegalnych cech powstałych w wyniku

// oddziaływania warunków środowiska na genotyp organizmu.

//

√

.

=

Q

√

.

∗

+

−

a

b

c

d

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

4 / 52

GEP - język K, genotyp

012345678901
*-/Qb+b+aaab

- genotyp wyrażony w języku K

// genotyp - zespół genów danego organizmu,

// warunkujący jego właściwości dziedziczne.

∗

−

/

Q

b

+

b

+

a

a

a

b

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

5 / 52

GEP - przykład wyrażenia boole’owskiego

{

A, O, N, I

}

;

A = AND, O = OR, N = NOT,

I = If-then-else: If a

=

1, then b; else c

0123456789012345
NIAbObbaaaabaabb

N

I

A

b

O

b

b

a

a

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

6 / 52

GEP - chromosomy i geny

Chromosomy GEP składają się z wielu genów, każdy o stałej
długości.

// Chromosomy - składniki jąder komórek, będące siedliskiem genów.

Założenia (GEP):

Gen =

h

glowa, ogon

i ⊂ {

funkcje,zmienne,stałe

} × {

zmienne,stałe

}

Ogon - zasobnik argumentów dla funkcji.

|

ogon

| = |

glowa

| (

ArgMax

−

1

) +

1.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

7 / 52

GEP - ORF

Otwarta ramka odczytu:

*b+a-a*ab

// ORF - każda sekwencja DNA lub RNA,

// która potencjalnie może ulec translacji na białko.

∗

b

+

a

−

a

∗

ab

+

//

+

b

+

|

{z

}

babbabbbababbaaa

|

{z

}

głowa

ogon

∗

b

+

a

−

a

∗

a

b

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

8 / 52

GEP - przykład chromosomu dla wyrażeń arytmetycznych

0123456789012

0123456789012

0123456789012

*Qb+*/bbbabab

-a+QbQbbababa

/ba-/*bbaaaaa

Sub-ET1

Sub-ET2

Sub-ET3

∗

Q

b

+

∗

/

b

b

b

a

−

a

+

Q

b

Q

b

/

b

a

Chromosomy można łączyć, np.

++(

Sub-ET1

)(

Sub-ET2

)(

Sub-ET3

)

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

9 / 52

GEP - przykład chromosomu dla wyrażeń booleowskich

Przykład

0123456789012345

0123456789012345

0123456789012345

OcIbAcaabcbccaaa

IANAIbbaaaabaaab

AcbcIcaaaacaccaa

Można utworzyć

I(

Sub-ET1

)(

Sub-ET2

)(

Sub-ET3

)

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

10 / 52

GEP - operacje genetyczne

1

Mutacja genetyczna

2

Inwersja genetyczna

3

Transpozycja genetyczna

1

Transpozycja genetyczna typu IS

2

Transpozycja genetyczna typu RIS

3

Przeniesienie genu

4

Rekombinacja genetyczna

1

Rekombinacja genetyczna jednopunktowa

2

Rekombinacja genetyczna dwupunktowa

3

Rekombinacja genetyczna zwykła

5

Operatory genetyczne dla stałych nymerycznych

1

Mutacja dc

2

Inwersja dc

3

Transpozycja dc IS

4

Mutacja losowych stałych mumerycznych

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

11 / 52

GEP - mutacja genetyczna - efekt kurczenia się fenotypu

*b+a

-

a*ab+//+b+

babbabbbababbaaa

*b+a

Q

a*ab+//+b+

babbabbbababbaaa

∗

b

+

a

−

a

∗

a

b

=⇒

∗

b

+

a

Q

a

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

12 / 52

GEP - mutacja genetyczna - efekt rozrastania się fenotypu

*b+a-a*a*

b

b+//+b+

babbabbbababbaaa

*b+a-a*a*

Q

b+//+b+

babbabbbababbaaa

∗

b

+

a

−

a

∗

a

b

=⇒

∗

b

+

a

−

a

∗

a

Q

b

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

13 / 52

GEP - inwersja genetyczna

Inwersja w GEP ograniczona jest tylko do głowy genów.

Przykład

Sekwencja “/Qb” w genie 1 (pozycje 1-3) została wybrana do inwersji.
Wynik:

012345678901234012345678901234012345678901234
-

/Qb

aadcdbadbdc-cbd+Qdbaabdacd+QbddQ-ddabdbbb

-

bQ/

aadcdbadbdc-cbd+Qdbaabdacd+QbddQ-ddabdbbb

Nowe chromosomy (indywidua) powstałe w wyniku inwersji są
syntaktycznie poprawne.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

14 / 52

GEP - transpozycja genetyczna

Fragmenty genomu (transposons) są aktywowane, a następnie są
przeniesione/kopiowane do innego miejsca w chromosomie.
W GEP są 3 rodzaje przestawiania fragmentów genów:

1

Transpozycja genetyczna typu IS (Insertion Sequence
transposition). Z całego chromosomu wybierana jest losowo
sekwencja IS. Jej kopia dodaje się w losowo wybranym miejscu
głowy genu, z wyjątkiem pierwszej pozycji.

2

Transpozycja genetyczna typu RIS (Root Insertion Sequence
transposition). Sekwencja wybierana jest z głowy genu, zaczyna się
od funkcji i jest kopiowana do startowej pozycji “root”. Głowa jest
skanowana w poszukiwaniu funkcji, począwszy od losowo wybranego
punktu (gdy nie ma funkcji, operator nic nie robi).

3

Przeniesienie genu (Gene transposition). Cały gen przenosi się do
początku chromosomu.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

15 / 52

Transpozycja genetyczna typu IS

Z całego chromosomu wybierana jest losowo pewna sekwencja “IS”
(Insertion Sequence). Jej kopia dodaje się w losowo wybranym
miejscu głowy genu, z wyjątkiem pierwszej pozycji.

Przykład

Chromosom składa się z trzech genów, każdy o długości głowy h

=

7.

Wybrano sekwencję “

Qc+

” w genie 3 (pozycje 3-5) i umieszczono

pomiędzy pozycje 1-2 w genie 2:
012345678901234012345678901234012345678901234
/cQQ*b+bccabdaaQb/Qdd-dcbdbadd-*d

Qc+

bccaabaad

/cQQ*b+bccabdaaQb

Qc+

/Q

dd-

dcbdbadd-*dQc+bccaabaad

<

usuń \dd-"

/cQQ*b+bccabdaaQb

Qc+

/Qdcbdbadd-*dQc+bccaabaad

Sekwencja “

dd-

” została usunięta, ponieważ nie mieści się w głowie genu.

Otrzymane w wyniku operacji “IS” nowe chromosomy (indywidua) są
syntaktycznie poprawne.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

16 / 52

GEP - transpozycja genetyczna typu RIS

Sekwencja “RIS” (Root Insertion Sequence) wybierana jest z głowy
genu, zaczyna się od funkcji i jest kopiowana do startowej pozycji
“root”. Głowa jest skanowana w poszukiwaniu funkcji, począwszy od
losowo wybranego punktu (gdy nie ma funkcji, operator nic nie robi).

Przykład

Chromosom składa się z trzech genów, każdy o długości głowy h

=

7.

Wybrano losowo pozycje 3-4 w genie 3: “

-Q

”. Operacja RIS kopiuje “

-Q

”

do korzenia genu i wypycha “

d+

”, ponieważ nie mieści się w głowie genu:

012345678901234012345678901234012345678901234
*a/cadQcabcdaca*aQb/ccccbbaaca/*c

-Q

d+

abccdabb

*a/cadQcabcdaca*aQb/ccccbbaaca

-Q

/*c

-Q

d+

abccdabb

<

usuń \d+"

*a/cadQcabcdaca*aQb/ccccbbaaca

-Q

/*c

-Q

abccdabb

W wyniku operacji “RIS”, ogon genu pozostaje nienaruszony i
wszystkie nowe chromosomy (indywidua) są syntaktycznie
poprawne.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

17 / 52

GEP - przeniesienie genu

(Gene transposition). Cały gen znika ze swojego oryginalnego
miejsca i przenosi się do początku chromosomu.

Przykład

Chromosom składa się z trzech genów, każdy o długości głowy h

=

7.

Wybrano losowo gen 2: “

-cbd+Qdbaabdacd

”:

012345678901234012345678901234012345678901234
/cQQ*bQbccadbdc

-cbd+Qdbaabdacd

+*dbbcbccaabcad

-cbd+Qdbaabdacd

/cQQ*bQbccadbdc+*dbbcbccaabcad

Operacja ta nie zmienia fenotypu w przypadku podwyrażeń
(Sub-ETs), które są argumentami funkcji matematycznych {+, *} lub
{A, O}. Wszystkie nowe chromosomy (indywidua) otrzymane w
wyniku tej operacji są syntaktycznie poprawne.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

18 / 52

GEP - rekombinacja genetyczna jednopunktowa

Materiał genetyczny rodziców jest wymieniany dokładnie w tym
samym punkcie.

Przykład

W chromosomach złożonych z 3 genów u rodziców, został wylosowany
punkt genu 2 na pozycji 3-4, jako punkt krzyżowania:

012345678901234012345678901234012345678901234

+++*-QQbbdddbbb*-d*cbbbcdaddbd+-baaaaacdccbba

Q+-Q///bbaacccb-cda+-dbcacadad+d/c**abdbcabdb

Wynik:

012345678901234012345678901234012345678901234

+++*-QQbbdddbbb*-d*

+-dbcacadad+d/c**abdbcabdb

Q+-Q///bbaacccb-cda

cbbbcdaddbd+-baaaaacdccbba

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

19 / 52

GEP - rekombinacja genetyczna dwupunktowa

Materiał genetyczny rodziców jest wymieniany w dwóch punktach.

Przykład

W chromosomach złożonych z 3 genów u rodziców, zostały wylosowane 2
punkty: 6-7 w genie 1 oraz 3-4 w genie 3.

012345678901234012345678901234012345678901234

+ca*-+cdacabbca/Qdd-c+cddacdac+/ccbd/bcbadabb

Qcb+b+acddaadad*/*b/adadaddcba/bc-a+Qacdbbbaa

Wynik:

012345678901234012345678901234012345678901234

+ca*-+c

cddaadad*/*b/adadaddcba/bc-

bd/bcbadabb

Qcb+b+a

dacabbca/Qdd-c+cddacdac+/cc

a+Qacdbbbaa

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

20 / 52

GEP - rekombinacja genetyczna zwykła

Wymieniane są całe geny rodziców.

Przykład

Chromosom składa się z 3 genów. Wymieniany jest gen 2:

012345678901234012345678901234012345678901234

+Qaa-dcabdaddac-a*b-/aabdbbdba+caQ*bQcdcbdcac

//Q//bacdacabba/b/d+/acddbbdac*-c*-/acdbacddd

Wynik:

012345678901234012345678901234012345678901234

+Qaa-dcabdaddac

-a*b-/aabdbbdba

+caQ*bQcdcbdcac

//Q//bacdacabba/b/d+/acddbbdac*-c*-/acdbacddd

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

21 / 52

Algorytm GEP

1

Utworzenie chromosomów populacji początkowej.

2

Wykonaj program i oblicz przydatność.

3

Jeżeli spełniony warunek stopu, to KONIEC, w przeciwnym razie
wykonaj krok 4.

4

Jeżeli uzyskano najlepsze pokolenie, to wykonaj krok 6, w przeciwnym
razie wykonaj krok 5.

5

Selekcja, replikacja, mutacja, inwersja, transpozycja typu IS, RIS,
transpozycja genów, rekombinacja jednopunktowa, rekombinacja
dwupunktowa, rekombinacja genetyczna.

6

Nowy chromosom następnego pokolenia, skok do kroku 2.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

22 / 52

GEP - przykład poszukiwania funkcji boole’owskiej -
pokolenie 1

Dane uczące modelują f

:

{

0, 1

}

3

→ {

0, 1

}

.

Chromosom=

<

gen1,gen2

>

, h

=

3, t

=

4. Operacja łącząca: OR.

Próbka

a

b

c

y

1

0

0

0

0

2

0

0

1

0

3

0

1

0

0

4

0

1

1

1

5

1

0

0

0

6

1

0

1

1

7

1

1

0

1

8

1

1

1

1

Pokolenie 1

01234560123456
NaObaacOAbbcca-[0]

=

4

AaNcbbaNcOaacc-[1]

=

2

OONcbbbNcbcbca-[2]

=

4

ANNcaacNcObaab-[3]

=

2

AbObcbcOAacaac-[4]

=

6

←−

AcNbcbbAONbbcc-[5]

=

4

NAcbcacNbOaaba-[6]

=

2

NbNbbaaAacbacb-[7]

=

3

NAAaccaONacbbb-[8]

=

4

AAaccacNcaabab-[9]

=

4

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

23 / 52

GEP - przykład poszukiwania funkcji boole’owskiej -
pokolenie 2

Próbka

a

b

c

y

1

0

0

0

0

2

0

0

1

0

3

0

1

0

0

4

0

1

1

1

5

1

0

0

0

6

1

0

1

1

7

1

1

0

1

8

1

1

1

1

Pokolenie 2

01234560123456
AbObcbcOAacaac- [0]

=

6

NaObabcOAbbcca- [1]

=

4

NAAacccONOcbbb- [2]

=

3

aaNcbcaNcOaacc- [3]

=

4

AcNbcbbOONbbcc- [4]

=

4

AcNbcbbAONbbcc- [5]

=

4

AbObcbcOAAcaac- [6]

=

7

←−

NAAaccaONacbbb- [7]

=

4

AaNcbbaNcNaacc- [8]

=

3

cNNcaabNcObaab- [9]

=

4

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

24 / 52

GEP - przykład poszukiwania funkcji boole’owskiej -
pokolenie 3

Próbka

a

b

c

y

1

0

0

0

0

2

0

0

1

0

3

0

1

0

0

4

0

1

1

1

5

1

0

0

0

6

1

0

1

1

7

1

1

0

1

8

1

1

1

1

Pokolenie 3

01234560123456
AbObcbcOAAcaac- [0]

=

7

AbcbcbcOAAcaab- [1]

=

8

←−

AaNbbbaNcNaacc- [2]

=

3

ANNbabbOONbbcc- [3]

=

3

AcNbcbbAONbbcc- [4]

=

4

AbAccbcOAAcaac- [5]

=

7

NaObaccOAbbcca- [6]

=

4

AbObcbcOAacaac- [7]

=

6

AbabbbcOAacaab- [8]

=

6

AbObcbbOAacaac- [9]

=

6

Wynik: f

(

a, b, c

) = (

a

∧

b

) ∨ (

a

∧

c

) ∨ (

b

∧

c

)

. Dokładność 100%.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

25 / 52

GEP - funkcja dopasowania - liczba trafień

i - numer rozwiązania zadania, czyli programu, j - numer przypadku,
P

i ,j

- wartość funkcji

wyznaczona przez program

,

T

j

- wartość docelowa

odczytana z danych

,

p - dokładność zadana przez projektanta,
f

i ,j

- funkcja dopasowania zadana przez projektanta.

Błąd bezwzględny

E

i ,j

=

|

P

i ,j

−

T

j

|

Błąd względny

E

i ,j

=

|(

P

i ,j

−

T

j

)

/T

j

| ·

100

Reguła dopasowania:

If E

i ,j

p, then f

i ,j

=

1, else f

i ,j

=

0

Funkcja dopasowania (fitness function) typu “liczba trafień”:

f

i

=

∑

j

f

i ,j

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

26 / 52

GEP - funkcja dopasowania - błąd średniokwadratowy

n - liczba przypadków.
Błąd średniokwadratowy bezwzględny

E

i

=

1

n

n

∑

j

=

1

|

P

i ,j

−

T

j

|

2

Błąd średniokwadratowy względny

E

i

=

1

n

n

∑

j

=

1

|(

P

i ,j

−

T

j

)

/T

j

|

2

Funkcja dopasowania dla i -tego programu:

f

i

=

1000

1

+

E

i

1000

// Przypadek idealny: f

i

=

1000.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

27 / 52

GEP - funkcja dopasowania - Rˆ2

Współczynnik korelacji liniowej Pearsona (“miara liniowości”) r

∈ [−

1, 1

]

.

// r

(

P, T

) ∈ [−

1, 1

]

, (r

= ±

1 - idealna zależność liniowa, r

=

0 -

zupełny brak korelacji liniowej).

P

i ,j

- wartość funkcji wyznaczona przez program,

T

j

- wartość docelowa odczytana z danych.

Współczynnik:

R

i

=

n

∑

n
j

=

1

(

T

i

P

i ,j

) −

∑

n
j

=

1

T

j

∑

n
j

=

1

P

i ,j

h

n

∑

n
j

=

1



T

2

j



−

∑

n
j

=

1

T

j

2

i

1

/2

·

h

n

∑

n
j

=

1



P

2

i ,j



−

∑

n
j

=

1

P

i ,j

2

i

1

/2

Funkcja dopasowania dla i -tego programu:

f

i

=

1000R

2

i

1000

// Przypadek idealny: f

i

=

1000.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

28 / 52

GEP - funkcja dopasowania dla klasyfikacji i syntezy
logicznej - macierz rozbieżności

Macierz rozbieżności (CM) w przypadku C klas:

Wynik

testu

x

1

x

2

· · ·

x

C

Stan

x

1

m

1,1

m

1,2

· · ·

m

1,C

faktyczny

x

2

m

2,1

m

2,2

· · ·

m

2,C

..

.

..

.

..

.

. ..

..

.

x

C

m

C ,1

m

C ,2

· · ·

m

C ,C

Macierz rozbieżności w przypadku C

=

2:

Wynik

testu

tak

nie

Stan

tak

TP

FN

faktyczny

nie

FP

TN

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

29 / 52

GEP - funkcja dopasowania dla klasyfikacji i syntezy
logicznej - reguła

Funkcja dopasowania dla i -tego programu = liczba trafień = liczba
prawidłowo sklasyfikowanych danych:

f

i

=

h n

Przypadek idealny (np. w problemie poszukiwania funkcji
boole’owskiej): f

i

=

n.

Dla C

=

2, możemy stosować regułę:

If

(

TP

i

=

0 lub TN

i

=

0

)

, then f

i

=

0, else f

i

=

h

=

TP

i

+

TN

i

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

30 / 52

GEP - funkcja dopasowania dla klasyfikacji i syntezy
logicznej - czułość i specyficzność

Wynik

testu

tak

nie

Stan

tak

TP

FN

faktyczny

nie

FP

TN

Wynik

idealny

TP

0

0

TN

Czułość (sensitivity):

SE

i

=

TP

i

TP

i

+

FN

i

,

TP

i

+

FN

i

>

0

Specyficzność (specificity):

SP

i

=

TN

i

TN

i

+

FP

i

,

TN

i

+

FP

i

>

0

Funkcja dopasowania dla i -tego programu:

f

i

=

1000

·

SE

i

·

SP

i

1000

Przypadek idealny: f

i

=

1000.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

31 / 52

GEP - funkcja dopasowania dla klasyfikacji i syntezy
logicznej - udział testów

Wynik

testu

tak

nie

Stan

tak

TP

FN

faktyczny

nie

FP

TN

Wynik

idealny

TP

0

0

TN

Udział testów dodatnich (positive predictive value):

PPV

i

=

TP

i

TP

i

+

FP

i

,

TP

i

+

FP

i

>

0

Udział testów ujemnych (negative predictive value):

NPV

i

=

TN

i

TN

i

+

FN

i

,

TN

i

+

FN

i

>

0

Funkcja dopasowania dla i -tego programu:

f

i

=

1000

·

PPV

i

·

NPV

i

1000

Przypadek idealny: f

i

=

1000.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

32 / 52

GEP - przykład aproksymacji funkcji - jak odkryć trzecie
prawo Keplera ?

III prawo Keplera: T

2

=

const

∗

a

3

, T - okres obiegu planety, a -

maksymalna odległość planety od środka masy układu Słońce-planeta,
const

= (

2π

)

2

/

(

G

(

M

+

m

))

, G - stała grawitacji, M - masa Słońca, m

- masa planety.

Planeta

a

T

=

a

3

/2

1

Wenus

0.72

0.61

2

Ziemia

1.00

1.00

3

Mars

1.52

1.84

4

Jowisz

5.20

11.90

5

Saturn

9.53

29.40

6

Uran

19.10

83.50

Wynik: dwa chromosomy o długości 15, (h

=

7), połączone operacją “+”:

+*-Qaa+

aaaaaaaa

+

a+a+-**

aaaaaaaa

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

33 / 52

GEP - przykład - diagnostyka raka piersi

Baza danych: ftp.ira.uka.de/pub/neuron.

Atrybuty: x

= [

d

0

, d

1

, d

2

, d

3

, d

4

, d

5

, d

6

, d

7

, d

8

]

, d

k

∈ [

0, 1

]

,

Wartości funkcji: y

∈ {

0, 1

}

.

Zbiór uczący:

{(

x, y

)

1

,

. . . ,

(

x, y

)

350

} ∈ [

0, 1

]

9

× {

0, 1

}

Zbiór testowy:

{(

x, y

)

1

,

. . . ,

(

x, y

)

174

} ∈ [

0, 1

]

9

× {

0, 1

}

Zadajemy parametry GEP: funkcję dopasowania (dokładność
klasyfikacji),

{+

,

−

,

∗}

- dopuszczalne działania, h

=

8, ...

Otrzymana macierz rozbieżności przy uczeniu:



121

0

8

221



⇒

Błąd klasyfikacji:

8

+

0

8

+

0

+

121

+

221

→

2.29%

Otrzymana macierz rozbieżności przy testowaniu:



62

3

1

108



⇒

Błąd klasyfikacji:

1

+

3

1

+

3

+

62

+

108

→

2.30%

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

34 / 52

GEP - przykład - diagnostyka raka piersi - c.d.

Otrzymany program w języku K:

*.d0.*.d8.+.d1.d4.d2

.d1.d2.d2.d5.d8.d2.d1.d8.d0

+

*.-.d8.*.*.d6.d1.d1

.d5.d7.d8.d3.d5.d0.d7.d2.d7

+

*.-.d3.d5.*.d6.*.d5

.d4.d7.d8.d0.d2.d5.d5.d3.d2

Otrzymany klasyfikator:

If f

(

d

0

, d

1

, d

2

, d

3

, d

4

, d

5

, d

6

, d

7

, d

8

)

θ, then y

=

1, else y

=

0

gdzie
- zadany próg: θ

=

0.1

- funkcja klasyfikatora wygenerowana przez program:

f

(

d

0

, d

1

,

. . . , d

8

) =

d

0

d

8

(

d

1

+

d

4

) +

d

1

d

8

(

d

6

−

d

5

) +

d

3

(

d

5

−

d

4

d

5

d

6

)

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

35 / 52

GEP - przykład - diagnostyka raka piersi - c.d.

Przykład działania reguły dla danych wziętych z bazy danych raka piersi:

(

d

0

, d

1

, d

2

,

. . . , d

8

) = (

0.2, 0.1, 0.1, 0.1, 0.2, 0.1, 0.2, 0.1, 0.1

)

f

(

0.2, 0.1, 0.1, 0.1, 0.2, 0.1, 0.2, 0.1, 0.1

) =

0.0166

0.0166

<

θ

=

0.1

⇒

y

=

0

(

d

0

, d

1

, d

2

,

. . . , d

8

) = (

0.5, 0.4, 0.6, 0.8, 0.4, 0.1, 0.8, 1.0, 0.1

)

f

(

0.5, 0.4, 0.6, 0.8, 0.4, 0.1, 0.8, 1.0, 0.1

) =

0.1224

0.1224 θ

=

0.1

⇒

y

=

1

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

36 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy

Wojewódzki Szpital Specjalistyczny w Rzeszowie, Kliniczny OGiP,
B. Obrzut, dr n. med.

Dane oryginalne:

93 rekordy

:

zrozumienie danych !



standaryzacja, ...,



kodowanie

Predyktory: BMI, choroby, operacje, OM, HP, G, FIGO

Wyjście: powikłania pooperacyjne:
{naciek rany, zaleganie moczu, zator tętnicy płucnej, gorączka,
limfotok, perforacja wrzodu dwunastnicy, arytmia serca, ...}

Założenie: Powiklania

∈ {

0, 1

}

.

Problem: Wytłumaczyć powikłania lub wykryć reguły.

“Ważenie” danych (D. Chassagne i in. (1993), Radiotherapy
and Oncology, 26, 195-202):

112 rekordów danych

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

37 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Predyktory:

BMI

, Choroby, Operacje, G, FIGO, HP typ, OM

Klasyfikacja wg WHO:

1

BMI

<

16 - wygłodzenie (underweight: severe thinness)

2

BMI

∈ [

16, 17

)

- wychudzenie (underweight: moderate thinness)

3

BMI

∈ [

17, 18.5

)

- niedowaga (underweight: mild thinness)

4

BMI

∈ [

18.5, 25

)

- wartość prawidłowa (normal range)

5

BMI

∈ [

25, 30

)

- nadwaga (overweight: severe thinness)

6

BMI

∈ [

30, 35

)

- otyłość I stopnia (obese class I)

7

BMI

∈ [

35, 40

)

- otyłość II stopnia (obese class II)

8

BMI 40 - otyłość III stopnia (obese class III)

BMI (WHO): niedowaga

(

a

1

)

, normalna

(

a

2

)

, nadwaga

(

a

3

)

, otylosc1

(

a

4

)

, otylosc2

(

a

5

)

, otylosc3

(

a

6

)

.

a

1

+

. . .

+

a

6

=

1,

a

1

,

. . . , a

6

∈ {

0, 1

}

.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

38 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Predyktory: BMI,

Choroby

,

Operacje

, G, FIGO, HP typ, OM

Choroby (przebyte i towarzyszące):
brak

(

b

7

)

, HA=nadciśnienie

(

b

8

)

, MIC=choroba niedokrwienna serca

(

b

9

)

,

HA MIC

(

b

10

)

, ASD=wada serca

(

b

11

)

, ARYTMIA

(

b

12

)

,

DM=cukrzyca

(

b

13

)

, HA DM

(

b

14

)

, HA LED=nadciśnienie+toczeń

(

b

15

)

,

ASTMA

(

b

16

)

.

b

7

+

b

8

+

. . .

+

b

16

=

1,

b

7

, b

8

,

. . . , b

16

∈ {

0, 1

}

.

Operacje (przebyte): nie

(

c

17

)

, tak

(

c

18

)

.

c

17

+

c

18

=

1,

c

17

, c

18

∈ {

0, 1

}

.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

39 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Predyktory: BMI, Choroby, Operacje,

G

, FIGO, HP typ, OM

G - dojrzałość histologiczna (grading):

G1 (dobrze zróżnicowany): tak

(

d

19

)

.

G2 (średnio zróżnicowany): tak

(

d

20

)

.

G3 (nisko zróżnicowany): tak

(

d

21

)

.

d

19

+

d

20

+

d

21

=

1,

d

19

, d

20

, d

21

∈ {

0, 1

}

.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

40 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Predyktory: BMI, Choroby, Operacje, G,

FIGO

, HP typ, OM

FIGO - stopień zaawansowania raka (Int. Federation of Gynecology and
Obstetrics, FIGO, 1995):

IB1 (średnica nacieku 4 cm): tak

(

f

22

)

IIB (naciek przymacicz niedochodzący do kości): tak

(

f

23

)

IA2 (głębokość nacieku

∈ (

3, 5

]

mm, średnica powierzchni nacieku 7

mm): tak

(

f

24

)

IB2 (średnica nacieku

>

4 cm):

(

f

25

)

IIA (naciek 2

/3 części górnych pochwy, bez zajęcia przymacicz):

(

f

26

)

f

22

+

f

23

+

. . .

+

f

26

=

1,

f

22

, f

23

,

. . . , f

26

∈ {

0, 1

}

.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

41 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Predyktory: BMI, Choroby, Operacje, G, FIGO,

HP typ

,

OM

HP typ

∈ {

akeratodes, adeno, keratodes

}

;

akeratodes:

(

h

27

)

, adeno:

(

h

28

)

, keratodes:

(

h

29

)

h

27

+

h

28

+

h

29

=

1,

h

27

, h

28

, h

29

∈ {

0, 1

}

.

OM: tak

(

k

30

)

. nie

(

k

31

)

If OM 4, then k

30

=

1, else k

31

=

1,

k

30

+

k

31

=

1, k

30

, k

31

∈ {

0, 1

}

.

Łącznie:

31 atrybutów zmiennych wejściowych (przy takim kodowaniu !)

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

42 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Spostrzeżenia:

1

Wartości predyktorów

∈ {

0, 1

}

. Są one jednak szacowane, nie zawsze

zmierzone dokładnie.

2

Jaka będzie predykcja, gdy

1

Średnica nacieku wynosi 1 cm, gdzie FIGO = IB1 (średnica nacieku 4
cm, f

21

),

2

BMI

=

24.9

∈ [

18.5, 25

)

- wartość prawidłowa

(

a

2

)

,

3

DM=cukrzyca

(

b

13

)

będzie bardziej lub mniej zaawansowana, ...

3

Założenie, że klasyfikator powinien być “miękki” wydaje się naturalne.

Cel: Dążymy do uzyskania reguł dla systemu P1-TS.
Podstawa: “Analytical Methods, ...” -

mocne zredukowanie problemu

przekleństwa wymiarowości systemów logiki rozmytej

- uzyskanie reguł dla

31 zmiennych dla P1-TS już nie powinno stanowić problemu.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

43 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Wynik GEP (po żmudnych przekształceniach)

If

12

∑

k

=

1

y

k

0.5, then y

=

1, else y

=

0

y

1

=

a

5

b

14

+

a

2

b

7

(

1

−

f

23

)

k

31

+

a

3

(

1

−

k

30

) (

1

−

f

23

)

c

17

d

20

y

2

= (

1

−

a

1

) (

1

−

a

5

) (

1

−

a

6

)

k

30

h

28

d

20

y

3

= (

1

−

a

1

) (

1

−

a

5

) (

1

−

a

6

)

k

30

(

1

−

h

28

) (

1

−

c

17

)

f

26

y

4

= (

a

3

+

a

4

)

k

30

(

1

−

h

28

) (

1

−

c

17

) (

1

−

f

26

)

d

19

y

5

= (

1

−

a

1

) (

1

−

a

5

) (

1

−

a

6

)

k

30

(

1

−

h

28

)

c

17

b

10

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

44 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Wyniki GEP - c.d.

y

6

=

a

2

k

30

(

1

−

h

28

)

c

17

(

1

−

b

7

) (

1

−

b

10

)

d

19

y

7

=

a

2

k

30

c

17

d

20

b

7

h

27

(

1

−

f

23

)

y

7

=

a

2

k

30

c

17

d

20

b

7

h

27

(

1

−

f

23

)

y

9

= (

a

3

+

a

4

)

k

30

(

1

−

h

28

)

c

17

(

1

−

b

10

)

f

23

y

10

= (

a

3

+

a

4

)

k

30

h

29

c

17

(

1

−

b

10

) (

1

−

f

23

) (

1

−

f

26

)

y

11

= (

a

3

+

a

4

)

k

30

c

17

(

1

−

b

9

) (

1

−

b

10

)

h

27

f

22

y

12

= (

a

3

+

a

4

)

k

30

c

17

(

1

−

b

9

) (

1

−

b

10

)

h

27

f

22

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

45 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Reguły P1-TS (“Analytical Methods, ...”):

y

1

=

a

5

b

14

| {z }

+

a

2

b

7

(

1

−

f

23

)

k

31

+

a

3

(

1

−

k

30

) (

1

−

f

23

)

c

17

d

20

MR1: If a

5

∧

b

14

, then y

=

1,

m

If

{otyłość II stopnia}

∧

{nadciśnienie

∧

cukrzyca}, then y

=

1

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

46 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Reguły P1-TS (“Analytical Methods, ...”):

y

1

=

a

5

b

14

+

a

2

b

7

(

1

−

f

23

)

k

31

|

{z

}

+

a

3

(

1

−

k

30

) (

1

−

f

23

)

c

17

d

20

MR2:
If

{BMI w normie}

∧

{Chorób nie było}

∧

{FIGO nie jest typu IIB}

∧

{OM 3},

y

=

1

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

47 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Trafność metareguł z konkluzją y

=

1:

PQ

y

=

1

, PQ

y

=

1

.

PQ

y

=

1

= liczba rekordów danych, które potwierdzają metaregułę:

poprzednik jest zgodny z rekordem danych
i następnik jest zgodny z rekordem danych.

PQ

y

=

1

= liczba rekordów danych, które nie potwierdzają

metareguły:
poprzednik jest zgodny z rekordem danych
lecz następnik nie jest zgodny z rekordem danych.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

48 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Metareguły z konkluzją y

=

1:

PQ

y

=

1

, PQ

y

=

1

 i ich trafność.

MR1:

a

5

b

14

,

<

1,0

>

#59

MR2:

a

2

b

7

(

1

−

f

23

)

k

31

,

<

3,0

>

#84,103,104

MR3:

a

3

(

1

−

k

30

) (

1

−

f

23

)

c

17

d

20

,

<

2,0

>

#16,91

MR4:

(

1

−

a

1

) (

1

−

a

5

) (

1

−

a

6

)

k

30

h

28

d

20

= (

a

2

+

a

3

+

a

4

)

k

30

h

28

d

20

,

<

1,0

>

#2

MR5:

(

a

2

+

a

3

+

a

4

)

k

30

(

1

−

h

28

) (

1

−

c

17

)

f

26

,

<

1,0

>

#49

MR6:

(

a

3

+

a

4

)

k

30

(

1

−

h

28

) (

1

−

c

17

) (

1

−

f

26

)

d

19

,

<

1,0

>

#9

MR7:

(

a

2

+

a

3

+

a

4

)

k

30

(

1

−

h

28

)

c

17

b

10

,

<

1,0

>

#35

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

49 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Metareguły z konkluzją y

=

1:

PQ

y

=

1

, PQ

y

=

1

 i ich trafność.

MR8:

a

2

k

30

(

1

−

h

28

)

c

17

(

1

−

b

7

) (

1

−

b

10

)

d

19

,

<

2,0

>

#43, 98

MR9:

a

2

k

30

c

17

d

20

b

7

h

27

(

1

−

f

23

)

,

<

15,2

>

#10, 15, 46, 47, 50, 68, 69, 70, 73, 74, 77, 85, 88, 110, 112

MR10:

(

a

3

+

a

4

)

k

30

(

1

−

h

28

)

c

17

(

1

−

b

7

) (

1

−

b

10

)

f

26

,

<

1,0

>

#58

MR11:

(

a

3

+

a

4

)

k

30

(

1

−

h

28

)

c

17

(

1

−

b

10

)

f

23

,

<

7,0

>

#19, 20, 21, 22, 105, 106, 107

MR12:

(

a

3

+

a

4

)

k

30

h

29

c

17

(

1

−

b

10

) (

1

−

f

23

) (

1

−

f

26

)

,

<

6,0

>

#6, 7, 8, 24, 31, 37

MR13:

(

a

3

+

a

4

)

k

30

c

17

(

1

−

b

9

) (

1

−

b

10

)

h

27

f

22

,

<

5,0

>

#27, 28, 29, 52, 53

MR14:

a

3

b

7

c

17

(

f

24

+

f

25

)

h

27

k

30

,

<

13,2

>

#3, 4, 34, 45, 60, 61, 62, 63, 64, 65, 72, 75, 80

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

50 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

∑ PQ

y

=

1

, PQ

y

=

1



=

h

59, 4

i

, 59

−

4

=

55 przypadków trafnie

wytłumaczonych przez reguły. Błąd dla y

=

1:

(

4

/59

) ∗

100

=

6.8%

Uwaga: Nowe (inne) metareguły dla y

=

0, (...)

CM:

Test y

=

1

Test y

=

0

Stan

y

=

1

TP

=

55

FN

=

4

faktyczny

y

=

0

FP

=

4

TN

=

49

Czułość: SE

=

55

/

(

55

+

4

) =

93.2% .

Specyficzność: SP

=

49

/

(

49

+

4

) =

92.4% .

Błąd:

(

4

+

4

)

/

(

55

+

4

+

49

+

4

) =

7.14%

Funkcja dopasowania dla i -tego wyniku f

i

=

1000

·

SE

i

·

SP

i

1000 .

Uwaga: Przy walidacji skrośnej (v

=

10), błąd jest rzędu 35%.

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

51 / 52

Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Wnioski:

DT, SVM, kNN, PNN - dają ten sam błąd uczenia równy 7.14%.

Tw. (“Analytical Methods, ...”). P1-TS: f

:

[

0, 1

]

n

→ [

0, 1

]

,

f

(

a

1

, a

2

,

. . . , k

31

) =

12

∑

k

=

1

y

k

,

f

:

[

0, 1

]

31

→ [

0, 1

]

Zaleta:

Dla x

0

=

a

0

1

, a

0

2

,

. . . , k

0

31

wyznaczamy f x

0

∈ [

0, 1

]

.

Propozycja decyzji ostatecznej: f x

0

θ

⇒

y

=

1

.

Wady:

Algorytm GEP jest bardzo czasochłonny.
Problem: Jak otrzymać reguły najchętniej akceptowalne przez lekarza ?

Jacek Kluska (Politechnika Rzeszowska)

Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej

2011

52 / 52