Автореферат (Построение импликативных зависимостей для аналитического описания предметных областей и обнаружения ошибок в данных), страница 2

11-13.07.2012 European PhD Program in Computional LogicWorkshop 2012, Dresden, Germanyhttp://www.epcl-study.eu/content/phdws12/;4. 1-3.07.2013EuropeanPhDPrograminComputionalWorkshop 2013, Dresden, Germanyhttp://www.epcl-study.eu/content/phdws13/5. 2.05.2013 IPID Doktorandtentreen, Cologne, Germanyhttps://www.daad.de/hochschulen/internationalisierung/ipid/13303.de.html6. 28.06.2013 International Seminar, Dresden Germany5Logichttp://tu-dresden.de/die_tu_dresden/fakultaeten/fakultaet_mathematik_und_naturwissenschaften/fachrichtung_mathematik/institute/algebra/veranstaltungen;7. 28.08.2012 What can FCA do for Articial Intelligence? 2012,Montpellier, Francehttp://fca4ai.hse.ru/2012/;8. 11-14.10.2012 Concept Lattices and Their Applications 2012,Malaga, Spainhttp://www.matap.uma.es/cla2012/CLA2012/Welcome.html;9.

24.03.2013 Formal Concept Analysis meets Information Retrieval2013, Moscow, Russiahttp://fcair.hse.ru/;10. 03.08.2013 What can FCA do for Articial Intelligence? 2013,Beijing, Chinahttp://fca4ai.hse.ru/2013.Ïî òåìå äèññåðòàöèè îïóáëèêîâàíî 7 ïå÷àòíûõ ðàáîòàõ, â òîì ÷èñëåäâå èç íèõ [5, 7] â æóðíàëàõ, âêëþ÷åííûõ â ñïèñîê ÂÀÊ.Ñòðóêòóðà è îáúåì äèññåðòàöèèÐàáîòà ñîñòîèò èç ïÿòè ãëàâ, âêëþ÷àÿ ââåäåíèå, çàêëþ÷åíèå, ñïèñîêëèòåðàòóðû. Îáúåì äèññåðòàöèè 153 ñòðàíèöû, âêëþ÷àÿ îãëàâëåíèå. Ñïèñîê ëèòåðàòóðû âêëþ÷àåò 86 íàèìåíîâàíèÿ.  òåêñò äèññåðòàöèè âõîäÿò 16 èëëþñòðàöèé, 2 òàáëèöû, 1 ëèñòèíã è 3 àëãîðèòìà.Ñîäåðæàíèå ðàáîòûÂî ââåäåíèè îïèñûâàþòñÿ öåëè ðàáîòû, îáîñíîâûâàåòñÿ åå àêòóàëüíîñòü è ïðàêòè÷åñêàÿ çíà÷èìîñòü.

Ïåðå÷èñëÿþòñÿ îñíîâíûå ðåçóëüòàòû, ïðåäñòàâëÿþòñÿ êîíñïåêòèâíûå ñâåäåíèÿ ïî èñòîðèè âî-6ïðîñà, êîòîðûå çàòðàãèâàþò ïîëîæåíèÿ äèññåðòàöèîííîãî èññëåäîâàíèÿ. Äàåòñÿ êðàòêèé îáçîð îñíîâíûõ ñìåæíûõ íàó÷íûõ íàïðàâëåíèé. Ïðîâîäèòñÿ ñðàâíåíèÿ ñ äðóãèìè ìåòîäàìè àíàëèçà äàííûõ,èñïîëüçóþùèìè àëãåáðàè÷åñêèå ðåøåòêè, à òàêæå ïðèâîäÿòñÿ ïðèìåðû ïðèìåíåíèÿ ìåòîäîâ è ñðåäñòâ àíàëèçà ôîðìàëüíûõ ïîíÿòèé(ÀÔÏ) äëÿ ðåøåíèÿ çàäà÷ àíàëèçà äàííûõ â ðàçëè÷íûõ îáëàñòÿõíàóê.Ìåòîäîëîãèÿ àíàëèçà ôîðìàëüíûõ ïîíÿòèé èñïîëüçóåòñÿ â äàííîé ðàáîòå êàê îñíîâíîé èíñòðóìåíòàðèé äëÿ ïîðîæäåíèÿ, àíàëèçàè ïðåäñòàâëåíèÿ èìïëèêàòèâíûõ òåîðèé. Êðîìå òîãî, ðàçðàáîòàííûå â ðàìêàõ äàííîé ðàáîòû ìåòîäû äîïîëíÿþò ìåòîäû ÀÔÏ, îñîáåííî â ÷àñòè, êîòîðàÿ êàñàåòñÿ íàõîæäåíèÿ îøèáîê â äàííûõ.Âî âòîðîé ãëàâå äàåòñÿ ââåäåíèå â ÀÔÏ, ñîäåðæàíèå êîòîðîãîïðåäíàçíà÷åíî äëÿ îáëåã÷åíèÿ ïîíèìàíèÿ ïîëîæåíèé äèññåðòàöèè.Îíî íà÷èíàåòñÿ ñ èçëîæåíèÿ ýëåìåíòîâ òåîðèè ðåøåòîê, òàê êàê èñòîðè÷åñêè ÀÔÏ âîçíèê ïðè ïîïûòêå ïðèäàòü ïðèêëàäíóþ íàïðàâëåííîñòü ýòîé òåîðèè.

 ñëåäóþùåì ðàçäåëå ïðåäñòàâëåíî ââåäåíèå â ÀÔÏ.  äâóõ çàêëþ÷èòåëüíûõ ïîäðàçäåëàõ âòîðîé ãëàâû ðàññìàòðèâàþòñÿ ÷àñòíûå âîïðîñû ÀÔÏ, èìåþùèå ïðÿìîå îòíîøåíèåê äàííîé ðàáîòå, òàêèå êàê ìåòîä àêòèâíîãî îáó÷åíèÿ Èññëåäîâàíèå ïðèçíàêîâ è âîïðîñû ïðåäñòàâëåíèÿ çíàíèé â âèäå äèàãðàììûðåøåòêè. òîì ÷èñëå äàþòñÿ ñëåäóþùèå îñíîâíûå îïðåäåëåíèÿ.G, M .

Ïóñòü I ⊆ G×M - áèíàðíîå îòíîøåíèå ìåæäó ìíîæåñòâàìè G è M . Òðîéêà K := (G, M, I) íàçûâàåòñÿ (ôîðìàëüíûì) êîíòåêñòîì. Ìíîæåñòâî G íàçûâàþò ìíîæåñòâîìîáúåêòîâ, ìíîæåñòâî M - ìíîæåñòâîì ïðèçíàêîâ. Ïóñòü A ⊆ M ,X ⊆ G. Ðàññìîòðèì îòîáðàæåíèÿ ϕ : 2G → 2M è ψ : 2M → 2G :Ïóñòü äàíû ìíîæåñòâàϕ(X) := {m ∈ M | gIm äëÿ âñåõ g ∈ X};ψ(A) := {g ∈ G | gIm äëÿ âñåõ m ∈ A}.ϕ è ψ èñïîëüçóþò åäèíîå îáîçíà÷åíèå (·)0 .Z ⊆ G. (Z)00 íàçûâàåòñÿ çàìûêàíèåì Z â K.Îáû÷íî âìåñòîÏóñòüZ ⊆ MÏóñòüèëè7X ⊆ G, A ⊆ M . (Ôîðìàëüíîå) ïîíÿòèåX0 = AÏóñòüy = (X, A).

Xåñòü ïàðà(X, A):A0 = X.èíàçûâàåòñÿ îáúåìîì ïîíÿòèÿâàåòñÿ ñîäåðæàíèåì ïîíÿòèÿy.y, Aíàçû-Ôîðìàëüíûå ïîíÿòèÿ ÷àñòè÷íî-óïîðÿäî÷åíû îòíîøåíèåì(X1 , A1 ) ≥ (X2 , A2 ) ⇐⇒ X1 ⊇ X2 (A2 ⊇ A1 ).m ∈ M, X ⊆ G, òîãäà m íàçûâàåòñÿ îòðèöàòåëüíûì ïðè00çíàêîì. m ∈ X â òîì è òîëüêî â òîì ñëó÷àå, åñëè íè îäèí x ∈ X0íå óäîâëåòâîðÿåò xIm.

Ïóñòü A ⊆ M ; A ⊆ X â òîì è òîëüêî â0òîì ñëó÷àå, åñëè âñå m ∈ A óäîâëåòâîðÿþò m ∈ X . Èìïëèêàöèåéâ êîíòåêñòå K = (G, M, I) íàçûâàåòñÿ ïàðà (A, B), ïèøóò A → B ,ãäå A, B ⊆ M . A íàçûâàåòñÿ ïîñûëêîé, B íàçûâàåòñÿ ñëåäñòâèåìèìïëèêàöèè A → B . Èìïëèêàöèÿ A → B óäîâëåòâîðÿåòñÿ ìíîæåñòâîì ïðèçíàêîâ N , åñëè A * N èëè B ⊆ N .  ïðîòèâíîìñëó÷àå ñ÷èòàþò, ÷òî ìíîæåñòâî ïðèçíàêîâ ïðîòèâîðå÷èò èìïëèêàöèè. Èìïëèêàöèÿ A → B âåðíà â K, åñëè îíà óäîâëåòâîðÿåòñÿ0âñåìè g , g ∈ G, òî åñòü êàæäûé îáúåêò, îáëàäàþùèé âñåìè ïðèçíàêàìè èç A òàêæå îáëàäàåò âñåìè ïðèçíàêàìè èç B . Ïîääåðæêîéèìïëèêàöèè â êîíòåêñòå K íàçûâàþò ìíîæåñòâî âñåõ îáúåêòîâ êîíòåêñòà K, ÷üè ñîäåðæàíèÿ ñîäåðæàò êàê ïîñûëêó, òàê è ñëåäñòâèåèìïëèêàöèè.

Àòîìàðíîé èìïëèêàöèåé íàçûâàþò òàêóþ èìïëèêàÏóñòüöèþ, â ñëåäñòâèè êîòîðîé ñîäåðæèòñÿ òîëüêî îäèí ïðèçíàê, òî åñòüA → b,ãäåA ⊆ M, b ∈ M .Íîâûå âåðíûå èìïëèêàöèè èç óæåèìåþùèõñÿ ìîæíî ïîëó÷èòü ñ ïîìîùüþA→A,A→B,A∪C →BÁàçèñîì èìïëèêàöèéïðàâèë Àðìñòðîíãà :A → B, B ∪ C → D.A∪C →DêîíòåêñòàKíàçûâàþò ìíîæåñòâîïëèêàöèé, èç êîòîðîãî ëþáàÿ âåðíàÿ â êîíòåêñòåLèì-K èìïëèêàöèÿ ìî-æåò áûòü âûâåäåíà (ñ ïîìîùüþ ïðàâèë Àðìñòðîíãà) è íèêàêîå ñîáñòâåííîå ïîäìíîæåñòâî ìíîæåñòâàÏîäìíîæåñòâî ïðèçíàêîâP ⊆ M8Líå îáëàäàåò òàêèì ñâîéñòâîì.íàçûâàåòñÿïñåâäîñîäåðæàíèåì,åñëèP 6= P 00Q,òàêîãî ÷òîQ ⊂ P,00Q ⊂ P .

Ìèíèìàëüíûé ïî ÷èñëó èìïëèêàöèé áàçèñ èçêàíîíè÷åñêèé áàçèñ èìïëèêàöèé. Ïîñûëêè ýòîãî áàçèñàèìååò ìåñòîâåñòåí êàêè äëÿ ëþáîãî ïñåâäîñîäåðæàíèÿìîæíî îïèñàòü â òåðìèíàõ ïñåâäî-ñîäåðæàíèé. Êàíîíè÷åñêèé áàçèñèìïëèêàöèé òîãäà ìîæíî ïðåäñòâàèòü â âèäå:{P → (P 00 \ P ) | P-ïñåâäî-ñîäåðæàíèå}.Çàâèñèìîñòÿìè ïðåäìåòíîé îáëàñòè íàçûâàþòñÿ òàêèå èìïëèêàöèè, êîòîðûå ÿâëÿþòñÿ èñòèííûìè êàê àêñèîìû èëè òåîðåìû âïðåäìåòíîé îáëàñòè. òðåòüåé è ÷åòâåðòîé ãëàâàõ íà ïðèìåðàõ äâóõ ïðåäìåòíûõîáëàñòåé ïðåäñòàâëåíû ðàçðàáîòàííûå àâòîðîì ìåòîäû è ñðåäñòâààâòîìàòèçàöèè, êîòîðûå íåîáõîäèìû ïðè èñïîëüçîâàíèè ìåòîäîëîãèè ÀÔÏ è â ïðîöåññå ïîñòðîåíèÿ èìïëèêàòèâíûõ òåîðèé.Òðåòüÿ ãëàâà ïîñâÿùåíà ðåøåíèþ çàäà÷è, íàïðàâëåííîé íàñîçäàíèå ìåòîäîâ è ñðåäñòâ àâòîìàòèçàöèè ïîñòðîåíèÿ âçàèìîñâÿçåé ìåæäó ñâîéñòâàìè ôóíêöèé íà êîíå÷íûõ ìíîæåñòâàõ.

Âîïðîñûî âçàèìîñâÿçÿõ ñâîéñòâ ôóíêöèé íà êîíå÷íûõ ìíîæåñòâàõ âîçíèêàþò â ðàçíûõ îáëàñòÿõ ìàòåìàòèêè. Ê èõ ÷èñëó îòíîñÿòñÿ: òåîðèÿâûáîðà; òåîðèÿ ðåøåòîê; òåîðèÿ ìíîæåñòâ; ïðèìåðû èññëåäîâàíèéâçàèìîñâÿçåé ìåæäó ñâîéñòâàìè ôóíêöèé, êîòîðûå ïðåäñòàâëåíûäàëåå, â ðàçäåëå 3.1. Îäíàêî êðîìå àêòóàëüíîñòè äëÿ äðóãèõ íàó÷íûõ äèñöèïëèí, ðàññìîòðåííàÿ â òðåòüåé ãëàâå çàäà÷à îáëàäàåòåùå îäíèì âàæíûì ïðåèìóùåñòâîì.  ñâÿçè ñ òåì, ÷òî ñâîéñòâàôóíêöèé îïðåäåëåíû ìàòåìàòè÷åñêè, ïðåäñòàâëÿåòñÿ öåëåñîîáðàçíûì àâòîìàòèçèðîâàòü ïðîâåðêó íàëè÷èÿ òåõ èëè èíûõ ñâîéñòâ óêîíêðåòíûõ ôóíêöèé. Åñëè, êðîìå òîãî, àâòîìàòèçèðîâàòü ãåíåðàöèþ ôóíêöèé íà êîíå÷íûõ ìíîæåñòâàõ, òî, òåì ñàìûì, áóäåò àâòîìàòèçèðîâàí ïðîöåññ ïîñòðîåíèÿ íà÷àëüíîãî êîíòåêñòà äëÿ èññëåäîâàíèÿ ïðèçíàêîâ.Êàê îòìå÷àåòñÿ âî âòîðîé ãëàâå, äëÿ ïðèìåíåíèÿ ìåòîäà èññëåäîâàíèå ïðèçíàêîâíåîáõîäèìî èìåòü âîçìîæíîñòü íàõîäèòüêîíòðïðèìåðû ê èññëåäóåìûì èìïëèêàöèÿì.

 äàííîì èññëåäîâàíèè êîíòðïðèìåðû áûëè íàéäåíû ñëåäóþùèì îáðàçîì. Ñíà÷àëà ãå-9íåðèðîâàëñÿ èñõîäíûé êîíòåêñò, è ñòðîèëñÿ åãî êàíîíè÷åñêèé áàçèñèìïëèêàöèé. Ïîñëå ýòîãî ãåíåðèðîâàëèñü ôóíêöèè íà ìíîæåñòâå çàäàííîãî ðàçìåðà. Ýòè ôóíêöèè ïðîâåðÿëèñü îòíîñèòåëüíî ðàíåå âûáðàííûõ ñâîéñòâ, äàëåå ïðîèçâîäèëàñü ïðîâåðêà ïîëó÷åííûõ êîìáèíàöèé ñâîéñòâ íà óäîâëåòâîðåíèå êàæäîé èìïëèêàöèè.  ñîîòâåòñòâèè ñ îïèñàíèåì ìåòîäà â ðàçäåëå 2.2.1 åñëè õîòÿ áû îäèí êîíòðïðèìåð áûë íàéäåí, òî ýòîò êîíòðïðèìåð äîáàâëÿëñÿ ê êîíòåêñòó, èáàçèñ âû÷èñëÿëñÿ çàíîâî. ïðîöåññå èññëåäîâàíèÿ ïðèçíàêîâ íà ñâîéñòâàõ ôóíêöèé íåáûëî íåîáõîäèìîñòè ïðîâåðÿòü âñå èìïëèêàöèè. Áëàãîäàðÿ òîìó,÷òî âîïðîñû âçàèìîñâÿçåé ñâîéñòâ ôóíêöèé èìåþò äëèòåëüíóþ èñòîðèþ èçó÷åíèÿ, íåêîòîðûå èìïëèêàöèè ìåæäó ñâîéñòâàìè ôóíêöèé, ïîëó÷åíèå êîòîðûõ ÿâëÿþòñÿ öåëüþ äàííîé ãëàâû, áûëè óæåèññëåäîâàíû äðóãèìè àâòîðàìè è äîêàçàíû êàê òåîðåìû. Ýòè çíàíèÿ èñïîëüçîâàëèñü â õîäå ïðîâåäåíèÿ äàííîãî èññëåäîâàíèÿ.

Áîëüøàÿ ÷àñòü áàçèñîâ èìïëèêàöèé íà ñâîéñòâàõ ôóíêöèé, îäíàêî, íåáûëà ðàíåå îñâåùåíà â ëèòåðàòóðå. Îíè âïåðâûå ðàññìîòðåíû è ÷àñòè÷íî äîêàçàíû â ðàìêàõ ðàáîòû â ðàçäåëå 3.3. Äîêàçàòåëüñòâàèìïëèêàöèé, âûïîëíåííûå àâòîðîì â ðàáîòå (óòâåðæäåíèÿ 3.3.7-9),à òàêæå ðÿäîì äðóãèõ àâòîðîâ (äëÿ áîëåå ïîëíîãî ïðåäñòàâëåíèÿ),èçëîæåíû â ðàçäåëå 3.3.2.  ðàçäåëå 3.3.3 ïðèâåäåí ïîäãîòîâëåííûéàâòîðîì ñïèñîê èìïëèêàöèé, äîêàçàòü êîòîðûå íå óäàëîñü. Îòìå÷åíî, ÷òî â ñëó÷àå äîêàçàòåëüñòâà âñåãî ïðåäñòàâëåííîãî ñïèñêà èìïëèêàöèé, ïîñòðîåíèå èìïëèêàòèâíîé òåîðèè áóäåò çàâåðøåíî.Ïðè äîêàçàòåëüñòâå èìïëèêàöèé áîëüøóþ òðóäíîñòü ïðåäñòàâëÿëè ñîáîé èìïëèêàöèè, èìåþùèå áîëüøóþ ïîñûëêó.

Ïðàêòè÷åñêèèìïëèêàöèè, èìåþùèå áîëåå ÷åòûðåõ ñâîéñòâ â ïîñûëêå, êðàéíåòðóäíû äëÿ ðàññìîòðåíèÿ ïîòîìó, ÷òî ìíîãèå èç ýòèõ ñâîéñòâ ÿâëÿþòñÿ çàâèñèìûìè. Äëÿ óïðîùåíèÿ ðàáîòû ñ òàêèìè èìïëèêàöèÿìè â ðàçäåëå 3.2 áûëî ñôîðìóëèðîâàíî, äîêàçàíî è â ïîñëåäóþùåìïðèìåíåíî óòâåðæäåíèå î âîçìîæíîñòè èçìåíåíèÿ âèäà áàçèñà èìïëèêàöèé.Ïóñòü G êàíîíè÷åñêèé áàçèñ èìïëèêàöèéêîíòåêñòà K, ñîäåðæàùèé èìïëèêàöèþ H → H 00 \ H . Òîãäà, åñëèÓòâåðæäåíèå 3.2.110X ⊆ H è X 00 = H 00 , òî ìíîæåñòâî èìïëèêàöèé G0 , ïîñòðîåííîåèç G çàìåíîé èìïëèêàöèè H → H 00 \H íà èìïëèêàöèþ X → H 00 \H ,îñòà¼òñÿ ìèíèìàëüíûì ïî ðàçìåðó áàçèñîì èìïëèêàöèé êîíòåêñòà K. ðàìêàõ èññëåäîâàíèÿ àâòîðîì äîêàçàòåëüíî óñòàíîâëåíà èñòèííîñòü ñëåäóþùèõ èìïëèêàöèé (óòâåðæäåíèÿ 3.3.3-9):•ÝÊÑ→Î, Í, ÎÀÎÁ;•ÈÍÒ→ÀÎÁ, ÎÁ;•Ì•Á•ÍÏ•Í•ÈÄ, •ÈÄ, Ì•ÈÄ, ÊÕʕÈÍÒ, ÍÏ•ÈÍÒ, ÈÄ, •ÈÍÒ, ÍÏ↔ÈÍÒ, Í, Î;•ÝÊÑ, ÍÏ↔ÝÊÑ, ÈÄ, Ì;•ÈÍÒ, Í, Ì→→Â, Ñ;ÈÍÒ, Ê, ÈÄ, ÍÏ, Î, Ñ, Í, Ì;→→→ÈÄ, ÊÃ;ÎÀÎÁ;→→Î;Î;→ÍÏ;Î, Í, Ñ;↔ÈÍÒ, ÊÃ;↔↔ÈÍÒ, Î;ÈÍÒ, Á.Ñîñòàâëåí ñïèñîê èìïëèêàöèé, èñòèííîñòü êîòîðûõ ïðåäñòîèòïðîâåðèòü äëÿ çàâåðøåíèÿ èññëåäîâàíèÿ (îòêðûòûå âîïðîñû):1.

ÊÃ→Â;2. ÈÄ, ÎÁ, ÀÎÁ3. ÀÒ→→ÎÀÎÁ;Í, ÎÁ, ÎÀÎÁ, ÀÎÁ, Â;4. ÈÍÒ, ÎÁ→Í, ÈÄ, ÎÀÎÁ;11→5. Í, ÈÍÒ6. ÀÒ, Ñ→ÈÄ;ÊÃ;→Ñ;8. Í, ÈÄ, Î, ÀÎÁ→7. Î, ÎÁ, ÀÎÁ→Ñ;10. Î, ÀÎÁ, ÊÃ→9. Î, Â, ÎÁ11. Ê→12. ÍÏ13. ÁÎÀÎÁ, Ñ, Â, Î;ÎÁ;→Î;15. ÈÍÒ, ÊÃ→14. Ì, ÎÁ16. Í, Ì→Í, Ê, ÎÀÎÁ, Ñ, Î;Î;→Ñ;18. ÈÍÒ, Â, ÎÁ→17.