1 Aproksymacyjne wyszukiwanie informacji w bazach danychPolitechnika Śląska Politechnika Śląska Instytut Informatyki Aproksymacyjne wyszukiwanie informacji w bazach danych Wykład - Bazy danych 3 – kierunek Informatyka sem. VII Gliwice 2005
2 Rodzaje zapytań precyzyjne zakresowe aproksymacyjne Gliwice 2005
3 Rodzaje zapytań aproksymacyjnychWektorowe – wyszukiwanie na podstawie podobieństwa dwóch wektorów, z których jeden reprezentuje wyszukiwany obiekt, a drugi kryteria pytania Oparte na prawdopodobieństwie – wyszukiwanie na podstawie prawdopodobieństwa spełnienia przez obiekt warunków pytania, Rozmyte – wyszukiwanie na podstawie stopnia zgodności obiektu z kryteriami pytania W języku naturalnym – semantyka języka określa sposób interpretacji pytania Gliwice 2005
4 Rys historyczny Twórca teorii zbiorów rozmytych: Lotfi Zadeh (1965r.)Praca inicjująca stosowanie zbiorów rozmytych w bazach danych: opracowanie V. Tahaniego o wyszukiwaniu informacji rozmytej (1976r.) Gliwice 2005
5 Badania nad zastosowaniem teorii zbiorów rozmytych w bazach danych (1)Zadawanie rozmytych pytań do bazy danych: Translator języka naturalnego wykorzystujący teorię zbiorów rozmytych PRUF - (Zadeh ) Pierwszy rozmyty języka zapytań (Takahashi ) (X jest bardzo niski) Fuzzy Query – tworzony od połowy 1997r. Przez Sonalysts Fquery – IBS PAN Warszawa (J. Kacprzyk, S. Zadrożny) dla MS Access SQLf – P. Bosc, O. Pivert itd. Gliwice 2005
6 Badania nad zastosowaniem teorii zbiorów rozmytych w bazach danych (2)Zapamiętywanie rozmytych informacji w bazie danych: rozmyte modele danych (B. P. Buckles, F. E. Petry) Rozmyty relacyjny model GEFRED – Uniwersytet w Granadzie (J. Cubero, M. Vila, K. Pons, J. Medina) Rozmyte modele obiektowych baz danych – Belgia (R. De Caluwe itd.) Zbiory rozmyte w bazach danych systemów geograficznych (M. Cobb, A. Yazici, K. Akkaya, V. Robinson) Gliwice 2005
7 Rodzaje pytań oraz przechowywanych danychPolitechnika Śląska Rodzaje pytań oraz przechowywanych danych Precyzyjne pytania - dokładne dane w BD Rozmyte pytania - dokładne dane w BD Precyzyjne pytania - rozmyte dane w BD Rozmyte pytania - rozmyte dane w BD Z takiej klasyfikacji pojawiają się dwa problemy: - jak zawrzeć w składni SQL rozmyte sformułowania - jak przechowywać informacje rozmyte w bazie danych. Stopniowo problemy te będą poruszane w kolejnych częściach prezentacji. Gliwice 2005
8 Problemy Jak przedstawić w składni języka SQL rozmyte sformułowania i jak ma przebiegać proces interpretacji takich zapytań? W jaki sposób przechowywać w bazie rozmyte dane? Gliwice 2005
9 Teoria zbiorów rozmytych -podstawowe pojęciaZbiór rozmyty – zbiór par, w pewnej numerycznej przestrzeni rozważań X A = {(µA(x), x)}, dla każdego x X, gdzie: µA – funkcja przynależności zbioru rozmytego A – każdemu elementowi zbioru x X przypisuje stopień przynależności µA(x) do zbioru A, przy czym µA(x) [0, 1] Gliwice 2005
10 Przykładowa funkcja przynależnościLiczba rozmyta Przedział rozmyty Przedział dokładny Wartość dokładna D l m n o a dm b Gliwice 2005
11 Reprezentacja liczb rozmytychLiczba rozmyta typu LR: A1 = (m, a, b) Przedział rozmyty typu LR: A2 = (m, n, a, b) Gliwice 2005
12 Postać zapytania w języku SQLSelect
13 Miejsca występowania wartości rozmytych w pytaniach niezagnieżdżonychWarunki filtrujące we frazie WHERE Warunki filtrujące we frazie HAVING Grupowanie wg wyrażeń zawierających wartości rozmyte – GROUP BY Porządkowanie wg kolumn zawierających wartości rozmyte – ORDER BY Wartości rozmyte we frazie SELECT Gliwice 2005
14 Diagram bazy danych Gliwice 2005
15 Interpretacja rozmytych warunków filtrujących w pytaniach SQLPrzykład Wyszukaj pracowników w wieku około 50 lat. Gliwice 2005
16 Wartość rozmyta około 50 1 ... X Gliwice 2005
17 Zapis w notacji języka SQLSELECT imie, nazwisko FROM pracownicy WHERE wiek JEST okolo 50 T(x) 1 (48) = 0.8 wiek Gliwice 2005
18 Uzupełnienie tabeli o tymczasową kolumnę zawierającą stopień zgodnościGliwice 2005
19 Warunki złożone Where W Where W1 AND W2 ... OR WkWi AND Wj min ((wi), (wj)) t-norma Wi OR Wj max((wi), (wj)) s-norma Gliwice 2005
20 Wyszukaj pracowników w wieku około 50 lat, mających staż pracy około 20 lat. SELECT imie, nazwisko FROM pracownicy WHERE wiek JEST okolo 50 AND staz_pracy JEST okolo 20 Uzupełniona tabela o tymczasowe kolumny zawierające wartości stopni zgodności Gliwice 2005
21 Podstawa wyboru wierszyMaksymalny stopień zgodności z warunkami pytania Przekroczenie średniego stopnia zgodności Przekroczenie pewnej zadanej wartości progowej Gliwice 2005
22 Wprowadzenie do zapisu pytań SQL warunku na stopień zgodnościPrzykład Wyszukaj pracowników, którzy mają około 50 lat, w odpowiedzi należy uwzględnić wiersze ze stopniem zgodności z kryterium pytania większym niż 0.7. Dotychczasowy zapis pytania: SELECT imie, nazwisko FROM pracownicy WHERE wiek JEST okolo 50 Gliwice 2005
23 Trzy formy zapisu warunku na stopień zgodnościforma dołączana do warunku rozmytego WHERE wiek jest okolo 50 AND DG > 0.7; forma funkcyjna WHERE DG(p.wiek, okolo 50) > 0.7; forma operatorowa WHERE (wiek jest okolo 50) > 0.7; Gliwice 2005
24 Wartości rozmyte w kolumnach tabelitabela: zapotrzebowanie (nr_zakl, rok, zapotrzebowanie_na _papier) Przykład Wyszukać zakłady, które złożyły zapotrzebowanie na niewielką ilość papieru. SELECT nr_zakl FROM zapotrzebowanie WHERE zapotrzebowanie_na_papier jest niewielkie; T(x) 1 x Gliwice 2005
25 Agregacja w pytaniach rozmytych (1)Funkcje agregujące na danych rozmytych (we frazie SELECT) „Wyznacz wartość średniego zapotrzebowania na tonery.” SELECT AVG(toner) FROM zapotrzebowanie WHERE rok = ‘2003’; Gliwice 2005
26 Agregacja w pytaniach rozmytych (2)Nakładanie warunków na funkcje agregujące w pytaniach rozmytych (fraza HAVING): Agregacja wartości ostrych – nakładany warunek rozmyty Agregacja wartości rozmytych – nakładany warunek ostry Agregacja wartości rozmytych – nakładany warunek rozmyty Rozmyte kwantyfikatory operujące na grupie wierszy Gliwice 2005
27 Agregacja w pytaniach rozmytych (3)Agregacja wartości ostrych – nakładany warunek rozmyty Wyszukać te zakłady, w których jest zatrudnionych około 10 kobiet, przy czym stopień zgodności z tym warunkiem powinien być większy od 0.65. SELECT nr_zakl FROM pracownicy WHERE plec = ‘K’ GROUP BY nr_zakl HAVING (count(nr_prac) jest okolo 10) > 0.65 Gliwice 2005
28 Agregacja w pytaniach rozmytych (4)Przykład Wyznacz dla każdego zakładu wartość średniego zapotrzebowania na papier. Wyszukaj te zakłady, w których wartość ta przekracza 30 ryz. SELECT nr_zakl, AVG(zapotrzebowanie_na_papier) FROM zapotrzebowanie GROUP BY nr_zakl HAVING AVG(zapotrzebowanie_na_papier) > 30; Gliwice 2005
29 Agregacja w pytaniach rozmytych (5)Agregacja wartości rozmytych Wyszukać te instytuty, których sumaryczne zapotrzebowanie na papier w danym roku wynosiło około 1000 ryz. W odpowiedzi powinny znaleźć się wiersze o stopniu zgodności co najmniej 0.7. SELECT nr_inst, rok FROM zapotrzebowanie z JOIN instytuty i ON z.nr_inst = i.nr_inst GROUP BY i.nr_inst, rok HAVING (sum(papier) jest okolo 1000) >= 0.7; Gliwice 2005
30 Rozmyte kwantyfikatory (prawie wszystkie, prawie żaden, około połowa...)Wyszukaj te zakłady, w których prawie wszyscy pracownicy to mężczyźni. W odpowiedzi powinny znaleźć się wiersze o stopniu zgodności co najmniej 0.7. SELECT nr_zakl, prawie_wszystkie(plec = ‘M’) FROM pracownicy GROUP BY nr_zakl HAVING prawie_wszystkie(plec = ‘M’) >= 0.7; 1 1 0.5 ... ... X X Funkcja przynależności dla wartości lingwistycznej prawie_wszystkie Gliwice 2005 Stopień zgodności obliczonego odsetka (0.925) z wartością lingwistyczną prawie_wszystkie
31 Grupowanie danych grupowanie rozmyte dokładnych danychgrupowanie rozmytych danych Gliwice 2005
32 Grupowanie rozmyte dokładnych danychgrupowanie względem wartości lingwistycznych Dane: pomiary temperatury w kolejnych dniach Wartości lingwistyczne: bardzo zimno, zimno, ciepło, bardzo ciepło itd. grupowanie według arbitralnego podziału dziedziny atrybutu Dane: staż pracy poszczególnych pracowników Podział dziedziny: około 5 lat, około 10 lat, około 15 lat itd. grupowanie rozmyte z zastosowaniem metody hierarchicznej Początkowo każda dana tworzy grupę Iteracyjne łączenie dwóch najbliższych grup grupowanie rozmyte według autorskiego algorytmu Połączenie idei metody hierarchicznej z klasycznym grupowaniem bazującym na uporządkowaniu danych Gliwice 2005
33 Metody wyznaczania odległości między grupaminajmniejsza odległość pomiędzy dowolną daną grupy A i daną grupy B: największa odległość pomiędzy dowolną daną grupy A i daną grupy B: średnia arytmetyczna wszystkich odległości pomiędzy wszystkimi danymi grup A i B: odległość pomiędzy punktem centralnym (wartością średnią) grupy A i punktem centralnym (wartością średnią) grupy B: gdzie mA, mB są wektorami: mA, mB. Gliwice 2005
34 Grupowanie rozmytych danychUwzględnienie w grupowaniu wszystkich parametrów opisujących wartości rozmyte Grupowanie według wartości modalnych Uwzględnienie wymienionych algorytmów grupowania rozmytego Gliwice 2005
35 Pytania zagnieżdżone Przykład pytania zagnieżdżonego:Wyszukaj zakłady, które w roku 2002 złożyły zapotrzebowanie na liczbę ryz papieru mniej więcej równą średniemu zużyciu we wszystkich zakładach. Dostępne tabele: Zapotrzebowanie (nr_zakl, rok, zapotrzebowanie_na_papier) Zuzycie (nr_zakl, rok, zuzycie_papieru) SELECT nr_zakl FROM zapotrzebowanie WHERE rok = ‘2002’ AND zapotrzebowanie_na_papier mniej wiecej (SELECT AVG(zuzycie_papieru) FROM zuzycie WHERE rok = ‘2002’); Gliwice 2005
36 Wartości rozmyte w pytaniach zagnieżdżonychw podzapytaniu wewnętrznym w podzapytaniu zewnętrznym w warunku wiążącym oba podzapytania Problem zapisu warunku na wartość stopnia zgodności forma dołączana do warunku rozmytego forma funkcyjna forma operatorowa Gliwice 2005
37 Pytanie zagnieżdżone w formie operatorowejW odpowiedzi powinny znaleźć się wiersze ze stopniem zgodności co najmniej 0.7. SELECT nr_zakl FROM zapotrzebowanie WHERE rok = ‘2002’ AND (zapotrzebowanie_na_papier mniej wiecej (SELECT AVG(zuzycie_papieru) FROM zuzycie WHERE rok = ‘2002’))>= 0.7; Gliwice 2005
38 Warunki wiążące w pytaniach zagnieżdżonychPorównanie wartości podzapytania zewnętrznego z wartością wyznaczaną w pytaniu wewnętrznym: Dokładna - rozmyta Rozmyta - dokładna Rozmyta -rozmyta Wartości rozmyte w warunku korelacji wiążącym pytania zagnieżdżone Gliwice 2005
39 Zależne kontekstowo interpretacje wartości rozmytychPrzykład: Wyszukać w bazie danych uczelni wysokich studentów. Uwzględnić wiersze ze stopniem zgodności przekraczającym 0.8. Dana tabela: Studenci (nr_stud, nr_kier, nazwisko, plec, wzrost) Tradycyjne podejście SELECT nazwisko FROM studenci WHERE (s.wzrost jest wysoki_wzrost) > 0.8 Gliwice 2005
40 Podejście kontekstoweDane są następujące tabele: Studenci (nr_stud, nr_kier, nazwisko, plec, wzrost), Wzrost (plec, wysoki_wzrost), SELECT nazwisko FROM Studenci s JOIN Wzrost w ON s.plec = w.plec WHERE (s.wzrost jest w.wysoki_wzrost) > 0.8 Gliwice 2005
41 Implementacja w SZBD PostgreSQLDlaczego SZBD PostgreSQL? dostępny kod możliwość tworzenia własnych typów, funkcji i operatorów Gliwice 2005
42 Implementacja typu rozmytegoReprezentacja wewnętrzna: a, m, dm, b Reprezentacja zewnętrzna: ‘l/m~n\o’ Przy wprowadzaniu danych: okolo(l, m, n, o) Funkcje konwersji wartości rozmytych do wartości lingwistycznych X l m n o a dm b 1 Gliwice 2005
43 Zaimplementowane funkcje i operatoryRodzaj nazwa Funkcje i operatory arytmetyczne +, -, *, / Funkcje i operatory porównania >=, >, <=, <, <>, = Funkcje i operatory wyznaczające wartość stopnia zgodności ~= Funktory iloczynu, sumy i negacji rozmytych &&&, |||, ~ Wartości predefiniowane dla typu rozmytego okolo_kilka, okolo_godzina itp. Funkcje konwersji typu rozmytego do postaci alfanumerycznej sekundy_to_lingw, dni_to_lingw Funkcje agregujące na wartościach typu rozmytego avg, sum, min, max Funkcje realizujące rozmyte kwantyfikatory prawie_zaden, prawie_wszystkie, okolo_polowa itd. Funkcje i operatory realizujące rozmyte grupowanie danych <, =, <<< Funkcje i operatory realizujące rozmyty warunek wiążący podzapytania *=, *>=, *>, *<=, *<, *<> Gliwice 2005
44 Testowa baza Zawodnicy6 tabel rekordów 12 złożonych testowych zapytań Gliwice 2005
45 Baza danych zawodnicy Struktura bazy danych zawodnicyOsoby (id_oso, imie, nazwisko, plec, data_ur, wzrost, waga, data_przyjecia, funkcja), Obecności (id_obe, id_tre, id_oso, sennosc, zmeczenie, stres, zlosc); Serie (id_ser, id_obe, nr, suma), Strzaly (id_strz, id_ser, nr, wynik), Treningi (id_tre, data, godz_od, godz_do, id_oso, id_war) Warunki (id_war, data, temperatura, wiatr, widocznosc) Id_oso – w tabeli treningi oznacza id. trenera Gliwice 2005
46 Diagram bazy danych ZawodnicyGliwice 2005
47 Przykłady definicji zmiennych lingwistycznych (1)Gliwice 2005
48 Przykłady definicji zmiennych lingwistycznych (2)Gliwice 2005
49 Przykładowe pytania rozmyte (1) wartości rozmyte we frazie where„Wyszukaj nazwiska wysokich zawodników średniej wagi, którzy przy słabej widoczności choć raz trafili w dziesiątkę. W odpowiedzi powinny znaleźć się wszystkie wiersze spełniające ze stopniem zgodności większym niż 0 kryteria pytania.” SELECT DISTINCT os.id_oso, os.imie, os.nazwisko FROM osoby os JOIN obecnosci ob ON os.id_oso = ob.id_oso JOIN treningi t ON ob.id_tre = t.id_tre JOIN warunki w ON t.id_war = w.id_war JOIN serie s ON s.id_obe = ob.id_obe JOIN strzaly st ON s.id_ser = st.id_ser WHERE ((os.wzrost ~= wysoki_wzrost_mezczyzny()) &&& (os.waga ~= srednia_waga_mezczyzny()) &&& (w.widocznosc ~= slaba_widocznosc())) > 0.0 AND st.wynik = 10; Gliwice 2005
50 Przykładowe pytania rozmyte (2) wartości rozmyte we frazie where„Wyszukaj daty treningów wraz z liczbą zawodników, którzy przystępując do treningu byli wyspani lub wypoczęci, zaś w czasie treningów nie denerwowali się (nie odczuwali stresu). W odpowiedzi powinny znaleźć się wszystkie wiersze spełniające ze stopniem zgodności większym niż 0,5 kryteria pytania.” Gliwice 2005
51 Przykładowe pytania rozmyte (3a) wartości rozmyte we frazie WHERE i HAVING„Wyszukaj zawodników, którzy odbywali dwa pierwsze treningi z małym stresem i mieli na nich chociaż jedną bardzo dobrą serię. W odpowiedzi powinny się znaleźć wiersze spełniające kryteria pytania ze stopniem większym niż 0.” „Wyszukaj warunki pogodowe panujące w czasie tych treningów, w trakcie których prawie wszyscy zawodnicy byli wyspani (stopień zgodności z warunkiem rozmytym wyspany powinien być nie mniejszy niż 0,8, a własność prawie wszystkie winna być spełniona ze stopniem zgodności nie mniejszym niż 0,7)”. Gliwice 2005
52 Przykładowe pytania rozmyte (4) grupowanie względem wartości rozmytych„Wyszukaj średnią liczbę punktów uzyskanych we wszystkich seriach dla poszczególnych zdefiniowanych przedziałów wartości siły wiatru.” „Określ wpływ zmęczenia zawodników na celność ich strzałów. (Wyznacz średnią liczbę punktów uzyskaną dla poszczególnych stanów zmęczenia).” Gliwice 2005
53 Przykładowe pytania rozmyte (5) wartości rozmyte w pytaniach zagnieżdżonych w podzapytaniach wewnętrznym i zewnętrznym „Wyszukaj nazwiska zawodników, którzy w poszczególnych treningach mieli najwięcej dobrych serii. W odpowiedzi powinny znaleźć się wiersze ze stopniem zgodności przekraczającym 0.” „Wyszukaj treningi, w których liczba bardzo_dobrych serii była większa niż dobrych. W rozwiązaniu należy uwzględnić wiersze ze stopniem zgodności przekraczającym 0.8.” Gliwice 2005
54 Przykładowe pytania rozmyte (6) wartości rozmyte w pytaniach zagnieżdżonych wartości rozmyte w warunku łączącym „Wyszukaj treningi przeprowadzone w najsłabszej widoczności, na których choć jeden zawodnik trafił dziesiątkę.” „Wyszukaj wyniki i cechy psychomotoryczne (senność, zmęczenie, stres) uczestników treningów, w czasie których wiatr był taki jak wiatr na najmniej udanym treningu. W odpowiedzi powinny się znaleźć wiersze spełniające kryteria pytania ze stopniem zgodności przekraczającym 0.5. ” „Wyszukaj daty tych treningów, na których odsetek wyspanych zawodników jest największy.” Gliwice 2005
55 Serwisy wspomagające nawiązywanie kontaktów międzyludzkichPoznawanie ciekawych osób o podobnych zainteresowaniach cechach charakteru czy odpowiadającym wyglądzie Gliwice 2005
56 Problemy: Sprecyzowanie wymagań, jakie powinna spełniać najbardziej odpowiadająca osoba Otrzymanie w odpowiedzi danych co najmniej kilku osób, spełniających w określonym stopniu podane kryteria Gliwice 2005
57 Wprowadzenie do języka zapytań elementów teorii zbiorów rozmytych pozwala na:Formułowanie rozmytych, nieprecyzyjnych warunków wyszukiwania (np. średni wzrost, szczupła sylwetka itd.) Określenie w odpowiedzi częściowej przynależności elementu do zdefiniowanego zbioru Gliwice 2005
58 Warstwy logiki rozmytej w prezentowanym serwisieGliwice 2005
59 Warstwa najniższa: funkcje podstawowe + operatoryZaimplementowano: Funkcje charakterystyczne: liniową, trójkątną, trapezową, wykładniczą oraz połączenie trapezowej i wykładniczej Operatory rozmyte: operator sumy OR (max spośród dwóch parametrów – s-norma Zadeh’a) operator iloczynu AND (min spośród dwóch parametrów - t-norma Zadeh’a) operator negacji NOT – różnica wartości 1 i parametru operator koncentracji CON – druga potęga wartości parametru operator rozproszenia DIL – pierwiastek z wartości parametru Gliwice 2005
60 Warstwa definicji cech, należących do kryterium wyszukiwarkiPrzykładowe cechy, jakie zdefiniowano w systemie: dotyczące wzrostu: is_very_short, is_short, is_medium, is_high, is_very_high dotyczące wieku: is_teenage, is_young, is_mature, is_senior dotyczące sylwetki: is_thin, is_normal, is_fluffy Do każdej cechy przyporządkowana jest dowolna funkcja charakterystyczna, którą można odpowiednio kształtować z poziomu interfejsu użytkownika Personalizacja zapytań (w zależności od cech osoby korzystającej z przeglądarki) Gliwice 2005
61 Aplikacja do zarządzania zapytaniami rozmytymiGliwice 2005
62 Zapytanie SQL Przykład:zapytanie wybiera osoby wysokie, młode lub średnie wiekiem, o szczupłej sylwetce, przy następujących danych osoby pytającej: wzrost 176cm, waga 65 kg: SELECT * FROM persons WHERE activity = true AND sex = ‘F’ AND (is_high(176,height) OP_AND is_thin(65,weight) op_and is_young(20,age) OP_OR is_medium(20,age))>0; Gliwice 2005
63 Wyszukiwarka rozmyta Gliwice 2005