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 1 / 52
2011rozmytej
Problem klasyfikacji danych
Dane: zbiór rekordów danych (przykładów, obserwacji, ...):
{(x1, y1) , . . . , (xQ, yQ)} �" X � {c1, . . . , cm} , X �" Rn.
Problem: Znalez
ć model (klasyfikator) przydzielający ci dla xi " Rn.
// Regresja:
// {(x1, y1) , . . . , (xQ, yQ)} �" Rn � R.
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice 2 / 52
2011rozmytej
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 3 / 52
2011rozmytej
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 (a + b) (c - d) - fenotyp
// fenotyp - zespół dostrzegalnych cech powstałych w wyniku
// oddziaływania warunków środowiska na genotyp organizmu.
"
// . = Q
".
"
+ -
a c
b d
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice 4 / 52
2011rozmytej
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 5 / 52
2011rozmytej
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
a a
b b
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice 6 / 52
2011rozmytej
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 = glowa, ogon �" {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 7 / 52
2011rozmytej
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+babbabbbababbaaa


głowa ogon
"
+
b
a -
a "
a
b
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice 8 / 52
2011rozmytej
GEP - przykład chromosomu dla wyrażeń arytmetycznych
012345678901201234567890120123456789012
*Qb+*/bbbabab-a+QbQbbababa/ba-/*bbaaaaa
Sub-ET1 Sub-ET2 Sub-ET3
" - /
a
Q + a
b b
+ Q
b
" Q
/
a
b b b b
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 9 / 52
2011rozmytej
GEP - przykład chromosomu dla wyrażeń booleowskich
Przykład
012345678901234501234567890123450123456789012345
OcIbAcaabcbccaaaIANAIbbaaaabaaabAcbcIcaaaacaccaa
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 52
2011 10 /
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 52
2011 11 /
GEP - mutacja genetyczna - efekt kurczenia się fenotypu
*b+a-a*ab+//+b+babbabbbababbaaa
*b+aQa*ab+//+b+babbabbbababbaaa
"
+
b "
a -
+
b
=�!
a "
a
Q
a
b a
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 12 /
GEP - mutacja genetyczna - efekt rozrastania się fenotypu
*b+a-a*a*bb+//+b+babbabbbababbaaa
*b+a-a*a*Qb+//+b+babbabbbababbaaa
"
+
b
"
a -
+
b
a "
=�!
a -
a
Q
a "
a
b b
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 13 /
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
-/Qbaadcdbadbdc-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 52
2011 14 /
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 52
2011 15 /
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-*dQc+bccaabaad
/cQQ*b+bccabdaaQbQc+/Qdd-dcbdbadd-*dQc+bccaabaad < usuń \dd-"
/cQQ*b+bccabdaaQbQc+/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 52
2011 16 /
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-Qd+abccdabb
*a/cadQcabcdaca*aQb/ccccbbaaca-Q/*c-Qd+abccdabb < usuń \d+"
*a/cadQcabcdaca*aQb/ccccbbaaca-Q/*c-Qabccdabb
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 52
2011 17 /
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 52
2011 18 /
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-cdacbbbcdaddbd+-baaaaacdccbba
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 19 /
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*-+ccddaadad*/*b/adadaddcba/bc-bd/bcbadabb
Qcb+b+adacabbca/Qdd-c+cddacdac+/cca+Qacdbbbaa
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 20 /
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 52
2011 21 /
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 52
2011 22 /
GEP - przykład poszukiwania funkcji boole owskiej -
pokolenie 1
Dane uczące modelują f : {0, 1}3 {0, 1}.
Chromosom=, h = 3, t = 4. Operacja łącząca: OR.
Pokolenie 1
01234560123456
Próbka a b c y
NaObaacOAbbcca-[0] = 4
1 0 0 0 0
AaNcbbaNcOaacc-[1] = 2
2 0 0 1 0
OONcbbbNcbcbca-[2] = 4
3 0 1 0 0
ANNcaacNcObaab-[3] = 2
4 0 1 1 1
AbObcbcOAacaac-[4] = 6 �!-
5 1 0 0 0
AcNbcbbAONbbcc-[5] = 4
6 1 0 1 1
NAcbcacNbOaaba-[6] = 2
7 1 1 0 1
NbNbbaaAacbacb-[7] = 3
8 1 1 1 1
NAAaccaONacbbb-[8] = 4
AAaccacNcaabab-[9] = 4
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 23 /
GEP - przykład poszukiwania funkcji boole owskiej -
pokolenie 2
Pokolenie 2
01234560123456
Próbka a b c y
AbObcbcOAacaac- [0] = 6
1 0 0 0 0
NaObabcOAbbcca- [1] = 4
2 0 0 1 0
NAAacccONOcbbb- [2] = 3
3 0 1 0 0
aaNcbcaNcOaacc- [3] = 4
4 0 1 1 1
AcNbcbbOONbbcc- [4] = 4
5 1 0 0 0
AcNbcbbAONbbcc- [5] = 4
6 1 0 1 1
AbObcbcOAAcaac- [6] = 7 �!-
7 1 1 0 1
NAAaccaONacbbb- [7] = 4
8 1 1 1 1
AaNcbbaNcNaacc- [8] = 3
cNNcaabNcObaab- [9] = 4
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 24 /
GEP - przykład poszukiwania funkcji boole owskiej -
pokolenie 3
Pokolenie 3
01234560123456
Próbka a b c y
AbObcbcOAAcaac- [0] = 7
1 0 0 0 0
AbcbcbcOAAcaab- [1] = 8 �!-
2 0 0 1 0
AaNbbbaNcNaacc- [2] = 3
3 0 1 0 0
ANNbabbOONbbcc- [3] = 3
4 0 1 1 1
AcNbcbbAONbbcc- [4] = 4
5 1 0 0 0
AbAccbcOAAcaac- [5] = 7
6 1 0 1 1
NaObaccOAbbcca- [6] = 4
7 1 1 0 1
AbObcbcOAacaac- [7] = 6
8 1 1 1 1
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 52
2011 25 /
GEP - funkcja dopasowania - liczba trafień
i - numer rozwiązania zadania, czyli programu, j - numer przypadku,
Pi,j - wartość funkcji wyznaczona przez program,
Tj - wartość docelowa odczytana z danych,
p - dokładność zadana przez projektanta,
fi,j - funkcja dopasowania zadana przez projektanta.
Błąd bezwzględny
Ei,j = |Pi,j - Tj |
Błąd względny
Ei,j = |(Pi,j - Tj) /Tj| � 100
Reguła dopasowania:
If Ei,j p, then fi,j = 1, else fi,j = 0
Funkcja dopasowania (fitness function) typu  liczba trafień :
fi = fi,j
"
j
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 26 /
GEP - funkcja dopasowania - błąd średniokwadratowy
n - liczba przypadków.
Błąd średniokwadratowy bezwzględny
n
1
Ei = |Pi,j - Tj|2
"
n
j=1
Błąd średniokwadratowy względny
n
1
Ei = |(Pi,j - Tj) /Tj |2
"
n
j=1
Funkcja dopasowania dla i-tego programu:
1000
fi = 1000
1 + Ei
// Przypadek idealny: fi = 1000.
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 27 /
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).
Pi,j - wartość funkcji wyznaczona przez program,
Tj - wartość docelowa odczytana z danych.
Współczynnik:

n (TiPi,j ) - "n "n
Tj Pi,j
"n
j=1 j=1 j=1
Ri =

1/2 1/2
2 2
n Tj2 - "n "n
Tj � n Pi2 - "n
Pi,j
"n
j=1 j=1 j=1 j=1
,j
Funkcja dopasowania dla i-tego programu:
fi = 1000Ri2 1000
// Przypadek idealny: fi = 1000.
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 28 /
GEP - funkcja dopasowania dla klasyfikacji i syntezy
logicznej - macierz rozbieżności
Macierz rozbieżności (CM) w przypadku C klas:
Wynik testu
x1 x2 � � � xC
Stan x1 m1,1 m1,2 � � � m1,C
faktyczny x2 m2,1 m2,2 � � � m2,C
. . . .
.
. . . . .
.
. . . .
xC mC ,1 mC,2 � � � mC ,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 52
2011 29 /
GEP - funkcja dopasowania dla klasyfikacji i syntezy
logicznej - reguła
Funkcja dopasowania dla i-tego programu = liczba trafień = liczba
prawidłowo sklasyfikowanych danych:
fi = h n
Przypadek idealny (np. w problemie poszukiwania funkcji
boole owskiej): fi = n.
Dla C = 2, możemy stosować regułę:
If (TPi = 0 lub TNi = 0 ) , then fi = 0, else fi = h = TPi + TNi
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 30 /
GEP - funkcja dopasowania dla klasyfikacji i syntezy
logicznej - czułość i specyficzność
Wynik testu Wynik idealny
tak nie
Stan tak TP FN TP 0
faktyczny nie FP TN 0 TN
Czułość (sensitivity):
TPi
SEi = , TPi + FNi > 0
TPi + FNi
Specyficzność (specificity):
TNi
SPi = , TNi + FPi > 0
TNi + FPi
Funkcja dopasowania dla i-tego programu:
fi = 1000 � SEi � SPi 1000
Przypadek idealny: fi = 1000.
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 31 /
GEP - funkcja dopasowania dla klasyfikacji i syntezy
logicznej - udział testów
Wynik testu Wynik idealny
tak nie
Stan tak TP FN TP 0
faktyczny nie FP TN 0 TN
Udział testów dodatnich (positive predictive value):
TPi
PPVi = , TPi + FPi > 0
TPi + FPi
Udział testów ujemnych (negative predictive value):
TNi
NPVi = , TNi + FNi > 0
TNi + FNi
Funkcja dopasowania dla i-tego programu:
fi = 1000 � PPVi � NPVi 1000
Przypadek idealny: fi = 1000.
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 32 /
GEP - przykład aproksymacji funkcji - jak odkryć trzecie
prawo Keplera ?
2
III prawo Keplera: T = const " a3, 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 = a3/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 52
2011 33 /
GEP - przykład - diagnostyka raka piersi
Baza danych:ftp.ira.uka.de/pub/neuron.
Atrybuty: x = [d0, d1, d2, d3, d4, d5, d6, d7, d8], dk " [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:

8 + 0
121 0
�! Błąd klasyfikacji: 2.29%
8 221
8 + 0 + 121 + 221
Otrzymana macierz rozbieżności przy testowaniu:

1 + 3
62 3
�! Błąd klasyfikacji: 2.30%
1 108
1 + 3 + 62 + 108
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 34 /
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 (d0, d1, d2, d3, d4, d5, d6, d7, d8) �, then y = 1, else y = 0
gdzie
- zadany próg: � = 0.1
- funkcja klasyfikatora wygenerowana przez program:
f (d0, d1, . . . , d8) = d0d8 (d1 + d4) + d1d8 (d6 - d5) + d3 (d5 - d4d5d6)
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 35 /
GEP - przykład - diagnostyka raka piersi - c.d.
Przykład działania reguły dla danych wziętych z bazy danych raka piersi:
(d0, d1, d2, . . . , d8) = (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
(d0, d1, d2, . . . , d8) = (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 52
2011 36 /
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 52
2011 37 /
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 (a1), normalna (a2), nadwaga (a3), otylosc1
(a4), otylosc2 (a5), otylosc3 (a6).
a1 + . . . + a6 = 1, a1, . . . , a6 " {0, 1} .
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 38 /
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 (b7), HA=nadciśnienie (b8), MIC=choroba niedokrwienna serca (b9),
HA MIC (b10), ASD=wada serca (b11), ARYTMIA (b12),
DM=cukrzyca (b13), HA DM (b14), HA LED=nadciśnienie+toczeń (b15),
ASTMA (b16).
b7 + b8 + . . . + b16 = 1, b7, b8, . . . , b16 " {0, 1} .
Operacje (przebyte): nie (c17), tak (c18).
c17 + c18 = 1, c17, c18 " {0, 1} .
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 39 /
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 (d19).
G2 (średnio zróżnicowany): tak (d20).
G3 (nisko zróżnicowany): tak (d21).
d19 + d20 + d21 = 1, d19, d20, d21 " {0, 1} .
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 40 /
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 (f22)
IIB (naciek przymacicz niedochodzący do kości): tak (f23)
IA2 (głębokość nacieku " (3, 5] mm, średnica powierzchni nacieku 7
mm): tak (f24)
IB2 (średnica nacieku > 4 cm): (f25)
IIA (naciek 2/3 części górnych pochwy, bez zajęcia przymacicz): (f26)
f22 + f23 + . . . + f26 = 1, f22, f23, . . . , f26 " {0, 1} .
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 41 /
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: (h27), adeno: (h28), keratodes: (h29)
h27 + h28 + h29 = 1, h27, h28, h29 " {0, 1} .
OM: tak (k30). nie (k31)
If OM 4, then k30 = 1, else k31 = 1, k30 + k31 = 1, k30, k31 " {0, 1} .
A
ą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 52
2011 42 /
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, f21),
2 BMI = 24.9 " [18.5, 25) - wartość prawidłowa (a2),
3 DM=cukrzyca (b13) 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 52
2011 43 /
Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.
Wynik GEP (po żmudnych przekształceniach)
12
If yk 0.5, then y = 1, else y = 0
"
k=1
y1 = a5b14 + a2b7 (1 - f23) k31 + a3 (1 - k30) (1 - f23) c17d20
y2 = (1 - a1) (1 - a5) (1 - a6) k30h28d20
y3 = (1 - a1) (1 - a5) (1 - a6) k30 (1 - h28) (1 - c17) f26
y4 = (a3 + a4) k30 (1 - h28) (1 - c17) (1 - f26) d19
y5 = (1 - a1) (1 - a5) (1 - a6) k30 (1 - h28) c17b10
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 44 /
Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.
Wyniki GEP - c.d.
y6 = a2k30 (1 - h28) c17 (1 - b7) (1 - b10) d19
y7 = a2k30c17d20b7h27 (1 - f23)
y7 = a2k30c17d20b7h27 (1 - f23)
y9 = (a3 + a4) k30 (1 - h28) c17 (1 - b10) f23
y10 = (a3 + a4) k30h29c17 (1 - b10) (1 - f23) (1 - f26)
y11 = (a3 + a4) k30c17 (1 - b9) (1 - b10) h27f22
y12 = (a3 + a4) k30c17 (1 - b9) (1 - b10) h27f22
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 45 /
Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.
Reguły P1-TS ( Analytical Methods, ... ):
y1 = a5b14 +a2b7 (1 - f23) k31 + a3 (1 - k30) (1 - f23) c17d20

MR1: If a5 '" b14, then y = 1,

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 52
2011 46 /
Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.
Reguły P1-TS ( Analytical Methods, ... ):
y1 = a5b14 + a2b7 (1 - f23) k31 +a3 (1 - k30) (1 - f23) c17d20

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 52
2011 47 /
Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Trafność metareguł z konkluzją y = 1: PQy=1, PQy=1 .
PQy=1 = liczba rekordów danych, które potwierdzają metaregułę:
poprzednik jest zgodny z rekordem danych
i następnik jest zgodny z rekordem danych.
PQy=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 52
2011 48 /
Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Metareguły z konkluzją y = 1: PQy=1, PQy=1 i ich trafność.
MR1: a5b14,
<1,0> #59
MR2: a2b7 (1 - f23) k31,
<3,0> #84,103,104
MR3: a3 (1 - k30) (1 - f23) c17d20,
<2,0> #16,91
MR4: (1 - a1) (1 - a5) (1 - a6) k30h28d20 = (a2 + a3 + a4) k30h28d20,
<1,0> #2
MR5: (a2 + a3 + a4) k30 (1 - h28) (1 - c17) f26,
<1,0> #49
MR6: (a3 + a4) k30 (1 - h28) (1 - c17) (1 - f26) d19,
<1,0> #9
MR7: (a2 + a3 + a4) k30 (1 - h28) c17b10,
<1,0> #35
Jacek Kluska (Politechnika Rzeszowska) Koncepcja klasyfikatora opartego na programowaniu ekspresji genów i logice rozmytej 52
2011 49 /
Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

Metareguły z konkluzją y = 1: PQy=1, PQy=1 i ich trafność.
MR8: a2k30 (1 - h28) c17 (1 - b7) (1 - b10) d19, <2,0> #43, 98
MR9: a2k30c17d20b7h27 (1 - f23),
<15,2> #10, 15, 46, 47, 50, 68, 69, 70, 73, 74, 77, 85, 88, 110, 112
MR10: (a3 + a4) k30 (1 - h28) c17 (1 - b7) (1 - b10) f26,
<1,0> #58
MR11: (a3 + a4) k30 (1 - h28) c17 (1 - b10) f23,
<7,0> #19, 20, 21, 22, 105, 106, 107
MR12: (a3 + a4) k30h29c17 (1 - b10) (1 - f23) (1 - f26),
<6,0> #6, 7, 8, 24, 31, 37
MR13: (a3 + a4) k30c17 (1 - b9) (1 - b10) h27f22,
<5,0> #27, 28, 29, 52, 53
MR14: a3b7c17 (f24 + f25) h27k30,
<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 52
2011 50 /
Przykład - przewidywanie powikłań pooperacyjnych w
leczeniu raka szyjki macicy - c.d.

PQy =1, PQy=1 = 59, 4 , 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, (...)
Test y = 1 Test y = 0
CM: 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 fi = 1000 � SEi � SPi 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 52
2011 51 /
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],
12
f (a1, a2, . . . , k31) = yk, f : [0, 1]31 [0, 1]
"
k=1
Zaleta:

0 0 0
Dla x0 = a1, a2, . . . , k31 wyznaczamy f x0 " [0, 1].

Propozycja decyzji ostatecznej: f x0 � �! 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 52
2011 52 /