Masarykova univerzita v Brně Fakulta informatiky
}w !"#$%&'()+,-./012345
Dolování v datech a bezpečnost
Vypracoval: Bc. Jan Frieser Vedoucí: RNDr. Lubomír Popelínský Ph.D. Brno, květen 2004
Prohlášení Prohlašuji, že tato práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, jež jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj. Děkuji RNDr. Lubomíru Popelínskému Ph.D., který mně umožnil realizovat diplomovou práci na velmi zajímavé téma. Můj dík mu patří i za poskytnutí dostatečné volnosti během samotné práce. Nemalou zásluhu na finální podobě práce má také Mgr. Jan Blaťák, který odhalil řadu formálních nedostatků v textu. Děkuji mu též za podněty při přípravě testů.
Shrnutí Data mining je velmi zajímavý obor informatiky, který se přes své relativní mládí, velmi rychle rozvíjí. Lze se s ním setkat při práci s databázemi, ve statistice, ale i v odvětvích, jako je umělá inteligence a podobně. V této práci nejprve zpřesníme pojem dolování v datech a podíváme se na jeho hlavní činnosti. V kapitole 3 rozšíříme činnost datového dolování zavedením distribuovaného prostředí. Ukážeme, jak modifikovat techniky získávání asociačních pravidel tak, aby je šlo využít i v distribuovaném prostředí. V následující kapitole 4 zavedeme pojem zachování soukromí při dolování v datech. Podrobně se zde budeme věnovat získávání asociačních pravidel se zachováním soukromí v distribuovaném prostředí s horizontálně dělenými daty. Kapitola 5 pak popisuje implementaci modelu uvedeném v kapitole 4 a výsledky ze systému DIODA, který představuje tuto implementaci.
Klíčová slova Data mining, distribuovaný data mining se zachováním soukromí, asociační pravidla, časté vzory
Obsah 1 Úvod
5
2 Data mining 2.1 Shlukování . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Klasifikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Časté vzory, asociační pravidla . . . . . . . . . . . . . . . . .
6 7 7 8
3 Distribuovaný data mining 11 3.1 Vertikálně dělená data . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Horizontálně dělená data . . . . . . . . . . . . . . . . . . . . . 13 4 Distribuovaný data mining se zachováním soukromí 4.1 Soukromí a jeho ochrana . . . . . . . . . . . . . . . . . 4.2 Asociační pravidla a zachování soukromí . . . . . . . . 4.3 Vertikálně dělená data . . . . . . . . . . . . . . . . . . 4.4 Horizontálně dělená data . . . . . . . . . . . . . . . . . 4.4.1 Komutativní šifrování . . . . . . . . . . . . . . 4.4.2 Bezpečné sjednocení . . . . . . . . . . . . . . . 4.4.3 Bezpečné počítání globálního supportu . . . . . 4.4.4 Omezení . . . . . . . . . . . . . . . . . . . . . . 5 Systém DIODA 5.1 Implementace . . . . . . . . 5.1.1 Použité komponenty 5.1.2 Praktický model . . 5.2 Testy . . . . . . . . . . . . . 5.3 Budoucí rozšíření a úpravy
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . . . . .
. . . . .
. . . . . . . .
. . . . .
. . . . . . . .
. . . . .
. . . . . . . .
16 16 19 19 21 22 23 24 26
. . . . .
29 29 30 31 35 39
6 Závěr
42
Literatura
43
3
Přílohy 44 A Popis datových souborů . . . . . . . . . . . . . . . . . . . . . 45 B Grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 C Manuál systému DIODA . . . . . . . . . . . . . . . . . . . . . 57
4
Kapitola 1
Úvod Zpracování dat a jejich následná interpretace je jeden z mnoha úkolů informatiky. Z dat uchovávaných ve formě nul a jedniček se však v poslední době stává i výnosný artikl – informace, které z nich lze vyčíst mohou mít pro některé subjekty vysokou hodnotu. V této práci se nebudeme zabývat právními ani etickými problémy samotného držení dat určitými subjekty. Zaměříme se na možnosti interpretace dat, zjišťování souvislostí a znalostí z dat – obecně tedy metodami nazývanými data mining. V češtině se pro data mining používá spojení dolování v datech, případně pak získávání znalostí z dat. Pro potřeby textu budeme používat jak anglického originálu, tak uvedených českých ekvivalentů. Pojmem dolování pak budeme myslet dolování v datech. V poslední době je data mining postaven před poněkud netypické úkoly vyplývající z ochrany osobních údajů. Data mining totiž umožňuje vydolovat z dat nové znalosti, které mohou mít pro některé osoby citlivý charakter. Hledání těchto znalostí se tak stává nejen problémem technickým, ale i problémem práva a etiky. S ochranou dat se potýká i data mining probíhající v distribuovaném prostředí. Zvyšuje se totiž počet případů, kdy jsou jednotlivé strany distribuovaného prostředí zainteresovány na výsledku, který jim mohou metody dolování v datech poskytnout, ale již nejsou ochotny přímo zpřístupnit svá data (obsahující obchodní tajemství, osobní údaje). I zde však data mining nabízí řešení. Také hledání asociačních pravidel může probíhat v distribuovaného prostředí, ve kterém jsou navíc kladeny požadavky na zachování soukromí. V této práci si ukážeme teoretické modely řešící zadané problémy a dále se budeme věnovat samotné implementaci a testování aplikace DIODA. Ta vychází z modelu pro zachování soukromí při získávání asociačních pravidel v distribuovaném prostředí s horizontálně dělenými daty.
5
Kapitola 2
Data mining Pokud se na data mining podíváme blíže, zjistíme, že jde o proces složený z několika kroků ([12], s. 2): 1. Sběr dat. Intuitivně zřejmá část, nejprve je nutné nashromáždit potřebná data, ze kterých chceme získat znalosti. 2. Čištění dat. Vychází z faktu, že veškerá zaznamenaná data jsou zatížena jistou chybou. Proto uložená data procházejí procesem čištění, kde se snažíme chyb zbavit – odstraňujeme tedy jakési šumy, nečistoty v datech. 3. Extrakce podstatných údajů. Pro samotné zjišťování znalostí často nepotřebujeme veškeré údaje, které data obsahují. Proto si vybereme jen atributy (nahlížíme-li na data z pohledu relačních dat), které jsou pro nás podstatné. 4. Získávání znalostí. Toto je právě fáze, která je často chápána jako celý data mining. Zde dochází k samotnému získání nových znalostí v podobě výstupních statistik, závislostí a podobně. 5. Vizualizace. Pro správné pochopení výsledků a lepší orientaci v nich následuje fáze vizualizace, která převede výsledky z předešlé fáze do čitelnější formy v podobě grafů, diagramů či schémat. 6. Vyhodnocení výsledků. Poslední fází je samotné vyhodnocení výsledků. Jedná se o jedinou fázi, kterou nelze zcela automatizovat. Výsledky totiž nemusí být vždycky správné a ani užitečné. Pro posouzení výsledků je proto vždy nutný lidský úsudek. Data mining tedy není úzce specializované odvětví. Naopak, čím dál častěji se s ním můžeme setkat například v databázových systémech, které již samy začínají ovládat některé techniky dolování v datech. K oboustranné spolupráci dochází mezi dolováním v datech a obory jako statistika nebo 6
strojové učení. Obecně proto není divu, že v době, nazývané často jako informační, nachází data mining čím dál tím častější uplatnění. Přibližme si nyní tři nejtypičtější úlohy, kterými se data mining zabývá. Jsou jimi hledání častých vzorů (případně pak asociačních pravidel), klasifikace a shlukování.
2.1
Shlukování
Vstupem pro metody zabývající se shlukováním (clustering) je obecně n-dimenzionální prostor bodů. V tomto prostoru se pak snažíme najít takové shluky bodů, které jsou v čemsi podobné, jsou si čímsi „blízkéÿ. Uvedeme si pár názorných příkladů (viz [12], s. 25). První příklad je z hluboké historie, kdy v Londýně vypukla epidemie cholery. Aniž by to tehdejší lékaři věděli, byli jedni z prvních, kdo použil (z dnešního pohledu) data mining: na mapě města si totiž značili místa, kde ošetřovali nemocné pacienty. Z ohnisek, kolem kterých se vyskytovalo nejvíce případů, se pak snažili vyčíst, proč právě na daných místech jsou lidé nejvíce postiženi, tedy co (případně kdo) je jejich společným důvodem pro onemocnění cholerou. Zjistilo se, že nejčastějším problémem je znečištěná studna, kterou daný okruh lidí používal. Druhý příklad je z dnešní doby. Pro zdokumentování vesmíru se v jednom projektu používá sedmirozměrného prostoru. Jeho body představují vzdálené body vesmíru, přičemž každý si kromě svého umístění dále nese údaje o vyzařované radiaci v dané vlnové délce. V takto definovaném prostoru se pak snažíme nalézt shluky bodů, které představují galaxie, soustavy planet a podobně. Poslední příklad nám bude nejspíš nejbližší. Na dokumenty můžeme v určitém smyslu nahlížet jako na body v prostoru vysoké dimenze, kdy prostorové umístění takového dokumentu je dané výskytem v něm obsažených jistých slov. Shluky bodů pak budou představovat podobné dokumenty např. zabývající se stejným tématem.
2.2
Klasifikace
Mezi klasifikací a shlukováním lze najít jisté podobné prvky. Shlukování mělo daný prostor bodů, u každého bodu pak byly známy jisté atributy. K těmto atributům jsme se pomocí technik shlukování snažili přidat nově vytvořený atribut, který by byl příznakem příslušnosti do konkrétního shluku. V klasifikaci již máme množinu entit, u každé známe její hodnoty atributů a navíc každá entita již má přiřazený klasifikační atribut, který zařazuje entitu do určité kategorie, třídy, shluku. Úkolem klasifikace je pak nově zadané entitě, na základě hodnot jejích ostatních atributů, „nastavitÿ klasifikační atribut – tedy zařadit novou entitu do jisté kategorie entit. 7
Jeden příklad za všechny: chceme si od banky vzít půjčku. Ta nám na základě údajů, které si o nás zjistí, buď peníze půjčí nebo ne (tedy z pohledu klasifikace – buď si nás zařadí do třídy klientů důvěryhodných nebo nesolventních).
2.3
Časté vzory, asociační pravidla
V této diplomové práci se budeme blíže věnovat právě hledání častých vzorů ([6]). Nejdříve si vysvětlíme samotný význam hledání častých vzorů na příkladu, který je nazýván market-basket problem, tedy jako problém nákupního košíku. Představme si obchod, v němž máme veliký počet nabízených položek. Tyto položky si zákazníci podle potřeby vkládají do svých nákupních košíků. Naším úkolem je zjistit, jaké množiny položek se často vyskytují v jednom košíku spolu – najít tzv. časté vzory. Formálně budeme častý vzor značit jako množinu (obecně) prvků {X1 , . . . , Xn }. Intuitivně by častým vzorem například pátečních nákupů mohla být množina {mouka, cukr, vejce}, neboť mnoho nakupujících se chystá přes víkend péci. V praxi jsou znalosti častých vzorů (konkrétně v případě nákupních košíků) použity k cílenému rozmístění zboží v obchodech, čímž se záměrně řídí průchod zákazníka mezi pulty se zbožím. Využití hledání častých vzorů však může být různé. Pokud si dosadíme za nákupní košíky dokumenty, do nichž „dávámeÿ slova, pak časté vzory mohou představovat například fráze. V tomto případě může být hledání častých vzorů velmi užitečné při činnosti internetových vyhledávačů. Základní vlastností častých vzorů je jejich stupeň, často označovaný i jako délka. Tato vlastnost popisuje počet hodnot, z nichž je vzor složen. Pokud budeme v textu psát o vzorech délky (stupně) n, myslíme tím vzory obsahující n hodnot n různých atributů. Míra, která je zavedena ve spojitosti s častými vzory je tzv. support (ve výrazech ji budeme značit sup). Pokud si představíme množinu nákupních transakcí (transakcí je myšlen obsah jednoho nákupního košíku), pak support daného častého vzoru představuje míru toho, jak mnoho nákupních košíků obsahuje daný vzor. Nejčastěji se setkáváme se supportem udávajícím konkrétní počet transakcí (např. 50 transakcí z 200 obsahuje daný častý vzor), nebo s procentuálním supportem (25 % transakcí obsahuje daný častý vzor. Vzorec pro výpočet supportu je tento: supAB =
support countAB database size
Kde support countAB představuje celkový počet transakcí, které obsahují vzor {A, B} a database size je celkový počet transakcí v databázi (velikost databáze). Při hledání častých vzorů pak nehledáme všechny časté vzory, ale jen ty s dostatečně velikým supportem – v textu pak budeme používat spo8
jení, že daný častý vzor splňuje zadaný support. Pro výpočet častých vzorů se používá algoritmus Apriori ([6]). Ten postupně hledá časté vzory délky jedna (obsahující pouze jednu položku), dvě a delší tak, jak je uvedeno na schématu algoritmu 1. Pro konstrukci několika modelů tento algoritmus využijeme, nikdy však nebudeme potřebovat jeho modifikaci. Při implementaci pak bude možno použít jakoukoli stávající realizaci algoritmu Apriori. Algoritmus 1 Apriori ([6], str. 5 elektronického dokumentu) Nechť: Lk je obecně množina častých vzorů délky k Nechť: D je množina všech transakcí Nechť: c.count je počet transakcí, které obsahují vzor c Nechť: minsup je hraniční hodnota minimálního supportu L1 obsahuje časté vzory délky 1 for k = 2; Lk−1 6= ∅; k + + do Ck = AprioriGen(Lk−1 ) /* generování kandidátských vzorů délky k */ for všechny transakce t ∈ D do Ct = subset(Ck , t) /* Kandidátské vzory obsažené v t */ for všechny kandidáty c ∈ Ct do c.count + + end for end for Lk = {c ∈ Ck |c.count ≥ minsup} end forS return k Lk Na hledání častých vzorů navazuje hledání tzv. asociačních pravidel. Ta vyjadřují vztah mezi položkami častého vzoru. Asociační pravidlo zapisujeme ve tvaru {X1 , . . . , Xn } ⇒ Y , kde X1 , . . . , Xn a Y jsou jednotlivé položky. Tento zápis pak znamená: pokud se v transakci vyskytují všechny položky X1 , . . . , Xn , pak máme vysokou šanci na výskyt i položky Y v dané transakci. Opět je zavedena míra spojená s asociačními pravidly, která je dána jako pravděpodobnost, že daná transakce obsahující položky X1 , . . . , Xn bude obsahovat i položku Y . Tato míra se označuje konfidence (zkráceně ji budeme značit conf ). I hledání asociačních pravidel budeme omezovat jen na pravidla, která splňují danou konfidenci, tedy na ta, jejichž konfidence je větší nebo rovna zadané hodnotě. Při výpočtu konfidence lze využít znalosti supportu, platí totiž následující vzorce: supAB⇒C confAB⇒C = (2.1) supAB supAB⇒C = supABC (2.2) Pro úplnost zde uveďme jak vypadají časté vzory a asociační pravidla na klasických relačních datech. V tomto případě nám jako transakce vystupují jednotlivé řádky relační tabulky. Hledání častých vzorů pak představuje 9
hledání takových hodnot atributů, jež jsou v této relační tabulce často zastoupeny. Je zde tedy silnější předpoklad, neboť se hledají časté hodnoty daných atributů, ne jen obecné množiny hodnot. Podobně pak s asociačními pravidly.
10
Kapitola 3
Distribuovaný data mining V dnešním světě všelijakých sítí má data mining poněkud ztíženou funkci: data, se kterými pracuje, jsou totiž často rozmístěna na několika místech. V našem textu se budeme soustředit na dva nejčastější případy – horizontální a vertikální rozdělení dat ([2], [4]). V případě vertikálního rozdělení dat jsou klasická relační data rozdělena mezi jednotlivá místa „po sloupcíchÿ. Z celé relační tabulky tvořící data všech stran má každá strana jen jistou množinu atributů. Uváděným učebnicovým příkladem je relační tabulka týkající se automobilu jako objektu, složeného z výrobků jistých výrobců. Každý výrobce si drží své údaje o dané části (kola, motor, skla, karoserie), které dohromady lze „pospojovatÿ do tabulky automobilů: jeden řádek pak představuje jeden automobil složený z jednotlivých komponent. Atributy automobilu jsou pak dány sjednocením atributů jednotlivých komponent. Horizontální dělení dat je také velmi časté a každý se s ním v jisté podobě určitě setkal. V tomto případě jsou relační data rozdělena do míst „po řádcíchÿ: pro získání kompletní množiny dat tak stačí vzít data jednotlivých stran a umístit je do jedné relační tabulky – všechny strany mají totiž stejné relační schéma, avšak jejich uložené transakce se týkají jiných entit. Pro lepší názornost opět uvedeme učebnicový příklad. Představme si jednotné softwarové vybavení nemocnic. Díky němu si každá nemocnice ukládá data svých pacientů, a protože je software ve všech nemocnicích stejný, lze jednoduchým přenesením dat ze všech nemocnic na jedno místo vytvořit cosi jako centrální registr. Pokud i v případě distribuovaného dolování v datech chceme používat již existující nástroje (pracující nad daty umístěnými na jednom místě), předchází samotnému procesu dolování, jak jsme si jej popsali v úvodu tohoto dokumentu, ještě navíc vybudování jakéhosi centrálního skladiště, do kterého umístíme data ze všech míst distribuovaného prostředí. Protože ovšem nejde pouze o nalezení výsledku nad danými daty, ale také o efektivitu samotného výpočtu, je často od přesouvání dat do jednoho místa upuštěno
11
– množství dat v řádech gigabytů není ani dnes zanedbatelné. Navíc, jak ukážeme později, přesouvání dat s sebou nese i jiné než technické problémy. Proto jsou častěji zaváděny protokoly, jichž se účastní jistý okruh stran a které dokáží nalézt správné výsledky, aniž by bylo nutné data zúčastněných stran přesouvat na jedno místo. Protože tato práce je zaměřena na získávání asociačních pravidel, předvedeme si zde protokoly pro jejich získávání jak v prostředí vertikálně dělených dat, tak hlavně v prostředí horizontálně dělených dat. Pro výpočet supportu a konfidence v distribuovaném prostředí budeme vycházet ze vzorců Psites i=1 support countABC (i) supAB⇒C = (3.1) P sites i=1 database size(i) Psites i=1 support countAB (i) supAB = (3.2) P sites i=1 database size(i) supAB⇒C (3.3) confAB⇒C = supAB kde distribuované prostředí tvoří sites stran, support countABC (i) představuje počet transakcí strany i, které obsahují vzor {A, B, C} a database size(i) je celkový počet transakcí strany i.
3.1
Vertikálně dělená data
Ukážeme si zde poněkud zjednodušený model počítání asociačních pravidel v prostředí s vertikálně dělenými daty. Ta budou počítána nad binárními relačními daty – tedy data budou tvořena maticí jedniček a nul. Nula na místě představující určitý atribut X znamená, že předem zvolená hodnota, která se k tomuto atributu váže, se na tomto místě nevyskytuje, jednička pak značí přítomnost této zvoleného hodnoty. Pro úplnost dodejme, že existují metody, jak z obecné relační tabulky vytvořit relační tabulku, jejímiž hodnotami budou pouze nuly a jedničky. Zformulujme si tedy výchozí situaci. Daný problém získání asociačních pravidel ukážeme na příkladu distribuovaného prostředí, které je tvořeno dvěmi stranami A a B. Samozřejmě na datech obou stran je ustanoven klíč, podle kterého jsou k sobě data strany A a strany B vázána – pro jednoduchost předpokládejme, že data obou stran jsou podle tohoto klíče uspořádána – tedy že pro každý řádek číslo i strany A platí, že příslušná data na straně B najdeme také na řádku i. Neformálně: kompletní relaci vzniklou spojením dat stran A a B přes daný klíč dostaneme jednoduše tak, že tabulky A a B opticky „připojímeÿ vedle sebe. Obecně bychom celkovou relační tabulku dostali jako výsledek relační operace join přes klíč hodnot stran A a B. Dále si ujasněme, co je známo oběma zúčastněným stranám. Jsou to: 12
• Atributy strany A: A1 , . . . , Ap , kde p je počet atributů strany A • Atributy strany B: B1 , . . . , Bq , kde q je počet atributů strany B • Celkový počet transakcí, n • Limit supportu, s Podívejme se nyní blíž, jak v tomto prostředí spočítat support daného vzoru. V dané modelové situaci mohou nastat dva případy. V prvním je vzor tvořen atributy pouze jedné ze zúčastněných stran, ve druhém tvoří vzor atributy z obou stran A i B. Pro výpočet supportu využijeme toho, že máme data upravená do podoby matice nul a jedniček. Je-li totiž vzor tvořen pouze atributy např. strany A, řekněme Aj , . . . , Ak , pak daný vzor je v transakci přítomen právě tehdy, když výsledek výrazu Aj · · · · · Ak (běžné násobení hodnot) je roven jedné. (Snadno se nahlédne, že hodnoty všech atributů tedy musí být nastaveny na hodnotu 1.) Pokud poté provedeme sumu přes všechny transakce strany A výrazů Aj · · · · · Ak , dostaneme celkový support. V případě, kdy vzor má podobu Aj , . . . , Ak , Bo , . . . , Bp , je tedy ~ = Aj · ·~· · · Ak tvořen atributy z obou stran, nejprve vytvoříme vektor X ~ = Bo · ·~· · · Bp . Vektor X ~ (resp. Y ~ ) – lépe jeho n-tá složka a vektor Y – představuje přítomnost častého vzoru Aj , . . . , Ak (resp. Bo , . . . , Bp ) na řádku n transakční tabulky strany A (resp. B). Následně pak provedeme ~ Y ~ , čímž dostaneme výsledný support vzoru již klasický skalární součin X. Aj , . . . , Ak , Bo , . . . , Bp . Případné testování odvozených asociačních pravidel na splnění konfidence lze převést na počítání supportu (podle vzorce 3.3).
3.2
Horizontálně dělená data
Model, který je použit pro běžné počítání asociačních pravidel v distribuovaném prostředí je znám a tvoří jej v základu následující lemma ([3], s. 1): Pokud má pravidlo support > s % globálně, potom alespoň na jedné straně distribuovaného výpočtu bude mít toto pravidlo „lokálníÿ support > s %. Než se pustíme do samotného popisu navrženého modelu, definujme si několik pojmů, se kterými budeme obecně pracovat a nad kterými zavedeme hledaný model. • Mějme transakční databázi DB, která je horizontálně rozdělena mezi n stran, které budeme značit S1 , . . . , Sn . Rozdělení databáze pak značíme DB1 , . . . , DBn , kde databáze DBi je umístěna na straně Si a platí: DB1 ∪ · · · ∪ DBn = DB 13
• Řekneme, že vzor X má lokální support X.supi na straně Si právě tehdy, když X.supi transakcí databáze DBi obsahuje vzor X. P • Globální support pravidla X je dán jako X.sup = ni=1 X.sup P i . Častý vzor splňuje support globálně právě tehdy, když X.sup > s∗ ni=1 |DBi |, kde s je procentuální hodnota minimálního supportu. • Množinou L(k) budeme myslet množinu častých vzorů stupně k, které splňují globální support • Množinou LLi(k) pak chápeme množinu lokálních častých vzorů, splňující lokálně daný support na strany Si . • Množinou GLi(k) definujeme jako GLi(k) = L(k) ∩ LLi(k) , tedy jako množinu častých vzorů splňující globálně daný support s tím, že daný support splňují i lokálně na straně Si . Výše uvedené lemma pak dalo za vznik modelu pojmenovaném FDM (fast distributed mining of association rules) ([5]), který určuje postup pro výpočet asociačních pravidel právě v prostředí, kterým se nyní zabýváme. Výpočet pak probíhá ve čtyřech krocích ([3], s. 3): 1. Prvním krokem je generování kandidátních vzorů. V této fázi každá ze zúčastněných stran distribuovaného výpočtu používá klasický algoritmus Apriori pro generování častých vzorů. Tedy přesněji, každá ze stran si vytvoří množinu kandidátních vzorů CGi(k) pomocí klasického algoritmu Apriori, kterému na vstup dáme množinu GLi(k−1) . Na každé straně tedy vznikne množina kandidátních častých vzorů stupně k, které jsou vygenerovány z množiny GLi(k−1) častých vzorů stupně (k − 1). Dochází tady k optimalizaci, kdy na vstupu Apriori jsou použity jen ty vzory, které splňují support globálně. Platí totiž, že z lokálních vzorů, které nesplňují globální support, již nelze vytvořit žádné vzory vyššího stupně globálně splňující support. 2. Druhým krokem je lokální prořezávání. Pro každý vygenerovaný vzor X množiny CGi(k) se spočítá jeho support X.supi v databázi DBi . Pokud X lokálně splňuje support s, je přidán do množiny LLi(k) . Zde se právě využívá uvedené lemma, kdy je jasné, že pokud vzor splňuje support globálně, bude splňovat support alespoň na jedné ze stran. 3. Ve třetím kroku vysílají všechny strany své množiny LLi(k) ostatním stranám aSkaždá ze stran následně počítá lokální support všech vzorů množiny ni=1 LLi(k) . 4. Závěrečný čtvrtý Skrok využívá toho, že je znám support všech častých vzorů množiny ni=1 LLi(k) na všech stranách. Výsledný globální support daného pravidla X spočítáme podle vzorce 3.1. Do výsledné mno14
žinyPL(k) pak umístíme jen ty vzory, jejichž X.sup splňuje X.sup > s ∗ ni=1 |DBi |. Pro testování, zda odvozená asociační pravidla splňují zadanou konfidenci, využijeme opět modelu pro zjišťování supportu.
15
Kapitola 4
Distribuovaný data mining se zachováním soukromí 4.1
Soukromí a jeho ochrana
Poslední dobou se čím dál tím častěji setkáváme s otázkami týkajícími se ochrany osobních dat. Je to logické, s rostoucí výměnou dat (nejen prostřednictvím Internetu) roste zastoupení důvěrných informací, které tato data obsahují. Důvěrnými informacemi však nemůžeme myslet pouze informace bezprostředně svázané s našimi osobami jakými jsou vyznání, zdraví, sexuální orientace a podobně. Každý den jsou zaznamenávána data, která vedou k našim osobám nepřímo – ať již to je díky používání mobilních telefonů nebo jen běžnému placení kreditními kartami. Právě takovéto „střípkyÿ informací, které se podaří nějaké třetí straně pospojovat, umožní nahlédnout do našeho soukromí více, než bychom si mohli připouštět. Touto třetí stranou však nemusí být zrovna „Velký Bratrÿ v podobě státu, v dnešní době se může dost dobře jednat o firmy nebo dokonce jednotlivce. Navíc se vždy najde někdo, kdo za tyto informace dobře zaplatí. Příkladem může být jakákoli banka: pokud se jí podaří získat zdravotní data svých (i potencionálních) zákazníků je jasné, že vážně nemocní jedinci půjčku nedostanou. Potřebu zavést mechanismy pro ochranu osobních dat si uvědomila i Evropská unie. Proto přijala evropské nařízení na ochranu dat (The European Community Directive on Data Protection, zkráceně EU Privacy Directive, [14]), které vstoupilo v platnost 25. listopadu 1998. Toto nařízení bylo již dříve přijato (tehdy patnácti) členskými státy Evropské unie, jako množina principů na ochranu soukromí a volného toku dat mezi členskými státy EU. Pro potřeby směrnice byly zformalizovány důležité pojmy: osobní data a zpracování osobních dat. Z pohledu dolování v datech je totiž důležité, že za osobní data jsou podle definice považována i ta data, která se k nějaké osobě vztahují přímo či nepřímo. Zavedení této směrnice se neobešlo bez potíží. Směrnice sama o sobě
16
totiž neumožňovala stejně volný tok informací mezi EU a USA jako mezi členskými státy EU. V Evropě je samozřejmě plno poboček amerických firem a na jakékoli datové toky takovýchto firem se vztahuje ono zmíněné nařízení EU, čímž se činnost evropských poboček značně zkomplikovala. Hrozilo i nebezpečí jakýchsi odvetných opatření ze strany USA. Nicméně vzniklá situace měla za následek, že se USA musely zamyslet nad vlastní situací ohledně ochrany osobních dat. Cílem USA se tak stalo propojení vlastních principů na ochranu osobních údajů s podobnými principy EU tak, aby byla umožněna stejná výměna dat jako mezi členskými státy EU. To se následně povedlo vytvořením kostry principů s názvem Safe Harbour ([13]), která byla přijata v červenci 2000 Evropskou unií jako dostatečný nástroj pro zajištění ochrany soukromých dat na straně USA. Díky tomuto „mostuÿ byl umožněn volný tok informací mezi EU a USA. Veškerý výše uvedený text se z části týká i této práce: v datech, nad kterými hledáme asociační pravidla, samozřejmě mohou být obsažena osobní data, navíc ještě rozmístěná v distribuovaném prostředí. Teoreticky totiž může nastat případ, kdy jemné definice toho, co jsou a co nejsou osobní údaje, se mohou lišit na každé ze stran účastnících se výpočtu v distribuovaného prostředí.
Technická řešení Pro zachování soukromí dat, která data mining zpracovává, existují dvě množiny technik: techniky založené na znečitelnění dat (v anglické literatuře označované jako data obfuscation based techniques – tedy jakési „zatemněníÿ dat) a techniky založené na separaci dat (data separation based techniques), kdy je bezpečnost zaručena znepřístupněním dat. Na pomyslné společné hranici těchto technik navíc můžeme najít tzv. techniky sumarizace (summarization), kdy jsou odhalována jen určitá data, jejichž zveřejnění neporuší soukromí – typicky se jedná o statistiky a „bezpečnéÿ dotazy nad danými daty. Data obfuscation Cílem této množiny technik je skrýt chráněnou informaci. Za tím účelem se na daná data nejčastěji aplikují některé z následujících operací ([1], s. 15): • Náhodná modifikace dat • Výměna hodnot mezi jednotlivými záznamy • Řízená modifikace dat Každá z operací má své výhody i nevýhody. Při náhodné modifikaci dat jsme postaveni před problém zpětné rekonstrukce původního rozložení
17
hodnot takto „znáhodněnéÿ veličiny. Znalost rozložení hodnot dané veličiny je důležitá např. při budování rozhodovacích stromů, což je častý základ klasifikačních metod dolování v datech. Výměnou hodnot se dosahuje ochrany soukromí jednotlivce: výměna zajišťuje, že entity neobsahují reálná data. Samozřejmě ale tato metoda odhaluje všechna soukromá data z pohledu celé skupiny, navíc v takto upravených datech již nelze hledat původní závislosti mezi jednotlivými hodnotami atributů. V posledním případě, kdy dochází k řízené modifikaci dat, jsou s velkou pravděpodobností zachovávány i závislosti mezi hodnotami. Nad takovými daty lze dělat různé statistiky závislé na mnoha veličinách (právě díky zachovávání závislostí), aniž by došlo k porušeních ochrany soukromí entit zastoupených v datech. Summarization Sumarizace zajišťuje ochranu soukromí skrytím samotných dat. K datům lze omezeně přistupovat dotazy (nejčastěji statistickými), které vracejí příslušné výsledky. V tomto případě vzniká problém určení, zda daná množina dotazů je bezpečná z pohledu prozrazení důvěrných dat. Proto se často tyto dotazy provádějí nad daty obsahující uměle vnesený šum, případně se šum vnášející chyby přidává až do výsledků dotazů. Data separation Při separaci dat jsou data známá jen důvěryhodným stranám. Nejčastěji jen vlastníci dat přistupují ke svým datům, ostatním jsou znepřístupněna. Veškeré operace nad daty provádí buď vlastník nebo důvěryhodná třetí strana. Tato diplomová práce se ve své praktické části bude věnovat právě metodě dolování v datech, která pracuje se separovanými daty – každá ze stran distribuovaného výpočtu si drží svá data, ke kterým může přistupovat jen ona sama. Pro výpočet výsledku, který bude vztažen na veškerá data všech zúčastněných stran, je ustanoven protokol mezi všemi stranami. Optimální by pro řešený problém bylo nalézt protokol, který by patřil do skupiny tzv. zero-knowledge protokolů: kromě samotného výsledku, na jehož získání by spolupracovaly všechny strany, by neposkytoval žádné jiné údaje. To je samozřejmě velmi silná podmínka, my se spíš smíříme s jakýmsi „limitním blížením seÿ k tomuto cíli. Ukážeme však, že nabízené řešení bude často postačující z pohledu zachování soukromí, případně nastíníme vylepšení, která mohou vést ještě k vyšší bezpečnosti zachování soukromí. Uvedený protokol však klade i jisté nároky na prostředí, ve kterém probíhá. Nebude-li uvedeno jinak, je požadované úrovně zachování soukromí dosaženo až při spolupráci tří a více stran (na příslušných místech bude ukázáno proč). Navíc budeme předpokládat tzv. semi-honest model protokolu.
18
V tomto modelu se jednotlivé strany protokolu drží předepsaných kroků, tedy nesnaží se jakkoli podvádět nebo narušovat běh výpočtu, ale mohou si zapamatovávat výsledky jednotlivých fází výpočtu. Naším úkolem bude, aby i v tomto modelu bylo co možná nejvíce zachováno soukromí jednotlivých stran.
4.2
Asociační pravidla a zachování soukromí
Jak již bylo řečeno dříve, jednou z hlavních úloh, kterými se data mining zabývá, je získávání asociačních pravidel. Ukázali jsme si, jak získávat asociační pravidla v distribuovaném prostředí. Nyní předvedeme, že lze upravit techniky získávání asociačních pravidel tak, aby (do jisté míry a s určitými omezeními) odpovídaly požadavkům pro zachování soukromí. Nejdříve nastíníme techniku v případě vertikálně dělených dat, později se do hloubky zaměříme na získávání asociačních pravidel (se zachováním soukromí) v horizontálně dělených datech. Právě toto téma je stěžejní pro zadanou diplomovou práci.
4.3
Vertikálně dělená data
Efektivní metody pro počítání asociačních pravidel v distribuovaném prostředí s vertikálně dělenými daty existují, jednu z nich jsem si již ukázali. Uvedli jsem si i učebnicový příklad, kdy lze takovéto metody použít. To, že rozšíření o požadavky na zachování soukromí jsou opodstatněné, můžeme ukázat právě na tomto příkladě. Jak jsme již uvedli, dodavatelé komponent pro automobil si o dané komponentě drží jisté informace, často i takové, které podléhají obchodnímu tajemství. V tom případě již dodavatelé nebudou ochotni poskytovat tato data pro jakýkoli data mining, ve kterém dochází k přesunu informací za účelem následného výpočtu. Nyní si představme situaci, ve které se ocitne výrobce automobilů a dodavatel pneumatik pro tyto automobily: neočekávaně dojde k několika stovkám poruch vyráběného automobilu s pneumatikami daného dodavatele. Situace je komplikovaná v tom, že problém se nevyskytuje s danými pneumatikami na jiných automobilech, ani s jinými pneumatikami na stejném typu automobilu. Jak výrobce automobilů, tak dodavatel pneumatik se necítí zodpovědní. Pod tlakem společnosti je však automobilka nucena překontrolovat velké množství aut, u kterých se může problém teoreticky vyskytnout. Jak dále ukážeme, existují modely, které umožňují vyhledat asociační pravidla se zachováním soukromí. V našem případě by to znamenalo automobilce a výrobci pneumatik identifikovat problém a ušetřit tak obrovskou sumu peněz. Na závěr uveďme, že podobný případ se stal automobilce Ford a jejímu dodavateli pneumatik Firestone ([15]). Začněme z výchozího modelu, který jsme uvedli pro získávání asociačních 19
pravidel v prostředí s vertikálně dělenými daty. Slabým místem uvedeného modelu z pohledu zachovávání soukromí je skalární součin. Samotný problém získávání asociačních pravidel se zachováním soukromí ve vertikálně dělených datech tak lze zúžit na problém bezpečného skalárního součinu. Řešení nabízí následující posloupnost kroků, které jednotlivé strany postupně provedou. Můžeme rovnou hovořit o protokolu ([4], s. 4). Každá ze stran vlastní n hodnot: strana A hodnoty x1 , . . . , xn , strana B hodnoty y1 , . . . , yn . Prvním krokem je vytvoření matice o n × n2 prvcích, které budou znát obě strany (v textu jde o matici prvků ai,j ). Použitím této matice a n2 náhodných čísel R1 , . . . , R n2 jedna ze stran (řekněme A) ~ = (x1 , . . . , xn ) a posílá straně „zakryjeÿ své soukromé hodnoty vektoru X 0 ~ B nově vytvořený vektor X : hx1 hx2 .. .
+ a1,1 ∗ R1 + a2,1 ∗ R1
+ a1,2 ∗ R2 + a2,2 ∗ R2
+ ··· + ···
+ a1, n2 ∗ R n2 i + a2, n2 ∗ R n2 i
hxn + an,1 ∗ R1 + an,2 ∗ R2 + · · ·
+ an, n2 ∗ R n2 i
~ 0 a svých hodnot vektoru Y ~ = (y1 , . . . , yn ) Strana B z obdrženého vektoru X ~ 0 .Y ~ , který zpět posílá straně A spolu s vektovytvoří skalární součin S = X n rem 2 hodnot: ha1,1 ∗ y1 ha1,2 ∗ y1 .. .
+ +
a2,1 ∗ y2 a2,2 ∗ y2
+ ··· + ···
ha1, n2 ∗ y1 + a2, n2 ∗ y2 + · · ·
+ +
an,1 ∗ yn i an,2 ∗ yn i
+ an, n2 ∗ yn i
A zná náhodné hodnoty, které použila v prvním kroku, a vektor n2 hodnot zaslaný stranou B. Přeskládáním Pn rovnice vedoucí k výpočtu S je schopná zjistit požadovanou hodnotu i=1 xi ∗ yi představující hledaný support. S = P n
i=1 xi ∗ yi +R1 ∗ (a1,1 ∗ y1 +R2 ∗ (a1,2 ∗ y1 .. .
+ ··· + ···
+ an,1 ∗ yn ) + an,2 ∗ yn )
+R n2 ∗ (a1, n2 ∗ y1 + a2, n2 ∗ y2 + · · ·
+ a2, n2 ∗ yn )
+ +
a2,1 ∗ y2 a2,2 ∗ y2
Bezpečnost celého protokolu je postavena na faktu, že v každé chvíli má strana více neznámých než rovností. To samo o sobě dává nekonečně mnoho možných řešení. Je nutné ovšem upozornit, že daný model má jistá omezení. Uvedeme zde již pouze výčet s neformálním vysvětlením. 20
Při použití tohoto protokolu v případě většího počtu stran může dojít k situaci, že více stran spolu bude během výpočtu spolupracovat. To může vést k tomu, že dohromady získají více rovnic než je neznámých, jejichž vyřešením se dozvědí hodnoty některé ze stran. Existují však postupy ([4], str. 5, 6), jak této spolupráci zabránit. Další problém přináší fakt, že pracujeme nad hodnotami tvořenými jen jedničkami a nulami. Při útoku hrubou silou mohou neznámé druhé strany nabývat pouze hodnot 0 nebo 1, což samo o sobě zjednodušuje útok. Jedná se především o vektor n2 hodnot, které ve druhé fázi posílá strana B straně A. Avšak i zde existuje řešení, spočívající v tom, že i strana B maskuje své hodnoty pomocí svých tajných náhodných čísel. V protokolu tak sice přibude ještě pár kroků navíc oproti původní verzi, ale zbavíme se i tohoto omezení. Posledním příkladem, kdy je ohrožena bezpečnost výpočtu je spíše skupina případů, kdy jedna ze stran protokolu „podvádíÿ – posílá upravené hodnoty. Jediný příklad za všechny – jedna ze stran pošle jako vstupní data vektor s jedničkou na jediném místě. Pak výsledek (0 nebo 1) prozradí hodnotu daného atributu dané transakce druhé strany.
4.4
Horizontálně dělená data
I v případě horizontálně dělených dat ukážeme význam zavedení požadavků na zachování soukromí. Vyjdeme z již uvedeného příkladu: záznamy z různých nemocnic. Nemocnice totiž velmi často zaznamenávají citlivá data týkající se nejen pacientů. Ze zaznamenaných dat jde totiž velmi často vyčíst i obecné praktiky dané nemocnice při léčbě. Jednoduchým příkladem je podávání léků. Pomocí technik získávání asociačních pravidel lze například zjistit, že pokud je lék XY podáván v létě, je u daných pacientů 80% šance na infekci horních cest dýchacích někdy během podzimu. Zjištění podobných pravidel může odhalit např. špatné léčebné postupy v dané nemocnici. Z toho důvodu pak nemocnice nebudou svá data poskytovat třetím stranám pro jakékoli zpracování. I zde uvedeme model, který umožňuje získání obecných informací vycházejících z dat několika stran (např. nemocnic), ale z těchto informací již nebude možné vyčíst nic o datech jednotlivých nemocnic ani to, jakých nemocnic se získané výsledky týkají. Výsledek bude aplikovatelný pouze na celou množinu zúčastněných stran. Vraťme se nyní k modelu FDM, který jsme si zavedli pro počítání asociačních pravidel v prostředí s horizontálně dělenými daty v kapitole 3.2. Podívejme se na algoritmus FDM z pohledu zachování soukromí, kdy budeme vycházet ze semi-honest modelu uvedeném v sekci popisujícím soukromí. Důležitou vlastností FDM je, že nedochází k odhalení jakékoli informace týkající se konkrétních záznamů. Toto nám ovšem nestačí, neboť naším úkolem je zajistit, aby žádná ze stran Si neprozrazovala své údaje týkající se množiny LLi(k) . Navíc pro jakýkoli častý vzor X nesmí dojít k prozrazení
21
hodnoty X.supi a v neposlední řadě ani velikost databáze DBi . Ukážeme, že zadané problémy lze vyřešit následujícími protokoly: nalezením bezpečného sjednocení častých vzorů a bezpečným nalezením globálního supportu.
4.4.1
Komutativní šifrování
Mnoho protokolů pro zajištění zachování soukromí využívá komutativní kryptografie. Protože i my použijeme jeden z takovýchto protokolů pro získání bezpečného sjednocení, budeme se chvíli komutativní kryptografií zabývat. Za komutativní šifrovací algoritmus budeme považovat takový, který splňuje následující rovnosti ([3], s. 4): • Nechť K1 , . . . , Kn ∈ K jsou vhodné šifrovací klíče, M množina možných vstupů pro zvolenou šifru využívající klíče z K. Pro libovolnou permutaci prvků i a j platí: EKi1 (. . . EKin (M ) . . . ) = EKj1 (. . . EKjn (M ) . . . ) • A dále pak ∀M1 , M2 ∈ M, M1 6= M2 a pro dané k, <
(4.1)
1 2k
P r(EKi1 (. . . EKin (M1 ) . . . ) = EKj1 (. . . EKjn (M2 ) . . . )) < ,
(4.2)
kde P r(X) značí vyčíslení pravděpodobnosti pravdivosti výrazu X. Proč vůbec zavádět komutativní šifru? Jedním z mnoha použití je možnost ověření, že dvě hodnoty jsou stejné, aniž bychom museli tyto hodnoty odhalovat. Mějme například dvě strany A a B. Strana A vlastní hodnotu iA , strana B hodnotu iB . Pro kontrolu, zda jsou dané hodnoty stejné, použijeme následující protokol: strana A zašifruje svojí hodnotu, dostane novou hodnotu EKA (iA ), kterou pošle straně B. Ta obdrženou hodnotu zašifruje svým klíčem komutativní šifry, čímž dostane hodnotu EKB (EKA (iA )). Podobně pro hodnotu iB , kde výměnou zašifrovaných hodnot dostane strana A hodnotu EKA (EKB (iB )). V tomto okamžiku lze jednoduše porovnat zašifrované hodnoty a v případě rovnosti můžeme prohlásit, že se výchozí hodnoty rovnají. Toto tvrzení vyplývá z rovnosti 4.1, rovnost 4.2 říká, že pokud byly původní hodnoty různé, s velmi vysokou pravděpodobností budou různé i zašifrované hodnoty. Nyní si uvedeme dva konkrétní případy komutativní šifry. Prvním bude upravená verze rozšířené šifry RSA ([10]), druhým pak schéma šifry Pohlig-Hellman ([9]). Komutativní RSA Šifra RSA je tvořena veřejným a soukromým klíčem, každý pak dvěmi složkami – exponentem a modulem. Šifrování hodnoty M probíhá spočítáním 22
výrazu M e (mod n), dešifrování hodnoty C pak vyhodnocením výrazu C d (mod n). (Šifra vychází z Fermatova malého teorému.) Při vhodně zvoleném modulu n splňuje RSA požadavky, které klademe na komutativní šifru. Pojďme se nyní blíže podívat na RSA šifru. Modulus n, který je stejný jak pro veřejný, tak pro soukromý klíč, má podobu n = p ∗ q, kde p, q jsou prvočísla. Exponent e (respektive d) tvoří zbylou část soukromého (veřejného) klíče, oba dohromady jsou pak vzájemně inverzní prvky modulo (p − 1) ∗ (q − 1). Tedy platí e ∗ d = 1 (mod ((p − 1) ∗ (q − 1))). Při vhodném výběru prvočísel p a q dostaneme požadované komutativní vlastnosti. Prvočísla p, q totiž musí být tzv. bezpečná (safe) ([8], s. 4): Bezpečné prvočíslo p je takové, které lze zapsat jako p = 2∗p0 +1, kde p0 je liché prvočíslo. Pohlig-Hellman Druhým příkladem komutativní šifry je šifra Pohlig-Hellman. Ta, stejně jako v případě předchozí šifry, využívá veřejného a soukromého klíče se stejným modulem n, který ovšem sám o sobě je prvočíslem. Jako exponenty (používané spolu s modulem stejně jako v případě RSA) jsou zvoleny náhodná čísla e a d taková, že e ∗ d = 1 (mod (n − 1)). Opět i tato šifra vychází z Fermatova teorému (Fermat’s little theorem), kdy lze ukázat, že M e∗d = M 1+k∗(n−1) = M (mod n) (aplikace postupného šifrování a dešifrování dá zpět původní hodnotu).
4.4.2
Bezpečné sjednocení
Již víme, jak komutativní šifru sestrojit a nyní si ukážeme, jak tuto šifru využijeme pro bezpečné sjednocení. Připomeňme, že v našem případě jde o bezpečné sjednocení častých vzorů daného stupně. Nejprve uvedeme protokol, díky němuž nebude možné zjistit, jaký klient je zdrojem daného vzoru. Uvedený protokol je popsán v algoritmu 2 ([3], s. 11). V prvním kroku každá ze stran zašifruje své časté vzory pomocí komutativní šifry. Již zašifrované vzory jsou pak poslány další straně. Následuje několik kroků, kdy strana, která obdrží na vstupu zašifrované časté vzory, které dosud nezašifrovala, tyto vzory dále zašifruje svojí šifrou a pošle dál. To celé se opakuje tak dlouho, dokud nejsou všechny vzory zašifrovány všemi stranami. Nyní můžeme využít rovnosti 4.1 dané v definici komutativní šifry. Protože stejné časté vzory se nyní budou rovnat i v zašifrované podobě, odstraněním duplicit si ušetříme množství přenášených zašifrovaných častých vzorů. Nyní opět posíláme zašifrované vzory mezi stranami tak dlouho, dokud nebudou všechny časté vzory dešifrovány všemi stranami. Na konci tohoto protokolu pak dostaneme množinu všech častých vzorů daného stupně, aniž bychom věděli, jaký častý vzor je z jaké strany.
23
Algoritmus 2 Nalezení bezpečného sjednocení častých vzorů ([2], str. 5) Nechť: R = ∅ for každou stranu i do vygeneruj LLi(k) for každý vzor X ∈ LLi(k) do zašifruj vzor X a přidej jej do množiny R end for end for/* všechny strany zašifrovaly své vzory a vložily je do R */ for každou stranu i do for každý vzor z R do if daný vzor XE ještě nebyl zašifrován na straně i then odeber vzor XE z množiny R zašifruj vzor XE klíčem strany i přidej zašifrovaný vzor XEi do množiny R end if end for end for/* všechny vzory zašifrované všemi stranami */ odstraň duplicity z R for každou stranu i do for každý vzor z R do if daný vzor XD ještě nebyl dešifrován na straně i then odeber vzor XD z množiny R dešifruj vzor XD klíčem strany i přidej dešifrovaný vzor XDi do množiny R end if end for end for/* množina R obsahuje sjednocení vzorů všech stran */ return R Přesuňme se nyní k algoritmu pro bezpečné počítání globálního supportu. Omezením a případným rozšířením obou algoritmů se budeme věnovat až v následné kapitole.
4.4.3
Bezpečné počítání globálního supportu
Nyní již dokážeme bezpečně vytvořit sjednocení lokálních častých vzorů. Abychom dokázali (opět bezpečně) spočítat globální support daného vzoru, zavedeme další protokol. Při hledání bezpečného sjednocení bylo hlavním cílem zajistit neprozrazení konkrétního vzoru konkrétní strany. V protokolu pro počítání globálního supportu půjde o neprozrazení hodnoty lokálního supportu daného vzoru. Uvedený bezpečný protokol bude vycházet z následující konstrukce:
24
n X X.sup ≥ s ∗ |DB| = s ∗ ( |DBi |) i=1 n X
X.supi
n X ≥ s∗( |DBi |)
i=1 n X
i=1
(X.supi − s ∗ |DBi |) ≥ 0
i=1
Na základě testování, zda zadaný výraz je větší než nula, pak vytvoříme protokol popsaný algoritmem 3 ([3], s. 12). V tomto protokolu jsou jednotlivé strany uspořádány do kruhu. První ze stran maskuje svou hodnotu supportu daného vzoru přidáním náhodného čísla. Vytvoří tak množinu dvojic: vzor, hodnota. Tuto množinu hodnot si v kruhu postupně předávají všechny strany, každá k hodnotě t spojené s daným vzorem X přičte navíc hodnotu X.supi −s∗di . Poslední strana v kruhu, kterou množina dvojic prochází, má dvě možnosti. Buď tuto množinu pošle zpět straně první, která na základě znalosti náhodných čísel určí, zda daný vzor splňuje globální support (pomocí testování zda je daná koncová hodnota u vzoru větší nebo rovna 0). Nebo lze ustanovit bezpečný protokol ([11]) mezi poslední a první stranou, díky kterému lze opět testovat hodnotu výrazu, zde ovšem aniž by se první strana dozvěděla konkrétní hodnotu výrazu (výsledná hodnota je označována jako excess support a v některých případech může být též považována za důvěrnou). Umíme tedy vytvořit množinu vzorů, které splňují zadaný support globálně. Naším cílem je však nalézt asociační pravidla. Ty vygenerujeme právě z nalezených globálních vzorů. Jako byl support u vzorů, hodnotou, která nás zajímá u asociačních pravidel, je jejich konfidence. Pro spočítání konfidence daného asociačního pravidla (lépe pro testování, zda dané pravidlo splňuje zadanou konfidenci) lze využít protokolu pro testování splnění supportu. Podobnou úvahou jako u supportu totiž splnění konfidence převedeme na testování hodnoty výrazu. Pn XY.supi Pi=1 ≥c n i=1 X.supi n n X X ⇒ XY.supi ≥ c ∗ ( X.supi )
{X ∪ Y }.sup ≥c ⇒ Y.sup
i=1
⇒
n X
i=1
(XY.supi − c ∗ X.supi ) ≥ 0
i=1
Podařilo se nám vytvořit veškerý aparát pro výpočet asociačních pravidel v distribuovaném prostředí se zachováním soukromí. Je ovšem na místě uvést, že předvedený model má i jistá omezení, jak dále uvedeme. 25
Algoritmus 3 Bezpečné nalezení globálního supportu ([2], str. 6) Nechť: R = ∅ Nechť: C je množina kandidátských vzorů Nechť: s je procentuální limit supportu Nechť: di je velikost databáze strany i if strana i je počáteční stranou then for každý vzor X ∈ C do vygeneruj náhodné číslo xr t = X.supi − s ∗ di + xr R = R ∪ {(X, t)} end for end if if strana i není počáteční ani koncovou stranou then for každou dvojici (X, t) ∈ R do t = X.supi − s ∗ di + t R = R − {(X, t)} ∪ {(X, t)} end for end if if strana i je koncová strana then for každou dvojici (X, t) ∈ R do t = X.supi − s ∗ di + t bezpečně spočítáme zda t − xr ≥ 0 (první strana protokolu zná xr ) if t − xr ≥ 0 then X splňuje globální support end if end for end if
4.4.4
Omezení
Omezení při spolupráci stran Vraťme se nejprve k prvnímu algoritmu – k výpočtu bezpečného sjednocení. Není totiž složité nahlédnout, že uvedený protokol nepatří do skupiny zero-knowledge protokolů: kromě výsledku totiž navíc poskytuje počet častých vzorů, které daná strana vlastní. Tento počet lze zjistit poté, co strana zašifruje své časté vzory a pošle je straně další. Ta sice nemůže zjistit, jaké časté vzory obdržela (jsou zašifrovány), ale počet samozřejmě zjistí lehce. I tento problém lze z části eliminovat pomocí úpravy uvedeného protokolu. První úpravu provedeme ještě před samotným zasláním zašifrovaných častých vzorů. Aby nedošlo k prozrazení počtu častých vzorů určité strany, dodá do své původní množiny častých vzorů každá strana ještě vzory „falešnéÿ – ty budou maskovat skutečný počet častých vzorů, které splňují lokální support. Jejich přítomnost totiž nevadí. To, že případně nesplňují 26
zadaný support, se zjistí ve fázi počítání globálního supportu. Druhým zlepšením, které povede k zastínění počtu vzorů, je přesně definované zasílání množin častých vzorů. Vytvoříme totiž jakýsi kruh, ve kterém budou vzory zasílány pouze jedním směrem. Každá strana tedy zašifruje své časté vzory spolu se vzory „klamnýmiÿ a pošle je sousedovi. Až danou množinu pravidel zašifrují všechny strany (tedy množina vzorů se bude nacházet právě hned vedle výchozí strany) dojde ke sjednocení zašifrovaných vzorů ve dvou krocích. Liché strany pošlou právě držené množiny straně 0, sudé pak straně 1. Až ty pak ze svých množin vytvoří celkové sjednocení tak, že strana 1 pošle množinu straně 0. (Formální popis algoritmu i s případnými důkazy správnosti lze nalézt [3], s. 5) O tomto protokolu pak lze dokázat, že kromě výsledku, kterým je hledané sjednocení, odhaluje nanejvýš ([3], s. 5): • Velikost průniku častých vzorů lichých stran. • Velikost průniku častých vzorů sudých stran. • Počet vzorů splňujících daný support nejméně na jedné liché a jedné sudé straně. Ani s tímto rozšířením se však úplně nezbavíme problémů. Pokud i v tomto protokolu dojde ke spolupráci dvou a více stran, je možné se dozvědět více informací, než jaké mají být odhaleny: poté, co dojde k zašifrování všech vzorů dané strany všemi ostatními stranami, lze využít toho, že stejné vzory budou zašifrovány do stejné podoby (viz 4.1). Při spolupráci stran i a i − 1 tak lze zjistit velikost průniku častých vzorů strany i a i + 1. Při spolupráci jednotlivých stran výpočtu má jistá omezení i druhý protokol pro bezpečné testování vzoru na splnění supportu. Tento protokol také nepatří mezi zero-knowledge protokoly – při spolupráci stran i − 1 a i + 1 lze totiž odhalit tzv. excess support strany i, hodnotu X.supi − s ∗ di . I zde se ovšem nabízí řešení ([3], s. 7), kdy se hodnota, která by mohla být zkompromitována spoluprácí dvou stran, rozdělí na n částí a rozešle n − 1 stranám. Pro odhalení takovéto hodnoty již pak nestačí spolupráce pouze dvou stran, ale rovnou všech zbylých n − 1 stran. Omezení při dvoustranném výpočtu V případě, kdy se výpočtu zúčastní pouze dvě strany, vyvstanou před námi nové problémy. Z výsledků totiž jedna či druhá strana může vyčíst víc, než v případě, kdy je ve výpočtu zapojeno tři a více stran. Splňuje-li jisté pravidlo globálně support a jedna ze stran ví (ze svých dat), že u ní toto pravidlo splněno není, pak je zřejmé, že druhá strana musí toto pravidlo splňovat (viz lemma pro počítání častých vzorů splňujících zadaný support v distribuovaném prostředí). Problém ovšem vyvstává i v protokolu 2. Obě strany totiž znají kandidátské vzory – tedy množinu danou jako sjednocení vzorů, 27
které splňují lokálně support alespoň na jedné ze zúčastněných stran. Díky této znalosti a spolu se znalostí výsledné množiny vzorů splňující support globálně si každá ze stran může rekonstruovat podmnožinu vzorů splněných druhou stranou. Proto jedinou možností v tomto případě je vyhnout se jakémukoli lokálnímu prořezávání a do sjednocení zahrnout veškeré kandidátské vzory, které byly danou stranou vygenerovány. Při zjišťování splnění supportu daného vzoru (protokol 3) je navíc nezbytné ustanovit bezpečný protokol pro testování zda t − xr ≥ 0, jinak dojde k prozrazení excess supportu jedné ze stran. Z výše uvedeného ovšem vyplývá, že i v případě, kdy se výpočtu zúčastní obecně n stran a n − 1 stran mezi sebou spolupracuje mimo uvedené protokoly, je možné se dozvědět opět „něco vícÿ o datech konkrétní strany. V nejhorším případě nemusí n−1 stran generovat žádný vstup do uvedených protokolů, čímž se veškeré výsledky budou vztahovat pouze na data jediné strany.
28
Kapitola 5
Systém DIODA V předchozích kapitolách byl popsán a vysvětlen potřebný teoretický základ pro samotnou implementaci celého modelu. Postupně vybudujeme aplikaci, která bude z větší části vycházet právě z uvedeného modelu, na některých místech si jej však poněkud zjednodušíme – i tak bude výsledná aplikace splňovat požadavky na zachování soukromí zúčastněných stran. Název systému – DIODA – vznikl vybráním vhodných písmen ze spojení Distributed mIning in hOrizontally partitioneD dAta. Implementacemi bezpečných algoritmů pro hledání častých vzorů v distribuovaném prostředí se v současnosti (duben 2004) zabývá jen pár výzkumných týmů. Bezpečně víme o dvou skupinách: The Cornell Database Group1 z Cornell University a Data Mining Research Lab2 z Ohio State University. Výzkumu se v obou případech účastní větší počet řešitelů. Kolegové z Ohio State University předložili v roce 2003 práci ([7]) na stejné téma jakým se zabývá tato diplomová práce, jejich model je však od námi používaného odlišný. Při výpočtu častých vzorů používají pouze jediného (závěrečného) prořezávání a v jejich modelu není použita komutativní kryptografie (při výpočtu bezpečného sjednocení používají obdobu centrálního skladiště).
5.1
Implementace
Pokud se na uvedený model podíváme z pohledu vývojáře, zjistíme, že hlavními body, které je nutné vyřešit ještě před samotnou implementací, jsou: • Zajištění výpočtu častých vzorů a asociačních pravidel. • Zajištění řízení distribuovaného výpočtu. • Zajištění komutativní šifry pro potřeby bezpečného sjednocení. 1 2
http://www.cs.cornell.edu/database/, duben 2004 http://dmrl.cis.ohio-state.edu/, duben 2004
29
Každý z těchto bodů představuje téma, které si samo zaslouží prostor rozsahu tohoto textu. Pro naše potřeby by tedy bylo značně neefektivní vytvářet veškeré zázemí „na zelené louceÿ, budeme se snažit maximálně využít již existujících a funkčních řešení, čímž navíc ukážeme univerzálnost teoretického modelu.
5.1.1
Použité komponenty
Výpočet vzorů a asoc. pravidel – WEKA Jako nástroj počítající časté vzory (a následně asociační pravidla) jsme si vybrali systém WEKA3 . Jedná se o open source software obsahující vlastní implementace několika nástrojů pro data mining. Co je pro nás důležité, obsahuje i implementaci algoritmu Apriori pro hledání častých vzorů. Projekt WEKA je vyvíjen v programovacím jazyce Java. Důvodů, proč použít právě systém WEKA, bylo hned několik: • GNU licence systému WEKA nám umožňuje upravit si její části podle našich specifických požadavků. • WEKA je neustále rozšiřována a upravována, dochází k odstraňování chyb a nepřesností. (V systému DIODA jsou použity komponenty ze systému WEKA 3.4.) • WEKA umožňuje běh svých nástrojů i v příkazovém řádku. Systém DIODA bude ze systému WEKA využívat pouze implementaci algoritmu Apriori. Je však nutné upozornit, že nelze využít tuto implementaci přímo, díky distribuovanému prostředí je nutné kompletně přepracovat strukturu výpočtu častých vzorů. Oproti klasickému případu, kdy výpočet neprobíhá v distribuovaném prostředí, v našem případě dochází opakovaně nejprve k jakémusi pozastavení výpočtu, následnému upravení vnitřních struktur pro potřeby výpočtu (bezpečné sjednocení kandidátských vzorů a výpočet globálních častých vzorů) a poté opětovnému spuštění výpočtu z bodu předešlého zastavení (viz kapitola 3.2). Řízení distribuovaného výpočtu Pro potřeby řízení distribuovaného výpočtu nám bude stačit jednoduchý interface, zajišťující zasílání zpráv mezi jednotlivými zúčastněnými stranami. Volbou systému WEKA, jako jedné z komponent systému DIODA, byl určen programovací jazyk – Java. Pro tento programovací jazyk samozřejmě existuje spousta velmi sofistikovaných nástrojů pro řízení distribuovaných 3 Více o systému WEKA lze najít na webových stránkách projektu (březen 2004): http: //www.cs.waikato.ac.nz/ml/weka/ a http://sourceforge.net/projects/weka/
30
výpočtů, pro naše potřeby si však zvolíme velmi jednoduchý interface s názvem OmniSockets4 . Bohužel se jedná o projekt, jehož vývoj byl zastaven v jeho rané fázi, jedinou dostupnou verzí je proto beta verze 1.0. Protože se ovšem také jedná o open source projekt s GNU licencí, několika drobnými zásahy lze OmniSockets upravit i pro potřeby systému DIODA. Komutativní šifra Kryptografickým základem systému DIODA je komutativní šifra. To, že systém DIODA umožní řešit zadanou úlohu bezpečně a se zachováním soukromí, je docíleno hlavně díky komutativní šifře. V teoretické části jsme si ukázali dva příklady takovýchto šifer: modifikovanou verzi rozšířené RSA a šifru Pohlig-Hellman. Opět využijeme toho, že existují volně dostupné implementace – v našem případě šifry RSA – a následnou úpravou si vytvoříme hledanou komutativní verzi RSA. V systému DIODA je zakomponována upravená implementace šifry RSA firmy Cryptix5 . Tato firma poskytuje svoje implementace šifer pod licencí Cryptix General Licence, která po dodržení jistých podmínek umožňuje jejich použití a případnou modifikaci. Víme, že komutativních vlastností RSA lze dosáhnout volbou tzv. bezpečných prvočísel p a q při vytváření modulu n. Problémem je konstrukce takovýchto prvočísel. Intuitivním řešením je generovat prvočísla a zjišťovat, zda náhodou nejsou bezpečná. To ale přináší netriviální časovou náročnost jak při samotném generování prvočísel, tak posléze při testování na prvočíselnost čísel (p−1) a (q−1) 2 2 . Lze však použít jistou optimalizaci ([8], s. 4): při generování klíčů této komutativní šifry totiž využijeme vlastnosti, že čísla (q−1) p, q, (p−1) musí být prvočísla kongruentní s číslem 5 modulo 6. Lze uká2 , 2 zat, že při generování takovýchto prvočísel hrubou silou, kdy testujeme, zda je vygenerované prvočíslo p0 kongruentní s 5 modulo 6 a navíc číslo 2p0 + 1 je prvočíslo, bude přibližně jedno z (ln p0 )2 číslo s požadovanými vlastnostmi.
5.1.2
Praktický model
Jak již bylo řečeno v úvodu této kapitoly, v systému DIODA provedeme několik změn oproti původnímu modelu. Tyto změny budou zavedeny pouze pro potřeby našeho experimentálního systému DIODA – nejsou nezbytně nutné pro případné další implementace. Bez nich by se ovšem realizace stala řádově složitější. Modifikace teoretického modelu Nejpodstatnější úpravou je vnesení nového prvku do celého systému – řídícího serveru. V systému DIODA tak figurují dva základní prvky: server, 4
Domovská stránka projektu OmniSockets (březen 2004): http://sourceforge.net/ projects/omnisockets/ 5 http://cryptix.org, srpen 2003
31
který bude pro daný výpočet vždy jen jeden, a množina klientů, kteří představují jednotlivé strany výpočtu původního teoretického modelu. Server sám o sobě neprovádí žádné výpočty nad daty ani neshromažďuje data klientů – po této stránce je naprosto bezpečným článkem systému a jeho zavedením nedochází k žádnému porušování soukromí jednotlivých klientů. Přidání serveru má pouze praktické důvody: prvním je nutnost vygenerovat šifrovací (a dešifrovací) klíče zúčastněným stranám, server zde tedy vystupuje jako autorita, které všechny strany důvěřují. Druhým úkolem serveru je synchronizovat distribuovaný výpočet. Začátek každého výpočtu je tak inicializován serverem až tehdy, pokud to umožňuje stav klientů. Druhá úprava z části souvisí s použitou implementací algoritmu Apriori. WEKA při výpočtu častých vzorů ve svých interních strukturách nepočítá s konkrétními hodnotami atributů, ale s jejich číselnými reprezentacemi. Navíc tato implementace počítá pouze nad nominálními daty, kdy u každého atributu je předem známá množina přípustných hodnot. Díky tomu je umožněn efektivnější výpočet, kdy častý vzor není tvořen n-ticí textových hodnot atributů, ale daná n-tice obsahuje pouze číselné odkazy na dané textové hodnoty. Právě kvůli číselným reprezentacím častých vzorů je nutné mezi klienty vytvořit takové prostředí, aby tyto reprezentace byly „kompatibilníÿ na všech klientech. Tedy lépe, aby pro každého klienta představovala daná číselná reprezentace častého vzoru ten samý častý vzor již přeložený zpět jako n-tice (obecně) textových hodnot. Protože číselné reprezentace častých vzorů se budují v závislosti na tvaru hlavičky ARFF datového souboru (což je vstupní datový soubor pro algoritmus Apriori, kde je navíc v hlavičce uveden i popis atributů), naším úkolem bude vytvořit jednotné hlavičky ARFF datových souborů všech klientů. Tím zajistíme kompatibilitu formátu častých vzorů mezi všemi klienty. Musíme si však uvědomit, že celý systém DIODA je založen na myšlence bezpečí a zachování soukromí. Obecně totiž nemusí všichni klienti používat pro dané atributy stejných hodnot – domény jednotlivých atributů, pokud si je představíme jako množiny, nemusí být stejné. Jsme tedy postaveni před podobný problém jako při bezpečném sjednocení: strany jsou zainteresovány na výsledku (vybudovat množinu všech hodnot daného atributu vyskytující se na všech klientech), ale přitom nesmí být prozrazeno, jaké hodnoty se váží k jednotlivým klientům. Využijeme proto již existující protokol pro bezpečné sjednocení, díky kterému si všechny strany přebudují hlavičku svých datových souborů. Po provedení tohoto inicializačního kroku se již mohou všechny strany zapojit do bezpečného výpočtu globálních častých vzorů se zachováním soukromí. Úroveň bezpečí a soukromí Cílem celého systému DIODA je poskytnout výsledek, na jehož výpočtu se podílí větší počet klientů, a přitom neohrozit bezpečí a soukromí dat 32
jednotlivých klientů. V teoretické části práce jsme ukázali dvě úzká místa systému – výpočet bezpečného sjednocení a bezpečné počítání supportu jednotlivých častých vzorů. Pro oba problémy byla nabídnuta řešení, navíc tato řešení šla aplikovat na více místech: při budování jednotných hlaviček datových souborů všech klientů (za pomoci protokolu bezpečného sjednocení) a při výpočtu konfidence asociačních pravidel (modifikací protokolu počítání supportu). Za podmínky tzv. semi-honest modelu protokolu představují oba algoritmy dostatečnou míru bezpečí pro zúčastněné strany, neboť nemůže dojít k odhalení žádných konkrétních dat jakékoli strany. Ani jeden z algoritmů však nepatří do rodiny tzv. zero-knowledge protokolů – kromě samotného výsledku totiž mohou poskytovat i jakési vedlejší výsledky, týkající se ostatních zúčastněných stran. Pro potřeby výpočtu bezpečného sjednocení proto byla přidána možnost zahrnutí „klamnýchÿ vzorů do budované množiny, u bezpečného počítání supportu pak bylo možné v posledním kroku přidat speciální protokol, který by zamezil zjištění tzv. excess supportu. Na tomto místě je nutné přiznat, že systém DIODA tato rozšíření neimplementuje, protože zvýšení bezpečnosti z nich plynoucí není pro naše experimentální potřeby podstatné. Systém DIODA zachovává i bez těchto rozšíření soukromí jednotlivých stran dostatečně. Hlavním bezpečnostním prvkem proto zůstává komutativní šifra. Její síla pak závisí na délce použitého šifrovacího klíče. Jak již bylo uvedeno, v systému DIODA generuje všem klientům jejich šifrovací (a dešifrovací) klíče server. Ten totiž nejdříve musí vygenerovat bezpečná prvočísla p a q, která jsou společnou součástí veřejného a soukromého klíče všech klientů. Použití tohoto řešení je opět pouze experimentální: přestože jsou prvočísla generována s jistým stupněm optimalizace, i nadále jde o proces s použitím hrubé síly. Navíc je nutno přiznat, že klíče od serveru ke klientovi putují nezabezpečeným kanálem, což by si jiný než experimentální systém neměl dovolit. Efektivnějším řešením by rozhodně byl model, ve kterém si klíče generují jednotlivé strany samy. Nejenže zde odpadá nutnost důvěryhodné autority (v našem případě serveru), ale navíc si volbou délky generovaných klíčů každý klient ovlivňuje míru zabezpečení šifry sám. Zde by pak bylo výhodnější použít, místo námi zvolené modifikace šifry RSA, šifru Pohlig-Hellman. Pokud dokážeme na samém začátku mezi klienty ustanovit bezpečný protokol, díky kterému by se klienti dohodli na modulu n šifry Pohlig-Hellman, pak si již každý klient může svoji dvojici klíčů vygenerovat sám. Omezení praktického modelu V předchozích několika odstavcích jsme se věnovali bezpečnosti systému DIODA, vyjádřili jsme se i k bezpečnostním limitům tohoto sytému. Bohužel aplikace DIODA má i další omezení plynoucí nejen z její experimentální povahy. 33
Při implementaci algoritmu Apriori jsme vycházeli z implementace obsažené v systému WEKA, z čehož plynou následující omezení: • Uchovávání veškerých dat ve speciálních strukturách přímo v paměti. To může vést k vyčerpání operační paměti. • Vstupní data mohou obsahovat pouze nominální hodnoty6 . Navíc jsme narazili na další problémy spojené se systémem WEKA: Doposud se nepodařilo sladit výsledky systémů DIODA a WEKA na sto procent. Problém vychází z naprosto odlišných filosofií obou systémů při počítání častých vzorů. K rozdílu ve výsledcích však dochází jen zřídka a lze jej považovat za nevýznamný – při testech uvedených v tomto textu došlo k rozdílu mezi systémy jen jednou a ve výsledku se jednalo o jedno jediné pravidlo, které jeden ze systémů do výsledku zahrnul a druhý nikoli. Chyba je způsobena rozdílnými strategiemi systémů WEKA a DIODA při testování častých vzorů na splnění supportu. Druhý problém je spojený s volitelným atributem ovlivňujícím hledání častých vzorů. Hlavními parametry výpočtu jsou minimální support pro hledané časté vzory a minimální konfidence pro hledaná asociační pravidla. WEKA ovšem umožňuje specifikovat i tzv. „vyšší minimální supportÿ. Systém WEKA totiž pracuje iterativně, kdy se k zadanému minimálnímu supportu hledaných častých vzorů blíží po jednotlivých krocích z hodnoty právě tohoto vyššího minimálního supportu. Snaží se tak nejdříve najít vzory s vysokým supportem a pokud jich nenalezne dostatek, tak hodnotu vyššího minimálního supportu sníží a zkouší výpočet znovu. A to tak dlouho, dokud nenarazí na zadaný minimální support nebo nenajde potřebný počet vzorů/asociačních pravidel. Standardně je horní hranicí pro minimální support hodnota 1.0 (tedy 100 % transakcí musí obsahovat daný častý vzor), od této hodnoty se po krocích postupuje k minimálnímu supportu zadaného uživatelem. Navíc počáteční hodnota vyššího minimální supportu je použita jako maximální support, který nalezená pravidla smějí splňovat – pokud mají support vyšší, již se s nimi dál nepočítá. Zde se ovšem, podle mého názoru, přestává chovat WEKA korektně. Pokud je totiž jistý častý vzor odstraněn z výběru proto, že má support vyšší než zadanou horní hranici, pak již s ním není počítáno ani v dalších krocích, kdy jsou budovány vzory delší. Může však dojít k situaci, kdy se vzor, původně vyloučený pro překročení hranice maximálního supportu, po přidání další hodnoty k jeho původním hodnotám rázem ocitne uvnitř hranic spodního a horního supportu. Pak by ovšem měl být tento vzor zahrnut ve výsledku. Bohužel tomu tak v současné verzi systému WEKA (3.4) není. Proto je tato volba v systému DIODA napevno nastavena na hodnotu 1.0 (tedy implicitní hodnotu v systému WEKA), aniž by šla změnit. 6
Momentálně však tento problém neřeší téměř žádný systém pro hledání častých vzorů.
34
Jistý problém představuje i komunikace mezi jednotlivými stranami distribuovaného výpočtu. Po programové stránce totiž nejsou vyřešeny reakce na chyby vzniklé při přenosu zpráv. Dojde-li tak během výpočtu k přerušení spojení mezi serverem a klientem (kde je ustanoveno pevné spojení), reaguje server ukončením celého výpočtu. Dodejme však, že k této situaci během vývoje ani testování doposud nedošlo. Předpokládejme, pro potřeby této experimentální verze, bezchybné spojení jak mezi serverem a klienty, tak při komunikaci mezi klienty. Shrnutí praktického modelu I přes omezení uvedená v několika předchozích odstavcích jsme vytvořili funkční aplikaci. Veškeré nedostatky jsou navíc spojeny převážně s použitím systému WEKA, který je sám o sobě velmi rozšířeným nástrojem pro dolování v datech. Vlastnosti a chování systému DIODA jsou tak převážně dány použitými komponentami.
5.2
Testy
Systém DIODA podstoupil samozřejmě i proces testování. Testy, které zde uvedeme, proběhly nad šesti různými datovými soubory, nad každým pak byla provedena skupina samostatných testů následující struktury: • Pro každý datový soubor bylo zvoleno jednotné nastavení algoritmu Apriori. Toto nastavení pak bylo použito při všech testech nad daným datovým souborem. • Nad celým datovým souborem byl proveden výpočet častých vzorů v systému WEKA, při kterém byla kromě výsledku zaznamenána i doba výpočtu. • Datový soubor byl poměrně rozdělen na 2, 3, 4 a 6 částí. Tyto soubory pak byly použity při výpočtech v systému DIODA, kterých se ve čtyřech samostatných testech zúčastnilo postupně 2, 3, 4 a nakonec 6 stran (klientů). U každého testu byly zaznamenány jak nalezené výsledky, tak statistiky o časech a počtu zaslaných zpráv. Ke vzniklým šesti skupinám testům nám navíc přibyly ještě dvě skupiny. V obou byl použit datový soubor z první skupiny testů, nyní však nebyla data rozdělena mezi klienty rovnoměrně. V první skupině testů vlastnil vždy jeden z klientů 99 % dat z původního datového souboru, zbylá data byla rozdělena (zde již poměrně) mezi ostatní klienty. U druhé skupiny vlastnil jeden z klientů vždy jen 1 % dat, ostatní klienti si pak poměrně rozdělili zbytek.
35
Datové soubory Systém DIODA – jeho jádro hledající asociační pravidla – vychází z implementace algoritmu Apriori použitém v systému WEKA. Vstupní datové soubory proto musí být ve formátu ARFF a navíc mohou obsahovat pouze nominální hodnoty. Popis použitých datových souborů je v příloze A.
Výsledky Veškeré výsledky, které zde budou komentovány, byly dosaženy se systémem DIODA 1.00 rc 1 v prostředí počítačové sítě Fakulty informatiky v Brně. Aby došlo k minimalizaci vlivu provozu na síti a zatížení počítačů na výsledky, proběhly veškeré testy v pozdních večerních hodinách. Serverem pro všechny testy byl fakultní stroj lethe (Intel Pentium 4 2,57 MHz, 512 MB RAM), klienty tvořilo postupně až šest stojů nymfe, každý s konfigurací AMD Athlon XP 1600+ s 512 MB operační paměti. Při počítání asociačních pravidel pomocí systému WEKA byl také použit stroj lethe. Správnost výsledků První testovanou vlastností je samozřejmě správnost výsledků. Veškeré výsledky byly proto konzultovány s výstupy algoritmu Apriori ze systému WEKA 3.4. Jen zopakujme, že v předchozích verzích systému WEKA nedocházelo ke korektnímu zaokrouhlování, od verze 3.4 je tento problém vyřešený. Až na test 4 jsou veškeré výsledky ze systému DIODA identické s výsledky aplikace WEKA. Rozdíl v testu 4 je tvořen jediným pravidlem, kdy aplikace WEKA našla (správně) 133 pravidel, kdežto DIODA pouze 132. Chyba může být zapříčiněna výpočtem globálního supportu mezi klienty: support je totiž počítán mezi klienty v reálné aritmetice v několika krocích, kdy se nám při nevhodně volených numerických konverzích může projevit chyba v zaokrouhlování. V systému WEKA je sice použita také reálná aritmetika, ale pouze jednou. I přes tento nedostatek považujeme přesnost výsledků experimentálního systému DIODA za dostatečnou. Časové průběhy Podívejme se nyní na časy výpočtů naměřené během jednotlivých testů. Opět budeme systém DIODA porovnávat se systémem WEKA – je však na místě uvést, že se v této vlastnosti jedná o neporovnatelné systémy. Navíc DIODA není optimalizována na rychlost (i přes to, že se jedná o distribuovaný výpočet), ale na bezpečí a zachování soukromí. Grafy související s časovými průběhy jsou umístěny v příloze B. Věnujme se nejprve prvním šesti skupinám testů, kdy jsou data poměrně rozdělena mezi klienty. Ve všech šesti skupinách je výpočetní zatížení kli36
entů víceméně stejné (viz obrázky 1–18 přílohy B). Ovšem podobnost v časech rozhodně není dána pouze poměrným rozložením dat. Z toho důvodu jsme navíc na každém datovém souboru klienta spustili i samostatně systém WEKA. Zde nám ovšem nešlo o zjištění samotného výsledku, ale o jakousi charakteristiku dat – čas výpočtu nám může prozradit, jak „složitáÿ data daný klient vlastnil v porovnání s ostatními klienty. To, že jsou časová zatížení klientů v systému DIODA rovnoměrná (a s rostoucím počtem klientů se smazávají víceméně i nejmenší rozdíly) pak svědčí o tom, že charakter a množství dat na jednotlivých klientech nejsou jedinými vlastnostmi ovlivňující dobu výpočtu na daném klientovi. Naopak, lze vysledovat velmi malý nárůst času u jednotlivých klientů při přidání dalšího klienta i přesto, že se tím zmenší datový soubor pro každého ze zúčastněných klientů. Důvody pro tuto tendenci jsou dva. Pokud jsou totiž data dostatečně nahodilá, dojde snížením počtu transakcí k vygenerování většího počtu častých vzorů (zde předpokládáme, že strany i po snížení počtu transakcí vlastní dostatečně velký reprezentativní vzorek dat). Přidáním nového klienta se nám navíc ve fázi počítání bezpečného sjednocení rozroste budovaná množina, která postupně prochází všemi klienty. Tato množina je zpracovávána na všech klientech, a proto se jejím zvětšením prodlouží i čas jejího zpracování.
Obrázek 5.1: test 7, časové zatížení klientů v systému DIODA – klient 1 vlastní 99 % dat, zbytek je rovnoměrně rozmístěn mezi ostatní klienty
Případy, kdy data nejsou poměrně rozdělena mezi klienty, jsou poněkud zajímavější a mohou nám o vlastnostech systému prozradit více. Ve skupině testů 7 vlastnil jeden z klientů většinu dat (99 % původního datového souboru), mezi ostatní klienty byl poměrně rozmístěn zbytek. Klient vlastnící většinu dat jasně vyčnívá nad ostatní klienty co do výpočtového času (obrázek 5.1). Časový poměr mezi klienty ale rozhodně neodpovídá rozložení dat, odpovídá spíše poměru 3:1. Je zde opět viděl rostoucí časový trend při přidání dalších klientů, jak jsme si ho popsali a zdůvodnili v předchozím odstavci.
37
Obrázek 5.2: test 8, časové zatížení klientů v systému DIODA – klient 1 vlastní 1 % dat, zbytek je rovnoměrně rozmístěn mezi ostatní klienty
Ve skupině testů 8 jsme data rozdělovali tak, že jeden z klientů vlastnil zhruba 1 % dat, zbylá data byla rovnoměrně rozdělována mezi zbylé klienty. Zde je ještě lépe vidět chování aplikace v závislosti na rozmístění dat mezi klienty: rozdíl mezi klientem vlastnícím 1 % dat a 50 % dat je zhruba dvojnásobný co do výpočetního času, přitom však již rozdíl mezi klienty s 1 % a 20 % dat nelze víceméně postřehnout (obrázek 5.2).
Obrázek 5.3: Doplnění testu 8 – jednotliví klienti mají stejná data jak v testu 8, výpočet však běží pouze na klientech číslo 1 a 2 a jejich části dat.
To, jak velikost dat ovlivňuje samotnou dobu výpočtu, dokreslí speciální test, který jsme provedli bez ohledu na výsledek. Ze skupiny testů 8 jsme zkopírovali 3 testy, kterých se zúčastnily vždy jen dvě strany – první klient vlastnil neustále datový soubor obsahující 1 % celého datového souboru, druhý klient vlastnil postupně 50 %, 33 % a 20 % celého datového souboru. (Využili jsme již přichystané soubory ze skupiny testů 8.) Tato nová skupina testů nám ukáže, jaký vliv má počet klientů při daném poměru rozmístění 38
transakcí mezi klienty na výpočetní zatížení jednotlivých klientů. Výsledky popisuje graf na obrázku 5.3. Je zajímavé, že poměry výpočetních časů zůstávají téměř zachovány (porovnáváme s klienty číslo 1 a 2 z testů, jichž se účastní 3, 4 a 5 klientů ve skupině testů 8). Zvětšení počtu klientů, které v tomto případě přináší i zvětšení celého datového souboru, ovšem znamená časový nárůst i na ostatních klientech. Tím se opět potvrdilo zjištění o navýšení časového zatížení všech klientů při přidání nového klienta.
Komunikační složitost Během testů jsme zaznamenávali i počty zpráv, které byly zaslány během výpočtů. U každého testu tak lze vypozorovat, že každý klient zpracuje víceméně stejný počet zpráv, který nezávisí na množství klientů zapojených do výpočtu. Počet zpráv na klienta je daný zpracovávanými daty a nastavením algoritmu Apriori – tedy je odvozen od nalezeného výsledku. Pokud se zamyslíme nad protokoly tvořící celý výpočet, bude nám hned jasné, proč tomu tak je: všechny protokoly mají stejnou filosofii, kdy určitá zpráva prochází postupně všemi klienty v jakémsi uzavřeném kruhu. Tento kruh je navíc budován nahodile, takže v optimálním případě by se v roli vstupního bodu kruhu (který je navíc i výstupní, a proto tento klient zpracovává o jednu zprávu víc než ostatní) měli vystřídat postupně všichni klienti. Pokud se tak opravdu stane, pak budou všichni klienti zpracovávat stejný počet zpráv. Z tohoto modelu protokolů vyplývá samozřejmě i to, že přidáním nového klienta zůstane počet zpráv zpracovávaných každým klientem stejný – dojde jen k prodloužení cesty při průchodu všemi klienty. Přidání nového klienta tak znamená konstantní navýšení celkového počtu zpráv, neboť i komunikace klienta se serverem představuje pro daný výpočet konstantní počet zpráv.
5.3
Budoucí rozšíření a úpravy
Aplikaci DIODA je nutné považovat za experimentální systém. Nejslabším místem je použití implementace Apriori ze systému WEKA. Filosofie této implementace (uložení dat v paměti apod.) znemožňuje výpočty nad skutečně obrovskými datovými soubory. Pokud přehlédneme problém s uložením dat, je však nejužším místem systému DIODA samotné generování asociačních pravidel. To probíhá tehdy, když jsou bezpečně sestrojeny množiny globálních častých vzorů. Při generování asociačních pravidel totiž nemáme žádnou optimalizaci jako při výpočtu globálních častých vzorů (zde nám „pomáhaloÿ lemma o budování množiny kandidátských častých vzorů). Je proto nejdříve vygenerována množina všech potenciálních asociačních pravidel, nad kterou je pak ustanoven bezpečný protokol (protokol 3) pro testování konfidence. Samozřejmě generování všech potenciálních asociačních
39
pravidel není efektivní – a nemyslíme teď ani tak efektivitu časovou, nýbrž prostorovou. Poměrně snadno zde totiž může dojít k nedostatku paměti pro výpočet a k následnému zhroucení systému DIODA. Problémy, na které bychom se měli soustředit z pohledu samotného výpočtu častých vzorů a asociačních pravidel, jsou tyto: • Efektivní zpracování datových souborů „libovolnéÿ velikosti. • Efektivní hledání asociačních pravidel v distribuovaném prostředí z předem známé množiny globálních častých vzorů. • Úprava bezpečných algoritmů – schopnost zpracovat „libovolnouÿ množinu vstupních dat. Druhá skupina budoucích úprav a rozšíření se bude týkat bezpečnosti. Zůstaňme u praktického modelu popsaném v této práci – v modelu s centrálním serverem a skupinou klientů. První implementační úpravou by mělo být zřízení bezpečného spojení mezi serverem a jednotlivými klienty, a to i v případě, kdy dojde k nahrazení šifry RSA šifrou Pohlig-Hellman a své klíče si budou generovat klienti sami. Tímto zminimalizujeme nejen případné bezpečnostní úniky spojené zavedením serveru – pro klienty se tím zminimalizuje i teoretická ztráta soukromí, kterou představuje samotná podstata komunikace mezi klientem a serverem při řízení výpočtu: například zjištěním času mezi zasláním signálu pro generování lokálních častých vzorů a obdržením zprávy potvrzující vygenerování lze odhadnout složitost provedeného výpočtu na daném klientovi a udělat si tak základní představu o jistém charakteru dat takto zkompromitovaného klienta. Obecně, pokud by se nám podařilo vytvořit prostředí, ve kterém by server vystupoval jako jakási důvěryhodná autorita (a přitom by neprováděl žádné výpočty nad daty ani by data neshromažďoval), pak by mohlo dojít k zajímavým rozšířením používaných protokolů. Server mohl např. hlídat podvádění mezi klienty, případně by se pokoušel zamezit nevyžádané spolupráci mezi klienty. Je však otázkou, zda by zavedení takovéto autority vůbec pro vyřešení problémů podvádění a spolupráce mezi klienty během výpočtu stačilo. K problémům bezpečnosti jsme se dostali i v úvaze, ke které nás přiměly testy prováděné systémem DIODA. Pro klienta vstupujícího do výpočtu jsou největším bezpečnostním rizikem případy, kdy se buď výpočtu účastní pouze 2 strany, nebo z toho plynoucí případ spolupráce všech ostatním klientů, čímž se opět dostáváme k dvoustrannému výpočtu. Proč by proto nemohl klient, namísto toho aby ve výpočtu figuroval jako jedna strana, rozdělit svá data na n částí a připojit do výpočtu n nezávislých klientů, o nichž by věděl, že se rozhodně nepodílejí na případné spolupráci zbylých stran výpočtu? Vraťme se nyní k výpočtu bezpečného sjednocení. I s veškerými rozšířeními (viz 4.4.4) nám hrozilo prozrazení velikosti průniku množin častých vzorů dvou stran. Pokud ovšem v našem případě umístíme oněch n klientů 40
za sebe, pak může dojít k prozrazení této hodnoty pouze u prvního klienta v řadě (kterému v kruhu protokolu předcházejí alespoň 2 „cizíÿ klienti). Volíme tedy jakési menší zlo, kdy nedojde k prozrazení hodnoty průniku všech uměle přidaných klientů (tedy původního „celéhoÿ klienta), ale v nejhorším případě pouze jednoho z nich. Také v protokolu pro bezpečné počítání supportu (lépe testování na splnění supportu) nám rozšíření nepomohla zabránit, při spolupráci všech zbylých stran, prozrazení excess supportu. Nešlo by ovšem využít náš případ s uměle vytvořenými klienty? Pokud totiž nyní využijeme rozšíření protokolu 3 ([3], s. 7), nemůže se stát, že by ze všech n zúčastněných klientů n − 1 spolupracovalo, čímž máme zajištěno neprozrazení excess supportu jednotP livých klientů. Bezpečný výpočet hodnoty ni=1 (X.supi − s ∗ di ) + xr nyní probíhá následovně: 1. Pro všechny strany i, i 6= 1 polož yi = X.supi − s ∗ di , pro i = 1 pak y1 = X.sup1 − s ∗ d1 + xr 2. Všechny Pn hodnoty yi náhodně rozděl na n hodnot zi,n takových, že yi = j=1 zi,j , kde n je počet stran. 3. Každá strana i pošle hodnotu zi,j straně j. P 4. Každá strana i spočte hodnotu wi = nj=1 zj,i a pošle výsledek straně n. P P 5. Strana n spočítá hodnotu ni=1 wi = ni=1 (X.supi − s ∗ di ) + xr . Následuje pak již použitý bezpečný algoritmus mezi stranou n (vlastP nící ni=1 (X.supi − s ∗ di ) + xr ) a stranou 1 (která zná hodnotu xr ), který otestuje, zda daný častý vzor splňuje zadaný support.
41
Kapitola 6
Závěr Systém DIODA, který vznikl jako výsledek této diplomové práce, je funkční implementací teoretického modelu pro hledání asociačních pravidel v distribuovaném prostředí se zachováním soukromí, tak jak jej popsali ve svých pracích Chris Clifton a Murat Kantarcioglu. Jedná se o natolik efektivní implementaci, že ji lze využívat podobně, jako již rozšířený a zavedený systém WEKA – nyní ovšem v distribuovaném prostředí se zachováním soukromí. Navíc se nám s největší pravděpodobností podařilo vytvořit první volně šiřitelný systém tohoto druhu a DIODA rozhodně patří mezi jednu z prvních implementací systému pro bezpečné dolování asociačních pravidel obecně. Přínos této práce je proto nemalý. Nejenže implementace potvrdila správnost a efektivnost teoretických úvah, ale zároveň odkryla řadu ryze praktických problémů pro další výzkum: efektivní metody hledání asociačních pravidel v distribuovaném prostředí z předem dané množiny častých vzorů, efektivní předávání hodnot mezi klienty v distribuovaném prostředí, bezpečnostní rozšíření spojená se zachováním soukromí jednotlivých klientů.
42
Literatura [1] Clifton C. Privacy, Security, and Data Mining - How do we mine data when we can’t even look at it. ECML/PKDD’2002, 2002, http: //citeseer.ist.psu.edu/561264.html (únor 2004) [2] Kantarcioglu, M., Clifton, C. Privacy Preserving Data Mining of Association Rules on Horizontally Partitioned Data. Workshop on Research Issues in Data Mining and Knowledge Discovery, 2002, http: //citeseer.ist.psu.edu/509234.html (únor 2004) [3] Kantarcioglu, M., Clifton, C. Privacy Preserving Data Mining of Association Rules on Horizontally Partitioned Data. Odesláno IEEE pro případnou publikaci, 2003, http://www.cs.purdue.edu/homes/ clifton/document/Kantarcioglu.pdf (únor 2004) [4] Vaidya, J., Clifton, C. Privacy Preserving Association Rule Mining in Vertically Partitioned Data. The Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002, http: //citeseer.ist.psu.edu/508863.html (únor 2004) [5] Cheung, D. W.-L., Han, J., Ng, V., Fu, A. W.-C., Fu, Y. A fast distributed algorithm for mining association rules. Proceedings of the 1996 International Conference on Parallel and Distributed Information Systems (PDIS’96), IEEE, Dec. 1996, str. 31–42, 1996 [6] Agrawal, R., Srikant, R. Fast Algorithms for Mining Association Rules. Proc. 20th Int. Conf. Very Large Data Bases, VLDB, 12–15, str. 487–499, 1994, http://citeseer.ist.psu.edu/agrawal94fast.html (únor 2004) [7] Veloso, A. , Meira, W., Parthasarathy, S., de Carvalho, M. B. Efficient, Accurate and Privacy-Preserving Data Mining for Frequent Itemsets in Distributed Databases. Proceedings of the Brazilian Symposium on Databases, 2003 [8] Benaloh, J. C., de Mare, M. One-Way Accumulators: A Decentralized Alternative To Digital Signatures. Lecture Notes in Computer Science,
43
765, str. 274–??, 1994, http://citeseer.ist.psu.edu/304083.html (únor 2004) [9] Pohlig, S. C., Hellman, M. E. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Trans. Inform. Theory, svazek IT-24, str. 106-110, 1978. [10] Rivest, R. L., Shamir, A., Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, str. 21-22, 1978. [11] Yao, A. C. How to generate and exchange secrets. 27th IEEE Symposium on Foundations of Computer Science, IEEE, str. 162-167, 1986. [12] Ullman, J. D. Data Mining Lecture Notes. Computer Science Department, Stanford University, http://www-db.stanford.edu/~ullman/ mining/allnotes.pdf (únor 2004) [13] U.S. Department of Commerce. Safe Harbor Overview, http://www. export.gov/safeharbor/ (únor 2004) [14] Olender, K. D. European Union Privacy Directive: A Primer. LEGA Media, http://www.legamedia.net/legapractice/ (únor 2004) [15] National Highway Traffic Safety Administration. Firestone tire recall, http://www.nhtsa.dot.gov/hot/Firestone/ (únor 2004)
44
Příloha A Popis datových souborů Význam přepínačů pro algoritmus Apriori: N – maximální počet hledaných pravidel, C – minimální konfidence hledaných pravidel, M – minimální support hledaných častých vzorů, I – výpis nalezených častých vzorů. Skupina testů 1 Datový soubor King and rook 1 , 28056 transakcí, 7 atributů. Závěr šachové hry bílý král – bílá věž – černý král. Nastavení pro Apriori: -N 9999 -C 0.3 -M 0.05 -I Skupina testů 2 Datový soubor Mushroom database 2 , 8124 transakcí, 23 atributů. Databáze hub – 22 atributů popisujících převážně vzhled dané houby. Navíc „klasifikačníÿ atribut o (ne)jedlosti houby. Nastavení pro Apriori: -N 9999 -C 0.9 -M 0.5 -I Skupina testů 3 Datový soubor Caravan data 3 , 5822 transakcí, 86 atributů. Data zákazníků pojišťovny – sociodemografická data. Nastavení pro Apriori: -N 9999 -C 1.0 -M 0.99 -I Skupina testů 4 Datový soubor Chess End-Game – KRKPA7 4 , 3196 transakcí, 37 atributů. Šachová hra bílý král, věž versus černý král, pěšec. Pěšec na A7. Bílý táhne. Nastavení pro Apriori: -N 9999 -C 1.0 -M 0.9 -I 1
http://www.hakank.org/weka/kropt.arff http://www.hakank.org/weka/MU.arff 3 http://www.hakank.org/weka/ticdata_categ.arff 4 http://www.hakank.org/weka/CH.arff 2
45
Skupina testů 5 Datový soubor sgi-mlc++ splice1 5 , 3190 transakcí, 61 atributů. Spojové můstky DNA primátů. Nastavení pro Apriori: -N 9999 -C 0.8 -M 0.2 -I Skupina testů 6 Datový soubor sgi-mlc++ DNA-nominal 6 , 3186 transakcí, 61 atributů. Spojové můstky DNA primátů. Nastavení pro Apriori: -N 9999 -C 0.7 -M 0.2 -I Skupina testů 7 a 8 Zde byl použit stejný datový soubor jako ve skupině 1. Rozdíl byl v rozdělení dat mezi jednotlivé klienty.
5 6
http://www.ics.uci.edu/~mlearn/MLRepository.html http://www.ics.uci.edu/~mlearn/MLRepository.html
46
Příloha B Grafy Ke každé skupině testů jsme vytvořili tři grafy: první zaznamenává časové průběhy výpočtů, druhý zaznamenává počty zpráv zaslaných během výpočtů. Třetí graf je tvořen výpočty v systému WEKA nad daty jednotlivých klientů systému DIODA. U časového grafu jsou zaznamenávány jak časy výpočtů jednotlivých klientů, tak celkový čas výpočtu systému DIODA. Pro porovnání je zaznamenán i čas výpočtu systému WEKA na stejném datovém souboru a se stejným nastavením. U grafu počtu zaslaných zpráv jsou uvedeny počty zpráv zaslaných každým klientem, serverem a celkový počet zpráv zaslaných během výpočtu. V grafech souvisejících se systémem DIODA jsou použity následující zkratky: kategorie w a s 1 2 3 4 5 6
popis kategorie čas výpočtu v systému WEKA čas výpočtu v systému DIODA počet zpráv zpracovaných serverem hodnoty vztažené ke klientovi na stroji nymfe10 hodnoty vztažené ke klientovi na stroji nymfe14 hodnoty vztažené ke klientovi na stroji nymfe13 hodnoty vztažené ke klientovi na stroji nymfe15 hodnoty vztažené ke klientovi na stroji nymfe16 hodnoty vztažené ke klientovi na stroji nymfe17
V grafech běhu systému WEKA jsou použity následující zkratky: kategorie w [klient] [klient]+ [klient]*
popis kategorie čas výpočtu v systému WEKA hodnota výpočtu nad daty daného klienta výpočet měl tendenci pokračovat složitost výpočtu vedla ke zhroucení systému
47
Obrázek 1: test 1 – časové zatížení klientů v systému DIODA
Obrázek 2: test 1 – počty odeslaných zpráv výpočtu v systému DIODA
Obrázek 3: test 1 – běh systému WEKA na datech klientů systému DIODA
48
Obrázek 4: test 2 – časové zatížení klientů v systému DIODA
Obrázek 5: test 2 – počty odeslaných zpráv výpočtu v systému DIODA
Obrázek 6: test 2 – běh systému WEKA na datech klientů systému DIODA
49
Obrázek 7: test 3 – časové zatížení klientů v systému DIODA
Obrázek 8: test 3 – počty odeslaných zpráv výpočtu v systému DIODA
Obrázek 9: test 3 – běh systému WEKA na datech klientů systému DIODA
50
Obrázek 10: test 4 – časové zatížení klientů v systému DIODA
Obrázek 11: test 4 – počty odeslaných zpráv výpočtu v systému DIODA
Obrázek 12: test 4 – běh systému WEKA na datech klientů systému DIODA
51
Obrázek 13: test 5 – časové zatížení klientů v systému DIODA
Obrázek 14: test 5 – počty odeslaných zpráv výpočtu v systému DIODA
Obrázek 15: test 5 – běh systému WEKA na datech klientů systému DIODA
52
Obrázek 16: test 6 – časové zatížení klientů v systému DIODA
Obrázek 17: test 6 – počty odeslaných zpráv výpočtu v systému DIODA
Obrázek 18: test 6 – běh systému WEKA na datech klientů systému DIODA
53
Obrázek 19: test 7 – časové zatížení klientů v systému DIODA
Obrázek 20: test 7 – počty odeslaných zpráv výpočtu v systému DIODA
Obrázek 21: test 7 – běh systému WEKA na datech klientů systému DIODA
54
Obrázek 22: test 8 – časové zatížení klientů v systému DIODA
Obrázek 23: test 8 – počty odeslaných zpráv výpočtu v systému DIODA
Obrázek 24: test 8 – běh systému WEKA na datech klientů systému DIODA
55
Obrázek 25: Doplnění testu 8 – jednotliví klienti mají stejná data jak v testu 8, výpočet však běží vždy na klientech číslo 1 a 2 a jejich části dat.
56
Příloha C Manuál systému DIODA Pro spouštění systému DIODA je nutné mít nainstalováno Java 2 Runtime Enviroment, nejlépe ve verzi 1.4.2 a vyšší. Zde uvedené příklady předpokládají správně nastavenou cestu pro spouštění programů v jazyce Java.
Spuštění serveru Základním příkazem pro spuštění systému DIODA v módu serveru je: java -jar dioda.jar -s Parametry ovlivňující běh serveru: přepínač argument -s -p celé číslo -k celé číslo -a soubor -IP/dom. jméno -v -h
význam Přepínač pro spuštění v režimu serveru. Číslo portu pro spojení s klienty. Velikost RSA klíčů v bitech. Soubor s přepínači pro algoritmus Apriori. IP adresa nebo doménové jméno serveru. Vypíše aktuální verzi systému DIODA. Vypíše nápovědu systému DIODA.
Spuštění klienta Základním příkazem pro spuštění systému DIODA v módu klienta je: java -jar dioda.jar -r server -f file kde server představuje IP adresu nebo doménové jméno počítače na kterém běží systém DIODA v režimu serveru, file představuje cestu k datovému souboru typu ARFF. Parametry ovlivňující běh klienta:
57
přepínač argument význam -p celé číslo Port klienta. -e celé číslo Port serveru. -r IP/dom. jméno IP adresa nebo doménové jméno serveru. -f soubor Datový soubor .ARFF. -IP/dom. jméno IP adresa nebo doménové jméno klienta. -v Vypíše aktuální verzi systému DIODA. -h Vypíše nápovědu systému DIODA.
Postup pro práci se systémem DIODA 1. Spusťte server DIODA. 2. Spusťte dva nebo více klientů a připojte je k serveru. 3. Poté, co dojde k přihlášení všech klientů k serveru, v konzoli serveru zmáčkněte „sÿ a henteri, čímž dáte povel k zahájení samotného distribuovaného výpočtu. Ten začne ihned poté, co všichni klienti obdrží své RSA klíče, které jim vygeneroval server. 4. Výpočet můžete kdykoli ukončit tak, že v konzoli klienta nebo serveru stisknete „.ÿ a henteri. Pokud server právě generuje RSA klíče, může zastavení trvat poněkud delší dobu. 5. Na konci výpočtu dojde k zobrazení výsledků (na klientech) a k výpisu statistik (na straně serveru). 6. Běh serveru a klientů zastavíte stisknutím „.ÿ a henteri.
58
