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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
52 / 52