Algoritmy pro binární faktorovou analýzu

VŠB – Technická univerzita Ostrava Fakulta elektrotechniky a informatiky

Algoritmy pro binární faktorovou analýzu

Aleš Keprt

autoreferát disertační práce

Ostrava Září 2006

Algoritmy pro binární faktorovou analýzu Autoreferát disertační práce http://www.keprt.cz/publikace/phd/ c 2006

Mgr. Aleš Keprt e-mail: [email protected] Školitel: prof. RNDr. Václav Snášel, CSc. Katedra informatiky Fakulta elektrotechniky a informatiky VŠB–Technická Univerzita Ostrava Ostrava–Poruba, Česko e-mail: [email protected] Oponenti: Ing. Pavel Praks, Ph.D. Katedra aplikované matematiky Fakulta elektrotechniky a informatiky VŠB–Technická Univerzita Ostrava e-mail: [email protected] doc. Ing. Hana Řezanková, CSc. Katedra statistiky a pravděpodobnosti Fakulta informatiky a statistiky Vysoká škola ekonomická v Praze e-mail: [email protected] doc. Ing. Ivan Zelinka, Ph.D. Ústav aplikované informatiky Fakulta aplikované informatiky Univerzita Tomáše Bati ve Zlíně e-mail: [email protected]

VŠB–Technická Univerzita Ostrava Fakulta elektrotechniky a informatiky Katedra informatiky http://www.cs.vsb.cz/

Abstract This doctoral thesis, or dissertation, is devoted to binary data and their factorization, which is a special kind of data analysis. Binary Factor Analysis (BFA) is a nonlinear analysis of binary data, where neither classical linear algebra, nor mathematical (functional) analysis can be used. It is a binary variant of a commonly used statistical method called factor analysis. Classical factor analysis was originally developed and used by psychologists to detect hidden psychic disorders by observation of visible symptoms. Classical factor analysis works with real valued data in normal distribution. Alongside it, Binary Factor Analysis uses the same notation with a different underlying algebra to express the same kind of analysis for binary valued data. In the past, it has been shown that although classical factor analysis often works seamlessly even for data of other kinds of distribution, it is not able to effectively express symptom–factor relations in binary data, which one can see for example in psychology, medicine, or sociology. Presented doctoral thesis aims to cover BFA from several different aspects, and to specialize on problem solving algorithms. It starts from the underlying algebra, and fundamental definitions. This first part of the work is rather mathematical, but only fundamental definitions are made to keep the text understandable. The second and main part is devoted to algorithms. Several original algorithms for BFA are proposed and described, they range from main factorization algorithms through important underlying algorithms to small supporting ones, with most space devoted to main factorization. Because of a large computational complexity of BFA, a considerable effort is also being put to investigation of parallel and distributed algorithms. Third part is devoted to experimental results. The last part is the user’s manual to BiF, a reference implementation of all presented algorithms. The manual contains not only technical description, but also guidelines aimed to be a starting point for an analyst, e.g. a sociologist or a psychologist, trying to check out how he or she can benefit from BFA. Most of presented algorithms are the results of my own work. They are based on a number of different fields of computer science and mathematics, and main benefits of binary factorization is supposed to be seen in human sciences. That’s also making the work truly interdisciplinary, and forced the notation to be unified throughout all chapters, and possibly less common in some particular cases.

3

Abstrakt Tato disertační práce je věnována binárním datům a jejich faktorizaci, což je zvláštní druh datové analýzy. Binární faktorová analýza (BFA) je nelineární analýzou binárních dat, kde nelze použít ani klasickou lineární algebru, ani matematickou (funkcionální) analýzu. Je binární variantou běžně užívané statistické metody zvané faktorová analýza. Klasická faktorová analýza byla původně vyvinuta a používána psychology k odhalování skrytých psychických poruch pomocí pozorování viditelných symptomů. Klasická faktorová analýza pracuje s reálnými čísly s daty v normálním rozdělení. Naproti tomu binární faktorová analýza používá stejnou notaci, ale s odlišnou základní algebrou, pro vyjádření stejného druhu analýzy pro binární data. Ačkoliv klasická faktorová analýza často funguje i na datech jiného než normálního rozdělení, není schopna efektivně vyjádřit symptom–faktorové relace v binárních datech, se kterými se můžeme setkat například v psychologii, medicíně nebo sociologii. Předkládaná disertační práce popisuje BFA z různých aspektů, především pak algoritmy k řešení této úlohy. Začíná popisem binární algebry, na které BFA stojí, a základních definic. Tato první část práce je spíše matematická, pro zachování srozumitelnosti textu se však omezuje jen na základní definice. Druhá a hlavní část práce je věnována algoritmům. Je předloženo a popsáno několik různých původních algoritmů pro řešení BFA, a to jak hlavní faktorizační algoritmy, tak důležité podpůrné a pomocné algoritmy; největší prostor je přitom věnován otázce samotné faktorizace. Z důvodu velké výpočetní složitosti BFA je část práce věnována i výzkumu paralelních a distribuovaných algoritmů. Třetí část práce je věnována experimentálním výsledkům. Poslední částí je uživatelský manuál programu BiF, což je referenční implementace všech představených algoritmů. Kromě technického popisu programu obsahuje manuál také koncepční rady vhodné jako výchozí bod pro analytika, např. sociologa nebo psychologa, který by chtěl BFA vyzkoušet použít. Většina prezentovaných algoritmů jsou výsledky mé vlastní práce. Jsou založeny na poznatcích z různých oblastí informatiky a matematiky, hlavní oblast použití binární faktorizace je dokonce až v humanitních vědách. To také dělá tuto práci interdisciplinární a vynutilo si používání jednotného značení a názvosloví, které v některých částech textu neodpovídá značení v dané oblasti obvyklému.

4

Obsah 1 Úvod

7

2 Současný stav řešené problematiky

8

3 Cíle disertační práce, organizace kapitol

10

4 Vlastní výsledky 4.1 Úvod do binárních vektorových prostorů a vektorová booleovská aritmetika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Koncept řádkových vah a kvality faktorů a koncepce určování počtu faktorů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Interpretace BFA . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Klasifikace klasických a paralelních BFA algoritmů . . . . . . . . . 4.5 Paralelní výpočetní rámec . . . . . . . . . . . . . . . . . . . . . . 4.6 Algoritmy preprocessingu . . . . . . . . . . . . . . . . . . . . . . . 4.7 Diskuze k neurosíťovému algoritmu . . . . . . . . . . . . . . . . . 4.8 Algoritmus Blind Search . . . . . . . . . . . . . . . . . . . . . . . 4.9 Algoritmus FCBFA . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 Aplikace genetických algoritmů na BFA . . . . . . . . . . . . . . . 4.11 Paralelní a distribuovaný výpočet . . . . . . . . . . . . . . . . . . 4.12 Algoritmus pseudo–dělení binárních matic (BMPD) . . . . . . . . 4.13 Binární pseudo–gradientní optimalizace (BPGD) . . . . . . . . . . 4.14 Podpůrné algoritmy a diskuze . . . . . . . . . . . . . . . . . . . . 4.15 Všechny experimenty na vlastních algoritmech . . . . . . . . . . . 4.16 Binární faktorizér BiF . . . . . . . . . . . . . . . . . . . . . . . .

11

5 Vlastní publikace 5.1 Publikace k binární faktorizaci . . . . . . . . . . . . . . . . . . . . 5.2 Mé ostatní publikace . . . . . . . . . . . . . . . . . . . . . . . . .

15 16 17

5

12 12 12 13 13 13 13 13 13 14 14 14 14 14 15 15

6

1

Úvod

Tento autoreferát popisuje disertační práci předloženou k obhajobě pod názvem Algorithms for Binary Factor Analysis (anglicky). Binární data, kterými se práce zabývá, jsou jedním ze základních kamenů počítačů. Zatímco dříve se často i nebinární data převáděla do a ukládala v binární podobě, obvykle z technických důvodů, dnes jsou binární data na fyzické úrovni, avšak na úrovni logické již bývá zvykem pracovat s daty v jejich přirozeném tvaru, který obvykle binární není. Analýza dat a hledání důležitých (ale často skrytých) informací v nich není vůbec nové téma, ale stále jde o věc velmi aktuální. Z hlediska informatiky je toto téma důležité i z důvodu rozvíjejícího se významu internetu nebo jako důsledek všeobecného důrazu na ekonomiku a ekonomické výdobytky civilizace. V tomto bodě zjišťujeme, že současný rozmach nových metod datové analýzy a získávání znalostí z dat nechává data binární povahy spíše na pokraji zájmu. Ačkoliv lidé vnímají většinu přirozených informací nebinárním způsobem, některé věci mají přirozeně binární povahu. Pro tato binární data můžeme použít analytické metody nebinárního charakteru, ale tyto techniky, obvykle založené na lineární algebře, aproximaci funkcí či hledání globálních extrémů, pro binární data nefungují dobře. Jejich selhání můžeme vysvětlit velmi specifickými vlastnostmi binárních dat, které také vyžadují specifické binární analytické metody. Jako příklad takové specificky binární metody můžeme uvést teorii konceptuálních svazů (FCA – formální konceptuální analýza, viz [4]) a související. Další specificky binární analytickou metodou je binární faktorová analýza (BFA), která je tématem této disertační práce. BFA je také binární, ale narozdíl od FCA je určena k jinému druhu analýzy. Je to nelineární analýza binárních dat, pro kterou nemůže být použita ani klasická lineární algebra, ani klasická matematická (funkcionální) analýza. V minulosti bylo opakovaně experimentálně doloženo, že klasické nebinární analytické metody následované dodatečným převodem výsledku do binární podoby nebo jiných dichotomických hodnot je z technického hlediska možno použít, ale dosažené výsledky nejsou uspokojivé (viz [14, 5]). Z toho důvodu vzniklo několik nových specificky binárních metod, užívajících booleovskou algebru. Binární faktorová analýza, nebo krátce binární faktorizace, je binární variantou běžné uživané statistické metody zvané faktorová analýza. Klasická faktorová analýza je metodou příbuznou datovému shlukování a původně byla vyvinuta a používána psychology ke zjišťování skrytých psychických poruch pomocí sledování viditelných symptomů. Teorie f.a. říká, že symptomy, které můžeme pozorovat, jsou důsledkem skrytých faktorů, jmenovitě že každý jednotlivý symptom je lineární kombinací faktorů. Faktor je tedy reálná veličina, kterou nelze změřit a je třeba ji vypočítat pouze ze znalosti jiných měřitelných reálných veličin (symptomů). Cílem faktorové analýzy tedy je nalezení faktorů a vyjádření závislosti (relace) mezi faktory a symptomy – tento vztah pak slouží k detekci psychických poruch. 7

Klasická faktorová analýza pracuje s daty – veličinami – reálné povahy s normálním rozdělením, binární faktorová analýza používá stejnou notaci, ale poněkud odlišnou algebru pro vyjádření stejného druhu analýzy pro data binárního typu. Přitom bylo experimentálně prokázáno, že klasická faktorová analýza často dobře funguje i pro data v jiném než normálním rozdělení, ale není schopna efektivně vyjádřit symptom–faktorové závislosti v binárních datech.

Příklad Jako příklad aplikace BFA můžeme uvést analýzu volitelných předmětů. Zajímáli nás, které skupiny volitelných předmětů si studenti obvykle zapisují společně, BFA dokáže na tuto otázku odpovědět, dokonce zřejmě i lépe, než jakákoliv jiná metoda. Nejprve potřebujeme datovou matici. Bude to binární matice, ve které budou zaneseny vybrané volitelné předměty (ty, které chceme analyzovat) a dostatečné množství studentů, kteří si některé z těchto předmětů zapsali. Sloupce datové matice pak představují jednotlivé předměty. Při sestavování nezáleží an pořadí předmětů, ale jednotlivé sloupce musejí být pojmenované, čili každý sloupec odpovídá jednomu konkrétnímu předmětu a toto je třeba zaznamenat (jako jméno sloupce). Každý řádek obsahuje data jednoho studenta; jedničky jsou ve sloupcích předmětů, které si daný student zapsal. Řádky jako takové však nejsou pojmenovány, studenti se tedy analýzy zúčastňují zcela anonymně. Tato anonymita je obecná vlastnost faktorové analýzy a minimálně z hlediska ochrany osobních údajů jde jistě o kladnou vlastnost. Výsledkem binární faktorové analýzy této matice jsou pak skupiny společně zapisovaných předmětů. Počet těchto skupin je jedním ze vstupních parametrů analýzy, čili předem musíme určit, kolik skupin chceme hledat. Každá jedna taková skupina se nazývá binární faktor (nebo jednoduše faktor). Binární faktor je tedy vybranou skupinou sloupců; obráceně můžeme říci, že každý sloupec buď patří, nebo nepatří do nějakého faktoru. Zvláštní vlastností binárních faktorů, která odlišuje BFA od běžných shlukovacích metod, je, že zařazení sloupce do nějakého faktoru nemá žádný vliv na jeho zařazení do ostatních faktorů. V extrémním případě je možné i to, aby sloupec byl zařazen do všech faktorů současně. Samozřejmě je naopak možné i to, aby některý sloupec nebyl zařazen do žádného faktoru – to se v praxi i běžně stává a stačí k tomu, abychom na začátku analýzy zvolili nějaký malý počet faktorů.

2

Současný stav řešené problematiky

Dle poměrně malého počtu vědeckých publikací věnovaných BFA, můžeme konstatovat, že jde o téma spíše na okraji vědeckého zájmu. Částečným důvodem a zároveň důsledkem tohoto stavu je fakt, že se stále jedná o problém považovaný za velmi obtížně algoritmicky řešitelný. Během posledních desetiletí byla BFA jen 8

sporadicky zmiňována ve vědeckých časopisech či na významných konferencích a není ani podporována běžným statistickým softwarem (s výjimkou BMDP [11] – softwarového balíku pro biomedicínu – který nepatří mezi nejznámější). Zatímco o klasické faktorové analýze je možno najít mnoho knih (např. [6, 8, 16]), o binární faktorové analýze žádná kniha neexistuje. Disertační práce proto vychází z článků z vědeckých časopisů a konferencí. Stav řešení problematiky BFA souhrnně popisují články Mickey, Mundle, Engelman [11] a Frolov, Húsek, Muraviev, Polyakov [3]. Tyto popisují dva algoritmy a jejich varianty; první používá jednoduchý regresní model optimalizace odhadnutého řešení, druhý funguje na bázi upravené Hopfieldovy neuronové sítě. Ani jeden z algoritmů nelze přímo podle zveřejněných článků naimplementovat a veřejné implementace, ani ve spustitelném, ani ve zdrojovém tvaru, nejsou k dispozici. Kromě toho je možno najít také publikace popisující aplikace BFA, opět jako články v časopisech – tentokrát zejména v oblasti humanitních věd sociologie, psychologie a medicíny. Je pochopitelné, že publikací v aplikační oblasti je podstatně více, že publikací týkajících se přímo výzkumu BFA algoritmů.

Oblasti užití BFA BFA je jistý druh datové analýzy, můžeme se s ní pochopitelně setkat v oblastech, kde se provádí analýza binárních dat. Může být použita v obecné statistice, ale aplikace převažující ve vědeckých publikacích jsou převážně z oblasti medicíny, sociologie a psychologie. Metoda je často zmiňována pod alternativním názvem „Boolean Factor Analysisÿ, čili Booleovská faktorová analýza (ve zkratce opět BFA). Poznamenejme, že tyto dva názvy – Binární f. a. a Booleovská f. a. jsou plně ekvivalentní a popisují stejnou techniku datové analýzy. První název převažuje v oblasti informatiky a matematiky ve studiu metody jako takové, zatímco druhý název je používán v aplikacích BFA v humanitních vědách. (Google říká, že přibližně 60% výskytů vede na název Booleovská f. a.) Nejstarší všeobecně známá a široce citovaná práce o BFA byla publikována v roce 1983 [11]. BFA je tam představena na biomedicínském příkladu sérologického testu (tj. na analýze krevního obrazu), podrobnější informace viz [7, 11]. Tento test je dobrým příkladem užití BFA a je dobře srozumitelný, proto je citován i dalších publikacích jiných autorů. Pattison, Breiger [13] diskutují užití obecně binárních booleovských metod v oblasti sociálních interakcí mezi lidmi. Zmiňují jmenovitě studium vztahů mezi jedinci a skupinami nebo mezi objekty stejného typu pozorováním jejich sociálních interakcí. Uvádějí také další zajímavé příklady známé i z jiných zdrojů, jako například úlohy typu jedinci a docházka (Foster, Seidman [1]), záznamy fluktuace akademických pracovníků mezi pracovištěmi (Freeman [2]) či organizace a komponenty jejich politické agendy (Mische, Pattison [12]). Podíváme-li se dále do minulosti, BFA byla zmiňována ve vědeckém psychologickém časopise jako „relativně nová metodaÿ v roce 1984 (Weber, Scharfetter [18]). Tato práce uvádí, že booleovská aritmetika užitá v BFA lépe odpovídá 9

povaze vztahů mezi symptomy a syndromy, o které se psychologie zajímá. Na druhou stranu Veiel [17] prezentoval opačné stanovisko, přesněji že booleovská aritmetika selhává u větších a reálných problémů. Můžeme najít i další příklady aplikací BFA. Jejich společným rysem je, že všechny spadají do oblasti humanitních věd, čili oblastí od informatiky poněkud vzdálených, takže tyto aplikace jako informatici nedokážeme vyhodnotit. Nejsnáze srozumitelné aplikace (pro informatiky) jsou zřejmě sociologické; smysl analýzy relací mezi studenty a jejich výběrem volitelných kurzů je jistě dobrým příkladem. Studenti jsou považování za anonymní „případyÿ a kurzy jsou neanonymní „proměnnéÿ. Výstupem BFA jsou pak binární faktory ve formě skupin kurzů, které jsou často navštěvovány stejnými studenty. Sociologové z těchto výsledků pak dokáží udělat další závěry, od filozoficky laděných teorií, až po prakticky užitečné statistiky. Další aplikací BFA je hledání mezi textovými dokumenty, kterým se zabývá celá řada publikací (např. Řezanková, Húsek, Snášel [15]). Toto je důležité téma a BFA je zde použitelné, ačkoliv její vysoká výpočetní složitost je problém, stejně jako u všech faktorově orientovaných metod datové analýzy. BFA je jistě užitečná především v případech, kde existuje důvod pro booleovskou aritmetiku, jak uvádí Weber, Scharfetter [18]. Podobné tradiční lineární techniky analýzy dávají v těchto binárních případech špatné výsledky. Disertační práce k tomuto tématu uvádí závěr, že BFA zřejmě není právě vhodná pro hledání mezi textovými dokumenty, hlavně z důvodu zmíněné obrovské výpočetní složitosti. Podobné varování dává i Pattison, Breiger [13]. V souvislosti s aplikacemi je zde i jedna důležitá otázka: Na jak velké matice můžeme binární faktorizaci aplikovat? Jde o spíše menší matice, ale zcela přesná odpověď na tuto otázku není známa. S ohledem na známé aplikace a také s odkazem na knihy o klasické faktorové analýze [8, 16] lze říci, že obvyklá datová matice pro faktorovou analýzu může mít velikost mezi 5×10 až 100×1000 bitů, s maximálním počtem řádků spíše otevřeným budoucím aplikacím. Sloupců je často mnohem méně než řádků a tento rozdíl se zvětšuje s velikostí matice.

3

Cíle disertační práce, organizace kapitol

Disertační práce prezentuje výsledek mého tříletého snažení o nalezení vhodného algoritmu pro řešení BFA. Během toho času vzniklo hned několik algoritmů, jak exaktních, tak přibližných. Kromě toho část času patřila také výzkumu možných aplikací BFA, což byla nelehká, ale potřebná část práce, zvláště pak v situaci, kdy běžný statistický software binární faktorizaci vůbec nepodporuje. Z osobního zájmu o paralelní a distribuované výpočty a programování pak vzešel další cíl: Navrhnout a implementovat navržené algoritmy také pro paralelní a distribuované prostředí, pokud to bude možné. Jelikož oblast binární faktorizace je tak málo studovaná jinými autory, disertační práce nemá moc na co navazovat a je tedy záměrně organizovaná do 10

uceleného celku, který popisuje danou problematiku (pokud možno) kompletně. Disertační práce je členěna do kapitol, které jsou seskupeny do čtyř celků – části. První část poskytuje úvod do problematiky a seznamuje s nosnou algebrou a základními definicemi. Tato část je spíše matematická, ale se snahou o co nejstručnější podání, protože příliš mnoho matematiky v úvodních kapitolách by spíše ztížilo srozumitelnost textu jako celku, než aby k němu přispělo. Druhá, hlavní část práce, kterou tvoří kapitoly 4 – 13, je věnována algoritmům. Jednotlivé kapitoly popisují různé algoritmy účastnící se na procesu řešení BFA, od hlavních faktorizačních algoritmů, přes důležité algoritmy v pozadí výpočtu, až po malé podpůrné algoritmy. Největší prostor je přitom samozřejmě věnován hlavním faktorizačním algoritmům. Z důvodu velké výpočetní složitosti BFA je zvláštní pozornost zaměřena také na paralelní a distribuované algoritmy, které mohou umožnit použití více počítačů k rychlejšímu provádění faktorizace. Třetí část práce je věnována provedeným experimentům, analýze jejich výsledků a závěrečnému vyhodnocení. Všechny podstatné experimenty jsou uvedeny až zde v samostatné kapitole, neboť experimentování s jednotlivými algoritmy by nemělo až takový smysl. Ačkoliv některé kapitoly ze druhé části (o algoritmech) také obsahují experimentální výsledky, hlavní srovnání a analýza faktorizačních algoritmů je odložena až na kapitolu 14 ve třetí části. Poslední část práce je uživatelským manuálem k programu BiF. BiF je binární faktorizátor (odtud název) připravený řešit BFA problémy. Program je napsaný v jazyce C++ a implementuje všechny algoritmy diskutované ve druhé části disertační práce, včetně algoritmů paralelních a distribuovaných. Manuál obsahuje kromě technických informací o použití programu také několik vodítek či metodických pokynů určených analytikům, kteří by chtěli prostřednictvím programu BiF vyzkoušet BFA využít. Program by měl být použitelný zejména pro sociology a psychology, což je ostatně také přímo prezentováno v experimentech v rámci kapitoly 14.

4

Vlastní výsledky

Vlastní výsledky lze jednou větou shrnout takto: Většina obsahu disertační práce je mými vlastními výsledky. Jedinou podstatnou výjimkou je algoritmus neuronové sítě v kapitole 7, a pak samozřejmě také samotná definice binární faktorové analýzy. Ostatní prezentované algoritmy, experimentální výsledky s výjimkou pasáží přejatých se společného článku [5] a také některé z úvodních definic jsou výsledky mé vlastní práce, to včetně diskuzí a analýz u jednotlivých témat (obvykle na konci kapitol). Nejdůležitější výsledky jsou vyjmenovány v následujících bodech.

11

4.1

Úvod do binárních vektorových prostorů a vektorová booleovská aritmetika

Sekce 2.3 a 2.4. Úvod do binárních vektorových prostorů shrnuje základní vlastnosti booleovské aritmetiky, když je aplikována na binární vektory a binární matice. Kromě běžných booleovských operací je zde také uvedena definice binárních prostoru, binárního vektoru, binární matice, součinu binárních matic a pseudo– podílu binárních matic. Ačkoliv se jedná o nepříliš komplikovanou matematiku, ani jediná jiná práce zabývající se BFA tyto základní definice a diskuzi k nim neobsahuje, ani formou odkazu na jiné dílo. Proto jsem tyto definice a diskuzi k nim sepsal sám.

4.2

Koncept řádkových vah a kvality faktorů a koncepce určování počtu faktorů

Sekce 3.3 a 3.4. V rámci úvodní části práce, kde je definována samotná BFA, jsem také provedl úvahu nad možnými zobecněními základní metody, která by byla zároveň sémanticky zajímavá a matematicky dobře podchytitelná. Tak vznikl pojem řádkových a sloupcových vah. Pojem kvality faktorů se snaží podchytit rozdílnou významnost jednotlivých faktorů, které ačkoliv v rámci analýzy vystupují jako sobě rovnocenné a je třeba je všechny počítat či hledat současně (kvůli jejich neomezeným korelacím), jejich výsledná či praktická užitečnost není určitě stejná. Otázka, jak určit počet faktorů, je ve většině prací týkajících se BFA mlčky přecházena, protože je těžké ji zodpovědět. Moje práce naopak ani tuto otázku nevynechává a přináší určitý náhled do této problematiky s návrhem řešení.

4.3

Interpretace BFA

Sekce 3.6. Ačkoliv u BFA vycházíme z čistě matematické definice, kdy ji prezentujeme jako metodu rozkladu binární matice na součin dvou menších binárních matic, toto nutně nemusí být jediná interpretace významu BFA. Ačkoliv při výpočtu je skutečně snahou realizovat tento maticový rozklad, v této definici není přímo vidět, jakým způsobem se BFA dá použít pro praxi. Aby tato otázka byla zodpovězena, práce se explicitně věnuje otázce interpretace BFA a uvádí následující alternativní interpretace: • Redukce dimenze prostoru • Porovnávání a vyhledávání dokumentů • Ztrátová komprese dat • Geometrická interpretace (hyperkrychle) • Rozdíly mezi faktorizací a běžným shlukováním 12

4.4

Klasifikace klasických a paralelních BFA algoritmů

Sekce 4.1 a 5.5. Nosným tématem práce je popis algoritmů pro řešení BFA. Proto práce obsahuje také souhrnné srovnání těch algoritmů, ne z hlediska jejich kvality, ale z hlediska jejich podobnosti. Sekce 4.1 klasifikuje regulární (neparalelní) algoritmy, sekce 5.5 potom klasifikuje algoritmy paralelní a distribuované.

4.5

Paralelní výpočetní rámec

Sekce 5.4. Poměrně velká část práce se zabývá specificky paralelním řešením BFA a jedním z vedlejších efektů výzkumů v této oblasti bylo vytvoření tzv. paralelního výpočetního rámce pro BFA. Tento rámec je algoritmus či kód, který poskytuje jednotné řešení základních operací se kterými BFA operuje tak, aby bylo možno je transparentně používat v paralelním a distribuovaném prostředí. Paralelní výpočetní rámec tedy vystupuje jako nosný základ všem konkrétním paralelním algoritmům pro řešení BFA a výrazně zjednodušuje jejich kód.

4.6

Algoritmy preprocessingu

Kapitola 6 popisuje algoritmy předzpracování, neboli preprocessingu, specificky vhodné pro BFA. Jedná se vesměs o poměrně jednoduché formy předzpracování, které jsou výpočetně nenáročné a byly experimentálně či formálně ověřeny jako vhodné pro BFA.

4.7

Diskuze k neurosíťovému algoritmu

Sekce 7.2. Neuronová síť Hopfieldova typu je jediným algoritmem pro řešení BFA, který je v práci obsažen a přitom není mým vlastním. Tento zajímavý algoritmus je však znám jen z prací jeho vlastních autorů, proto jsem ho podrobil analýze a uvádím k němu diskuzi ve dvou rovinách: kritický pohled zmiňující slabá místa algoritmu, která jeho autoři sami (pochopitelně) příliš nezmiňují a návrhy na úpravu algoritmu za účelem odstranění těchto nedostatků.

4.8

Algoritmus Blind Search

Algoritmus Blind Search („slepé hledáníÿ popsaný v kapitole 8 je nový samostatný algoritmus pro řešení BFA. I když jde o velmi jednoduchý algoritmus, je na něm ukázána celá řada důležitých vlastností procesu BFA a tyto poznámky jsou často používány v dalších sofistikovanějších algoritmech, včetně algoritmů paralelních.

4.9

Algoritmus FCBFA

Algoritmus FCBFA popsaný v kapitole 9 je odvozený od algoritmu Blind Search a používá navíc formální koncepty (z formální konceptuální analýzy – FCA). Tento 13

algoritmus je založen na vlastním teorému popisujícím vztah mezi FCA a BFA.

4.10

Aplikace genetických algoritmů na BFA

Kapitola 10 a zvláště pak sekce 10.3 popisuje dva genetické algoritmy použitelné pro řešení BFA. Druhý z nich, označovaný jako GABFA, se dokonce jeví jako vůbec nejlepší algoritmus pro BFA, alespoň provedené testy to takto jednoznačně ukazují.

4.11

Paralelní a distribuovaný výpočet

Jak již bylo naznačeno, všechny hlavní faktorizační algoritmy uvedené v disertační práci podporují paralelní a/nebo distribuovaný výpočet. Toto je zvlášť diskutováno v sekcích 10.4 a 10.5. Přínos paralelních a distribuovaných výpočetních algoritmů, zvláště pak na úloze s vysokou výpočetní složitostí jako je BFA, je v dnešní době rozmachu vícejádrových procesorů velmi patrný.

4.12

Algoritmus pseudo–dělení binárních matic (BMPD)

Pojem pseudo–dělení binárních matic je definován hned v úvodu práce v sekci definic, ale z formální definice přímo nevyplývá žádný algoritmus řešení. Kapitola 11 popisuje algoritmus, který jsem navrhl a ačkoliv pseudo–dělení samo o sobě nemůže BFA vyřešit, jedná se o klíčový prvek v mnoha algoritmech. Zároveň se jedná o nejpomalejší bod výpočtu BFA, takže zrychlení této operace má přímý vliv na rychlost celé faktorizace a to často tak velký, že výpočetní náročnost ostatních operací je někdy až zanedbatelná.

4.13

Binární pseudo–gradientní optimalizace (BPGD)

Kapitola 12. Algoritmus BPGD, čili binární pseudo–gradientní optimalizace, představuje jediný algoritmus postprocessingu, tedy dodatečného zpracování, v práci uvedený. Tento algoritmus je možno použít pro optimalizaci výsledku BFA spočítaného jiným algoritmem. Jak ukázaly experimenty, BPGD je velmi efektivním způsobem pro samotné řešení BFA, protože dokáže poměrně spolehlivě najít kvalitní řešení i na bázi výchozího řešení získaného náhodnou projekcí.

4.14

Podpůrné algoritmy a diskuze

Kapitola 13 popisuje a diskutuje podpůrné algoritmy, které mají doplňující charakter v BFA, ale jedná se o mé vlastní výsledky, proto jsou v práci také uvedeny. Věci popisované v této kapitole jsou diskutovány také v běžné literatuře (např. Knuth [9, 10]), ale ukázalo se, že běžná literatura se věnuje jemně odlišným otázkám a nabízí postupy, které jsou pro BFA nevhodné.

14

Sekce 13.1 diskutuje použití bitově kódovaných matic a vektorů pro binární výpočty, především z hlediska výpočetní rychlosti. Sekce 13.2 až 13.4 popisují algoritmy pro efektivní výpočet kombinačního čísla, vyjmenování všech kombinací a sestavení náhodné kombinace. Sekce 13.5 popisuje univerzální algoritmus pro stanovení počtu jedničkových bitů ve vektoru.

4.15

Všechny experimenty na vlastních algoritmech

Kapitola 14. Všechny faktorizační algoritmy jsou otestovány a vzájemně porovnány v několika experimentech. Jak se ukázalo, k tomu, abychom mohli vidět, který algoritmus opravdu je (nebo není) lepší pro BFA je nutno provést takový experiment, který má vypovídací hodnotu. V publikacích jiných autorů se často vyskytují postupy, které jsou tendenčně zaměřeny tak, aby zvýraznily deklarovanou kvalitu vlastního algoritmu tam prezentovaného, tomuto jsem se však chtěl vyhnout. Mnou prezentované testy mají několik částí, jak na uměle vytvořených, tak na reálných datech a algoritmy jsou vždy testovány vzhledem k daným datům a především bez nějakých úvodních předpokladů, které by mohly některý algoritmus neopodstatněně zvýhodnit.

4.16

Binární faktorizér BiF

Součástí práce je také program BiF představující referenční implementaci všech prezentovaných faktorizačních algoritmů, včetně preprocessingu a postprocessingu a paralelního a distribuovaného výpočtu. V tomto programu jsou zahrnuty také některé další BFA algoritmy, které nejsou příliš diskutovány v disertační práci, protože ještě nejsou ve finálním publikovatelném stavu. Také je zde algoritmus náhodných projekcí, který není pro svou jednoduchost v práci přímo diskutován, ale je používán v kapitole 14 v rámci testů BPGD.

5

Vlastní publikace

Výsledky své práce jsem odborně publikoval v 35 případech, z toho 6× před zahájením doktorského studia a 29× během tohoto studia. Jedná se o publikace na domácích a zahraničních konferencích, v odborných časopisech a kapitolu v knize. Některé publikace vznikly pouze jako vedlejší produkt mé práce na binární faktorizaci, proto je seznam rozdělen na dvě části – v první jsou nejdůležitější práce s obsahem přímo souvisejícím s mou disertační prací, ve druhé části jsou pak ty ostatní. Obě části jsou seřazeny pozpátku podle data. Za nejvýznamnější publikaci považuji článek Binary Factor Analysis with Genetic Algorithms z konference 4th IEEE International Workshop on Soft Computing as Transdisciplinary Science and Technology, který byl otištěn ve sborníku LNAI/LNCS (Springer).

15

5.1

Publikace k binární faktorizaci

1. Keprt A. Simple and Fast Computation of Binomial Coefficients. In proceedings of Wofex 2006. VŠB Technical University, Ostrava, Czech Republic, 2006, pp. 346–351, ISBN 80-248-1152-9. 2. Keprt A. Possible Interpretations of Binary Factor Analysis. In proceedings of Znalosti 2006, Hradec Králové. VŠB Technical University, Ostrava, Czech Republic, 2006, pp. 280–283, ISBN 80-248-1001-8. 3. Keprt A. Thread Local Storage. In proceedings of Objekty 2005. VŠB Technical University, Ostrava, Czech Republic, 2005, pp. 85–91, ISBN 80-2480595-2. 4. Húsek D., Řezanková H., Frolov A.A., Polyakov P., Snášel V., Keprt A. Comparison of Different Approaches to Factorization of Binary Variables. In proceedings of ITAT 2005, Račkova Dolina, Slovakia. Ed. Peter Vojtáš, Univerzita Pavla Jozefa Šafárika, Košice, Slovakia, 2005, pp. 55–64, ISBN 80-7097-609-8. 5. Keprt A. Paralelní řešení binární faktorové analýzy. In proceedings of ITAT 2005, Račkova Dolina, Slovakia. Ed. Peter Vojtáš, Univerzita Pavla Jozefa Šafárika, Košice, Slovakia, 2005, pp. 223–232, ISBN 80-7097-609-8. 6. Keprt A. Recent Advances in Binary Factor Analysis. In proceedings of Wofex 2005. VŠB Technical University, Ostrava, Czech Republic, 2005, pp. 376–381, ISBN 80-248-0866-8. 7. Keprt A., Snášel V. Binary Factor Analysis with Genetic Algorithms. In proceedings of 4th IEEE International Workshop on Soft Computing as Transdisciplinary Science and Technology – WSTST 2005, Muroran, Japan. Springer Verlag, Berlin–Heidelberg, Germany, 2005, pp. 1259–1268, ISBN 3-540-25055-7. In LNCS/LNAI series Advances in Soft Computing, ISSN 1615-3871. 8. Keprt A., Snášel V. Pseudo–dělení binárních matic a jeho aplikace. In proceedings of Znalosti 2005, Vysoké Tatry, Slovakia. Published by VŠB Technical University, Ostrava, 2005, pp. 41–50, ISBN 80-248-0755-6. 9. Keprt A., Snášel V. Genetické algoritmy pro redukci dimenze a analýzu binárních dat. In proceedings of Znalosti 2005, Vysoké Tatry, Slovakia. Published by VŠB Technická Univerzita, Ostrava, 2005, pp. 242–249, ISBN 80-248-0755-6. 10. Keprt A., Snášel V. Binární faktorová analýza genetickým algoritmem. In proceedings of ITAT 2004, Popradské Pleso, Slovakia. Ed. Peter Vojtáš, Univerzita Pavla Jozefa Šafárika, Košice, Slovakia, 2004, pp. 49–58, ISBN 80-7097-589-X. 16

11. Keprt A., Snášel V. Binary Factor Analysis with Help of Formal Concepts. In proceedings of CLA / Concept Lattices and their Applications 2004. Ed. Václav Snášel, Radim Bělohlávek, VŠB Technická Univerzita Ostrava, Czech Republic, 2004, pp. 90–101, ISBN 80-248-0597-9. 12. Keprt A. Binary Factor Analysis. In proceedings of Wofex 2004. VŠB Technical University, Ostrava, Czech Republic 2004, pp. 298–303, ISBN 80-2480596-0. 13. Keprt A. Binary Factor Analysis and Its Usage in Data Mining. In proceedings of Poster 2004. ČVUT (České vysoké učení technické), Fakulta elektrotechnická, Praha, 2004. 14. Keprt A. Using Blind Search and Formal Concepts for Binary Factor Analysis. In proceedings of Dateso 2004, Desná–Černá Říčka. Ed. Václav Snášel, Jaroslav Pokorný, Karel Richta, VŠB Technical University Ostrava, Czech Republic; CEUR WS – Deutsche Bibliothek, Aachen, Germany; 2004, pp. 120–131, ISBN 80-248-0457-3 (VŠB TUO), ISSN 1613-0073 (CEUR). 15. Húsek D., Frolov A.A., Keprt A., Řezanková H., Snášel V. O jednom neuronovém přístupu k redukci dimenze. In proceedings of Znalosti 2004, Brno. Ed. Václav Snášel, VŠB Technical University, Ostrava, 2004, pp. 327–337, ISBN 80-248-0456-5. 16. Keprt A. Binární faktorová analýza a komprese obrazu pomocí neuronových sítí. In proceedings of Wofex 2003. VŠB Technical University, Ostrava, 2003, ISBN 80-248-0106-x.

5.2

Mé ostatní publikace

1. Keprt A. Kombinace C++ a .NET – jak a proč. In proceedings of Objekty 2006, Praha. (accepted) 2. Lacko B. & Ševčík V. (eds.) Kybernetika a společnost na prahu XXI. století. Chapter XI. Vzory v návrhu her. VUT Brno, 2005, pp. 59–64, ISBN 80214-3058-3. 3. Keprt A., Fojták M. Komprese barevného obrazu vícevrstvou neuronovou sítí. In poster proceedings of Znalosti 2005, Vysoké Tatry, Slovakia. Published by VŠB Technická Univerzita, Ostrava, 2005, pp. 53–56. 4. Keprt A., Zlý M. Efektivní implementace neuronových sítí pomocí vektorových instrukcí. In poster proceedings of Znalosti 2005, Vysoké Tatry, Slovakia. Published by VŠB Technická Univerzita, Ostrava, 2005, pp. 57– 60.

17

5. Keprt A. Vzory v návrhu her. In proceedings of Tvorba softwaru 2005. Tanger s.r.o., Ostrava, 2005, pp. 61–68, ISBN 80-86840-14-X. 6. Keprt A. Digitalizace časopisu Falstaff. In proceedings of Tvorba softwaru 2005. Tanger s.r.o., Ostrava, 2005, pp. 69–75, ISBN 80-86840-14-X. 7. Keprt A. Nulovatelné typy pod lupou. In proceedings of Tvorba softwaru 2005. Tanger s.r.o., Ostrava, 2005, pp. 76–82, ISBN 80-86840-14-X. 8. Keprt A. Horké novinky v jazyce C# 2.0. (3 parts). In: ComputerWorld. Volume 15. No. 42,43,44/2004. ISSN 1210-9924. 9. Keprt A. Nové prvky jazyka Visual C# 2.0 (2005). In proceedings of Objekty 2004, Praha. Ed. David Ježek, Vojtěch Merunka, VŠB Technical University, Ostrava, 2004, pp. 15–32, ISBN 80-248-0672-X. 10. Keprt A. Vývoj a řízení projektu síťové počítačové hry. In proceedings of Objekty 2004, Praha. Ed. David Ježek, Vojtěch Merunka, VŠB Technical University, Ostrava, 2004, pp. 98–108, ISBN 80-248-0672-X. 11. Keprt A., Zlý M. Využití SIMD instrukcí pro implementaci neuronových sítí. In proceedings of ITAT 2004, Popradské Pleso, Slovakia. Ed. Peter Vojtáš, Univerzita Pavla Jozefa Šafárika, Košice, Slovakia, 2004, pp. 201– 210, ISBN 80-7097-589-X. 12. Keprt A. Jazyk C# a .NET Framework na Linuxu. In proceedings of Tvorba softwaru 2004. Tanger s.r.o., Ostrava, 2004, pp. 97–105, ISBN 80-8598896-8. 13. Keprt A. PCA a porovnávání zkompresovaných obrázků. In poster proceedings of Znalosti 2004, Brno Ed. Václav Snášel, VŠB Technical University, Ostrava, 2004, pp. 29–32. 14. Keprt A. Architektura DirectShow. In proceedings of Objekty 2003. Ed. Václav Snášel, VŠB Technical University, Ostrava, 2003, pp. 108–119, ISBN 80-248-0274-0. 15. Keprt A. Historie DirectX. In: ComputerWorld. Volume 11. No. 28/2000. ISSN 1210-9924. 16. Keprt A. Rozhraní DirectInput (2 parts). In: ComputerWorld. Volume 11. No. 27,28/2000. ISSN 1210-9924. 17. Keprt A. Jak si popovídat se svým PC – DirectSoundCapture. In: ComputerWorld. Volume 11. No. 26/2000. ISSN 1210-9924. 18. Keprt A. Dovolte, abych se představil, mé jméno je DirectX. In: ComputerWorld. Volume 11, No. 14/2000. ISSN 1210-9924. 18

19. Keprt A. DirectX. In proceedings of Objekty 1999. Ed. Vojtěch Merunka, Vladimír Sklenář, Česká Zemědělská Univerzita, Praha, 1999, pp. 215–222, ISBN 80-213-0552-5. 20. Keprt A. Textové editory pro ZX Spectrum (2 parts). In: ZX Magazín. 1994, Vol. 1994, No. 1,2/1994. ISSN 1210-4833.

19

Reference [1] Foster B.L., Seidman S.B. Overlap Structures of Ceremonial Events in Two Thai Villages. In: Thai Journal of Development Administration. Volume 24, 1984, pp. 143-–157. [2] Freeman L.C. Q-Analysis and the Structure of Friendship Networks. In: International Journal of Man–Machine Studies. Volume 12, 1980, pp. 367–378. [3] Frolov A.A., Húsek D., Muraviev I.P., Polyakov P.A. Binary Factorization in Hopfield–like Autoassociative Memory. In: Network: Computation in Neural Systems. volume 15 (2005). [4] Ganter B., Wille R. Formal Concept Analysis: Mathematical Foundations. Springer–Verlag, Berlin–Heidelberg–New York, 1999, ISBN 3-540-62771-5. [5] Húsek D., Keprt A., Řezanková H., Frolov A.A., Polyakov P., Snášel V. Comparison of Different Approaches to Factorization of Binary Variables. In proceedings of ITAT 2005, Račkova Dolina, Slovakia. Ed. Peter Vojtáš, Univerzita Pavla Jozefa Šafárika, Košice, Slovakia, 2005, pp. 55–64, ISBN 80-7097-609-8. [6] Child D. Essentials of Factor Analysis. Continuum International Publishing, 2006, ISBN 0826480004. Original edition 1970, ISBN 0039100758. [7] Keprt A. Using Blind Search and Formal Concepts for Binary Factor Analysis. In proceedings of Dateso 2004, Desná–Černá Říčka. Ed. Václav Snášel, Jaroslav Pokorný, Karel Richta, VŠB Technická Univerzita Ostrava, Czech Republic; CEUR WS – Deutsche Bibliothek, Aachen, Germany; 2004, pp. 120–131, ISBN 80-248-0457-3 (VŠB TUO), ISSN 1613-0073 (CEUR). [8] Kline P. An Easy Guide to Factor Analysis. Routledge, London–New York, 1994, 194 pp., ISBN 0-415-09489-5 (hbk) & 0-415-09490-9 (pbk). [9] Knuth D.E. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd. Addison–Wesley, 1997, ISBN 0-2018-9684-2. [10] Knuth D.E. The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions. Addison–Wesley, 2005, 160 pp. ISBN 0-2018-5394-9. [11] Mickey M.R., Mundle P., Engelman L. P8M – Boolean Factor Analysis. In: BMDP (Bio-Medical Data Processing) Manual, vol. 2. Ed. W.J.Dixon. University of California Press, Berkeley, CA (USA), 1990. [12] Mische A., Pattison P.E. Composing a Civic Arena: Publics, Projects, and Social Settings. In: Poetics. Volume 27, 2000, pp. 163-–194. 20

[13] Pattison P.E., Breiger R.L. Lattices and Dimensional Representations: Matrix Decompositions and Ordering Structures. In: Social Networks. vol.24(2002), pp. 423–444. Elsevier Science, 2002. ISSN 0378-8733. [14] Řezanková H., Húsek D., Frolov A.A. Using Standard Statistical Procedures for Boolean Factorization. In proceedings of SIS 2003, Napoli (Naples), Italy, 2003, ISBN 88-8399-053-6. [15] Řezanková H., Húsek D., Snášel V. Metody pro shlukování v případě binárních dat a jejich aplikace na textové dokumenty. In proceedings of Znalosti 2003. VŠB Technická Univerzita, Ostrava, 2003, pp. 43–52, ISBN 80-2480229-5. [16] Überla K. Faktorenanalyse, 2nd. Springer–Verlag, Berlin–Heidelberg–New York, 1971. ISBN 3-540-04368-3, 0-387-04368-3. (slovenský překlad: Alfa, Bratislava, 1974) [17] Veiel H.O. Psychopathology and Boolean Factor Analysis: a mismatch. In: Psychological Medicine. Cambridge University Press, volume 15 (1985), issue 3 (Aug), pp. 623–630, ISSN 0033-2917. [18] Weber A.C., Scharfetter C. The Syndrome Concept: History and Statistical Operationalizations. In: Psychological Medicine. Cambridge University Press, volume 14 (1984), issue 2 (May), pp. 315–339, ISSN 0033-2917. Poznámka: Seznam referencí obsahuje jen odkazy citované v tomto autoreferátu. Další citace k tématu práce jsou v disertační práci samotné.

21