Proceedings of the 2018 eC 5th Student Computer Science Research oSR Conference C Stu University of Primorska Press StuCoSReC Preface Proceedings of the 2018 5th Student Computer Science Research Conference It is no longer necessary to emphasize that computer science is omnipresent today. Terms as digitalization, Edited by Industry 4.0 etc. are frequently heard in the mass media Iztok Fister jr. and Andrej Brodnik and are becoming a part of our everyday life. The rapid advances in computer science require a large investment Reviewers and Programme Committee in research and development. In particular, it is impor- Klemen Berkovič ■ University of Maribor, Slovenia Lucija Brezočnik tant to educate young scientists, which is one of the ■ University of Maribor, Slovenia Patricio Bulić objectives of the StuCoSReC conference. ■ University of Ljubljana, Slovenia Zoran Bosnić ■ University of Ljubljana, Slovenia In front of you is the proceedings of the fifth Stu- Borko Bošković ■ University of Maribor, Slovenia CoSReC conference. The StuCoSReC is intended for Janez Brest ■ University of Maribor, Slovenia masters & PhD students to show their research achieve- Andrej Brodnik ■ University of Primorska and University of Ljubljana, Slovenia ments. Socializing is also important and the confer- Haruna Chiroma ence is an excellent opportunity for students to get to ■ Gombe State University, Nigeria Mojca Ciglarič ■ University of Ljubljana, Slovenia know each other. The conference connects students of Jani Dugonik ■ University of Maribor, Slovenia computer science and goes beyond the invisible limits of Iztok Fister ■ University of Maribor, Slovenia faculties. The uniqueness of StuCoSReC conference is Iztok Fister Jr. ■ University of Maribor, Slovenia that it is organized each year by different higher educa- Matjaž Gams ■ Jozef Stefan Institute, Slovenia tion institution. The University of Ljubljana - Faculty Tao Gao ■ North China Electric Power University, China of Computer and Information Science is proud to host Andres Iglesias ■ Universidad de Cantabria, Spain the conference this year. Branko Kavšek ■ University of Primorska, Slovenia Miklos Kresz ■ University of Szeged, Hungary Twelve papers addressed this conference, covering sev- Niko Lukač ■ University of Maribor, Slovenia eral topics of the computer science. All the papers were Uroš Mlakar ■ University of Maribor, Slovenia reviewed by two international reviewers and accepted Marjan Mernik ■ University of Maribor, Slovenia for the oral presentation. Eneko Osaba ■ University of Deusto, Spain Vili Podgorelec ■ University of Maribor, Slovenia Peter Rogelj ■ University of Primorska, Slovenia Xin-She Yang ref. prof. dr. Nikolaj Zimic ■ Middlesex University, United Kingdom Damjan Vavpotič ■ University of Ljubljana, Slovenia Grega Vrbančič ■ University of Maribor, Slovenia Aleš Zamuda ■ University of Maribor, Slovenia Nikolaj Zimic ■ University of Ljubljana, Slovenia Borut Žalik ■ University of Maribor, Slovenia Published by University of Primorska Press Titov trg 4, si-6000 Koper Editor-in-Chief Jonatan Vinkler Managing Editor Alen Ježovnik Koper, 2018 isbn 978-961-7055-26-9 (pdf) www.hippocampus.si/isbn/978-961-7055-26-9.pdf isbn 978-961-7055-27-6 (html) www.hippocampus.si/isbn/978-961-7055-27-6/index.html DOI: https://doi.org/10.26493/978-961-7055-26-9 © University of Primorska Press Kataložni zapis o publikaciji (CIP) pripravili v Narodni in univerzitetni knjižnici v Ljubljani COBISS.SI-ID=296769024 ISBN 978-961-7055-26-9 (pdf) ISBN 978-961-7055-27-6 (html) Contents Preface II Papers Regulacija plovca v zračnem tunelu (zračna levitacija) na osnovi mehke logike ◆ Primož Bencak, Dominik Sedonja, Andrej Picej, Alen Kolman, Matjaž Bogša 5–13 Razpoznavanje literature v dokumentih in določanje njihovih sklicev v besedilu ◆ Matej Moravec, David Letonja, Jan Tovornik, Borko Boškovič 15–19 Klasifikacija samomorilskih pisem ◆ Dejan Rupnik, Denis Ekart, Gregor Kovačevič, Dejan Orter, Alen Verk, Borko Boškovič 21–25 Načrtovanje poprocesorja za pretvorbo NC/ISO G-kode v translacije za 3/5 osnega robota ACMA ABB XR701 27–33 ◆ Gregor Germadnik, Timi Karner, Klemen Berkovič, Iztok Fister Using constrained exhaustive search vs. greedy heuristic search for classification rule learning ◆ Jamolbek Mattiev, Branko Kavšek 35–38 Real-time visualization of 3D digital Earth ◆ Aljaž Jeromel 39–42 Towards an enhanced inertial sensor-based step length estimation model ◆ Melanija Vezočnik, Matjaž Branko Jurič 43–46 Breast Histopathology Image Clustering using Cuckoo Search Algorithm ◆ Krishna Gopal Dhal, Iztok Fister Jr., Arunita Das, Swarnajit Ray, Sanjoy Das 47–54 Time series classification with Bag-Of-Words approach post-quantum cryptography ◆ Domen Kavran 55–59 The problem of quantum computers in cryptography and post-quantum cryptography ◆ Dino Vlahek 61–64 Named Entity Recognition and Classification using Artificial Neural Network ◆ Luka Bašek, Borko Boškovič 65–70 Context-dependent chaining of heterogeneous data ◆ Rok Gomišček, Tomaž Curk 71 StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October III Regulacija plovca v zra čnem tunelu (zra čna levitacija) na osnovi mehke logike Primož Bencak Dominik Sedonja Andrej Picej Univerza v Mariboru Univerza v Mariboru Univerza v Mariboru Fakulteta za strojništvo Fakulteta za strojništvo Fakulteta za strojništvo Smetanova 17, Maribor Smetanova 17, Maribor Smetanova 17, Maribor primoz.bencak@ dominik.sedonja@ andrej.picej@ student.um.si student.um.si student.um.si Alen Kolman Matjaž Bogša Univerza v Mariboru Univerza v Mariboru Fakulteta za strojništvo Fakulteta za strojništvo Smetanova 17, Maribor Smetanova 17, Maribor alen.kolman@ matjaz.bogsa@ student.um.si student.um.si POVZETEK 1. UVOD Teorija mehke logike je prisotna že dobrih 40 let, razvita Zračna levitacija predstavlja mirovanje (v nadaljevanju: leb- pa je bila z namenom preprostega in intuitivnega vodenja denje) telesa v neki točki dvignjeni od tal, zaradi umetno sistemov. Mehka logika namreč posnema človeško sklepanje ustvarjene sile zračnega toka, ki je nasprotno enaka sili teže ter sprejemanje odločitev na podlagi dejstev. V preteklih telesa [3]. Lebdenje objekta (plovca) v cevi je s stališča regu- desetletjih se je uveljavila kot učinkovita in procesorsko ne- lacije zahtevnejši problem, saj gre za nelinearen dinamični zahtevna alternativa klasičnim tehnikam vodenja. Čeprav sistem drugega reda. Za vodenje takega sistema moramo se pojavljajo pomisleki o njeni uporabnosti na zahtevnejših zelo dobro nastaviti parametre PID regulatorja ali se poslu- aplikacijah, je vendarle našla svoj prostor v mnogih segmen- žiti drugačnega načina vodenja, kot je mehka logika. Sistem tih našega življenja. je bil najprej zgrajen in preizkušen v simulacijskem okolju, nato pa je bil prenešen v realno okolje in za dane razmere Mehka logika nam omogoča, da lahko sami določimo karak- optimiziran. teristiko regulatorja, napram linearnemu PID regulatorju, kjer je le-ta vedno linearna in zato v večini primerov nepri- Ideja za izdelavo sistema lebdenja izhaja iz članka [3], v ka- merna za vodenje nelinearnih sistemov, razen v omejenih ob- terem avtorji s PID regulatorjem uspešno vodijo takšen sis- močjih delovanja. V članku je tako predstavljena regulacija tem. Izrazito nelinearen sistem avtorji linearizirajo v okolici valjastega plovca znotraj zračnega tunela na osnovi mehke delovne točke, sledi identifikacija modela in nato iz dobljenih logike z dolgim mrtvim časom (angl. dead time). Opravljene formul izpeljejo prenosno funkcijo, ki je vstavljena v uporab- so bile simulacije omenjenega sistema v MATLAB/Simulink- niški vmesnik, preko katerega vodijo sistem. u, izdelano je bilo preizkuševališče za vodenje plovca ter iz- vedena primerjava med klasično tehniko vodenja in tehniko Dušan Fister pa predlaga uporabo naprednih optimizacij- vodenja z mehko logiko. Preizkuševališče je namenjeno uče- skih algoritmov po vzoru iz narave za nastavljanje parame- nju sistemov daljinskega vodenja in preizkušanju različnih trov PID regulatorja, da dosežemo najboljše razmerje med tipov regulatorjev. vzponskim časom, prenihajem in statičnim pogreškom, ter ga preizkusi na dvoosnem SCARA robotu [4]. Kjučne besede V članku je predstavljena rešitev, kjer postopka linearizacije zračna levitacija, mehka logika, mikrokrmilniki, LabVIEW in določanja parametrov PID regulatorja ni potrebno izvesti, saj ni potrebno poznati niti funkcije sistema. Uporabili smo mehki regulator, pri čemer kot vhodna podatka uporabimo le oddaljenost od točke ekvilibriuma oz. referenčne točke (točka v prostoru stanj sistema, kjer je doseženo ravnotežno stanje sistema) in odvod te razdalje, torej hitrost premikanja objekta. Mehka logika se uporablja na veliko različnih področjih kot so: aeronavtična industrija [10], avtomobilska industrija (pre- stavljanje menjalnika [5], strategija nadzora električnega vo- zila [9]), medicina (večnamenska kontrola anestezije, nadzo- rovanje arterijskega tlaka med anestezijo) [17], nadzorovanje StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.5-13 Ljubljana, Slovenia, 9 October 5 polnjenja in praznjenja baterij [12], procesiranje slik v indu- je namesto funkcije kar število). Pisanje baze pravil mehke striji [1] in še na mnogih drugih. logike za posamezen sistem ni trivialno kakor nakazuje me- toda, saj je potrebno dobro poznavanje sistema, zato pravila Struktura članka v nadaljevanju je naslednja: drugo po- pišejo strokovnjaki (angl. expert ) dotičnega področja. Stro- glavje opisuje teoretično ozadje lebdenja v zraku in mehke kovnjak mora določiti tudi vhodne in izhodne pripadnostne logike, tretje poglavje govori o simulaciji sistema v MATLAB/- funkcije. V kompleksnejših sistemih lahko število funkcij in Simulink-u, v četrtem poglavju je predstavljen postopek na- pravil preseže zmožnost človeškega uma in strokovnjak ne črtovanja fizičnega dela sistema (angl. hardware), v petem more zapisati ustreznega števila pravil [13]. poglavju je govora o programskem delu (angl. software), sledijo še rezultati in na koncu sklep s podanimi možnostmi V sisteme regulacije s pomočjo mehke logike velikokrat vstopa za izboljšavo obstoječega sistema. t.i. ostra vrednost, v obliki podatka iz senzorja (npr. tem- peratura zraka). To informacijo je potrebno mehčati (angl. 2. LEBDENJE V ZRAKU fuzzification), kar pomeni, da informacijo spremenimo v meh- Lebdenje v zraku je v osnovi preprosto opisati, saj mora ko vrednost (besedno oz. številčno). Ta postopek poteka veljati le: P F = 0. To pomeni, da je potrebno izpolniti s pomočjo pripadnostnih funkcij (funkcije, ki določajo pri- pogoj F padnost elementov iz senzorja posamezni mehki množici in g = Fz. Vendar, ko želimo za izbrani sistem na ta način izračunati vrednost F lahko zavzamejo vrednost med 0 in 1). Poznamo več vrst z , ki predstavlja silo ustvar- jeno s pomočjo pretoka zraka v cevi, naletimo na težavo, saj pripadnostnih funkcij, in sicer Z, S , π, sigmoidno, Gaussovo, moramo za optimalno vodenje poznati razne koeficiente, ki zvončasto, odsekoma linearno, trikotno in trapezoidno pri- niso konstante (težavo predstavljajo koeficient potiska – od- padnostno funkcijo. Od sistema in strokovnjaka je odvisno visen od Reynoldsovega števila; gostota zraka – odvisna od katere pripadnostne funkcije bodo uporabljene v posamezni temperature, nadmorske višine, . . . in hitrost zraka v cevi). situaciji. Mehko sklepanje se izvede na podlagi baze pra- Iz drugega Newtonovega zakona lahko zapišemo ravnotežno vil. Na ta način se vhodni podatki pretvorijo v izhodne, enačbo lebdenja v zraku (1) in nato razčlenimo posamezno ki pa so mehke vrednosti. Z mehko vrednostjo računalnik silo (2). oz. krmilnik ne more operirati, zato je mehko vrednost po- trebno ponovno ostriti (angl. defuzzification), da dobimo Enačbe: numerično vrednost, s katero lahko računalnik računa oz. na podlagi le-te proži določeno akcijo na aktuatorju. Poznamo F = Fz − Fg, (1) več metod ostrenja, in sicer metodo največje vrednosti, te- žiščno metodo in poenostavljeno težiščno metodo. V praksi 1 F = · Cd · ρ · A · (vw − z0)2 − m · g, (2) se pogosto uporablja poenostavljena težiščna metoda, ki je 2 računsko dokaj preprosta in ne zahteva prevelike procesorske moči [13]. pri čemer je Cd koeficient potiska, ρ gostota zraka, A presek objekta na katerega deluje zrak, vw hitrost zraka v cevi, z višina na kateri se nahaja objekt v cevi, m masa objekta in g težnostni pospešek. Slika 2: Shematski prikaz mehkega inferenčnega stroja. Vir [13]. Slika 1: Delovanje sil na objekt v cevi. Vir [3]. Ugotovimo lahko, da se na ta način elegantno izognemo za- 2.1 Mehka logika pletenemu matematičnemu zapisu in reševanju diferencial- Začetki mehke logike segajo v leto 1985, ko sta to metodo nih enačb zgolj z dobrim poznavanjem procesa. Kljub temu predstavila Takagi in Sugeno. Pri mehki logiki gre za manj se pojavljajo pomisleki, ki odvračajo od uporabe mehke lo- matematično zapletene zapise relacij med vhodnimi in iz- gike. Argumenti proti se nanašajo predvsem na to, da ni sis- hodnimi spremenljivkami, saj so spremenljivke lahko lingvi- tematičnega pristopa k načrtovanju tovrstnih sistemov, pri stične (podane z besedami naravnega jezika – velik, majhen, kompleksnejših sistemih lahko mehka logika postane ovira in hiter, počasen, . . . ). Operacije nad mehkimi spremenljiv- ogroža stabilnost sistema [8], ter da predstavlja manjvreden kami izvajamo z mehkimi operatorji (unija, presek in kom- inženirski pristop k vodenju [13]. plement). Sestaviti pa je potrebno tudi bazo pravil, ki je v osnovi pri mehkih sistemih zgrajena iz ”če-potem”(angl. 3. SIMULACIJA LEBDENJA V ZRAKU ”if-then”) mehkih pravil, ki opisujejo vzročno – posledično Za uspešno simulacijo modela je potrebno implementirati dogajanje v sistemu. Glede na izhodno spremenljivko lo- naslednje sestavne dele: čimo več tipov mehkih pravil, in sicer Mamdani [6] sisteme (vhodi in izhodi so lingvistični), Takagi-Sugeno (mehka pra- vila, kjer je izhod ostra vrednost) [11] in Singleton (izhod • plovec, ki predstavlja reguliran objekt StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 6 • regulacijo (regulator in Smithov prediktor) območju okoli delovne točke. Za nastavitev parametrov re- gulatorja je bilo uporabljeno MATLAB-ovo orodje pidtool. Regulacija oziroma zaprto zančno vodenje vsebuje povratno Prenosna funkcija reguliranega sistema je sestavljena iz dveh informacijo izhoda s pomočjo senzorjev in povratne zanke sklopov - ventilatorja in reguliranega objekta (plovca). Pre- sistema. nosno funkcijo ventilatorja zapišemo s členom prvega reda, plovca pa s členom drugega reda [3]. Slednjo razvijemo na V osnovi je bila ideja vodenje na daljavo, kar pomeni, da se podlagi ravnotežnih enačb, ki smo jih zapisali zgoraj (enačbi algoritem regulacije ne izvaja na istem krmilniku, ki krmili (1) in (2)). Enačbo (2) preuredimo tako, da lahko iz rezulti- ventilator. Posledično so podaljšani časi do prihoda podatka rajoče sile F izrazimo pospešek z00. Enačbo lineariziramo v v regulator. V kolikor se sistem obnaša zelo dinamično (ča- okolici delovne točke in nad njo izvedemo Laplaceovo trans- sovne konstante sistema so majhne), lahko pride do težav formacijo. Izrazimo izhod (∆z(s) - prirastek višine od rav- pri regulaciji. Zaradi je PID regulatorju bil dodan Smithov novesne točke) proti vhodu (∆v(s) - prirastek hitrosti zraka prediktor, ki glede na matematični model regulirane proge od ravnovesne lege) ter tako dobimo prenosno funkcijo Z(s). predvidi obnašanje regulatorja med časom, ko ni na voljo Ventilator modeliramo kot člen prvega reda, z ojačenjem kv novega podatka. V vseh realnih sistemih prihaja v povratni in vzponskim časom τs. Celotna izpeljava funkcije je podana zanki do zakasnitev, ki jih je potrebno za uspešno regulacijo v članku [3], zaradi nazornosti pa so tukaj podani samo bi- upoštevati. Smithov prediktor uporablja model predikcije stveni poudarki. zakasnitve izhoda procesa, primerja razliko med predvide- nim in željenim izhodom ter določi potrebno korekcijo [7]. Prenosna funkcija ventilatorja je tako podana kot: Prednost dodanega Smithovega prediktorja v primerjavi s v(s) k samim PID regulatorjem je hitrejši odziv in manjši prenihaj v V (s) = = , (3) pri odzivu na vrednost nič, kot prikazuje slika 3. u(s) τs + 1 kjer je kv konstanta ventilatorja, podana v m/s in τ V s vzpon- ski čas sistema (čas, da ventilator doseže nazivno hitrost pretoka zraka). Prenosno funkcijo objekta v vetrovniku po izpeljavi zapi- šemo kot: ∆z(s) 1 a Z(s) = = · , (4) ∆v(s) s s(s + a) Parameter a, je podan kot: 2 · g a = , (5) veq veq pa je potrebna hitrost zraka, da vzpostavimo ravnovesno Slika 3: Stopnični odziv PID regulatorja brez in z uporabo lego objekta v vetrovniku (dosežemo ekvilibrium): Smithovega prediktorja. q v g·m eq = (6) 1 ·C 2 d ·ρ·A Pri dejanskem nastavljanju parametrov regulatorja simula- Skupna prenosna funkcija sistema H cije niso bile v veliko pomoč, kar je tudi eden izmed glavnih s je podana kot: razlogov, da je bilo uporabljeno vodenje z mehko logiko. Z H(s) = V (s) · Z(s) (7) enakimi pripadnostnimi funkcijami in enakimi pravili, ki so bila uporabljena na realnem sistemu, je bil simuliran še od- ziv na stopnico z regulatorjem na osnovi mehke logike. Re- in je tretjega reda. Integratorski člen v prenosni funkciji zultati so napram pridobljenim s PID regulatorjem mnogo Z(s) nakazuje na potencialno nestabilnost sistema. Objekt boljši. Vzponski čas je padel za okoli 15%, mehki regula- v vetrovniku ima namreč tendenco, da odleti iz cevi, v ko- tor pa je prav tako izničil prenihaj, ki se pojavlja pri PID likor se ne poslužimo pravilnega pristopa pri načrtovanju regulatorju, kar je vidno na sliki 4. regulatorja. Prav tako zaradi integralskega člena v preno- sni funkciji le-tega ne potrebujemo v regulatorju, zato je Pri načrtovanju mehkega regulatorja se tako nismo ukvarjali teoretično dovolj le regulacija s PD regulatorjem (v okolici z matematičnim modelom in konstantami sistema, ampak delovne točke). Kljub temu, se v praksi doda zelo mala vre- so bile pripadnostne funkcije postavljene glede na dejanski dnost integralnega (I) člena z namenom izboljšanja odziva. odziv sistema, hitrost veq pa določena empirično. Simulacije v MATLAB-u so bile narejene še preden so bili znani vsi parametri sistema (Cd, hitrost zraka, hitrost za- jema podatkov,...), da je bilo okvirno preverjeno delovanje sistema. Tudi če bi uspelo natančno izmeriti vse potrebne parametre, se modelirani sistem zaradi raznih motenj iz oko- lice, ki jih je prezahtevno modelirati, ne bi odzval enako kot realni sistem. Treba je poudariti tudi to, da naj bi izraču- nano delovanje regulatorja zaradi linearizacije, veljalo le v StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 7 Prvotna ideja regulacije plovca v cevi je zajemala regula- cijo preko kotnega zasuka oz. pospeška. Plovec, tj. telo z aerodinamično obliko, naj bi zato vseboval vse kompo- nente potrebne za zajem, obdelavo in posredovanje podat- kov gostujočemu sistemu. V ta namen je bila v plovec vgra- jena mikrokrmilniška plošča STM32F103C8T6 (t.i. Blue Pill ), kombinirani senzor MPU-6050, baterijsko napajanje ter vmesnik Bluetooth HC-05. Senzor MPU-6050 vsebuje integrirani MEMS (Mikro Elektro Mehanski Sistem) pospe- škometer in žiroskop. Ta sočasno zajema podatke v X, Y in Z osi, ter je preko komunikacije I2C povezan s krmilnikom. Prikaz, nadzor in regulacija potekajo na računalniku, kamor se obdelani podatki pošiljajo preko Bluetooth komunikacije. Zaradi potrebe po napajanju plovec vsebuje 3.7 V LiPo ba- terijo s kapaciteto 270 mAh, ki naj bi zagotavljala energijo celotnemu sistemu do 4 ure. Plovec je zaradi potrebe po čim bolj stabilnem gibanju in vrtenju okoli svoje osi, izdelan v obliki kaplje z dodanimi Slika 4: Stopnični odziv mehkega in PID regulatorja. lopaticami. Ohišje plovca je bilo načrtovano v programu SolidWorks in natisnjeno s 3D tiskalnikom. Potrebnih je bilo nekaj iteracij, da so bile zagotovljene dimenzijske tole- 4. IZVEDBA REALNEGA SISTEMA rance in usklajene velikosti delov. V programu SolidWorks V nadaljevanju bo predstavljena priprava strojne in pro- je bila prav tako opravljena simulacija pretoka zraka po cevi gramske opreme za preizkuševališče in reguliran objekt, tj. in izračun težišča plovca z vsemi komponentami (slika 6). plovec. 4.1 Priprava strojne opreme Teoretično delovanje mehkega regulatorja je bilo potrebno preveriti tudi v praksi, zato smo zbrali oz. izdelali vse po- trebne komponente za regulacijo. Sistem sestavlja: • plovec, ki predstavlja reguliran objekt (vsebuje MPU- 6050, mikrokrmilnik STM32F103, Bluetooth modul HC- 05, 3.7 V LiPo baterijo) • tunel oz. regulacijska proga (cev iz pleksi stekla, usmer- nik, ventilator Dr. Mad Thrust KV3300) • zunanje vezje za regulacijo (STM32F407 Discovery Bo- ard, optični senzor VL53L0X, krmilnik za ventilator ESC 20A) Slika 6: 3D model plovca z vgrajenimi komponentami. Regulacijsko progo predstavlja votla cev, skozi katero ven- tilator piha zrak (slika 18). Za ventilatorjem je nameščen usmernik, ki skrbi za enakomeren laminarni pretok zraka, s tem pa je preprečeno nastajanje vrtincev, ki neugodno vpli- vajo na gibanje in regulacijo plovca. Za ventilator je bil izbran Dr. Mad Thrust KV3300, ki ga poganja brezkrtačni elektromotor z nazivno močjo 400 W in ga krmili ESC z ma- ksimalnim tokom 20 A. Regulacija hitrosti se izvaja preko pulzno širinske modulacije, pri čemer mora biti frekvenca preklapljanja 50 Hz. Zaradi težav s pridobivanjem koristnih informacij za regulacijo s senzorja MPU-6050, je bil sistemu dodan optični senzor za merjenje razdalje. Širina plastične cevi ni omogočala povečanja plovca, ki je že bil na meji svoje velikosti, zato je bil senzor nameščen izven plovca na nosi- lec, pritrjen na vrhu cevi. Izvajanju regulacije je tako name- njeno zunanje vezje, ki ga sestavljata krmilnik STM32F407 Discovery Board in senzor za merjenje razdalje. Krmilnik je namenjen generiranju pulzno širinske modulacije za kr- miljenje ventilatorja in posledično pretoka zraka skozi cev, Slika 5: Shematski prikaz regulacijske proge. kar za regulacijo predstavlja vhodno spremenljivko. Sprva je StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 8 bil kot merilnik razdalje uporabljen infrardeči senzor Sharp povzročalo težave pri obdelavi podatkov in regulaciji. Ko- GP2Y0A21YK0F (10 – 80 cm), ki je bil zaradi prevelikih tna hitrost se je spreminjala naključno zaradi trkov v stene nihanj v izmerjeni razdalji, zamenjan z optičnim senzorjem plastične cevi, zato ni bilo mogoče pridobiti uporabnih po- STM VL53L0X. Slednji ima popolnoma linearno karakte- datkov, pospeškometer pa vrača zelo šumne meritve, ki so ristiko ter višji domet (do 2 m), vendar komunicira preko same po sebi neprimerne za dvojno integracijo. Pri mikro- protokola I2C. Regulacija se izvaja na računalniku, ki je s krmilniku (STM32F407VG), ki je skrbel za branje podatkov krmilnikom povezan preko USB komunikacije. iz senzorja časa preleta (VL53L0X), je bila prav tako upo- rabljena komunikacija I2C. Tudi ti podatki so bili poslani na računalnik, tokrat preko USB povezave. Na računalniku so bili podatki nato uporabljeni v regulaciji. Rezultat regu- lacije je bil podatek za hitrost vrtenja ventilatorja, ki je bil nato poslan nazaj na isti mikrokrmilnik. Na mikrokrmilniku je bil napisan tudi program za generiranje pulzno-širinskega signala, ki je bil namenjen krmilniku hitrosti vrtenja (ESC) motorja, glej sliko 8. Slika 7: 3D model zgornjega dela preizkuševališča. 4.2 Priprava programske opreme Za namene projektne naloge so bili napisani programi, ki so Slika 8: Shematski prikaz regulacijske proge. se izvajali na uporabljenih krmilnikih, kot tudi program, ki se je izvajal na osebnem računalniku in je skrbel za regula- Kot orodje za prejemanje, pošiljanje in obdelavo podatkov cijo. Za mikrokrmilnik z oznako STM32F103C8T6, ki se je na računalniku je bil uporabljen program LabVIEW. Za pre- nahajal v plovcu, ter za mikrokrmilnik serije STM32F407VG jemanje in pošiljanje podatkov je bilo v njem uporabljeno Discovery Board, je bil uporabljen programski jezik C. Pri orodje VISA, ki omogoča branje in pisanje podatkov iz/na programiranju je bil v pomoč namenski, brezplačni program računalniški komunikacijski vmesnik. To orodje je bilo upo- CubeMX, ki omogoča lažjo konfiguracijo vseh enot mikro- rabljeno pri prejemanju podatkov iz Bluetooth povezave, kot krmilnika, pripravi vse potrebne knjižnice in ustvari grobo tudi pri prejemanju in pošiljanju podatkov preko USB po- zasnovo vseh programov [16]. Pisanje programa za oba mi- vezave s krmilnikom STM32F407. Sprva je bil program za krokrmilnika pa je bilo opravljeno v integriranem razvojnem regulacijo sestavljen s PID regulatorjem, ki ga je enostavno okolju (IDE) µVision programskega paketa Keil. Oba ome- sestaviti z ustreznim blokom v programu LabVIEW, nato pa njena programa sta namenjena delu in programiranju mikro- je bil zaradi težav implementacije ter pravilnega delovanja krmilnikov z Arm Cortex procesorji [2]. Pri programiranju na vetrovniku ustvarjen mehki regulator tipa Mamdani. krmilnikov so bile uporabljene tudi posebne visokonivojske knjižnice, t.i. knjižnice HAL (angl. Hardware Abstraction Layer ), ki so posebej namenjene programiranju krmilnikov serije STM32. HAL knjižnice olajšajo in pospešijo programi- ranje, saj omogočajo delo z lažje razumljivimi ukazi [15]. Za mikrokrmilnik v plovcu (STM32F103C8T6) je bil napisan program, ki je omogočal branje pospeškov in kotnih hitrosti iz pospeškometra. Za komunikacijo med senzorjem in krmil- nikom je skrbel protokol I2C. Komunikacija je bila imple- mentirana s pomočjo že napisanih prosto dostopnih knjižnic. Vsi podatki so bili ustrezno obdelani in s pomočjo Bluetooth modula HC-05 poslani na računalnik. Podatki so bili sprva prikazani s pomočjo programa LabVIEW, kasneje pa je bilo načrtovano te podatke uporabiti v Kalmanovem filtru pri iz- računu višine plovca v vetrovniku. Ta naloga se je izkazalo za zelo zahtevno, saj se za pravilno delovanje Kalmanovega Slika 9: Blok diagram regulacijske zanke v LabVIEW-u. filtra priporoča zelo natančen model sistema, poleg tega so podatki iz senzorja MPU-6050 vsebovali preveč motenj in V programu LabVIEW, glej sliko 9, je bil takšen regula- šuma, da bi se iz njih dalo razbrati uporabne meritve, kar bi tor ustvarjen s pomočjo orodja imenovanega Fuzzy System StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 9 Designer. S tem orodjem se ustvari mehki regulator, ka- teremu določimo število in oblike pripadnostnih funkcij ter napišemo bazo pravil. Kot je razvidno iz slike 10, vhodni množici v mehki regulator predstavljata pogrešek med de- jansko in željeno višino plovca v vetrovniku, ter njegov od- vod. Mehki regulator spreminja vrednost pulzno-širinskega signala v malem območju okoli vrednosti, pri kateri plovec lebdi v vetrovniku. Hitrost veq potrebna za levitacijo pa je odvi- sna od mase plovca in zmožnosti premikanja po cevi – če se plovec zatika ob cev, je potrebna višja hitrost in obratno. Slika 11: Plovec aerodinamične oblike. ki jih povzroča ventilator, so odpravljene tako, da je pla- stična osnova privita na debelejši in težji kos podlage. Za pravilno delovanje sistema, je zelo pomemben tudi nemoten, predvsem pa zadosten dotok zraka, ki služi tudi hlajenju kr- milnika ESC. Ta se lahko zaradi visokih nazivnih tokov pri krmiljenju ventilatorja temu primerno segreje. Napajanje sistema je možno izvesti na več načinov, z uporabo labora- torijskega napajalnika (0-50V, 20 A), računalniškega napa- Slika 10: Regulacijska proga z vključenim mehkih regula- jalnika ali s pomočjo LiPo baterije 3S, ki je pogosto upo- torjem. Veličina y predstavlja višino, na kateri se nahaja rabljena v modelarstvu. Na ta način je zagotovljena tudi plovec. prenosljivost preizkuševališča, ki je primerno za demonstra- cijsko rabo v pedagoškem procesu. 5. SESTAVLJANJE KOMPONENT 6. REZULTATI Sestava komponent vetrovnika je bila sorazmerno preprosta, V končnem izdelku nam PID regulatorja ni uspelo imple- vendar je bilo kljub temu med gradnjo sistema potrebno re- mentirati predvsem zaradi: šiti nekaj težav. Optični senzor VL53L0X komunicira s kr- milnikom STM32F407 preko I2C komunikacije, zato je bila omejena dolžina kabla, ki povezuje senzor s krmilnikom. Kr- • predolgega časa zajema položaja plovca. Čas potreben milnik je bilo zato potrebno namestiti v neposredno bližino za pridobitev novega podatka o višini je trajal preko senzorja. V ta namen je bil izdelan preprost nosilec, ki je bil 100 ms, kar je bilo za regulacijo sistema občutno pre- z vročim lepilom pritrjen na cev vetrovnika, kot prikazuje več. Dodatno je potrebno upoštevati še čas do nove na- slika 17. Na spodnji strani je bila cev skupaj z usmernikom stavitve hitrosti, ki ga zaradi USB komunikacije v obe zraka vstavljena v osnovo, natisnjeno s 3D tiskalnikom. Iz smeri, ter obdelave algoritma ocenjujemo na vsaj 10 spodnje strani je bil vanjo nameščen še ventilator ter v škatlo ms. Težava s posredovanjem novega podatka sicer ni ob osnovi krmilnik motorja, ki je z dvema žicama povezan bila v samem senzorju, saj le-ta zmore zagotoviti novo na mikrokrmilnik (slika 16). Prvi testi so pokazali, da se vrednost vsakih 20 ms v režimu hitrega zajema podat- v sistemu pojavi precej vibracij, ki neugodno vplivajo na kov, temveč v izvajanju prekinitvene rutine. Najnižji, premikanje plovca po cevi. Oblika plovca, predvsem širina, še mogoč čas proženja prekinitev preko časovnika je je omejena s komponentami, ki se nahajajo v njem, poleg znašal 100 ms. Natančnega razloga, zaradi katerega tega pa še z notranjim premerom cevi. Preširok plovec se nismo mogli doseči hitrejšega izvajanja prekinitev, ne zaradi preslabega obtoka zraka ni vrtel in se je zatikal ob poznamo, predvidevamo pa, da je bil procesor v tem cev. Ožji plovec je bil s stališča vrtenja ob zagonu boljša iz- času preobremenjen. bira, vendar zaradi notranjih komponent in načina izdelave, njegovega težišča ni bilo lahko spraviti na os vrtenja, zato • nezmožnosti PID regulatorja, da mu nastavimo karak- je kmalu po začetku vrtenja postal nestabilen. Plovec je bil teristiko, saj se v celotnem področju regulator obnaša še dodatno obtežen, saj so se na ta način povečale časovne enako. PID regulator, ki je bil sposoben držati plovec konstante sistema in spustile zahtevo po visokem vzorčeval- v bližini referenčne točke smo sicer izdelali, vendar z nem času. Pri končni izvedbi so združene dobre lastnosti rezultatom nismo bili zadovoljni. obeh prej omenjenih izvedb. Na začetku je plovec ožji in za- gotavlja zadosten obtok zraka, zadnji del plovca pa je širši. Opletanje plovca je rešeno s tem, da je razlika med širino V obeh omenjenih pomanjkljivostih PID regulatorja pa ima plastične cevi in zadnjega dela plovca le 1 mm, istočasno pa uporaba mehkega regulatorja prednost. Uporaben je pri po- je s krilci omogočeno njegovo vrtenje. časnejših časih vzorčenja, njegova največja prednost pa je ta, da omogoča bolj transparentno nastavljanje njegovih pa- Čeprav je bila prvotna ideja o regulaciji preko podatkov žiro- rametrov [13]. Strokovnjak, ki načrtuje regulator ima tako skopa in pospeškometra opuščena, pa je bilo vrtenje plovca izboljšano predstavo o relaciji med vhodnimi in izhodnimi pomembno, saj se je plovec ob konstantnem vrtenju lažje podatki, kar pa je za PID težko trditi. Glavni parametri, premikal ter lažje dosegel želeno vrednost višine. Vibracije, od katerih je odvisno delovanje mehkega regulatorja so šte- StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 10 vilo in položaj pripadnostnih funkcij ter pravila, ki povežejo vhodne in izhodne pripadnostne funkcije. Končni regulator je imel 5 pripadnostnih funkcij za vsako vhodno in izhodno množico, med sabo pa jih je povezovalo 25 pravil. Vse pripadnostne funkcije so trikotne nezvezne oblike, kakor so prikazane na sliki 12. Slika 14: Stopnični odziv mehkega regulatorja na realnem sistemu. Uporabljen je bil zeleni plovec z maso 25 g. Kot je razvidno iz stopničnega odziva na sliki 14, se plovec Slika 12: Pripadnostne funkcije mehkega regulatorja in ka- med skrajnima višinama premakne v približno dveh sekun- rakteristika - nelinearna ravnina. dah. Ob željenem manjšem nastavitvenem času pride do večjih prenihajev, kar lahko pomeni, da plovec odleti iz ve- Z uporabo mehkega regulatorja, smo se prav tako izognili trovnika in zadane senzor, ki je nameščen nad vetrovnikom uporabi Smithovega prediktorja, ki sicer v nekoliko spreme- ter ga poškoduje. Podobno se zgodi pri spuščanju plovca, njeni obliki obstaja tudi za mehki regulator [14]. kjer lahko plovec pri večjih prenihajih poškoduje usmernik zračnega pretoka. Iz teh razlogov je bil narejen kompromis Težave z dolgimi časi zajema (T med prenihajem in nastavitvenim časom pri odzivu mehkega s) smo rešili tudi na način, da smo v končni regulaciji uporabili težji plovec, zaradi česar regulatorja. je bil odziv sistema počasnejši in posledično je mehki regula- tor lažje in bolje reguliral sistem. Ugotovili smo tudi, da je mehki regulator manj občutljiv na spremembe reguliranega objekta – plovca, je pa potrebno poudariti, da telesa z nizko maso (žogica za namizni tenis) na ta način ni mogoče regu- lirati, ker so časovne konstante tega objekta precej nižje od plovca, uporabljenega v naši nalogi. Slika 15: LabVIEW kontrolna plošča. Sistem v taki obliki je tudi stabilen in odporen na motnje. Preizkuševališče (slike 16, 17, 18) lahko dvignemo ali mu spremenimo naklon, pri čemer regulator še vedno odlično opravlja svoje delo. Slika 13: Uporabljeni plovci za testiranje preizkuševališča. Pred začetkom regulacije je bilo potrebno poiskati le vre- dnost hitrosti zraka v cevi, pri kateri plovec v vetrovniku lebdi (veq), kar naredimo z enostavnim povečevanjem hitro- sti vrtenja motorja z drsnikom na nadzorni plošči v pro- gramu LabVIEW (slika 15). Takšen način zagona vetrov- nika je bil uporabljen zlasti zaradi uporabljenih različnih plovcev (slika 13), pri katerih so se ravnovesne vrednosti vrtenja motorja med seboj. Ko je ta vrednost zabeležena in vpisana, lahko regulator ustrezno regulira višino plovcev različnih oblik in tež. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 11 Slika 16: Spodnji del preizkuševališča. Slika 18: Celotni sistem. Slika 17: Zgornji del preizkuševališča. kazali smo, da lahko z mehko logiko vodimo kompleksnejši sistem, ki ima dolge čase zajema in bi ga sicer s PID regu- 7. SKLEP latorjem ob enakih pogojih zelo težko vodili brez dodanega Članek zajema izvedbo regulirane levitacije plovca v zrač- Smithovega prediktorja ali nasploh. Za nastavitev regula- nem tunelu, pri čemer gre za sistem daljinskega vodenja. torja smo porabili veliko manj časa, kot smo ga sicer za po- Regulacija se izvaja na oddaljenem sistemu, v našem pri- skus implementacije PID regulatorja, ki nam ni dajal pravih meru na osebnem računalniku. Višino plovca v cevi nam rezultatov. Ob predpostavki, da se mase plovca, na katerem je uspelo regulirati ne glede na visoke mrtve čase, kar nam je bil mehki regulator nastavljen ne spremenijo bistveno, re- sicer s PID regulatorjem ni povsem uspelo. Aplikacija na gulator ohranja solidne odzive, bolj kot sama masa pa na osebnem računalniku (LabVIEW) nam omogoča, da nasta- rezultate bolj vpliva hrapavost in stabilnost plovca v cevi. vimo želeno višino, sistem pa se samodejno odzove. Poleg tega lahko v njej istočasno spremljamo realne vrednosti po- ZAHVALA speškov in kotnih hitrosti plovca, v kolikor uporabimo ome- Iskreno se zahvaljujemo rednemu profesorju dr. Dušanu Gle- njeno izvedbo z vgrajenim krmilnikom. Tekom dela smo ichu ter asistentu mag. Blažu Pongracu s Fakultete za elek- naleteli na več težav, največ težav je predstavljala strojna trotehniko, računalništvo in informatiko v Mariboru za po- oprema in implementacija I2C komunikacije med optičnim moč pri izvedbi simulacij in načrtovanju programske opreme. senzorjem (VL53L0X) in mikrokrmilnikom (STM32F407). Dodatne težave, ki jih nismo povsem odpravili so vibracije cevi, ki vplivajo na vrtenje plovca in ga občasno popolnoma zaustavijo, saj se ta namesto da bi se vrtel, prične odbijati REFERENCES od stene. Problem je tudi trenje med plovcem in steno ve- [1] C. G. Amza and D. T. Cicic. Industrial image trovnika, ki prav tako zavira vrtenje, ter pa opletanje plovca, processing using fuzzy-logic. Procedia Engineering, ker ta ni povsem centriran. Vsekakor pa so nekatere izmed 100:492–498, 2015. teh težav privedle do tega, da smo se odločili za uporabo [2] armKEIL. MDK Microcontroller Development Kit. mehke logike. Dostopno na: http: //www2.keil.com/mdk5/.Dostopano:16.9.2018. Težave, ki so ostale, predstavljajo možnosti nadaljevanja [3] J. Chacon, J. Saenz, L. d. l. Torre, J. M. Diaz, and dela na projektu in dodatnih izboljšav sistema. Boljše re- F. Esquembre. Design of a Low-Cost Air Levitation zultate obeta uporaba širše cevi, tako bi bili nekoliko manj System for Teaching Control Engineering. Sensors, omejeni z oblikami in dimenzijami plovcev. Regulator, ki 17(10):2321, 2017. trenutno nadzira sistem je bil v primerjavi s PID, izdelan v [4] D. Fister, R. Šafaric, and I. Fister. Nastavljanje zelo kratkem času, vendar je že v začetni fazi testiranja da- parametrov regulatorja z optimizacijskimi algoritmi. jal spodbudne rezultate, vendar pa smo zaradi pomanjkanja In StuCoSReC: Proceedings of the 2015 2nd Student časa morali izpustiti napredno optimizacijo procesa. Do- Computer Science Research Conference, pages 13–17, StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 12 2015. [5] A. M. Gavgani, A. Sorniotti, J. Doherty, and C. Cavallino. Optimal gearshift control for a novel hybrid electric drivetrain. Mechanism and Machine Theory, 105:352 – 368, 2016. [6] I. Iancu. A mamdani type fuzzy logic controller. In Fuzzy Logic-Controls, Concepts, Theories and Applications. InTech, 2012. [7] A. Ingimundarson and T. Hägglund. Robust tuning procedures of dead-time compensating controllers. Control Engineering Practice, 9(11):1195–1208, 2001. [8] K. Ngorex. Slideshare. Dostopno na: https://www.slideshare.net/poerslide/ lecture7-ml-machines-that-can-learn.Dostopano: 7.8.2018. [9] O. Kraa, A. Aboubou, M. Becherif, M. Ayad, R. Saadi, M. Bahri, and H. Ghodbane. Fuzzy logic maximum structure and state feedback control strategies of the electrical car. Energy Procedia, 50:178 – 185, 2014. Technologies and Materials for Renewable Energy, Environment and Sustainability (TMREES14 – EUMISD). [10] R. Li, Y. Guo, S. K. Nguang, and Y. Chen. Takagi-Sugeno fuzzy model identification for turbofan aero-engines with guaranteed stability. Chinese Journal of Aeronautics, 31(6):1206–1214, June 2018. [11] K. Mehran. Takagi-sugeno fuzzy modeling for process control. Industrial Automation, Robotics and Artificial Intelligence (EEE8005), 262, 2008. [12] N. Rai and B. Rai. Control of fuzzy logic based PV-battery hybrid system for stand-alone DC applications. Journal of Electrical Systems and Information Technology, 2018. [13] R. Šafarič and A. Rojko. Inteligentne regulacijske tehnike v mehatroniki. Fakulteta za elektrotehniko, računalništvo in informatiko, 2007. [14] A. Sakr, A. M. El-Nagar, M. El-Bardini, and M. Sharaf. Fuzzy smith predictor for networked control systems. In Computer Engineering & Systems (ICCES), 2016 11th International Conference on, pages 437–443. IEEE, 2016. [15] ST. Description of STM32F4 HAL and LL drivers. Dostopno na: https://www.st.com/resource/en/user_manual/ dm00105879.pdf.Dostopano:16.9.2018. [16] ST. STM32CubeMX. Dostopno na: https: //www.st.com/en/development-tools/stm32cubemx. html\#sw-tools-scroll.Dostopano:16.9.2018. [17] Tutorialspoint. Fuzzy Logic Applications. Dostopno na: https://www.tutorialspoint.com/fuzzy_logic/ fuzzy_logic_applications.htm.Dostopano: 7.8.2018. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 13 Razpoznavanje literature v dokumentih in dolo čanje njihovih sklicev v besedilu Matej MORAVEC David LETONJA Fakulteta za elektrotehniko, Fakulteta za elektrotehniko, računalništvo in informatiko računalništvo in informatiko Koroška cesta 46, Koroška cesta 46, 2000 Maribor, Slovenija 2000 Maribor, Slovenija matejmoravec19@gmail.com david.letonja@gmail.com Jan TOVORNIK Borko BOŠKOVI Č Fakulteta za elektrotehniko, Fakulteta za elektrotehniko, računalništvo in informatiko računalništvo in informatiko Koroška cesta 46, Koroška cesta 46, 2000 Maribor, Slovenija 2000 Maribor, Slovenija jan.tovornik@gmail.com borko.boskovic@um.si POVZETEK v dokumentih, predstavljen v tem članku, temelji na upo- Pojav plagiatorstva je vedno bolj pogost, saj v današnjem rabi regularnih izrazov in posameznih korakih pregledovanja času obstaja zelo veliko elektronskih virov, preko katerih dokumentov, predstavljenih v naslednjih poglavjih. Glavna lahko dostopamo do želene vsebine. V ta namen je bilo prednost našega pristopa je, da je neodvisen od jezika, v ka- razvitih veliko različnih pristopov za detekcijo plagiatov. V terem je dokument napisan. članku predstavimo pristop, kjer v dokumentih razpoznamo navedeno literaturo in znotraj dokumenta poiščemo, kje se Članek je strukturiran tako, da v naslednjih poglavjih pred- nahajajo sklici v besedilu. Uspešnost našega pristopa smo stavimo sorodno delo, nato opišemo delovanje našega pri- preizkusili s pomočjo različnih metrik. Dosegli smo 67 % stopa, opišemo rezultate eksperimenta in na koncu podamo natančnost in 80 % mero F1 za razpoznavo virov. kratek zaključek, kjer povzamemo naše ugotovitve skozi ce- lotno delo. Kjučne besede razpoznavanje literature, analiza citatov, plagiatorstvo, po- 2. SORODNA DELA dobnost datotek V članku [7] sta avtorja predstavila nov pristop k odkriva- nju plagiatorstva, imenovan Analiza vrstnega reda citatov 1. UVOD ali COA (Citation Order Analysis). Ta deluje na podlagi Plagiat je delo, ki je prepisano, povzeto od drugod in ob- analize citatov in sklicevanja na vire oziroma literaturo ter javljeno, prikazano kot lastno [3]. Večina strokovnih doku- vsebuje naslednje korake: mentov vsebuje navedeno literaturo. Če se literatura nahaja v dokumentu ali ne, je seveda odvisno od vrste dokumenta. 1. preoblikovanje dokumenta za procesiranje citatov in njihovih pojavitev v dokumentu, Razpoznavanja literature in kasneje iskanja njihovih sklicev znotraj besedila smo se lotili z idejo, da bi na tak način 2. ujemanje citatov z njihovimi navedbami v literaturi, pripomogli k večji natančnosti programov, ki preverjajo, ali je določeni dokument plagiat ali ne. Definicija plagiata v 3. med dokumenti se preveri podobnost citatov. V osnovni SSKJ pravi, da je plagiat tisto, “kar je prepisano, prevzeto različici sistema se upošteva samo vrstni red citatov, od drugod in objavljeno, prikazano kot lastno, navadno v v naprednejši različici sistema pa se ocenjuje tudi raz- književnosti” [3]. dalja med dvema citatoma. Če se dokument prevede v drugi jezik, se lahko vrstni red citatov znotraj stav- Pristop razpoznavanja literature in iskanja njihovih sklicev kov ali odstavkov spremeni zaradi različnih struktur stavkov ali drugačnega načina pisanja. Za ocenitev pristopa so opravili preizkuse na 800.000 prosto dostopnih znanstvenih publikacij, med katere so tudi skrili 20 posebej zasnovanih plagiariziranih dokumentov. Da je scenarij izgledal bolj realističen, so nekaj citatov izbrisali, dodali par novih, nekaterim spremenili stil, nekatere pa med seboj zamenjali. Pristop je od 20 testnih dokumentov uspe- šno odkril 19 in na stotine drugih dokumentov, ki so vsebo- StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.15-19 Ljubljana, Slovenia, 9 October 15 vali vsaj nekaj plagiariziranih odsekov. Več kot ima doku- traj poglavja razpozna posamezno literaturo in te oznake ment navedenih citatov, težje je odkriti plagiarizem. literature doda v seznam. V tretji fazi pregleda celoten do- Preoblikovanje dokumentov iz formata pdf v xml je trajalo kument in poišče, na kateri strani in v katerem odstavku 2 sekundi za vsak dokument. V 96 % vseh zgoraj omenjenih znotraj strani se nahajajo sklici na literaturo. dokumentov/publikacij je bilo ujemanje citatov z njihovimi navedbami v bibliografiji uspešno. Preden smo pričeli z razpoznavanjem in gradnjo seznama Največja prednost opisanega pristopa je neodvisnost od je- literature, smo zaradi različno strukturiranih dokumentov zika, v katerem je dokument napisan, in neodvisnost do pa- naleteli na prvi izziv. Naša prva naloga je bila, da smo v rafraziranja. Časovna zahtevnost je v primerjavi s pristopi, dokumentu najprej našli, kje se nahaja poglavje z navedeno ki temeljijo na podobnosti besedil, zanemarljiva. Največja literaturo. To smo rešili tako, da smo zapisali tak regularni slabost pristopa pa je odvisnost od pravilnega citiranja. izraz, ki je razpoznal čim več različnih načinov zapisa po- Slabost tega pristopa je ob enem prednost pristopov, ki te- glavja, ki vsebuje literaturo. meljijo na podobnosti besedil, zato se za doseganje najbolj- ših rezulatov priporoča kombinirana uporaba obeh pristo- Vsebino poglavja z navedeno literaturo smo ravno tako pre- pov. iskali s pomočjo regularnih izrazov. Z namenom razpozna- vanja čim večjega števila virov znotraj poglavja smo zapisali V članku [8] so še opisani rezultati, ki so jih avtorji pridobili večje število regularnih izrazov. Rešitve smo se lotili tako, ob avtomatski obdelavi ogromne količine znanstvenih član- da smo razpoznavali vrstico po vrstico znotraj poglavja z kov v skladu z natančno določenimi kriteriji ocenjevanja. navedeno literaturo. Ob posameznem najdenem viru smo Populacijo znanstvenih člankov, ki so jo uporabljali, so ure- zapisali njegovo oznako (številko), v za to namenjen seznam. dili v skupine tako, da so zadostili kriterijem medsebojne Ta seznam smo zgradili z namenom za kasnejše iskanje skli- povezanosti, tj. povezanost v tematiki. Dokumenti iste te- cev na posamezen vir v besedilu. matike kažejo na zelo visoko stopnjo korelacije med seboj. Avtorji dokažejo, da lahko z njihovim pristopom zelo do- Množica dokumentov, ki smo jo uporabili kot učno množico bro določimo tematiko dokumenta le s pomočjo razpoznane za naš pristop je vsebovala strokovna oziroma znanstvena literature v dokumentih. dela z različnih fakultet. Vsi dokumenti so bili zapisani v slovenskem jeziku in so po večini bili drugače strukturirani. Delo Irene Marshakove [9] opisuje novo formalno metodo za Zaradi različno strukturiranih dokumentov je bilo razpozna- klasifikacijo dokumentov. Ta metoda temelji na analizi refe- vanje sklicev toliko večji izziv. renc oziroma sklicev s pomočjo indeksiranja literature znan- stvenih člankov. Vsakemu sklicu se dodeli indeks od začetka Za prepoznavanje poglavja, ki je vsebovalo navedeno lite- do konca dokumenta. Po dodelitvi indeksov dokumentom se raturo, smo uporabili regularni izraz, specifičen za element le-ti indeksi in številka reference oziroma sklica medsebojno pagraf (

). Ta regularni izraz lahko razbijemo na več primerjajo. Primer, da imata dve ali več del veliko sklicev delov: z enakimi indeksi, nakazuje, da je morebiti eno ali več del izmed teh plagiat. • V prvem delu, poiščemo vse odstavke

, ki imajo Članek [4] opisuje, kako je potekalo prvo mednarodno tek- vsebino atributa xml:id, ob pb (page break) in p (od- mnovanje v odkrivanju plagiatorstva. Na tem tekmovanju stavku) celo število. se je izvajala delavnica PAN - Delavnica o odkrivanju pla- • V drugem delu se prvemu regularnemu pravilu, pri- giatorstva, avtorstva in zlorabe socialne programske opreme družuje iskanje odstavkov

v poljubnem jeziku. V (zloraba osebnih podatkov preko družabnih omrežij). primeru, da bi želeli poiskati le določen jezik, bi morali To tekmovanje oziroma natečaj je bil razdeljen na več po- vsebino atributa xml:lang specifično navesti. dročij (13 različnih: različne težavnosti, več vrst nalog itd.) in to z enim razlogom, da bi preprečili kršitve, kot so pla- • V zadnjem delu pa k prej navedenima praviloma do- giatorstvo in kraja osebnih podatkov. “Stranski efekt” tega damo pravilo za iskanje odstavkov

po specifičnih tekmovanja je bil postaviti oceno, kako dobro detektiramo naslovih, pod katerimi se predstavlja literatura. plagiatorstvo in varnost osebnih podatkov bodisi iz avtor- skih del ali družabnih omrežij. Hkrati pa izbrati množico ljudi, ki bi razvijala različne algoritme za bolj varni jutri. Regularni izraz poišče celoten odstavek, v katerem je podan naslov poglavja literature. Ker naslov poglavja najverjetneje Članek [10] opisuje novo obliko združevanja dokumentov vsebuje oštevilčenje, mora regularni izraz to tudi razpoznati. imenovano: so-citiranje. Je pristop, kjer ob navedbi vira Upoštevati moramo tudi dejstvo, da obstaja več vrst ošte- navedemo skupaj več virov (dokumente, knjige, internetne vilčevanja, kar nam dodatno oteži razpoznavanje. Po za- vire, na katere se nato sklicujemo). Avtorji predpostavljajo poredni številki poglavja sledi naslov poglavja, pri katerem uporabo so-citiranja zato, da zmanjšamo količino literature. preverjamo naslednje besedne zveze (upoštevajo se velike in Tako združujemo vire, ki temeljijo na isti tematiki, so iz iste male črke): založbe, imajo iste avtorje, ali pa preprosto so-citiramo zato, ker najdemo eno stvar iz dveh različnih virov. • seznam virov, 3. PREDLAGANA METODA • seznam literature, Predlagana metoda vsebuje tri faze. V prvi fazi detektira poglavje, ki vsebuje navedeno literaturo. V drugi fazi zno- • viri, StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 16 • literatura, 4. REZULTATI V tem poglavju bomo primerjali dobljene rezultate z ročno • seznam uporabljenih virov in dobljenimi rezultati in prikazali uspešnost našega pristopa. • reference. Kontingenčna tabela je tip tabele, zapisan v matrični obliki, ki prikazuje frekvenčno porazdelitev več spremenljivk. Ve- Če vzorec ustreza določenemu izrazu, se najdeno poglavje liko se uporablja pri inženirskih, znanstvenih raziskavah ipd. tretira kot poglavje literature, ki vsebuje seznam literature Tabela prikaže osnovno idejo medsebojne povezave med dvema oziroma virov. spremenljivkama in lahko pomaga pri iskanju medsebojne interakcije [1]. Literatura je lahko podana na več načinov: Tabela 1: Zapis kontingenčne tabele [5]. • oštevilčena z navadnimi oklepaji, podatki / kla- pravilen sklic napačen sklic • oštevilčena z oglatimi oklepaji ali sifikacija • neoštevilčena. pravilen sklic resnični pozi- lažno pozitivni tivni (tp) (fp) Da smo razpoznali te tri načine, smo uporabili 2 različna napačen sklic lažno negativni resnični nega- regularna izraza, enega za oštevilčen način in enega za neo- (fn) tivni (tn) številčen način podajanja literature. Oba regularna izraza, za vsako podano literaturo, podata v seznam naslednje po- Na Sliki 1 so prikazane vrednosti in njihove oznake, ki jih datke: lahko klasificiramo iz podatkov. V našem primeru lažno negativne vrednosti predstavljajo sklice, ki jih je program našel, a v dokumentu ne obstajajo. Resnično pozitivne vre- • številka strani, na kateri je literatura podana, dnosti predstavljajo sklice, ki v dokumentu dejansko obsta- • zaporedna številka v seznamu (če le-ta obstaja), jajo in jih je program našel, ter lažno pozitivne vrednosti so tiste, ki v dokumentu obstajajo, a jih program ni našel. • prva beseda (kot priimek avtorja). Ta seznam se v nadaljevanju uporabi za lažjo in bolj orga- nizirano iskanje referenc. S ciljem poiskati čim več sklicev v besedilu, smo zapisali različne regularne izraze. V našem pristopu smo zagotovili odkrivanje sklicev tam, kjer avtor dokumenta navaja sklice na način, da v oglate ali navadne oklepaje zapiše posame- zno oznako vira ali pa navede več virov znotraj oklepajev. Naš pristop najde tudi sklice, kjer avtor v oklepajih navede prvega avtorja. Za pravilno prepoznavanje poglavij, literature/virov in skli- cev smo uporabili regularne izraze. Za vsak korak v opisa- nem postopku se je uporabil svoj regularni izraz. Za prepoznavanje referenc oziroma sklicev na literaturo smo uporabili kar 4 različne regularne izraze, ki razpoznavajo naslednje načine sklicevanja: • enoštevilčno v navadnih in oglatih oklepajih ((0), [0]), • večštevilčno v navadnih in oglatih oklepajih ((1, 2, 3), [1, 2, 3]), • avtor brez oklepajev (Vir: avtor ...), • avtor z navadnimi in oglatimi oklepaji ((avtor ...), [av- tor ...]). Slika 1: Prikaz vrednosti, ki jih lahko vrne klasifika- tor [2]. . Iskanje in prepoznavanje referenc se opravlja nad celotnim dokumentom in z največ regularnimi izrazi, zato je ta korak Kontingenčna matrika je za ocenjevanje uspešnosti našega v večini primerov časovno najzahtevnejši. pristopa uporabna, saj lahko s pomočjo le-te izračunamo StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 17 natančnost, preciznost, priklic in mero F1, kot prikazujejo pa nismo našli. V dokumentu za primerjavo pa smo našli naslednje enačbe: le 20 pravilnih sklicev, a 5 sklicev nismo našli. Med vsemi sklici ni bilo nobenega, ki bi se nahajal na isti strani, v istem odstavku. Na podlagi takih rezultatov z našo metodo nismo tp + tn ugotovili oziroma ne moremo ugotoviti, če gre za plagiat ali accuracy = (1) tp + tn + f p + f n ne. Na podlagi rezultatov tretje izvedbe primerjave dveh do- kumentov z našo metodo prav tako ne moremo ugotoviti, če tp gre za plagiat ali ne. Primerjave sploh ne moremo narediti, precision = (2) tp + f p saj naša metoda od 6 sklicev v objavjenem dokumentu ni našla nobenega. V dokumentu za primerjavo je sicer našla tp 20 sklicev, vendar jih v tem primeru ne moremo uporabiti recall = (3) tp + f n za primerjavo. 2P R Na podlagi izvedenega eksperimenta lahko vidimo, v katerih F 1 = (4) P + R primerih je predlagana metoda uporabna. Če so avtorji do- kumentov dosledni in “pravilno” navajajo sklice in literaturo, potem lahko z uporabo predlagane metode dokaj učinkovito Za izračun uspešnosti smo uporabili 100 dokumentov. Od ugotovimo, ali je dokument plagiat ali ne, oziroma lahko v tega smo jih 31 izločili, saj so bili sklici navedeni tako, da primeru uporabe ostalih metod za preverjanje plagiatorstva niti človek ne bi znal razpoznati, na kateri vir se oseba v do- s to metodo povečamo oziroma zmanjšamo verjetnost, da je kumentu sklicuje. Največji problem v dokumentih je torej delo plagiat. predstavljalo naštevanje virov tako, da sta bila pod isto šte- vilko našteta dva ali več virov. Zato smo za izračun uporabili 69 dokumentov in na koncu izračunali točnost, natančnost, 5. UGOTOVITVE IN PROBLEMI priklic in metriko F1. Za izračun uspešnosti smo uporabili Skozi razvoj našega pristopa k odkrivanju plagiatorstva smo mikro povprečenje, kjer smo združili dobljene rezultate kla- naleteli na kar nekaj težav. Glavna težava v našem delu je sifikatorja. bil način navajanja in sklicevanja na vire. Kot je zabeleženo V Tabeli 2 so prikazani rezultati posameznih izračunov. v navodilih za pisanje zaključnih del [6], vidimo, da je nave- denih kar nekaj napotkov, kako pravilno navajati in se nato sklicevati na vire. Tabela 2: Metrike uspešnosti razpoznavanja litera- ture. Navedbo virov in literature je potrebno zapisati kot seznam Metrika Rezultat na koncu zaključnega dela. V ta seznam je potrebno zabele- žiti vse vire, na katere smo se sklicevali v zaključnem delu. Točnost (angl. accuracy) 0,67 Vsakega izmed virov je potrebno oštevilčiti z arabskimi šte- Natančnost (angl. precision) 0,88 vilkami znotraj oglatih oklepajih (Slika 2). Priklic (angl. recall) 0,74 Metrika F1 (angl. F1 score) 0,80 Slika 2: Pravilna navedba vira. Uspešnost našega programa, ki smo jo izračunali na podlagi mikro povprečenja, je 67 %. Seznam literature in virov je potrebno urediti po abecednem vrstnem redu avtorjev. V primeru, da ni navedenih avtor- 4.1 Eksperiment za ugotavljanje plagiatorstva jev, uredimo po naslovu vira. Pomanjkljivost in napačno Z namenom prikaza uporabnosti našega pristopa v smislu sklicevanje virov zmanjšuje vrednost zaključnega dela [6]. ugotavljanja plagiatorstva med dokumenti smo izvedli en manjši eksperiment. Pri tem smo uporabili dva dokumenta. Težave nam je povzročalo tudi iskanje navedenih sklicev v En dokument je predstavljal že objavljeno delo, drug doku- seznamu literature in virov. Ta seznam so nekateri študentje ment pa smo s tem dokumentom v smislu navajanja litera- navajali napačno in na več različnih načinov: ture in navajanja sklicev primerjali. Navedeni potek primer- jave smo izvedli trikrat (z različnimi dokumenti). 1. naštevanje z vezajem (-), Pri prvi primerjavi dveh dokumentov, smo v objavljenem 2. naštevanje s piko (•), dokumentu z našo metodo našli 34 pravilnih sklicev in nič napačnih. V dokumentu za primerjavo z objavljenim pa smo 3. seznam literature in virov NI bil naveden za vsemi po- našli 52 pravilnih sklicev in nič napačnih. Ugotovili smo, da glavji na svoji strani, ampak je bil mnogokrat pred je od teh 52 sklicev 34 takih, ki se pojavijo na isti strani, v mnogimi poglavji, včasih kar na enaki strani kot neko istem odstavku kot v objavljenem dokumentu. Na podlagi drugo poglavje. teh rezultatov lahko z veliko verjetnostjo trdimo, da gre za plagiat, saj je zelo majhna verjetnost, da bi dva dokumenta imela na istih straneh, v istih odstavkih tako veliko sklicev Zaradi vseh teh napak naša programska rešitev ni mogla na literaturo. V primerjavi drugih dveh dokumentov smo v uspešno napolniti svojega seznama z viri, na podlagi kate- objavljenem dokumentu našli 37 pravilnih sklicev, 2 sklica rih je nato iskala sklice po dokumentu. Ta problem je eden StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 18 izmed glavnih razlogov, zakaj smo morali izmed 100 doku- [3] Plagiat. http://bos.zrc-sazu.si/cgi/a03.exe? mentov zavreči 31 dokumentov. name=sskj_testa&expression=ge%3Dplagiat*&hs=1. Dostopano 29. 4. 2018. Razlog, kateremu se prav tako nismo morali izogniti, je bilo [4] E. S. M. K. E. A. Benno Stein, Paolo Rosso. Pan napačno sklicevanje virov. Avtorji so se na sam vir sklicevali workshop. uncovering plagiarism, authorship and napačno na več načinov: social software misuse. https://pdfs.semanticscholar.org/160b/ 1. sklicevanje brez oklepajev () ali brez zavitih oklepajev 400d726eb042d0867d537c447e858716e7b7.pdf. Dostopano 8. 6. 2018. [], v katerih bi naj bila navedena zaporedna številka vira oziroma avtor, [5] J. D. Borko Boškovič and J. Brest. Študijska literatura pri predmetu Jezikovne tehnologije. 2018. 2. sklicevanje v obliki 1. ali 1, [6] FERI. Navodila za pisanje zaključnih del na študijskih programih prve in druge stopnje um feri. 2018. 3. sklicevanje v obliki (vir1 vir2 vir3 itd.), kjer sklici med seboj niso bili pravilno ločeni. Za ločevanje sklicev so [7] B. Gipp and J. Beel. Citation based plagiarism študentje uporabljali znake, kot je na primer podpičje detection - a new approach to identify plagiarized (;), work language independently. HT ’10 Proceedings of the 21st ACM conference on Hypertext and 4. sklicevanje na vir, ki na seznamu virov ne obstaja, hypermedia, 2010. [8] M. M. Kessler. Bibliographic coupling between 5. sklicevanje po začetnicah imena oziroma priimka av- scientific papers. American Documentation, 1963. torja, [9] I. V. Marshakova. System of document connections 6. nekateri študentje so se sklicevali na prilogo na enak based on references. način kot na vir, zato je naša programska rešitev na- http://garfield.library.upenn.edu/marshakova/ pačno razpoznala sklic. marshakovanauchtechn1973.pdf. Dostopano 8. 6. 2018. Probleme nam je povzročala tudi implementacija regularnih [10] H. Small. Co-citation in the scientific literature: a new izrazov. Problem je bil ta, da so avtorji včasih navajali in se measure of the relationship between two documents. sklicevali na vire na dva ali več različnih načinov. Potrebno 1973. je bilo zapisati vgnezdene regularne izraze (glej poglavje 3), ki so v nekaterih dokumentih delovali, v nekaterih pa ne. Ne- katere vgnezdene regularne izraze je bilo potrebno ločiti na več regularnih izrazov. Tako smo najprej preverili najpogo- steje uporabljene načine navedbe in sklicevanja virov, nato pa tiste manj pogoste, da smo tako pokrili čim več načinov navedb. 6. ZAKLJU ČEK Plagiatorstvo je zaradi čedalje lažjega dostopa do elektron- skih virov vse bolj pogosto. Skozi raziskovalno nalogo smo prikazali, kako bi znotraj dokumenta razpoznali literaturo in poiskali njihove sklice v besedilu. Vključitev takega načina preverjanja plagiarizma bi po našem mnenju veliko pripo- mogel k bolj natančni detekciji plagiata, saj veliko tistih, ki poizkusijo oddati plagiat, spremenijo vsebino, literatura pa ostane nespremenjena. Največja prednost našega pristopa je torej ta, da je pristop neodvisen od jezika, v katerem je dokument napisan. Z uspešnostjo našega pristopa smo zadovoljni, vendar je uspešnost razpoznave literature in kasneje določitve njiho- vih sklicev v besedilu v veliki meri odvisna od “pravilnosti” sestave dokumenta. Uspešnost bi lahko izboljšali tako, da bi zapisali še več bolj specifičnih regularnih izrazov in tako učinkoviteje razpoznali literaturo v različnih dokumentih. 7. LITERATURA [1] Kontingenčna tabela. https: //en.wikipedia.org/wiki/Contingency_table. Dostopano 10. 5. 2018. [2] Metrika f1. https://en.wikipedia.org/wiki/F1_score. Dostopano 10. 5. 2018. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 19 Klasifikacija samomorilskih pisem Dejan Rupnik Denis Ekart Gregor Kovačevič Fakulteta za elektrotehniko, Fakulteta za elektrotehniko, Fakulteta za elektrotehniko, računalništvo in informatiko računalništvo in informatiko računalništvo in informatiko Koroška cesta 46 Koroška cesta 46 Koroška cesta 46 Maribor, Slovenija Maribor, Slovenija Maribor, Slovenija dejan.rupnik@student.um.sidenis.ekart@student.um.si gregor.kovacevic@student.um.si Dejan Orter Alen Verk Borko Bošković Fakulteta za elektrotehniko, Fakulteta za elektrotehniko, Fakulteta za elektrotehniko, računalništvo in informatiko računalništvo in informatiko računalništvo in informatiko Koroška cesta 46 Koroška cesta 46 Koroška cesta 46 Maribor, Slovenija Maribor, Slovenija Maribor, Slovenija dejan.orter@student.um.si alen.verk@student.um.si borko.boskovic@um.si POVZETEK smo pridobili s spletnih strani [12, 3, 6, 4], lažna pa smo se- V našem delu smo se osredotočili na klasifikacijo poslovilnih stavili sami. Vsa pisma so v angleškem jeziku. Uporabili smo pisem samomorilcev. Pozornost smo posvetili na razpoznavo 63 pristnih in 19 lažnih pisem. Postopek analize pisem je po- pristnih pisem te narave, od pisem, ki to niso, oz. so le-ta la- tekal v več korakih. Prvi izmed njih je bilo predprocesiranje žna. S pomočjo procesiranja naravnega jezika in algoritmov besedila, kjer smo kot rezultat dobili prečiščeno besedilo (tj. strojnega učenja želimo doseči, da se pristna pisma v večini samo standardni znaki, brez simbolov in ločil). Nato smo ločijo od lažnih. Implementirali smo program v program- izvedli oblikoslovno označevanje besed in povezavo ključnih skem jeziku Python, pripravili korpus in izvedli nadzorovano besed s posameznimi koncepti iz tega področja. Naredili smo strojno učenje. Pisma smo klasificirali z metodami: Deci- statistiko posameznih pisem (povprečno število besed ipd.). sionTreeClassifier, SVC, GaussianProcessClassifier, AdaBo- Izvedli smo tudi teste berljivosti, kateri so izračunali dve ostClassifier, KNeighborsClassifier, RandomForestClassifier, različni metriki. Tudi te smo uporabili pri strojnem učenju. MLPClassifier, GaussianNB in QuadraticDiscriminantAna- Dodatno smo opravili tudi analizo čustev, nato pa vse rezul- lysis. Najboljše rezultate smo dosegli z odločitvenim dreve- tate združili v datoteke CSV. Te so bile osnova za gradnjo som, kjer smo dosegli 68% natančnost. odločitvenih dreves pri strojnem učenju. Uporabljeno je bilo nadzorovano strojno učenje. Rezultati eksperimenta so poka- zali, da je uporabljen pristop uspešno ločeval med pristnimi KLJU ČNE BESEDE in lažnimi pismi. klasifikacija samomorilskih pisem, procesiranje naravnega je- zika, odločitvena drevesa 2. SORODNA DELA V članku [10] so avtorji uporabili 66 poslovilnih pisem, od 1. UVOD katerih je bilo 33 pristnih in 33 lažnih. V raziskavi je prisos- Zaradi samomora vsako leto umre več kot 800.000 oseb (v tvovalo 11 strokovnjakov s področja mentalnega zdravja in Sloveniji več kot 300), približno 25-krat toliko pa jih samo- 31 psihiatrov pripravnikov. Zbrana mnenja so primerjali z 9 mor poskuša narediti [14][11]. Velikokrat, ko vidimo samo- algoritmi strojnega učenja: morilen zapis, smo v dilemi ali ta oseba misli resno ali pa je to poizkus iskanja pozornosti [7]. Nekatera pisma so tudi lažna - na primer pri umorih, kjer bi želel storilec prikazati, • LMT, da je žrtev storila samomor. Posledično je njihova klasifika- cija pomembna za preventivo ter za razreševanje morebitnih • LinSMO, nejasnosti. • Descision, Za samo izvedbo klasifikacije smo najprej potrebovali pristna • JRip, pisma samomorilcev ter lažna pisma. Korpus pristnih pisem • NB, • PART, • J48, • Logistic, • IB3 in • OneR. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.21-25 Ljubljana, Slovenia, 9 October 21 Kombinacija določenih algoritmov je v povprečju dala 78% 3.3 Test berljivosti natančnost. Specialisti izbranega področja so dosegli 63% Nad korpusom smo izvedli testa berljivosti po Flesch in natančnost, pripravniki pa zgolj 49% natančnost pri ločevanju Flesch-Kicaidovi metodi. Ocena berljivosti besedila (angl. pisem. Flesh score) smo izračunali po enačbi (1), kjer RE pred- stavlja enostavnost branja (angl. readability ease). V članku [2] so naredili študijo vsebine samomorilskih pi- RE = 206 , 83 − (1 , 015 ∗ ASL) − (84 , 6 ∗ ASW ) (1) sem ljudi, ki so samomor skušali storiti ter druge skupine ljudi, ki je samomor dejansko storila. Študijo so izvedli s V enačbi (2) ASL predstavlja povprečno dolžino stavka (angl. programom za tekstovno analizo, kateri uporablja jezikovno average sentence length). povpraševanje in štetje besed (angl. Linguistic Inquiry and stBesed Word Count). ASL = (2) stStavkov Članek [1] opisuje študijo samomorilskih pisem iz Mehike. V enačbi (3) ASW predstavlja povprečno število zlogov na Preučevali so vzorec 212 samomorov, kjer je 106 oseb napi- besedo (angl. average number of syllables per word). salo poslovilno pismo, ostalih 106 pa tega ni storilo. Ugoto- stZlogov vili so, da se osebnostne lastnosti tistih, ki poslovilna pisma ASW = (3) stBesed napišejo in tistih oseb, ki jih ne, pretirano ne razlikujejo. Višji je RE (ocena berljivosti besedila) manjša je kompleks- 3. PRIPRAVA BESEDILA nost besedila. Metoda vrne oceno berljivosti besedila (angl. readability score), katera je realno število med 0 in 100, 3.1 Predprocesiranje vendar pa zaradi napak v formatiranju lahko pride do od- Ko smo pripravili korpus s poslovilnimi pismi samomoril- stopanja. Ta odstopanja smo normalizirali na pričakovane cev, je bilo le-te potrebno pripraviti za nadaljnjo uporabo. vrednosti. Flesch-Kinicaid metoda nam pove nivo berljivosti Iz pisem smo odstranili ločila, številke ter vse ostale nestan- besedila in se izračuna po enačbi (4), kjer TW predstavlja dardne znake. Pri predprocesiranju besedila smo prav tako število vseh besed (angl. total words), TS je število vseh pretvorili velike črke v male. stavkov (angl. total sentences) in TSYL število vseh zlo- gov (angl. total syllables). Pričakovan rezultat je decimalno Algoritem 1: Priprava besedila. število med 0 in 13, katero sovpada s povprečnim nivojem Input : neobdelano besedilo ( besedilo) berljivosti v šolskih razredih v Združenih Državah Amerike. Output: obdelano besedilo ( izhod) Zaradi zahteve po številu besed v stavkih, smo teste bral- for znak in besedilo do nosti izvajali na osnovnem - neprocesiranem besedilu [13]. if znak=JE CRKA() then T W T SY L if znak= JE VELIKA() then RL = 0 , 39 ∗ ( ) + 11 , 8 ∗ ( ) − 15 , 59 (4) T S T W DODAJ V IZHOD(SPREMENI V MALO( znak)) Vrednosti RE in RL smo vključili v datoteko CSV. else DODAJ V IZHOD( znak) end 3.4 Analiza čustev else if znak=JE PRESLEDEK() then Za uspešno delovanje algoritma smo potrebovali tudi analizo DODAJ V IZHOD( znak) čustev. Ta nam iz vsakega pisma izlušči emocije, ki se jih da else if znak=JE OPUˇ S ˇ CAJ() then razpoznati na podlagi zapisanega besedila. Pri analizi smo DODAJ V IZHOD( znak) si pomagali z modulom WNAffect [5]. Procesirano besedilo end smo vstavili v funkcijo in kot rezultat dobili slovar čustev, ki end se pojavijo v besedilu ter vsoto njihovih magnitud. Na koncu smo iz vseh obdelanih pisem in pridobljenih unikatnih čustev ročno generirali statični slovar vseh emocij. 3.2 Oblikoslovno označevanje Za meritve povprečij in ostalih statističnih podatkov smo Algoritem 2: Pridobivanje čustev. naredili oblikoslovno označevanje (angl. parts of speech tag- ging), kjer smo implementirali tokenizacijo in označili besede function GetEmotion ( besedilo); glede na pomen v povedi. Vsaki besedi se je po zagonu algo- Input : označeno besedilo ( besedilo) ritma dodala oznaka, katera nam je povedala za kakšno vrsto wna=WNAffect() besede gre. Uporabili smo knjižnico NLTK [8]. Bila je do- for znacka in besedilo do dana podpora za večnitno delovanje, ker je lahko proces na if znacka != LO ˇ CILO then velikih korpusih časovno zelo potraten. Metoda z večnitnim custva=PRIDOBI ČUSTVA() delovanjem rezultatov ne shranjuje v spremenljivke v po- if custvo != NONE then mnilniku, temveč jih v datoteke na trdem disku. return ( znacka, custvo, stopnja) end end Po uspešni implementaciji algoritma smo sešteli vse poja- end vitve oznak ter naredili slovar povprečnih pojavitev določenih označb. Torej, koliko glagolov, ločil, samostalnikov itd., vse- buje povprečno pismo. Nato smo seznam označb normali- 4. ZDRUŽITEV REZULTATOV FUNKCIJ zirali na omejen nabor značk. Pridobili smo tudi statistiko Ko smo implementirali vse omenjene funkcije, smo morali za vsako posamezno pismo, kjer ohranimo podatek, kateri rezultate združiti ter jih pripraviti za strojno učenje. Rezul- slovar pripada kateremu pismu. tate smo zato združili v datoteke CSV. V prvo izmed datotek StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 22 Slika 1: Generirano odloˇ citveno drevo. smo po vrsticah shranili imena pisem, oznake, ocene ter nivo robnejši rezultati štirih najuspešnejših pa so predstavljeni v bralnosti in statistiko (št. besed, št. stavkov, itd.) za vsako poglavju 5.1: posamezno pismo. • DecisionTreeClassifier(max depth=5), V drugo datoteko smo shranili skupna povprečja vseh prist- nih in nepristnih pisem za vsakega izmed klasifikacijskih at- • SVC(kernel=”linear”, C=0,025), ributov posebej. Omeniti je potrebno, da so posamezne vred- nosti, kot na primer: značke oblikoslovnega označevanja in • GaussianProcessClassifier(1,0 * RBF(1,0)), magnitude posameznih čustev, normalizirane s številom be- • AdaBoostClassifier(), sed v besedilu. Tabela 1 prikazuje del datoteke povprecja.csv, ki vsebuje povprečja atributov. • KNeighborsClassifier(3), • SVC(gamma=2, C=1), 5. NADZOROVANO STROJNO U ČENJE Ko smo pripravili datoteki CSV smo se morali odločiti ka- • RandomForestClassifier(max depth=5, n estimators=10, tero vrsto strojnega učenja bomo uporabili. Uporabili smo max features=1), nadzorovano strojno učenje in zgradili odločitveno drevo, • MLPClassifier(alpha=1), prikazano na sliki 1. • GaussianNB() in Za generiranje odločitvenega drevesa smo uporabili knji- žnico sklearn [9], katera loči bazo klasifikacijskih podatkov • QuadraticDiscriminantAnalysis(). na učno in testno množico ter na dva vektorja klasifikatorjev. S pomočjo teh spremenljivk smo nato generirali napovedni 5.1 Rezultati model. Iz napovednega modela pa izračunali preciznost, pri- V sledečih tabelah so prikazani rezultati klasifikacije z upo- klic in mero F1. rabo različnih klasifikatorjev. Rezultati so bili izračunani iz povprečja 10.000 instanc klasifikacije, kjer se je vsakič na- Skupno smo uporabili deset različnih klasifikatorjev, pod- ključno izbralo 95% pisem za učno in 5% pisem za testno StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 23 priklic za 6% in mera F1 za 5%. Tabela 1: Povpreˇ cne vrednosti atributov, ki jih upo- rabimo pri strojnem uˇ cenju. Pristna pisma Nepristna pisma Tabela 2: Rezultati klasifikatorja DecisionTree. Ocena berljivosti 85,14 84,35 preciznost priklic mera F1 Nivo berljivosti 4,40 5,38 nepravilna 0,52 0,50 0,49 MD 0,02 0,02 pravilna 0,84 0,89 0,85 PRP 0,04 0,05 skupno povprečje 0,68 0,70 0,67 RB 0,06 0,07 NN 0,18 0,19 VBP 0,06 0,07 Tabela 3: Rezultati klasifikatorja SVC. JJ 0,09 0,09 IN 0,09 0,10 preciznost priklic mera F1 DT 0,08 0,6 nepravilna 0,27 0,27 0,27 Število besed 79,59 173,42 pravilna 0,77 1,00 0,86 Število zlogov 94,24 209,79 skupno povprečje 0,52 0,63 0,56 Število znakov 304,98 691,32 Število povedi 7,37 14,05 Upanje 0,02 0,00 Tabela 4: Rezultati klasifikatorja GaussianProcess. Ljubezen 0,05 0,02 preciznost priklic mera F1 Obup 0,01 0,00 nepravilna 0,38 0,34 0,35 Sreča 0,01 0,00 pravilna 0,80 0,94 0,85 Nejasnost 0,01 0,00 skupno povprečje 0,59 0,64 0,60 Spokojnost 0,02 0,00 Začudenje 0,02 0,01 Sproščenost 0,01 0,00 Zgroženost 0,01 0,00 Tabela 5: Rezultati klasifikatorja AdaBoost. Žalost 0,01 0,01 preciznost priklic mera F1 Odpuščanje 0,01 0,00 nepravilna 0,51 0,50 0,49 Dobrohotnost 0,01 0,00 pravilna 0,84 0,89 0,84 Stiska 0,01 0,00 skupno povprečje 0,68 0,69 0,67 Gotovost 0,01 0,00 Strah 0,01 0,00 Naklonjenost 0,01 0,00 množico. Instanca v našem primeru predstavlja naključno razdelitev pisem na učno in testno množico (iz nabora vseh pisem - pristnih in lažnih). Prikazani so rezultati preciz- nosti in priklica za posamezen razred, kot tudi povprečne vrednosti. Za mero F1 so izračunane povprečne vrednosti. Za tovrsten pristop testiranja smo se odločili zaradi majhne učne množice. Za najboljši klasifikator se je izkazala metoda odločitvenih dreves (angl. decision tree classifier), katera je dosegla 68% natančnost, ostale metrike pa so prikazane v tabeli 2. Za izračun povprečja je bilo v vseh tabelah uporabljeno makro povprečje. Tudi metoda AdaBoost se je izkazala kot zelo natančno, vendar je imela malenkost nižjo vrednost priklica. Pri našem testiranju se je tudi izkazala kot bistveno počasnejša, kot metoda odločitvenih dreves. Rezultati klasifikatorja SVC z linearnim jedrom so zapisani v tabeli 3, klasifikatorja GaussianProcess v tabeli 4 in rezultati klasifikatorja AdaBoost v tabeli 5. Po analizi klasifikatorjev smo odločitveno drevo še grafično predstavili v formatu PDF. Po pregledu korenov smo ugo- tovili, da izločanje določenih atributov vrne boljše rezultate. Najboljše rezultate smo dosegli pri izločitvi atributov za šte- vilo znakov, besed in črk. Preciznost je bila izboljšana za 4%, StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 24 6. ZAKLJU ČEK več kot 300 ljudi, a zaznati je upad tega žalostnega V tem delu smo se osredotočili na klasifikacijo samomoril- dejanja, 2017. nih pisem. Program pisma analizira postopoma. Najprej nad [12] J. Russel. A collection of suicide notes & letters - korpusom izvedemo predprocesiranje besedila, da dobimo russel’s cyber journal, 2008. čisto besedilo (same male črke, brez ostalih znakov). Nato [13] stephenhky. Flesch-kincaid readability measure - se izvede oblikoslovno označevanje besed in statistika posa- everything about data analytics big data, data meznih pisem. Opravili smo tudi test berljivosti besedila, ki analytics, 2016. ga uporabimo pri strojnem učenju. Analiziramo tudi čustva, [14] Wikipedia. Suicide, 2018. nato pa vse skupaj združimo v datoteko CSV in izvedemo nadzorovano strojno učenje. Kot je razvidno iz rezultatov smo zadani projekt razpoz- nave pristnih poslovilnih pisem uspešno izvedli. Po podat- kih avtorjev članka [10] so strokovnjaki s področja psiholo- gije dosegli 63% natančnost, medtem ko naša metoda vrača rezultate z 68% natančnostjo. Tukaj je pomembno opozoriti, da v našem članku nismo upo- rabili istega nabora pisem, kot so ga avtorji prej omenjenega članka. Posledično rezultatov naših eksperimentov ni mogoče neposredno primerjati z rezultati v sorodnih člankih. Pri- dobitev pristnih in lažnih pisem, ki ustrezajo pogojem, je izredno zapleteno opravilo, pri katerem bi za večjo zaneslji- vost pri zagotavljanju norm potrebovali ustrezno usposobl- jene osebe, ki bi obenem imele dostop do tovrstnih arhivov. V prihodnosti bi lahko metodo razširili tako, da ne bi bila omejena samo na angleški jezik. Izboljšave bi tudi prinesla večja množica pisem in dodatne metode za ocenjevanje struk- ture besedila. 7. VIRI [1] L. A. L. L. Chávez-Hernández AM1, Páramo D. Suicide notes in mexico: what do they tell us? Suicide Life Threat Behav, 36:709–15, December 2006. [2] L. D. Handelman LD. The content of suicide notes from attempters and completers. Oxford University Press, 28:102–104, 2007. [3] J. Harper. A collection of real suicide notes | historic mysteries, 2015. [4] A. A. Leenaars. Suicide notes in the courtroom. 1999. [5] C. Michard. clemtoy/wnaffect a python module to get the emotion of a word., 2017. [6] O. P. M. Mukta Rani, Shalini Girdhar. Suicide note: The last words. 2015. [7] NIJZ. Svetovni dan preprečevanja samomora: ”vzemi si trenutek, reši življenje”, 2017. [8] NLTK. Natural language toolkit, 2017. [9] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011. [10] J. Pestian, H. Nasrallah, P. Matykiewicz, A. Bennett, and A. Leenaars. Suicide note classification using natural language processing: A content analysis. Biomedical Informatics Insights, 2010:19–28, August 2010. [11] Politikis. Zaradi samomora vsako leto v sloveniji umre StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 25 Na črtovanje poprocesorja za pretvorbo NC/ISO G-kode v translacije za 3/5 osnega robota ACMA ABB XR701 ∗ † Gregor GERMADNIK Timi KARNER Klemen BERKOVI Č Fakulteta za elektrotehniko, Fakulteta za strojništvo Fakulteta za elektrotehniko, računalništvo in informatiko Smetanova ulica 17 računalništvo in informatiko Koroška cesta 46 2000 Maribor, Slovenia Koroška cesta 46 2000 Maribor, Slovenia timi.karner@um.si 2000 Maribor, Slovenia gregor.germadnik klemen.berkovic1@um.si @student.um.si Iztok FISTER Fakulteta za elektrotehniko, računalništvo in informatiko Koroška cesta 46 2000 Maribor, Slovenia iztok.fister@um.si POVZETEK 1. UVOD V moderni dobi imamo na voljo večje število robotov, ki pre- V preteklosti se roboti v industriji niso tako številno upora- vzemajo vedno večje število opravil v industriji, saj so poceni bljali kot pa se v sedanjem svetu industrije, saj so jih preka- in preprosti za montažo. Po navadi je potrebno z dobavo ro- šali t.i. računalniško-numerično krmiljeni stroji (angl. Com- bota kupiti tudi programske pakete oz. programsko opremo, puter Numerical Control, krajše CNC), ki že imajo točno do- ki omogoča programiranje robotovih funkcij, ter predstavlja ločeno natančnost in zagotavljajo dolgoročno ponovljivost. največji strošek nakupa. V tem članku zato prikazujemo, Z razvojem krmilnikov PID (angl. Proportional–Integral kako z implementacijo poprocesorja za pretvorbe NC/ISO –Derivative controller ) in harmoničnih gonil, ki zagotavljajo G-kode v translacije 3/5 osnega robota ACMA proizvajalca natančnejše določanje položajev osi robota, je robotizacija ABB model XR701 ta strošek zmanjšamo. Cilji doseženi v zacvetela. Danes se lahko nekateri roboti že približajo eno- članku so: razvoj poprocesorja, ki z linearno algebro in z stavnejšim strojem CNC, vendar jih zaradi reguliranja več razčlenjevanjem pretvori program za rezkanje kompleksnej- prostorskih stopenj težko presegajo. Zato se roboti večinoma ših oblik večjih dimenzij, pohitritev nastavitve in pretvorbo uporabljajo za manj natančne ponovljive, nevarne, težke in kode z uporabo uporabnikom prijaznega vmesnika izdela- velikokrat monotone operacije, ki zmanjšujejo poklicne bo- nega v programski opremi Visual Studio 2017 CLI (angl. lezni pri človeku. Zaradi eksponentne rasti novih robotov Combined Language Infrastructure) in programskim jezikom in njihove pripadajoče programske opreme je postala upo- C++. Glavni dosežen cilj članka je varčevanje pri nakupu raba starejših modelov robotov različnih proizvajalcev vse licence programske opreme za pretvarjanje ISO G-kode v zahtevnejša. Nova programska oprema se ne ujema več z robotsko kodo. mehanskimi lastnostmi robota, kar omejuje nakup robota istega proizvajalca. Kjučne besede stroj CNC, programski jezik C++, ISO G-koda, linearna Za vodenje robotov oz. strojev CNC uporabljamo program algebra, program NC, poprocesor, robot NC pridobljen s poprocesiranjem položajev orodja (angl. Cutter Location, krajše CL). Poprocesor je opredeljen kot vmesno orodje in omogoča obdelavo podatkov med program- sko opremo za računalniško podprto načrtovanje (angl. Com- puter Aided Design, krajše CAD) in računalniško podprto ∗Dopisni avtor proizvodnjo (angl. Computer Aided Manufacturing, krajše † CAM), ki pripravi program za proizvodne stroje. Z njim za- Pomoč pri upravljanjem robota ACMA XR701 gotavljamo vodenje proizvodnega stroja glede na načrtovan izdelek in je unikaten glede na mehanske lastnosti stroja. Na področju našega raziskovalnega dela lahko najdemo na- slednja sorodna dela. Sekirnik [11] v svoji diplomski nalogi opisuje, kako s programsko opremo Siemens NX 8.5 popro- cesira podatke s sistemov CAD in CAM v G-kodo s pomočjo programa, narejenega v programski opremi Microsoft Office Excel, in kot izhod generira numerični program za dodajanje točk. Nastavitev izhodnega programa in robota je zahtevna StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.27-33 Ljubljana, Slovenia, 9 October 27 naloga, saj je potrebno imeti predznanje tako o robotu kakor Njegovi glavni členi so prikazani na Sliki 1. tudi o formatu numeričnega krmilnega programa. V magistrskem delu Filipič [2] opisuje uporabo program- ske opreme RobotStudio, kjer se v virtualnem okolju ustvari model robota ACMA XR701, ki omogoča učenje robota brez poseganja v industrijske procese. Izhodni program je zapi- san s programsko kodo ABB, iz katere avtor poprocesira vrednosti za robotsko kodo ACMA iz ukazov MoveJ in Mo- veL. Magistrsko delo Nilssona [8] in članek [10] po drugi strani opisujeta, kako lahko z ukazov G2 in G3 v G-kodi generiramo ukaz MoveC za krožni gib robota ABB. V našem članku opisujemo razvoj dodatnega poprocesorja, ki s pridobljeno kodo (tj. programom NC ali ISO G-kodo) izvede ponovno pretvorbo v numerični jezik razumljiv pro- Slika 1: Prikaz robota ACMA ABB XR701 [3] gramu za dodajanje točk. Vhod predlaganega poprocesorja je program v NC oz. ISO G-kodi za 3/5 osnega robota in podatki obdelave (npr. lokacija polizdelka in postavitev Legenda: mehanizma) pridobljenih s pomočjo grafičnega uporabiškega vmesnika (angl. Graphical User Interface, krajše GUI). Ta 1. Podstavek robotskega 8. Tretji člen robota (3. os) s pomočjo razčlenitve izlušči s programa translacije in iz po- mehanizma 9. Motor z gonilom (4. os) datkov GUI strukturira numerični program za učenje točk 2. Motor z gonilom (1. os) 10. Sklep drugega in robota. Obdelava kode 5 osnega robota je zelo preprosta, 3. Vrtljivo podnožje tretjega člena (5. os) saj podatke izlušči in jih ustrezno oblikuje glede na G ukaze 4. Motor z gonilom (2. os) 11. Pritrdilna prirobnica in podatke obdelave. Težava se pojavi pri kartezični G-kodi 5. Protiutež (6. os) za 3 osnega robota, kjer je krožna giba ukazov G2 in G3 6. Ravnotežna vzmet 12. Prenosna konzola potrebno preoblikovati v dovolj majhne translacije oz. inter- 7. Drugi člen robota 13. Krmilna omara polacije, ki ustrezajo natančnosti robota. Ta problem smo rešili z izračunom ustreznih vektorjev glede na ukaz krožnega 2.1 Primerjava CNC stroja z robotom giba. Določitve kota med dvema vektorjema smo izračunali Z vidika avtomatizacije je obdelovalni stroj CNC avtomati- s funkcijo atan2 (inverzni tangens 2) izpeljano s pomočjo tri- ziran sistem, ki samostojno obdeluje polizdelek po zapisani gonometričnih funkcij in določanjem točk krožnega izseka z ISO G-kodi ali programu NC. Najpreprostejši obdelovalni rotacijsko matriko. Po poprocesiranju je treba ponovno ob- stroji omogočajo pomikanje v smeri x, y in z (3 osni stroji). delati podatke s programom, ki iz programa za učenje točk Imenujemo jih kartezični, saj so brez rotacijskih osi in težko pretvori točke v numerični jezik robota. obdelujejo kompleksnejše oblike, razen v primeru uporabe kroglastega rezkarja. Z dodajanjem dodatnih osi oz. rotacij Struktura članka je v nadaljevanju naslednja. V poglavju 2 lahko obdelujemo kompleksnejše oblike. Zaradi njihove to- predstavimo robota ACMA XR701. Opis predlagane reši- gosti dosegajo večjo natančnost in ponovljivost ter manjšo tve je vsebina poglavja 3. Rezultati so predstavljeni v po- obrabo kot roboti [5]. Njihova slabost je majhen delovni pro- glavju 4. Članek zaključimo s poglavjem 5, kjer povzamemo stor za večji delovni prostor je treba povečati konstrukcijo opravljeno delo in napovemo možnosti za nadaljnje delo. stroja in izbrati material in obliko elementov konstrukcije, ki so odporni na upogib za doseganje dobre natančnosti. 2. ROBOT ACMA XR701 Zaradi njegovega pravokotnega delovnega prostora in kon- Robot ACMA XR701 je bil zasnovan leta 1994 v podjetju strukcije prav tako težko opravlja zahtevnejše obdelovalne Renault Automation. To je antropomorfni industrijski robot položaje, s čimer pa robot nima težav, saj je delovni prostor s šestimi prostostnimi stopnjami in velikim delovnim prosto- po katerem ga lahko poljubno vodimo sferičen in dostopen rom. Razvili so ga za manipulacijo, strego in sestavo, zaradi s poljubno postavitev robota. njegove zanesljivosti, hitrosti in natančnosti pa ga upora- bljamo predvsem za uporovno varjenje. Omogočal je uspe- 2.2 Poprocesor za pretvorbo G-kode šne avtomatizirane rešitve tudi v kosovni proizvodnji. [3] Obdelovalni stroji postajo vedno bolj zahtevni, saj se v indu- striji pogosto uporabljajo površine poljubnih oblik. Ročno Robot je v obliki paralelograma, ki omogoča večjo nosilnost programiranje kompleksnejših površin je v tem primeru ne- zaradi večje vztrajnosti in nižjega težišča. [1, 6] Premešča smiselno. Zato se v ta namen uporablja programska oprema mase na šesti osi od 125 kg do 270 kg. Zgornja roka je lahko za pretvorbo modela CAD v ISO G-kodo ali program NC obremenjena z največjo maso do 160 kg. Vse osi so opre- 3/5 osnega obdelovalnega stroja. Pri tem mesto rezila CL mljene s trifaznim sinhronim električnim brezkrtačnim mo- pridobivamo neposredno z modela CAD, ki smo ga popro- torjem Brushless, ki omogočajo hitrosti do 3 m/s. Motorji cesirali v programski opremi CAM. so opremljeni z resolverji, ki v vsakem trenutku daje infor- macijo o položaju osi. Za doseganje večje natančnosti ima Pri komunikaciji med sistemom CAD/CAM in strojem NC vsak servomotor vgrajeno dodatno elektromagnetno zavoro lahko večkrat pride do težav zaradi nekompatibilnosti, zato in reduktor [3]. Zaradi starosti robota in obrabe mehanskih je potrebno za vsako orodje oz. stroj ustvariti unikaten po- elementov je natančnost robota 0, 3 mm. procesor oz. vmesnik za pretvorbo podatkov CL v ustrezen StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 28 numerični strojni jezik [4]. V našem primer smo to izvedli manj specifične nastavitve, kot sta, na primer, natančnost z implementacijo poprocesorja, ki pretvori G-kodo oz. pro- robota in nastavitev natančnosti števil s plavajočo vejico, gram NC v točke za učenje robota ACMA in z obsoječim kjer nastavimo število decimalnih mest koordinat. Z GUI programom pretvori pridobljene točke v numerični strojni smo z aplikacijskimi vmesniki (angl. Application Program- jezik ACMA. Proces pretvorbe prikazuje Slika 2. ming Interface, krajše API) izvajali pretvorbo, pridobivali vhodno G-kodo in shranjevali pridobljen programa ACMA za učenje točk in razčlenjeno G-kodo s klikom na gumb. Za razvoj vmesnika smo uporabili programsko okolje Visual studio 2017 in izdelali GUI s pomočjo programskega paketa Windows Forms C++/CLI, ki ga ponuja uporabljeno ra- zvojno okolje. C++/CLI je jezikovna specifikacija, ki jo je razvil Microsoft je namenjena nadomeščanju upravljalnih (angl. Managed ) razširitev za C++ [7, 9], katere namen je poenostaviti starejšo upravljalno sintakso C++, ki je zdaj opuščena. C++/CLI je standardizirana v standard ECMA- 372. Trenutno je na voljo, kot programski paket za Visual Studio 2005 - 2017, vključno z izdajami Express. 3.2 Pretvorba G-kode v program robota ACMA Pretvorba G-kode v program 3/5 osnega robota ACMA te- melji na uporabi standardnih knjižnic, ki nam olajšajo delo s pisanjem funkcij. To je zbirka razredov in funkcij napisanih v baznem jeziku C++. Osnovo pretvorbe predstavlja razred Pridobitev Koordinat, ki je opremiljen z javnimi metodami za arhiviranje, upravljanje s spremenljivkami pridobljenih iz vhodne G-kode oz. programa NC in podatkov iz GUI. Vse- buje tudi zasebne metode za pridobivanje vrednosti iz vho- Slika 2: Prikaz pretok podatkov dnih podatkov, zasebne metode za preračunavanje krožnih gibov v ustrezne interpolacije. Delovanje glavnega aplikacij- skega vmesnika ”Pretvori vhodno G-kodo” je predstavljeno Zaradi enostavnosti uporabljamo programsko opremo CA- s Psevdokodom 1. Kjer spremenljivke z velikimi tiskanimi D/CAM, ki že pripravi G-kodo oz. program NC glede na črkami predstavljajo sistemski nizi pridobljen iz vmesnika uporabljeno orodje. Za pretvorbo G-kode v jezik za uče- GUI. Psevdokod 1 vsebuje tudi klice javnih metod, katerih nje robota ACMA moramo vhodno kodo razčleniti in po ime je ločen s podčrtaji. potrebi s pomočjo interpolacije izračunati dodatne točke gi- bov. Izhodno kodo, ki predstavlja program za učenje točk robota, mora biti tudi primerno strukturirana. Po obdelavi, Algoritem 1 Aplikacijski vmesnik za pretvorbo G-kode program za učenje točk ponovno pretvori kodo v numerično 1: String∧ AcmaIzpis, GkodaIzpis; robotsko kodo ACMA. 2: Pridobitev Koordinat Koord; 3: Koord.Vhodni Podatki(VHGKODA, NATANC, RELX, 3. RAZVOJ POPROCESORJA RELY, RELZ, RELA, RELB, RELC, STDEC, V, A, Razvoj poprocesorja za pretvorbo G-kode v robotski jezik RAMA, KOMOLEC, ZAPESTJE); 3/5 osnega robota ACMA je sestavljen iz treh faz: 4: OUTACMA->Clear(); 5: OUTGKODA->Clear(); • kreiranje uporabniškega vmesnika, 6: AcmaIzpis = Koord.Izpis Glave Prog ACMA(); • pretvorbe G-kode v program robota ACMA 7: OUTAACMA->AppendText(AcmaIzpis); • evaluacija. 8: Koord.Clear Data(); 9: while Koord.Zakljucni Znak() is not ture do 10: Koord.Pridobitev Vrstice(); V nadaljevanju opisujemo omenjene faze podrobneje. 11: if Koord.P razna V rstica() is not true then 3.1 Uporabniški vmesnik 12: AcmaIzpis = Koord.Izpis Koord Prog ACMA(); 13: GkodaIzpis = Koord.Izpis Vrstice Gkode(); Težave v modernem svetu so vidne pri kompleksnost naprav 14: Koord.Prepis Podatkov(); in programov, saj jih praviloma uporabljajo manj izobraženi 15: OUTGKODA->AppendText(GkodaIzpis); kadri. Zato se za pohitritev in zmanjševanje napak pri krmi- 16: OUTAMCA->AppendText(AcmaIzpis); ljenju strojev CNC in robotov ACMA uporablja namenski 17: Koord.Clear Data(); uporabniški vmesnik, v našem primeru predstavljeni kot gra- 18: end if fični uporabniški vmesnik, ki natančno opredeli nastavljanje 19: end while parametrov stroja in s tem olajša njegovo uporabo. 20: AcmaIzpis = Koord.Izpis Noge Prog ACMA(); 21: OUTACMA->AppendText(AcmaIzpis); V našem primeru smo razvili GUI, preko katerega lahko 22: Koord.Clear Data(); nastavimo položaj polizdelka, konfiguracijo robota in druge StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 29 Omenjeni vmesnik GUI se sestoji iz treh glavnih delov: Algoritem 2 Psevdokoda za določanje sekvence za nasta- vitev konfiguracije robota 1: if Rama is Levo then • zajem podatkov in strukturiranje numeričnega programa 2: AcmaIzhod.append(”13 +0 13 +0\n”); ACMA za učenje točk, 3: else if Rama is Spredaj then • razčlenjevanje podatkov in preverjanje zapolnjenost vr- 4: AcmaIzhod.append(”13 +0\n”); stice in 5: end if • pretvorba krožnih izsekov v translacije, kjer je to po- 6: if Komolec is Zgoraj then trebno. 7: AcmaIzhod.append(”@77 13 +0\n”); 8: end if V nadaljevanju članka opisujemo omenjene glavne dele po- 9: if Zapestje is N izko then drobneje. 10: AcmaIzhod.append(”@77 @77 13 +0\n”); 11: end if 3.2.1 Zajem podatkov in struktura numeričnega pro- grama za učenje točk za robota ACMA XR701 Pri določitvi konfiguracije je potrebno biti pozoren na trans- Robota ACMA programiramo prek medija (magnetno zapi- formacijo koordinatnega sistema, saj se pri normalni konfi- sana zgoščenka) s sintakso za dodajanje točk. Za programi- guraciji (Rama:levo, Komolec:zgoraj in Zapestje:nizko) ko- ranje moramo zapisati v niz določeno zaporedje znakov za ordinatni sistem robotske celice transformira os x za 180◦ dodajanje točk linearnih gibov oz. translacij. V ta namen in os z za 180◦ v koordinatni sistem orodja, prikazano na strukturiramo glavo, vsebino točk in nogo programa in je Sliki 5. zgrajena z zaporedja klikov, ki so opredeljeni v Tabeli 1. Tabela 1: Vrednosti tipk konzole za programiranje robota ACMA Izbira menija ’x’ F1 @59 Vrednost ”x” F6 @64 Tab 09 F9 @67 Enter 13 F10 @68 Esc 27 Tipka desno @77 Ničelno točko polizdelka, postavitev robota, točke gibov oz. translacij in druge manj pomembne podatke pridobimo z javno metodo Vhodni Podatki. Te podatke pridobimo prek GUI in jih arhiviramo v razred Pridobitev Koordinat. Pred uporabo je nize potrebno ustrezno pretvoriti glede na upo- rabo zasebnih metod. Z metodami Izpis Glave Programa ACMA, Izpis Koordinat Programa ACMA, Izpis Vrstice G kode in Izpis Noge Programa ACMA polnimo niz znakov, glede Slika 5: Koordinatni sistemi robota [3] na strukturo opredeljeno s Sliko 3 in Sliko 4 ter z Algorit- mom 2, ki vrnejo sistemski niz za izpis v bogato tekstovno polje RichTextBox. Za ponoven izpis smo z javno metodo Vsebina programa ACMA je sestavljena z vpisovanjem točk Clear Data počistili spremenljivki za izpisovanje izhodne G- in poteka na enak način, kot dodajanje ničelne točke. Raz- kode in programa ACMA za učenje točk ter priredili spre- likuje se v tem, da še dodamo hitrost v in pospešek a prika- menljivkam znotraj razreda vrednost 0, ki določajo prazno zano na Sliki 6. vrstico in pridobivajo vrednosti posamezne koordinate, ki opisuje podpoglavje 3.2.2. @64 " X "09 " Y "09 " Z "09 " A "09 " B "09 " C " + @68 13 +0 " v " 13 +0 " a " 13 +0 27 27 +0 27 +0 ’3 ’ +0 ’1 ’ +0 @80 @80 @80 @80 @80 @80 @80 @80 +0 13 Slika 6: Sekvenca za določanje točk, hitrosti in po- 13 13 13 27 speška @64 " x "09 " x "09 " x "09 " x "09 " x "09 " x " + @68 Slika 3: Sekvenca za nastavitev ničelne točke Noga zaključi program s sekvenco prikazano na Sliki 7. ’8 ’ @77 13 +0 13 +0 @77 @77 @77 13 +0 27 27 27 27 27 +0 @59 Slika 4: Sekvenca za nastavitev načina dodajanje Slika 7: Sekvenca noge programa ACMA za doda- koordinat janje točk StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 30 3.2.2 Razčlenjevanje podatkov in preverjanje zapol- Algoritem 5 Preverjanje zapolnjenost vrstice njenost vrstice 1: if StP raznihP olj is 10 or (V pisanP odatek[0] is true Za dodajanje novega izdelka v industriji operater brez pred- and StP raznihP olj is 9) then znanja težko uporablja G-kodo različnih struktur. V ta na- 2: PraznaVrstica = true; men smo strukturirali metodo za branje ključnih podatkov 3: else s poljubnih G-kod. 4: PraznaVrstica = false; 5: for i ∈ 0, · · · , 6 do Za razčlenjevanje podatkov niza smo napisali javno metodo 6: if V pisanP odatek[i] is f alse then Pridobitev Vrstice, ki preverja znake vrstice do ukaza G, 7: Vrstica[i] = PredhodnaVrstica[i]; nato se preverjanje nadaljuje do parametrov X, Y , Z, A, 8: end if B, C, I, J in K kar je prikazano v Algoritmu 3. Za vsak 9: end for parameter se z zasebno metodo Pridobi Vrednost zapisu- 10: end if jejo znaki v medpomnilnik, dokler so enaki številom, piki ali minusom. Metoda vrne medpomnilnik, ki se pretvori v tip 3.2.3 Pretvorba krožnih izsekov G2 in G3 (long double), s pomočjo funkcije stof (angl. string to float ), prikazano v Algoritmu 4. Kot je bilo že omenjeno, v GUI dodajamo program NC za 3/5 osnega robota. Program za 5 osnega robota preprosto vrednosti polja Vrstica prišteje nastavitev robota in struk- turira izhodni program ACMA za dodajanje linearnih točk Algoritem 3 Razčlenjevanje vhodne G-kode z določenimi rotacijami. Določanje koordinat gibov v pro- 1: while T renutniZnak is not \n do gramu NC za 3 osnega robota je zahtevnejše, saj je potrebno 2: if T renutniZnak is G za ukaza G2 oz. G3, ki predstavljata krožni izsek, določiti and (N aslednjiZnak is Stevilo 0 − 3) then ustrezne interpolacije oz. odseke in jih definiranti glede na 3: Nastavi na naslednji znak; natančnost robotovih gibov. V ta namen smo napisali za- 4: Vrstica[0] = Trenutna vrednost; sebni metodi G2 Algebra in G3 Algebra za izračun giba G2 5: UkazInicializiran = true; ter G3. 6: UkazVpisan[0] = true; 7: Zmanjšaj StPraznihPolj; Za izbiranje izpisa se je uporabila izjava (switch case), ki 8: end if glede na vhodno celo število G ukaza (0, 1, 2, 3) izvede do- 9: if T renutniZnak is X ločen primer. G0 in G1 izpišeta vhodne podatke v izhoden and N aslednjiznak is Stevilo niz z ustrezno strukturo in ukaza G2 in G3 se pred izpisom and U kazV pisan[0] is true pretvorita v ustrezne translacijske gibe. and U kazInicializiran is true then 10: Nastavi na naslednji znak; Za lažjo predstavo smo pretvorbo G2 in G3 krožnega giba 11: Vrstica[1] = Pridobi Vrednost(); predstavili z realnim primerom, prikazanim na Sliki 8 in 12: UkazVpisan[1] = true; Sliko 9. 13: Zmanjšaj StPraznihPolj; 14: end if N0 G1 X0 Y0 15: //Ponovitev za parametre Y, Z, A, B, C, I, J, K N1 G2 X5 Y5 I0 J5 16: Nastavi na naslednji znak; N2 G3 X10 Y10 I5 J0 17: end while Slika 8: Primer NC programa Algoritem 4 Pridobivanje vrednosti parametrov 1: string Medpomnilnik; 2: while T renutniZnak is Stevilo do 3: Medpomnilnik += TrenutniZnak; 4: Nastavi na naslednji znak; 5: end while 6: Nastavi na prejšnji znak; 7: return stof(Medpomnilnik); Slika 9: Primer G-koDE oz. NC programa krožnega Za določanje prazne vrstice preverimo polje binarnih vredno- izseka G2 in G3 sti UkazVpisan in StPraznihPolj pridobljenih v Algoritmu 3. Če pogoji, ki so predstavljeni v Algoritmu 5 veljajo, vrstico preskočimo oz. je ne izpišemo. To je prikazano v Algoritmu 1 Izračun interpolacij oz. odsekov bomo izvedli z linearno z javno metodo Prazna Vrstica, ki vrne dvojiško vrednost. algebro in trigonometričnimi funkcijami iz študijske litera- StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 31 ture [12]. Iz podatkov določimo vektorja, ki izhajata s sre- dišča krožnega izseka do predhodnih koordinat ZV (začetni vektor) ter do trenutnih koordinat KV (končni vektor) pri- kazana na Sliki 9. Začetni vektor je definiran kot nasprotna smer vektorja. x    zv i ZV = y = − j (1)  zv    zzv k Končni vektor, ki je definiran kot razlika začetne oz. pred- hodne koordinate in vektorja središča krožnega izseka od trenutne koordinate. Slika 10: Prikaz izpeljave inverznega tangensa 2 x        kv x xpred i KV = y = y − y − j (2)  kv     pred    zkv z zpred k θ l = 2 · π · r · (8) 360 Radij krožnega izseka se izračuna s pomočjo skalarnega pro- dukta in sicer dolžina vektorja ~ a z vrednostmi i, j in k raz- S tem izračunamo število interpolacij z dolžino loka v odvi- vidno s Slike 9. snosti od natančnosti robota in določimo kot interpolacije s kotom med vektorjema v odvisnosti od število interpolacij. Preostane nam še izračun posamezne interpolacije, ki se iz- q p r = |~ a| = a2 + a2 + a2 = i2 + j2 + k2 (3) vede z rotacijsko matriko. Pri tem je treba paziti, po kateri 1 2 3 ravnini potuje krožni gib razvidno z G-kode in Algoritma 6. Kot med vektorjema θ je razlika od inverznega tangensa za- Algoritem 6 Določanje delovne površine četnega vektorja in končnega vektorja. Kot vektorja je izra- 1: if I is N otDef ined then žen v radianih, med - π in π prikazano s Enačbo (4). 2: Delovna površina YZ y 3: else θ = arctan (4) 4: if J is N otDef ined then x 5: Delovna površina XZ 6: else Pri tem so se pojavile težave, če je bila vrednost imenovalca 7: Delovna površina XY x enaka 0, saj takrat ulomek ni definiran. 8: end if 9: end if Za rešitev težave s Slike 10 predpostavimo, da velja y = sin θ in x = r + cos θ in določimo novo Enačbo (5) ter jo preuredimo v Enačbo (6). S pomočjo skalarnega produkta Za naš primer sta pri G2, krožni gib v smeri urnega kazalca, in Pitagorovega izreka izračunamo polmer krožnega izseka podana parametra I in J, za katerga sledi Enačba (9). in s tem dobimo končno Enačbo (7). x   cos θ sin θ 0 x  θ y inter zv = arctan (5) y = −sin θ cos θ 0 · y (9)  inter     zv  2 r + x zinter 0 0 1 zzv Za gib G3 proti smeri urinega kazalca preoblikujemo rota- θ arctan (x, y) = θ = 2 (6) cijsko matriko po Enačbi (10). 2 x      inter cos θ −sin θ 0 xzv y θ = 2 arctan (7) y = sin θ cos θ 0 · y (10)  inter     zv  px2 + y2 + x zinter 0 0 1 zzv Z Enačbo (8) lahko iz obsega kroga določimo lok l oz. krožni V ravninah XZ in Y Z uporabljamo G2 in G3 za gibanje v izsek kota θ. obliki vijačnice (angl. Helix ). Program ACMA se lahko v StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 32 teh ravninah uporabi za ukaza G2 in G3 v obliki krožnega možnost je uporaba MSLU (angl. Microsoft Layer for giba, ki ni standardiziran in giba potujeta v smeri osi z. Unicode) za operacijske sistemom Windows 95, 98 in S tem je treba prilagoditi tudi rotacije robota. Če imamo Me, ki bi omogočala delovanje zgrajenega programa. krožni gib v ravnini XZ, prilagajamo rotacijo okoli osi x (ro- tacija Rψ), če imamo gib v ravnini Y Z, prilagajamo rotacijo 5. ZAKLJU ČEK okoli osi y (rotacija Rθ). To izvedemo z izračunom kota in- Članek opisuje razvoj poprocesor za pretvorbo G-kode, ki terpolacije po Enačbi (10) in tega prištejemo oz. odštejemo omogoča translacije za 3/5 osnega robota ACMA. Omenjeni od ustrezne rotacije robota. S tem dosežemo, da je rezkar poprocesor izpolnjuje vse predpostavke, ki smo si jih zadali vedno pravokoten na obdelovalno površino in se enakomerno na začetku raziskovalnega dela. obrablja orodje ter odvzema material, kar posledično vpliva na kakovost obdelave. Seveda bi ga lahko izboljšali tako, da bi združili poprocesor G-kode in pretvorbo v numerični programski jezik ACMA. 4. POSKUSI IN REZULTATI Tako bi lahko robotu ACMA implementiral neposredno po- Poprocesor za pretvorbo G-kode je kompleksna aplikacija, vezavo preko serijske komunikacije, če robot to omogoča, in saj njegova izdelava traja dlje časa in zahteva popolno po- ga poljubno programirali oz. vodili. S tem bi omogočili znavanje stroja, za katerega program načrtujemo. V simula- hitrejše prilagajanje programa in zmanjšali čas priprave, ki cijah deluje idealno, vendar teorija in praksa vedno ne gresta najbolj vpliva na ekonomičnost, saj med tem časom robot z roko v roki. V praksi običajno hitro naletimo na nepred- stoji. videne težave. Iz rezultatov poskusov lahko izluščimo nasle- dnje ugotovitve: Pri implementaciji ukazov G2 in G3 bi lahko kodo skrajšali tako, da bi prek serijske komunikacije neposredno programi- rali z ABB programskim jezikom, če robot to omogoča. Za 1. Za izdelavo poprocesorja in vmesnika GUI je potrebno dodajanje giba MoveC bi lahko pri določanju vmesne tretje obsežno znanje programiranja v jeziku C++/CLI ter točke krožnega giba uporabili enačbe s poglavja 3.2.3. dobro poznavanje programskega okolja Visual Studio 2017. 6. VIRI IN LITERATURA 2. Prvotno je bil poprocesor zapisan tako, da je celotno [1] T. Bajd, M. Mihelj, J. Lenarčič, A. Stanovnik, and vhodno in izhodno G-kodo skupaj z generiranem pro- M. Munih. Robotika. Fakulteta za elektrotehniko, gramom ACMA shranjeval v pomnilnik. To je zah- 2008. tevalo 3-krat več pomnilnika od izboljšane verzije, ki [2] M. Filipič. Posredno programiranje robota ACMA obdeluje vrstico po vrstico in jo sproti izpisuje. To se XR701. Magistrsko delo, Univerza v Mariboru, pravi, da pri vsaki vrstici prepiše predhodne podatke Fakulteta za elektrotehniko, računalništvo in in jih med delovanjem izpisuje na izhodno mesto (bo- informatiko, 2014. gato tekstovno polje), kar privarčuje pomnilnik. [3] F. Klobučar and J. Zgonc. Robotika: Vodenje in programiranje robota ABB XR701. 3. S programiranjem poprocesorja smo imeli težave z pri- [4] R. S. Lee and C. H. She. Developing a postprocessor dobivanjem ključnih podatkov z vhodne G-kode, saj je for three types of five-axis machine tools. The ponavadi G-koda bogata z dodatnimi nastavitvami, ki International Journal of Advanced Manufacturing pa v našem primeru niso nujne. Da bi se izognili shra- Technology, 13(9):658–665, Sep 1997. njevanjem neuporabnih podatkov, smo dopisali if stav- [5] W. Lei and Y. Hsu. Accuracy test of five-axis cnc kom pogoje za zagotavljanje iskanja ključnih podat- machine tool with 3d probe–ball. part i: design and kov. Za našo pridobljeno G-kodo z CAM programske modeling. International Journal of Machine Tools and opreme Siemens NX 8.5 je program deloval brezhibno, Manufacture, 42(10):1153 – 1162, 2002. G-kode drugih programskih oprem bi lahko povzročale težave. [6] A. Lesnika. Robotski sistemi : interno gradivo za program mehatronika. Višja strokovna šola, 2012. 4. Težave smo imeli tudi z doseganjem natančnih gibov, [7] M. D. Network. .NET Programming with C++/CLI saj robotu ni uspelo izvesti majhnih oz. kratkih tran- (Visual C++). slacij. Ta problem smo odpravili z zmanjšanjem hitro- [8] D. Nilsson. G-Code to RAPID translator for sti in pospeška gibov. Robot-Studio. Master of science, University West, Department of Engineering Science, 2016. 5. Težave pri računanju interpolacij smo imeli ker določe- [9] V. Ragunathan. C++/CLI Primer. Springer, 2016. nih kotov nismo mogli izračunati zaradi nedefiniranega ulomka. Odpravili smo jo z implementacijo inverznega [10] F. Ribeiro. 3d printing with metals. Computing tangensa 2. Control Engineering Journal, 9(1):31–38, Feb 1998. [11] M. Sekirnik. Priprava robotiziranega sistema ACMA 6. Uporaba programa na starejših sistemih lahko predsta- XR701 in obračalne mize za postopke 3D frezanja. vlja težave, saj je program preveden za 64-bitno arhi- Diplomsko delo, Univerza v Mariboru, Fakulteta za tekturo procesorjev. Program smo prevedli tudi za 32- strojništvo, 2015. bitno arhitekturo procesorjev, katerem bi morali pre- [12] B. Z. Sovič Tina, Simon Špacapan and R. Erveš. veri združljivost z operacijskim sistemom Windows 98. Matematika 1 : skripta. Technical report, V nasprotnem primeru je potrebno program prevesti Univerzitetna založba, 2018. z uporabo programa Microsoft Visual C++ 2005, saj je zapis podatkov v našem primeru v Unicode. Druga StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 33 Using constrained exhaustive search vs. greedy heuristic search for classification rule learning Jamolbek Mattiev Branko Kavšek PhD student, teaching assistant Assistant Professor University of Primorska University of Primorska, Jožef Stefan Institute Slovenia Slovenia (+386)-70366331 (+386)-56117654 jamolbek.mattiev@famnit.upr.si branko.kavsek@upr.si ABSTRACT introduced in [1]. It studies the frequency of items occurring Existing classification rule learning algorithms use mainly greedy together in transactional databases, and based on a threshold heuristic search to find regularities (e.g., a decision tree or a set of called support, identifies the frequent itemsets. Another threshold, rules) in data for classification. In recent years, extensive research confidence, which is the conditional probability that an item was done in the machine learning community on learning rules appears in a transaction when another item appears, is used to using exhaustive search – association rule mining. The objective pinpoint association rules. there is to find all rules in data that satisfy the user-specified In classification [4], by the help of the analysis of training data we minimum support and minimum confidence constraints. Although develop a model which is then used to predict the class of objects the whole set of rules may not be used directly for accurate whose class label is not known. The model is trained so that it can classification, effective and efficient classifiers have been built distinguish different classes in the data. The training data is using these, so called, classification association rules. having data objects whose class label is known in advance. In this paper we compare a “classical” classification rule learning Classification analysis is the organization of data in given classes. algorithm that uses greedy heuristic search to produce the final Also known as supervised classification, the classification uses classifier (a set of decision rules) with a class association rule given class labels to order the objects in the data collection. learner that uses constrained exhaustive search to find Classification approaches normally use a training set where all classification rules on a “real life” dataset. objects are already associated with known class labels. The results show that the “classical” classification rule learning There are many classification approaches such as statistical [8], algorithm generates a more compact classifier whose individual divide-and-conquer [6] and covering [3] approaches. Based on rules are somehow “less accurate”. On the other hand, the class these approaches numerous algorithms have been derived such as association rule learner produces individual classification rules PART [5], Naive Bayes [8], See5 [12], C4.5 [11], Prism [3] and that are “highly accurate” but the overall classification accuracy RIPPER [6]. However, traditional classification techniques often of the classifier remains yet to be checked. produce a small subset of rules, and therefore usually tend to miss detailed rules that might play an important role. CCS Concepts The aim of our research presented in this paper is to compare a • Computing methodologies → Machine learning → Machine “classical” state-of-the-art classification rule learning algorithm learning approaches → Rule learning that uses greedy heuristic search (PART [5]) with a class • Computing methodologies → Machine learning → Cross- association rule learner that uses constrained exhaustive search validation (a modified version of the APRIORI algorithm [2]). • Computing methodologies → Machine learning → Learning paradigms → Supervised learning → Supervised learning by 2. PRELIMINARY CONCEPTS classification Let D be a dataset with n attributes { A , A , ... , A } and |D| 1 2 n Keywords records (objects) where each record has an object identifier (OID). Data mining, machine learning, classification rules, association Let C = { c c c 1 , 2 ,..., k } be a list of class labels. A specific value rules, search, heuristics. of an attribute A and class C is denoted by lower-case letters a i im 1. INTRODUCTION and c respectively. j Classification rule mining and association rule mining are two important data mining techniques. Classification rule mining aims Definition 1. An item is described as an attribute and a specific at discovering a small set of rules in the database to form an value for that attribute, denoted by 〈( A , a )〉, e.g. 〈( A , a )〉, i im 1 11 accurate classifier. Association rule mining finds all rules in the 〈( A , a )〉, 〈( A , a )〉, etc. database that satisfy some minimum support and minimum 1 12 2 21 Definition 2. An itemset is a set of items, e.g., confidence constraints [2]. For association rule mining, the target of mining is not predetermined, while for classification rule 〈( A , a ),( A , a )〉,〈( A , a ),( A , a )〉, etc. 1 11 2 21 1 11 3 31 mining there is one and only one pre-determined target, i.e., the Definition 3. A Constraint_Itemsets is a user-defined set of class or dependent attribute. itemsets in which each itemset is said to be a constrained itemset, e.g., Constraint_Itemsets = { Association rule mining is the discovery of what are commonly 〈( A , a ),( A , a )〉,〈( A , a )〉}. 1 11 2 21 3 31 called association rules. Association rule mining, one of the most Definition 4. A class association rule R has the form important and well researched techniques of data mining, was first itemset  c where c C is a class label. j j StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.35-38 Ljubljana, Slovenia, 9 October 35 Definition 5. A rule R satisfies Constraint_Itemsets if its contained in a given transaction t. All the missing details of the antecedent (itemset) contains at least one itemset in Apriori algorithm can be found in [1] and [2]. Constraint_Itemsets. 1) L1 = {Large 1-itemsets}; Definition 6. The actual occurrence ActOcc(R) of a rule R in D is   the number of records of D that match R's antecedent. 2) for ( k =2; Lk 1  ; k ++ ) do begin 3) C =apriori-gen( L Definition 7. The support of rule R, denoted by Supp(R), is the k k 1  ); // New candidates number of records of D that match R's antecedent and are labeled 4) Forall transaction t  D do begin with R's class. 5) C C t =subset( k , t ); // Candidates contained in t Definition 8. The confidence of rule R, denoted by Conf(R), is 6) Forall candidates c  Ct do defined by equation (1) as follows: 7) . c count++; 8) end Supp(R) Conf (R)  (1)  ActOcc(R) 9) L c C k ={ k | . c count  minsup} 10) end 3. PROBLEM STATEMENT 11) Answer =⋃ L ; Consider a relational data set D with n attributes. A record of D is k k a set of attribute-value pairs, denoted by T. A pattern is a subset of Figure 1: The Apriori algorithm a record. We say, a pattern is a k-pattern if it contains k attribute- value pairs. All the records in D are categorized by a set of classes 3.2 PART Algorithm C. The PART rule learning algorithm [5] combines the two approaches C4.5 [11] and RIPPER [6] in an attempt to avoid their It is required to generate the complete set of Class Association respective problems. Unlike both C4.5 and RIPPER it does not Rules by Apriori and PART algorithms. Another focus will be on need to perform global optimization to produce accurate rule sets, comparing the advantages and disadvantages of using these two and this added simplicity is its main advantage. It adopts the algorithms. separate and conquer strategy in that it builds a rule, removes the instances it covers, and continues creating rules recursively for the 3.1 Apriori Algorithm remaining instances until none are left. It differs from the standard Association rule generation [14] is usually split up into two approach in the way that each rule is created. In essence, to make separate steps: a single rule a pruned decision tree is built for the current set of instances, the leaf with the largest coverage is made into a rule, 1. First, minimum support is applied to find all frequent and the tree is discarded. itemsets in a database. The prospect of repeatedly building decision trees only to discard 2. Second, these frequent itemsets and the minimum most of them is not as bizarre as it first seems. Using a pruned tree confidence constraint are used to form rules. to obtain a rule instead of building it incrementally by adding While the second step is straight forward, the first step needs more conjunctions one at a time avoids the over-pruning problem of the attention. Finding all frequent itemsets in a database is time basic separate and conquer rule learner. Using the separate and consuming since it involves searching all possible itemsets (item conquer methodology in conjunction with decision trees adds combinations). The set of possible itemsets is the power set over I flexibility and speed. It is indeed wasteful to build a full decision tree just to obtain a single rule, but the process can be accelerated (the set of all items) and has size 2n 1 (excluding the empty set significantly without sacrificing the above advantages. which is not a valid itemset). Although the size of the powerset grows exponentially in the number of items n in I, efficient search The key idea is to build a “partial” decision tree instead of a fully is possible using the downward-closure property of support (also explored one. A partial decision tree is an ordinary decision tree called anti-monotonicity) which guarantees that for a frequent that contains branches to undefined subtrees. To generate such a itemset, all its subsets are also frequent and thus for an infrequent tree, we integrate the construction and pruning operations in order itemset, all its supersets must also be infrequent. Exploiting this to find a “stable” subtree that can be simplified no further. Once property, efficient algorithms (e.g., Apriori [2]) can find all this subtree has been found tree-building ceases and a single rule frequent itemsets. is read off. Figure 1 gives the sketch of the Apriori algorithm. Apriori uses a The tree-building algorithm is summarized as follows: it splits a “bottom up” approach, breadth-first search and a tree structure to set of examples recursively into a partial tree. The first step count candidate item sets efficiently. The first pass of the chooses a test and divides the examples into subsets accordingly. algorithm simply counts item occurrences to determine the large The PART implementation makes this choice in exactly the same 1-itemsets. A subsequent pass, say pass k, consists of two phases. way as C4.5. Then the subsets are expanded in order of their First, the large itemsets L found in the (k-1)-th pass are used to average entropy, starting with the smallest (the reason for this is k 1  that subsequent subsets will most likely not end up being generate the candidate itemsets C . Next the database is scanned k expanded, and the subset with low average entropy is more likely and the support of candidates in C is counted. For fast counting, to result in a small subtree and therefore produce a more general k we need to efficiently determine the candidates in C that are rule). This continues recursively until a subset is expanded into a k leaf, and then continues further by backtracking. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 36 But as soon as an internal node appears which has all its children Table 1. Discretization of numeric attributes expanded into leaves, pruning begins: the algorithm checks whether that node is better replaced by a single leaf. This is just Inches Weight Price_euros the standard “subtree replacement” operation of decision-tree pruning, and the PART implementation makes the decision in Bins Name Bins Name Bins Name exactly the same way as C4.5. If replacement is performed the algorithm backtracks in the standard way, exploring siblings of [10.1 – 14] Small [0.69 – 1.75] Light [174 – 800] Low the newly-replaced node. However, if during backtracking a node is encountered whose every child is not a leaf (and this will (14 – 16] Standard (1.75 – 2.21] Medium (800 – 1300] Mid-range happen as soon as a potential subtree replacement is not performed) then the remaining subsets are left unexplored and the (16 – 18.4] Gaming (2.21 – 4.7] Heavy (1300 – 6099] High corresponding subtrees are left undefined. Due to the recursive structure of the algorithm this event automatically terminates tree generation. Additional details about the PART algorithm can be In Table 2, the best class association rules which have at least found in [5]. 90% confidence are shown according to the Apriori algorithm. Table 3 shows the classification rules which are found by the 4. EXPERIMENTAL EVALUATION AND PART algorithm (Conf. and Cov. In these tables stand for RESULTS confidence or accuracy and coverage, respectively). In this paper, we used a real-life dataset [13] called “Laptop Results show individual class association rules are more accurate prices” to illustrate the class association and classification rules (confident) and have a higher coverage compared to individual learning process. This dataset consists of 1.304 examples which classification rules. On the other hand, classification rules cover have 11 “independent” attributes each and one class attribute. the search space “completely” and do not overlap while class Three numeric attributes (Inches, Weight, and Price_euros) are association rules may (heavily) overlap and are not guaranteed to discretized into nominal attributes (as illustrated in Table 1). cover all the examples. Table 2. Class Association Rules found by the Apriori algorithm Class association rules Conf. Cov. { Inches=Standard, Cpu=Intel Core i3} ==> { Price_euros=Low } 100% 114 { ProductTypeName=Notebook, Inches=Standard, Cpu=Intel Core i3} ==> { Price_euros=Low } 100% 110 { Inches=Standard, Cpu=Intel Core i3, Ram=4GB } ==> { Price_euros=Low } 100% 89 { ProductTypeName=Notebook, Inches=Standard, Cpu=Intel Core i3, Ram=4GB } ==> { Price_euros=Low } 100% 85 { Inches=Standard, Cpu=Intel Core i3, OpSys=Windows 10} ==> {Price_euros=Low} 100% 84 { Inches=Standard, Cpu=Intel Core i3, Gpu=Intel } ==> {Price_euros=Low} 100% 82 { Inches=Standard, Cpu=Intel Core i3, Memory=HDD } ==> { Price_euros=Low } 100% 76 { ScreenResolution=1366x768, Cpu=Intel Celeron, Gpu=Intel } ==> { Price_euros=Low } 100% 67 { Inches=Standard, Cpu=Intel Core i3, Ram=4GB, Weight=Medium } ==> { Price_euros=Low } 100% 67 { ProductTypeName=Gaming, ScreenResolution=Full HD, Ram=16GB, Memory=SSD + HDD, Gpu=Nvidia } 94% 72 ==> { Price_euros=High } { ProductTypeName=Gaming, ScreenResolution=Full HD, Ram=16GB, Memory=SSD + HDD, Gpu=Nvidia, 94% 72 OpSys=Windows 10} ==> { Price_euros=High } { Inches=Standard, Ram=4GB, Memory=HDD, Weight=Medium } ==> { Price_euros=Low } 94% 143 { ProductTypeName=Notebook, Ram=4GB, Memory=HDD, Weight=Medium }==> { Price_euros=Low } 94% 142 { ProductTypeName=Gaming, ScreenResolution=Full HD, Cpu=Intel Core i7, Ram=16GB, Memory=SSD + HDD} 94% 71 ==> { Price_euros=High } { ProductTypeName=Gaming, ScreenResolution=Full HD, Cpu=Intel Core i7, Ram=16GB, Memory=SSD + HDD, 94% 71 OpSys=Windows 10} ==> { Price_euros=High } { ScreenResolution=1366x768, Ram=4GB, Weight=Medium } ==> { Price_euros=Low } 93% 120 { ProductTypeName=Notebook, ScreenResolution=1366x768, Ram=4GB, Weight=Medium } 93% 112 ==> { Price_euros=Low } { Inches=Standard, ScreenResolution=1366x768, Ram=4GB, Weight=Medium } ==> { Price_euros=Low } 93% 120 { ProductTypeName=Notebook, Inches=Standard, ScreenResolution=1366x768, Ram=4GB, Weight=Medium} 93% 120 ==> { Price_euros=Low } { ProductTypeName=Gaming, ScreenResolution=Full HD, Ram=16GB, Memory=SSD + HDD } 93% 75 ==> { Price_euros=High } { ScreenResolution=Full HD, Ram=16GB, Memory=SSD + HDD, Gpu=Nvidia }==> {Price_euros=High } 93% 75 { ProductTypeName=Gaming, ScreenResolution=Full HD, Ram=16GB, Memory=SSD + HDD, OpSys=Windows 10} 93% 75 ==> {Price_euros=High} { ScreenResolution=Full HD, Cpu=Intel Core i7, Ram=16GB, Memory=SSD + HDD, Gpu=Nvidia } 93% 74 ==> {Price_euros=High} { ProductTypeName=Gaming, Ram=16GB, Memory=SSD + HDD, Gpu=Nvidia, OpSys=Windows 10, Weight=Heavy } 93% 72 ==> {Price_euros=High} StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 37 Table 3. Classification Rules found by the PART algorithm Classification rules Conf. Cov. { Ram = 16GB, Memory = SSD, ScreenResolution = Full HD } ==> { Price_euros= High } 80% 36 { Ram = 16GB, Memory = SSD } ==> { Price_euros= High } 94% 49 { Ram = 16GB, Inches = Gaming } ==> { Price_euros= High } 94% 49 { Ram = 4GB, ProductTypeName = Notebook, Cpu = Intel Core i3, ScreenResolution = 1366x768 } 98% 52 ==> { Price_euros=Low } { Ram = 4GB, ProductTypeName = Notebook, Cpu = Intel Core i5, Memory = HDD } 74% 48 ==> {Price_euros=Low} { Ram = 4GB, ProductTypeName = Notebook, Cpu = Intel Celeron } ==> {Price_euros=Low} 100% 48 { Cpu = Intel Core i3, Memory = HDD } ==> { Price_euros=Low } 98% 47 { Ram = 16GB } ==> { Price_euros= High } 70% 35 { Ram = 4GB, ProductTypeName = Notebook, Cpu = Intel Core i5 } ==> { Price_euros= Low } 49% 17 { Ram = 4GB, ProductTypeName = Notebook, Cpu = Intel Other } ==> { Price_euros= Low } 100% 30 { Ram = 4GB, ProductTypeName = Notebook } ==> { Price_euros= Low } 97% 58 { Cpu = Intel Core i7, ProductTypeName = Ultrabook, Inches = Standard } ==> { Price_euros= High } 70% 31 { Cpu = Intel Core i7, ProductTypeName = Gaming, Inches = Standard } 61% 33 ==> { Price_euros= Mid-Range } { Cpu = Intel Core i7, Inches = Standard, Memory = SSD } ==> { Price_euros= Mid-Range } 51% 33 { Cpu = Intel Core i7, Inches = Small } ==> { Price_euros=High } 71% 41 { Cpu = Intel Celeron } ==> { Price_euros= Low } 100% 40 { ProductTypeName = Gaming, Cpu = Intel Core i7} ==> { Price_euros= High } 76% 29 { Memory = SSD + HDD } ==> { Price_euros= Mid-Range } 58% 42 { Cpu = Intel Core i7} ==> { Price_euros= Mid-Range } 49% 23 { Cpu = Intel Core i5, Weight = Light, Company = Dell } ==> { Price_euros= Mid-Range } 49% 18 { Cpu = Intel Core i5, Weight = Light, ProductTypeName = Ultrabook } ==> {Price_euros= Mid-Range } 50% 21 { Cpu = Intel Core i5, Memory = SSD, Weight = Light } ==> {Price_euros= Mid-Range } 49% 30 { Cpu = Intel Core i5, Gpu = Intel } ==> {Price_euros= Mid-Range } 48% 38 [3] Cendrowska, J. (1987). “PRISM: An algorithm for inducing 5. CONCLUSIONS AND FUTURE WORK modular rules”. International Journal of Man Machine Overall, it can be observed from the experimental results (Apriori Studies. volume 27, no. 4, pp. 349-370. algorithm) that the features of the cheaper laptops (rules in [4] Duda, R., and Hart, P. (1973). “Pattern Classification and Table 2 with the right-hand side Price_euros=Low) were inches: Scene Analysis”. John Wiley & Sons. Standard or Small, CPU: Intel Core i3 or Celeron, RAM: 4GB, Weight: Light or Medium, Memory: HDD, GPU: Intel, Operative [5] Frank, E., and Witten, I. (1998). “Generating accurate rule System: Windows 10 and Screen Resolution: 1366x768. sets without global optimization”. Proceedings of the Fifteenth International Conference on Machine Learning, The expensive laptops (rules in Table 2 with the right-hand side Morgan Kaufmann, San Francisco, pp. 144-151. Price_euros=High) were mostly Gaming laptops with SSD or SSD+HDD memory, 16GB RAM, Intel Core i7 CPU, Nvidia [6] Fürnkranz, J. (1996). “Separate-and-conquer rule learning”. GPU, Heavy weight and Full HD Screen Resolution. Technical Report TR-96-25, Austrian Research Institute for Artificial Intelligence, Vienna. The results on the chosen dataset show that the Apriori algorithm [7] Fürnkranz, J., and Widmer, G. (1994). “Incremental reduced generates more accurate individual classification rules with higher error pruning”. Proceedings of the 11th Annual Conference coverage/accuracy than the PART algorithm. However, class on Machine Learning, Morgan Kaufmann, pp. 70-77. association rules may be highly overlapping which can affect the overall accuracy of the classifier. [8] John, G.H., and Langley, P. (1995). “Estimating Continuous Distributions in Bayesian Classifiers”. Proceedings of the In future work we shall check the overall accuracy and coverage Eleventh Conference on Uncertainty in Artificial of “complete” classifiers generated by class association rules Intelligence. Morgan Kaufmann, San Mateo. pp. 338-345. algorithm, broaden our comparison to more (diverse) datasets and compare also the learning times of both algorithms. [9] Liu, B., Hsu, W., and Ma, Y. (1998). “Integrating Classification and Association Rule Mining”. Singapore. 6. REFERENCES [10] Patel, R., Vala, J., and Patel, K. (2014). “Comparative Study [1] Agrawal, R., Amielinski, T., and Swami, A. (1993). “Mining on Associative Classification techniques”. association rule between sets of items in large databases”. In Proceeding of the ACM SIGMOD International Conference [11] Quinlan, J. R. (1993). “C4.5: Programs for Machine on Management of Data, pp. 207-216. Learning”. San Mateo, Morgan Kaufmann. [2] Agrawal, R., and Srikant, R. (1994). “Fast algorithms for [12] Quinlan, J. R. (2008). “Data mining tools see5 and c5”. mining association rules”. Research Report CA 95120, IBM [13] https://www.kaggle.com/ionaskel/laptop-prices/home Almaden Research Center, San Jose, California. (accessed on 17.8.2018). [14] http://software.ucv.ro/~cmihaescu/ro/teaching/AIR/docs/Lab 8-Apriori (accessed on 17.8.2018). StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 38 Real-time visualization of 3D digital Earth Aljaž Jeromel Faculty of Electrical Engineering and Computer Science, University of Maribor Koroška cesta 46, 2000 Maribor, Slovenia aljaz.jeromel@student.um.si ABSTRACT understanding of the planet [2]. A new method for real-time visualization of Earth in 3D is presented. The method dynamically calculates visualization Quite a few methods for visualization of Earth and plan- data and works in several steps. Firstly, the vertex coordi- ets have been developed and optimized since the historical nates in 3D are calculated. Then, the UV coordinates for Gore speech. During the years 2003 to 2006, a group of texturing are calculated from vertex’ position. The vertices Italian computer scientists presented a method for high per- are connected into triangles and sent to the shader pipeline, formance terrain visualization, named BDAM, and two of where they are processed by vertex shader, geometry shader its improvements, PBDAM and CBDAM [3, 4, 5]. Schnei- and fragment shader. The vertex shader transforms the ver- der and Westermann have also proposed a method using tices from the world space to screen space. Geometry shader nested meshes for high quality terrain rendering with min- corrects possible interpolation errors by inserting extra ver- imal GPU overhead in 2006 [6]. In 2007, Schafhitzel et al. tices where needed, while the fragment shader assigns the proposed a method for rendering of the planets, including a colour to resulting fragments. The main advantage of the simulation of the atmosphere, in real-time [7]. A short book proposed method over the state of the art methods is its sim- on planet visualization was written in 2008 by Östergaard, plicity. Experimental results have shown that the proposed which discusses the implementation challenges of a digital method produces a high FPS (frames per second), which globe and presents the implementation solution with some makes it suitable for real-time visualization. optimizations [8]. Cozzi and Ring took that achievement one step further in 2011, by writing an exhaustive book on vir- Keywords tual globe design, along with multiple propositions on how to deal with implementation issues that can occur, and the Computer Graphics, 3D Rendering, Object Geometry full C# implementation [9]. 1. INTRODUCTION This paper is focused on real-time rendering of 3D Earth With the use of 3-dimensional (3D) graphics, a lot of things map. A method for a dynamic visualization is presented can be visualized, from simple cubes to complex models of and explained, and the efficiency of the method is discussed. real-life objects. The need for an application that visualizes The proposed method firstly calculates visualization vertices geographical and other data about the Earth in 3D has been on the screen, then calculates their UV coordinates. The expressed as early as 1998 by then vice president of the US results of these steps fill the Vertex Buffer Object, which Al Gore [1]. He proposed many practical uses for such an is sent to the graphics card. There, the calculated vertices application, named ”Digital Earth”. The proposed uses in- are processed by the vertex shader, geometry shader, and clude education, national border negotiations, redeployment the fragment shader programs, before the map is drawn on of police force to the most problematic areas, biodiversity the screen. According to experimental results, the proposed preservation, climate change prediction and improvement of method produces high enough FPS (frames per second) to agricultural productivity. Because most world maps use the be used in high performance applications. The proposed Mercator projection, which deforms the view of the world, method is much simpler and light-weight than the state of the visualization of Earth in 3D can teach the children a lot the art visualization methods. The floating point precision more about our planet than the conventional 2D maps can. errors are handled by means of normalizing the coordinates The digital model of Earth, combined with many kinds of to the visible part of the Earth, while the interpolation errors data (e.g. historical, geodetic, etc.) could also lead to better are processed by the geometry shader on the GPU. This paper also does not concern itself with acquisition of texture data; the implementation behind it is out of scope of this paper. This paper is organized as follows. The method for visual- ization is explained in Section 2. The results, produced by the method, namely frames per second (FPS) in relation to the number of triangles rendered, are presented in Section 3. The conclusion is given in Section 4. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.39-42 Ljubljana, Slovenia, 9 October 39 2. METHODOLOGY The rendering procedure, presented in this paper, consists ~ ~ a R of following steps. Firstly, the visible tiles are calculated. b = |~c| (3) |~a| p|~c|2 − R2 Then, the vertices and their UV coordinates are calculated. The vertex data is sent to the graphics card for drawing. Fi- nally, the vertex, geometry, and fragment shader finalize the calculations, and the result is drawn to the screen. These ~b − ~c ~ p t = ~ c + |~c|2 − R2 (4) steps are presented in more detail in the following subsec- |~b − ~c| tions. 2.1 Vertex generation Finally, the coordinates of the points are normalized. The first step in 3D graphics pipeline is the generation of vertices. In many applications that use 3D graphics, some 2.2 UV coordinate calculation modelling software is used to generate the model, already The UV coordinates for texturing are calculated from the complete with vertices, UV coordinates, and normals of the vertex’ coordinates. If the map tiles use Mercator projec- object. However, such models are not suitable for high- tion, which distorts the image in the direction of vertical resolution realistic display applications because of three rea- axis (V coordinate), that has to be reversed first [10]. The sons: U coordinate is calculated simply from the normalized ver- tex position, p = (x, y, z), as in Equation ??. • A model file with sufficient number of vertices for real- istic display of the highest quality would be extremely large, arc tan( x ) U = z + 0.5, (5) • Rendering of too many vertices results in a very low 2π FPS (frames per second) environment when using mediocre graphics cards, due to insufficient available graphics With the help of constant M (Equation 7), the V coordinate memory or shader processing cores, is then calculated using Equation ??. • Older versions of shader programs don’t support the use of 64-bit precision, which is required for rendering of the most detailed views of the Earth. arc sinh[tan(2 M arc sin[y])] V = + 0.5, (6) 2π Because our goal was compatibility with some of the older versions of shading language, 64-bit precision could not be used in shader programs. Therefore, in presented applica- M = arc tan[sinh(π)]. (7) tion, dynamic vertex generation was used, which also meant that the precision-critical data could not be processed by shader programs on the GPU. Because of that, the FPS Because shader programs use 32-bit precision, an additional (frames per second) in our application is a bit lower than it step is required when calculating the UV coordinates. When could have been in an ideal setting. rendering a close-up view, only a really small part of the For the vertex generation, a ray casting algorithm is used. Earth is visible, which means the difference between mini- The screen is divided in up to 121 equally spaced points, and mum and maximum UV coordinates is really small too. Be- from each of those points, a ray is sent out. This produces cause of that, the UV coordinates can be normalized to the a grid on the screen with up to 10 rows and columns. The visible part of the Earth. The minimum and maximum vis- rays’ intersections with sphere representing the Earth are ible row and column of tiles were already calculated before calculated. If we have a ray ~ r = (rx, ry, rz), sphere with ra- vertex generation step. Instead of having the V value 0 at dius R, the camera positioned at ~ c = (cx, cy, cz), and the dot the south pole and 1 at the north pole, we can adjust it to product between ray direction and camera position vectors be 0 at the bottom of the bottommost visible row and 1 to dt, the closest intersection, ~ p, between ray and the sphere be at the top of the topmost visible row. The U coordinate can be calculated by Equation ??. is also mapped from 0 at the left of leftmost visible column and 1 at the right of rightmost visible column. That way, the precision errors in shader programs are kept in check when p ~ p = ~ c − (dt + dt2 + R2 − |~ c|2) ~ r. (1) rendering the high resolution close-up views of the Earth. Note that the part under the square root is negative when 2.3 Vertex shader the ray and the sphere do not intersect. In that case, the The vertex shader program’s only task is to transform the ray’s direction is adjusted a bit, so that it touches the sphere. vertex position from the world space into screen space by The tangent point, ~ t, is calculated using Equation ??, with multiplying with the standard model-view-projection ma- intermediate vectors ~ a (Equation ??) and ~b (Equation ??) trix. In case the model vertex buffer is used instead of the dynamically calculated vertex buffer, the vertex shader also remaps the UV coordinates to adapt them to the Merca- |~c|2 tor projection, using Equation ?? and the constant M from ~ a = ~ c + ~ r (2) −dt Equation 7. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 40 arc sinh[tan(2M [V − 0.5])] V 0 = 0.5 − . (8) 2π 2.4 Geometry shader Geometry shader program has one of the most important tasks in this whole process. It handles the interpolation er- rors that happen at the edges of the map. Because OpenGL fragment interpolation is always linear, errors occur when one of the points in the triangle has the U coordinate of 0.1 and another point in the same triangle has the U coordinate of 0.9. In that case, the shader should interpolate from 0.1 down to 0, then jump to 1 and from there continue inter- polating down to 0.9. The models circumvent this issue by duplicating vertices at the UV coordinate wrap-arounds, so if we’re using a model, the geometry shader can be skipped. The geometry shader program takes in the set of vertices representing a primitive, in our case a triangle. It checks the U coordinate of all 3 vertices, and if the difference be- tween any 2 of them is higher than 0.7, it inserts another vertex between them, to split the triangle into 2 or more triangles, setting the inserted point’s U coordinate to 0 for one triangle and 1 for the other. It then outputs all of the resulting triangles to the following stages of the rendering pipeline. 2.5 Fragment shader The fragment shader program’s task is to determine the colour of each fragment. OpenGL allows the shader pro- gram to access up to 32 different textures during each draw call. But because a lot of textures converge at the north and south pole, multiple draw calls are needed during each frame. Each of those calls is passed one of the tile textures. The fragment shader program is responsible for mapping of UV coordinates to the texture, and discarding all of the frag- ments that do not sample from the texture, passed in the current call. If the fragment is not discarded in this draw call, the fragment shader program samples the passed tex- ture to obtain the fragment’s colour, which is finally output to the depth testing. 3. RESULTS In this section, the results of rendering the Earth with the proposed method are presented. The average time needed to process and render a frame was measured, and the aver- age FPS (Frames per second) was calculated. The measure- ments were done on a personal computer with the following configuration: Intel Core i5-3570K CPU 3.40 GHz, 32 GB of RAM, GeForce GTX 1060 Windforce OC 6GB, running 64 bit operating system Windows 10 Education. The width and height of all the texture units used were 256 pixels. Their total size on disk was 9560 terabytes. The result of Figure 1: The result of rendering the same area in rendering three different levels of detail (LOD) of the same three different LOD-s area is shown in Figure 1. During standard rendering, the screen was divided into a grid of 10 × 10 rectangles, each of which was split into two triangles. FPS calculation was done by lowering the grid’s dimensions all the way down to 1 rectangle, and measuring the average time required to render a frame. Using that StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 41 information, the average FPS was calculated. The results [4] P. Cignoni, F. Ganovelli, E. Gobbetti, F. Marton, are shown in Table 1. F. Ponchio, R. Scopigno. Planet-sized batched dynamic adaptive meshes (p-bdam). In Proceedings of IEEE Visualization, pages 149–155. IEEE, October Table 1: Average FPS when rendering a pre-set 2003. number of triangles [5] E. Gobbetti, F. Marton, P. Cignoni, M. Di Benedetto, Number of triangles Average FPS F. Ganovelli. C-bdam - compressed batched dynamic 2 452.90 adaptive meshes for terrain rendering. Computer 8 350.62 Graphics Forum, 25(3):333–342, December 2006. 18 397.89 [6] J. Schneider and R. Westermann. Gpu-friendly 32 407.09 high-quality terrain rendering. Journal of WSCG, 50 405.80 14(1-3):49–56, February 2006. 72 364.40 98 356.11 [7] T. Schafhitzel, M. Falk, T. Ertl. Real-time rendering 128 370.66 of planets with atmospheres. Journal of WSCG, 162 382.86 15(1-3):91–98, January 2007. 200 359.95 [8] J. Östergaard. Planet Rendering Using Online High-Resolution Datasets. Linköping University, Norrköping, Sweden, 2008. As seen from the table, though the results vary, the average [9] P. Cozzi and K. Ring. 3D Engine Design for Virtual FPS generally tends to decrease with a higher number of Globes. A K Peters, Ltd., Natticks, Massachusetts, triangles. This can be seen in Figure 2, where the dotted USA, 2011. line represents the 6th order of the polynomial trending line. [10] D. H. Maling. Coordinate Systems and Map Projections, Second Edition. Pergamon Press, Oxford, England, 1992. Figure 2: Graph representing the average FPS in relation to the number of rendered triangles, with the 6th order polynomial trending line (dotted) 4. CONCLUSION In this paper, a method for real-time visualization of Earth in 3D is presented. It works by dynamically calculating the visualization data and uploading it to the graphics card, where it is processed by the vertex shader, geometry shader, and fragment shader. The experimental results have shown that the method produces a very high FPS (frames per sec- ond), which allows for the usage in applications, where high performance is important. 5. REFERENCES [1] A. Gore. The digital earth: Understanding our planet in the 21st century. Australian Surveyor, 43(2):89–91, June 1998. [2] M. F. Goodchild. The use cases of digital earth. International Journal of Digital Earth, 1(1):31–42, March 2008. [3] P. Cignoni, F. Ganovelli, E. Gobbetti, F. Marton, F. Ponchio, R. Scopigno. Bdam - batched dynamic adaptive meshes for high performance terrain visualization. Computer Graphics Forum, 22(2):505–514, November 2003. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 42 Towards an enhanced inertial sensor-based step length estimation model Melanija Vezočnik Matjaž Branko Jurič University of Ljubljana, Faculty of Computer and University of Ljubljana, Faculty of Computer and Information Science Information Science Ljubljana, Slovenia Ljubljana, Slovenia mv6082@student.uni-lj.si matjaz.juric@fri.uni-lj.si ABSTRACT models require acceleration, angle-based models require the Inertial sensors found in Internet-of-Things devices such as opening angle of the leg and the input of multiparameter smartphones and smartwatches can be used to track user’s models combines two or all three of the previously listed activity as well as step length. In particular, rapidly grow- parameters. ing interest in pedestrian dead reckoning – indoor position- ing approach that calculates current position as the sum of In this work we present our research towards an enhanced previous position and vector with step length and heading inertial sensor-based step length estimation model that in- information – prompts to develop refined step length esti- creases the accuracy of estimated step length. Section 2 mation models to overcome inaccuracy in determining step overviews step length estimation models. Section 3 describes length. In this work we present our research towards an en- the derivation and Section 4 the evaluation of the proposed hanced inertial sensor-based step length estimation model. model. Section 5 presents results, whereas Section 6 dis- For this purpose, we extend an existing step-frequency-based cusses them. Finally, Section 7 concludes this work present- model with acceleration and make it less user-specific. We ing future research directions. evaluated the performance of the proposed model for one sensor position and different walking speeds and obtained 2. OVERVIEW OF STEP LENGTH ESTIMA- very promising results comparable to related models. We will further improve the accuracy of the proposed model TION MODELS and modify it, so it will require less time for tuning, and Step length is determined in several phases. In order to thoroughly address the pre-processing of the sensor data. acquire inertial sensor measurements, a sensor has to be We will also test the proposed model for different sensor set-up on user’s body, most commonly in hand, pocket or positions and pedestrian-dead-reckoning-based indoor posi- centre of body mass. Acquired data – usually accelerome- tioning. ter measurements – have to be pre-processed to eliminate errors. Steps are detected before step length is determined Keywords using a step length estimation model that often has to be tuned. Next, we briefly present the categories of the models inertial sensors, pedestrian dead reckoning, step length esti- (step-frequency-based, acceleration-based, angle-based and mation multiparameter). 1. INTRODUCTION 2.1 Step-frequency-based models Over the past few years, user engagement enabling Internet- Step-frequency-based models require step frequency as an of-Things (IoT) technologies are emerging. In particular, in- input. They commonly exploit linear relationship between ertial sensors can be utilized to track user’s activity as well as step length and step frequency and have to be tuned prior to step length since they can be found in smartphones, smart- utilization. The following two models include user’s height. watches and other IoT devices. They also exhibit advan- Renaudin et al. [6] proposed a model based on linear rela- tages such as easy accessibility, inexpensiveness and small- tionship between step length and step frequency, whereas size. Moreover, estimating step length is also applicable Tian et al. [2] exploited the link between square root of step in diverse areas, especially in indoor positioning approach frequency and step length. On the contrary, Zhang et al. [1] called pedestrian dead reckoning [1, 2, 3, 4] that determines included user’s leg length in their model, but based it on the the current position by adding vector with step length and linear relationship between step length and step frequency, heading information to the previous position. similarly as the model proposed by Renaudin et al. [6]. Throughout this work we address inertial sensor-based step length estimation models. According to [5], they can be 2.2 Acceleration-based models classified into four categories based on the parameters they Acceleration-based models require acceleration as an input. require as an input. These parameters are obtained from They often exploit the link between step length and accel- inertial sensor measurements. The categories are: step- eration properties such as minimum and maximum accel- frequency-based [1, 2, 6], acceleration-based [3, 7], angle- eration values within the step. Weinberg [7] proposed such based [8] and multiparameter [4, 9]. Step-frequency-based model. It calculated step length as the product of a tuneable models require step frequency as an input, acceleration-based constant and fourth principal root of the difference between StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.43-46 Ljubljana, Slovenia, 9 October 43 maximum and minimum vertical acceleration values within 0.38 a step. Similarly, Do et al. [3] based their model on verti- cal displacement of the centre of body mass. This model 0.36 includes user’s leg length, but it does not include any tune- able constants. 0.34 0.32 2.3 Angle-based models Angle-based models require the opening angle of the leg as 0.3 an input. They often exploit linear relationship between step length and the opening angle of the leg. Diaz and Gon- 0.28 zales [8] proposed such model. It includes two tuneable con- stants. 0.26 Value of tunable constant 0.24 2.4 Multiparameter models The input of multiparameter models combines two or all 0.22 three of the previously listed parameters: step frequency, acceleration or the opening angle of the leg. These models 0.2 usually extend existing models with additional parameters. 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Average walking speed [m/s] For example, Mikov et al. [4] included the inverse of step frequency in the Weinberg model [7]. Similarly, Bylemans et al. [9] also based their model on the difference between Figure 1: Values of tuneable constants in the model maximum and minimum acceleration values within a step, proposed by Tian et al. [2] for different walking but they included step frequency and absolute average ac- speeds. celeration value in walking direction in the model. 3. THE DERIVATION OF THE PROPOSED 4. EVALUATION For the evaluation of the proposed model, we used data from MODEL the repository described in the previous section that includes Before we started deriving a new model, we carried out an measurements acquired in two independent sets of field tests in-depth analysis and comparison of 13 relevant representa- on two straight test paths: 15- and 108-m-long. We used tive inertial sensor-based step length estimation models [5], the data collected on the shorter path to tune the models where we studied the influence of four typical sensor po- and the data collected on the longer path to evaluate the sitions and different walking speeds on their performance. performance of the models. We tuned the models with personalized and universal sets of constants. We also established a benchmark repository To eliminate the impact of smartphone orientation, we only for the performance evaluation of inertial sensor-based step considered hand-reading position as shown in Figure 2, where length estimation models that includes more than 22 km of the user is carrying the smartphone in hand. Smartphone’s gait measurements obtained from 15 adults using off-the- local coordinate system is considered as follows: y-axis is shelf smartphone. This repository is openly available at: pointing in the walking direction and z-axis is pointing in https://github.com/repositoryadmin/SLERepository. the opposite direction of the floor. Smartphone’s position is fixed. Three steady walking speeds were tested: slow, In [5], we obtained the best overall evaluation results for normal and fast. Participants self-selected walking speeds universal sets of constants for the model proposed by Tian to their preference, but they were asked to maintain the et al. [2] and therefore started deriving our enhanced model walking speed as similar as possible for the time of the ex- from this model. The model proposed by Tian et al. [2] periment. One person always monitored the execution of the calculates step length as: experiments and counted the number of participants’ steps. √ SL = K · F · h, (1) Despite the fact that persons self-selected slow, normal and fast walking speeds to their preference, we observed that av- where SL represents estimated step length, K tuneable con- erage walking speeds ranged from 0.45 m/s to 1.25 m/s for stant, h user’s height and F step frequency. slow walking speed, 0.90 m/s to 1.65 m/s for normal walking speed and 1.40 m/s to 2.00 m/s for fast walking speed [5]. We observed that average walking speed during tests af- fected the values of tuneable constant in the model as shown Measurements were acquired using off-the-shelf Samsung Ga- in Figure 1. We can see that on average the values of the con- laxy S7 edge smartphone. Sampling frequency was 100 Hz stant increase with the increased walking speed. We there- with standard deviation of 8 Hz. Therefore, acquired mea- fore include mean absolute acceleration in walking direction surements were resampled to 100 Hz by employing linear in our model. To make the proposed model less user-specific, interpolation. We used peak detection algorithm for step we exclude user’s height and calculate step length as: detection and determined personalized constants of the pro- √ posed model and the models selected for the comparison us- SL = K1 · F · aK2 mean, (2) ing optimization analysis on the data collected on the shorter where SL represents estimated step length, K1 and K2 are path. We employed personalized sets of constants to eval- tuneable constants, amean mean absolute acceleration value uate the performance of the models on the data collected in walking direction and F step frequency. on the longer path. For every test, we have calculated the StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 44 same model by employing substitution [5]. The model pro- posed by Do et al. [3] expectedly performed the worst since it does not contain any tuneable constants. 7. CONCLUSION In this work we presented our research towards an enhanced inertial sensor-based step length estimation model. We based our model on the model proposed by Tian et al. [2] since we obtained the best evaluation results for it for universal sets of constants [5]. We eliminated user’s height from the model and included mean absolute acceleration in walking direction instead. We tested the proposed model for one sensor position in hand and obtained promising evaluation results comparable to re- lated models. We will further improve the accuracy of the proposed model and test it for more sensor positions. We also plan to modify Figure 2: Hand-reading position. the proposed model, so it would require less time for tun- ing and thoroughly address the pre-processing of the sensor data. Moreover, we will conduct additional experiments us- performance as: ing different IoT devices and test the proposed model for |d − d∗| pedestrian-dead-reckoning-based indoor positioning. e = · 100% (3) d∗ Acknowledgments where e is error, d is the estimated distance of walked path and d∗ the real distance of walked path. M. V. received funding for doctoral studies from the Univer- sity of Ljubljana – 2016 generation. Authors would like to thank all the volunteers who participated in the experiment. 5. RESULTS Table 1 shows the performance of the models. It includes 8. REFERENCES mean errors and standard deviations of the models with [1] P. Zhang, X. Chen, X. Ma, Y. Wu, H. Jiang, D. Fang, respect to total walked distance. Mean errors range from Z. Tang, and Y. Ma, “SmartMTra: Robust Indoor 3.76 % to 16.84 % and standard deviations from 2.41 % to Trajectory Tracing Using Smartphones,” IEEE Sensors 7.56 %. Journal, vol. 17, no. 12, pp. 3613–3624, 2017. [2] Q. Tian, Z. Salcic, K. I. K. Wang, and Y. Pan, “A Table 1: The performance of the models. Multi-Mode Dead Reckoning System for Pedestrian Mean Standard Tracking Using Smartphones,” IEEE Sensors Journal, Models errors [%] deviations [%] vol. 16, no. 7, pp. 2079–2093, 2016. Tian et al. [2] 4.35 2.78 [3] T. N. Do, R. Liu, C. Yuen, M. Zhang, and U. X. Tan, Zhang et al. [1] 8.91 6.86 “Personal Dead Reckoning Using IMU Mounted on Renaudin et al. [6] 8.91 6.86 Upper Torso and Inverted Pendulum Model,” IEEE Sensors Journal, vol. 16, no. 21, pp. 7600–7608, 2016. Do et al. [3] 16.84 7.56 Weinberg [7] 4.36 3.80 [4] A. Mikov, A. Moschevikin, A. Fedorov, and A. Sikora, “A localization system using inertial measurement units Diaz and 5.25 4.54 from wireless commercial hand-held devices,” in 2013 Gonzales [8] International Conference on Indoor Positioning and Mikov et al. [4] 7.44 5.93 Indoor Navigation (IPIN), 2013, pp. 1–7. Bylemans et al. [9] 5.68 4.61 [5] M. Vezočnik and M. B. Jurič, “Inertial Sensor-Based Proposed model 3.76 2.41 Step Length Estimation Models: A Review,” In Review Process, 2018. [6] V. Renaudin, M. Susi, and G. Lachapelle, “Step Length Estimation Using Handheld Inertial Sensors,” Sensors, 6. DISCUSSION vol. 12, no. 7, pp. 8507–8525, 2012. Overall, the proposed model slightly outperformed all the [7] H. Weinberg, “Using the ADXL202 in pedometer and other models. Quite similar performance achieved the mod- personal navigation applications,” Analog Devices els proposed by the Tian et al. [2], Weinberg [7], Diaz and AN-602 application note, vol. 2, no. 2, pp. 1–6, 2002. Gonzales [8], Bylemans et al. [9] and Mikov et al. [4]. Even [8] E. M. Diaz and A. L. M. Gonzalez, “Step detector and though the model proposed by Mikov et al. [4] extends the step length estimator for an inertial pocket navigation Weinberg model [7] it did not perform better on average. system,” in 2014 International Conference on Indoor The models proposed by Zhang et al. [1] and Renaudin et Positioning and Indoor Navigation (IPIN), 2014, pp. al. [6] performed similarly since they can be rewritten to the 105–110. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 45 [9] I. Bylemans, M. Weyn, and M. Klepal, “Mobile on Mobile Ubiquitous Computing, Systems, Services and phone-based displacement estimation for opportunistic Technologies, 2009. UBICOMM’09., 2009, pp. 113–118. localisation systems,” in Third International Conference StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 46 Breast Histopathology Image Clustering using Cuckoo Search Algorithm Krishna Gopal Dhal1, Iztok Fister Jr.2, Arunita Das3, Swarnajit Ray4, Sanjoy Das5 1 Dept. of Computer Science and Application, Midnapore College (Autonomous), Paschim Medinipur, West Bengal, India. Email: krishnagopal.dhal@midnaporecollege.ac.in 2Faculty of Electrical Engg. and Computer Sc., University of Maribor, Slovenia, Email: iztok.fister1@um.si. 3Dept. of Information Technology, Kalyani Govt. Engineering College, Kalyani, Nadia, India. Email: arunita17@gmail.com. 4Skybound Digital LLC, Kolkata, West Bengal, India. Email: swarnajit32@gmail.com. 5Dept. of Engg. and Technological Studies,University of Kalyani, Kalyani, India, Email: dassanjoy0810@hotmail.com ABSTRACT processing significantly assists pathologists and has attracted many attentions in both research and clinical practice. Breast histopathological image segmentation is exigent due to the A critical requirement in computer-aided diagnosis is existence of imperceptibly correlated and indistinct multiple segmentation, which is typically measured as the basis of regions of concern. Clustering based segmentation is one of the automated image analysis. It provides assistances for various most significant approaches to perform proper segmentation of quantitative analyses such as shape, size, texture, and other such complex images. K-means is the well-known clustering imagenomics [5, 6]. However, it is difficult to achieve stout and techniques but very sensitive to initial cluster centers and easy perfect pathological image segmentation as these images convergences to local optima. Therefore, researchers are frequently reveal background clutter with many noises, artifacts employing Nature-Inspired Optimization Algorithms (NIOA) in such as blurred regions introduced during image acquisition, and this domain. This study develops Cuckoo Search (CS) algorithm based image clustering model for the proper segmentation of poor contrast between the foreground and the background. breast histopathology images. Experimental results show that CS Second, there exist significant variations on cell size, shape, and provides better-quality segmented images compare to classical K- intracellular intensity heterogeneity [5, 6]. means algorithm by considering the computational time, fitness In this study, proper segmentation of breast values and the values of quality parameters. histopathology images is the main aim. Many efforts have been performed to attain automated segmentation of breast KEYWORDS histopathology images which includes thresholding [7, 8], Clustering, K-means, Image Segmentation, Optimization, Swarm watershed method [9, 10], Active Contour model [8, 11], edge intelligence, Histopathology image. based approach [14], neural network [15, 16] etc. A Particle Swarm Optimization (PSO) with Otsu criterion based multi-level thresholding technique was proposed by Jothi and Rajam [7] to 1 Introduction automatically segment the nuclei from hematoxylin and eosin Breast Cancer is the mainly widespread kind of cancer in women (H&E) – stained breast histopathology images. To remove noise, worldwide [1]. Present breast cancer clinical practice and the input image filtered by 3x3 gaussian filter. Experimental result treatment mostly depend on the evaluation of the disease’s proved that this method automatically segmented the nuclei diagnosis. Bloom-Richardson grading system [2] describes the effectively. A Localized Active Contour Model (LACM) in scoring of three morphological features of the dubious tissue, conjunction with an automatic technique for optimal curve which are fraction of tubule construction, amount of nuclear pleo- placement with Krill Herd Algorithm (KHA) was developed by morphism, and mitotic cell count. However, the scoring had been Beevi et. al. [8] for the segmentation of nuclei from breast performed by pathologists based on the visual assessment of the histopathology images. Based on Hausdorff (HD) and Maximum tissue’s biopsy sample under the microscope [3]. Therefore, Address Distance (MAD) measures segmentation performance researchers concentrate and suggest the use of image analysis was investigated. The proposed segmentation approach provided methods to mitigate the said issue [4]. Digital histopathology and superior results compared to GA, Bacterial Foraging Algorithm microscopy images carry out an important role in decision making (BFA), Harmony Search (HS) algorithm and FCM clustering in disease diagnosis, as they could provide wide information for method by considering the convergence rate, objective function computer-aided diagnosis (CAD), which facilitates quantitative values, computational time, sensitivity, precision and F-score. analysis of digital images with a high throughput processing rate Shen et. al. [9] developed one improved watershed algorithm by [5, 6]. At present, analysis of digital histopathology through image StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.47-54 Ljubljana, Slovenia, 9 October 47 incorporating opening-closing reconstruction and the distance The paper is organized as follows: section 2 transform with chamfer algorithm after color deconvolution, and demonstrates the problem formulation and brief implementation H-minima. It was claimed that the proposed segmentation model of CS algorithm. Section 3 describes the experimental results and accurately detect the nuclei and overcome the limitation of the paper is concluded in section 4. classical watershed algorithm like over-segmentation due to the sensitivity to noise. Another novel approach is to segment the nuclei regions 2. Image Clustering using Cuckoo Search (CS) and then resolve the overlapping or clump nuclei separation Algorithm through heuristic approaches like the Concave Point Detection Clustering is a process of organizing data into clusters that have [11]. Wienert et. al. [11] presented novel contour-based high intra-cluster and low inter-cluster similarity. It is clear that "minimum-model" cell detection and segmentation approach that intra-cluster similarity should be maximized and inter-cluster used minimal a priori information and detects contours similarity should be minimized. Based on this idea, objective independent of their shape. Experimental results proved that the functions are defined [24]. The best partitioning of a given data set proposed segmentation model capable to avoid the segmentation can be attained by minimizing/maximizing one or more objective bias with respect to shape features and allows for an accurate functions. The objective functions can be formed by capturing a segmentation with high precision (0.908) and recall (0.859). certain statistical–mathematical relationship among the individual A few researchers also presented different voting data items and the candidate set of representatives of each cluster algorithms, which cast votes along gradient directions amplifying (also known as cluster centroids) [25]. votes inside the centre of nuclei thereby locating the seed points as ones having maximum votes [12, 13, 14]. Consequently, the 2.1 Problem Formulation detected nuclei seed points had been either utilized to initialize Suppose one specific dataset consists of 𝐶 classes (i.e. 𝐶 active contours [12, 13] or an edge grouping algorithm [14]. 1, 𝐶 Recently, deep neural network proved its effective performance in 2, … , 𝐶𝑐) and 𝑁 features. Therefore, the clustering problem is the finding of the optimal position of 𝐶 centroids in an 𝑁-dimensional breast histopathology image segmentation field [15, 16]. Su et. al. space i.e. each centroid is an 𝑁 -dimensional vector. With this [15] employed one fast Deep convolutional neural network (CNN) premises, the ith individual or solution of the applied optimization for pixel-wise region segmentation of breast histopathology algorithm is a vector with 𝑁. 𝐶 components which can be denoted images. Experimental results proved that the proposed as follows [19, 26]: segmentation model gave superior performance over both the LBP feature-based and texton-based pixel-wise methods within less 𝑋 1, 𝑋2, … … … . 𝑋𝐶) (1) computational time. Naylor et. al. [16] developed one hybrid 𝑖 = (𝑋𝑖 𝑖 𝑖 𝑗 𝑗 𝑗 𝑗 nuclei segmentation model by combining deep learning and Where , 𝑋 = (𝑥 , 𝑥 , … … … . 𝑥 ) 𝑖 1,𝑖 2,𝑖 𝑁,𝑖 mathematical morphology. Test results showed the promising performance of the proposed model. So any solution in the population of the employed optimization Although, clustering based segmentation which shows algorithm consists of 𝑁. 𝐶 components, each of which can take its effective performance in hematopathology [17] or other any real value. histopathology [18] image segmentation domain, but have not The fitness function 𝐹𝑖𝑡 has been calculated by summing out the been used in breast histopathology image field according to best Euclidean distance between the data vector instance 𝑏𝑘 and the of the knowledge. Therefore, this study concentrates to apply the centroid of class 𝐶𝐿 it belongs to according to minimum distance clustering based segmentation to segmentize the different regions 𝐶𝐿 criterion to the corresponding centroid i.e. (𝑋 𝑚𝑖𝑛(𝑏𝑘)) as in K- of the breast histopathology images. K-means is the well-known 𝑖 clustering techniques but sensitive to initial cluster centres and means. easy convergences to local optimization. Therefore, Nature- 𝐷𝑣 𝐶𝐿 Inspired Optimization Algorithms (NIOA) are successfully 𝐹𝑖𝑡 (𝑋 𝑚𝑖𝑛(𝑏𝑘) (2) 𝑖) = ∑ 𝑑 (𝑏 𝑘=1 𝑘, 𝑋 ) 𝑖 employed to overcome the problems of K-means in image clustering domain [19-23]. For example, Orman et. al. [20] 𝐷𝑣 is the number of data vectors to be clustered. 𝑑(. , . ) is the developed Particle Swarm Optimization (PSO) based satellite and Euclidean distance, 𝑋𝑖 is the ith solution of the population. So by MRI image clustering model and claimed that it outperformed choosing the discussed fitness function, the problem can be some state-of-the-art methods for image classifier such as K- considered as a minimization problem which is defined as means, Fuzzy C-means, K-Harmonic means and Genetic follows: Algorithm based model. In this study, Cuckoo Search (CS) algorithm has been employed and compared with classical K- 𝑋𝑜 = Arg[Min∀𝑖(𝐹𝑖𝑡(𝑋𝑖))] (3) means algorithms. Experimental results show that CS provides better-quality segmented images compare to classical K-means by 𝑋𝑜 is the optimal set of centroids. In the case of image clustering, considering the values of objective (fitness) function, 𝐶 depends on user, 𝑁 = 3 for RGB colour image, 𝐷𝑣 is equal to computational time and quality parameters. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 50 image size. The partitions into 𝐶 classes should maintain the In CS, exploration of the search space has been done by the following properties: following expression: 1. Each cluster should have at least one data vector assigned i.e., 𝑥𝑡𝑖,𝑗 = (𝑈𝑏𝑗 − 𝐿𝑏𝑗) ∗ 𝑈𝑗(0, 1) + 𝐿𝑏𝑗 (8) 𝐶𝑖 ≠ ∅ ∀𝑖 ∈ {1, 2, … . . , 𝑐} 2. Two different clusters should have no data vector in Where, 𝑈𝑏𝑗 and 𝐿𝑏𝑗 are the upper and lower bound of the specific common i.e., variable. 𝑈𝑗(0, 1) is the random variable drawn from the uniform 𝐶𝑖 ∩ 𝐶𝑗 = ∅, ∀𝑖 ≠ 𝑗 𝑎𝑛𝑑 𝑖, 𝑗 ∈ {1, 2, … , 𝑐}. distribution. But, this exploration ability of the CS algorithm 3. Each data vector should definitely be attached to a crucially depends on the probability 𝑝𝑎 ∈ [0,1] as this fraction of cluster i.e. nests is abandoned. ∪𝑐𝑖−1 𝐶𝑖 = 𝐷𝑣 Pseudo Code of the traditional CS is given as Algorithm 1. 2.2 Cuckoo Search (CS) Algorithm Cuckoo search (CS) algorithm is a powerful Algorithm 1: Cuckoo Search Algorithm optimization algorithm proposed by Xin-she Yang and Suash Deb in 2009 under the inspiration of the obligate brood parasitism of Step-1: Take objective function and generate initial some cuckoo species by laying their eggs in the nests of other host population of 𝑛 solution randomly using Eq.8. birds [27, 28]. Step-2: While termination condition does not meet Do A solution in the original cuckoo search algorithm corresponding Step-3: for 𝑖=1 to 𝑛 Do to cuckoo nests represents the position of the cuckoo egg within Step-4: Generate new solutions around 𝒙𝑖 with Lévy the search space. Mathematically, this position is defined as: Flight as per Eq.5 Step-5: 𝑓𝑡 = Suppose the new solution is 𝒖𝒊 and find the fitness 𝑥𝑡 𝑡 𝑖 = {𝑥𝑖,𝑗 }, for 𝑖 = 1, … . , 𝑛 and for 𝑗 = 1, … … . , 𝑑 (4) values of 𝒖𝒊 Step-6: 𝑗 = [𝑟𝑎𝑛𝑑 (0, 1) ∗ 𝑛 + 1] Where, n denotes the number of cuckoo nests in the population, d Step-7: if 𝑓𝑡<𝑓𝑖 then is the dimension of the problem to be solved, and t the generation Step-8: 𝒙 number. Generation of new solution signifies the exploitation of 𝑗 = 𝒖𝒊; 𝑓𝑗 = 𝑓𝑡 the current solutions is carried out by using the Lévy flight Step-9: end if distribution expressed as: Step-10: if 𝑟𝑎𝑛𝑑 (0, 1) < 𝑃𝑎 then Step-11: Do the initialization of worst nest according to Eq.8 𝑥𝑡+1 𝑡 𝑖 = 𝑥𝑖 + 𝛼. 𝐿 é𝑣𝑦() (5) and 𝑃𝑎 Step-12: end if 𝛼 > 0 represents a scaling factor of the step size drawn from Lévy Step-13: if 𝑓𝑡<𝑓𝑚𝑖𝑛 distribution i.e. 𝐿 é𝑣𝑦() . Lévy distribution has the ability of Step-14: 𝒙𝑏𝑒𝑠𝑡 =𝑢𝑖 ; 𝑓𝑚𝑖𝑛=𝑓𝑡; //replace the global best solution exploring a large amount of search space. In this study, Step-15: end if Mantegna’s algorithm [28] has been used to generate Lévy Step-16: end for distribution. It produces random numbers according to a Step-17: end While symmetric Lévy stable distribution as described below— 𝜎 = [𝛤(1 + 𝛽) 𝑠𝑖𝑛(𝜋𝛽/2)/𝛤((1 + 𝛽)/2)𝛽2(𝛽−1)/2)]1/𝛽 (6) 3. Experimental Results Where, Γ is the gamma function, 0< β ≤ 2. σ is the standard The experiment has been performed over 40 colour breast deviation. As per Mantegna’s algorithm, the step length v can be histopathology images with MatlabR2012b and Windows-7 OS, calculated as, x64-based PC, Intel(R) Pentium (R)-CPU, 2.20 GHz with 4 GB RAM. The proposed methods are tested on images taken from 𝑣 = 𝑥 UCSB Bio-Segmentation Benchmark dataset [29, 30]. Fig.1 │ 𝑦 │ 1/𝛼 ⁄ (7) represents the original images of different breast histopathology images. Here, x and y are taken from normal distribution and 𝜎𝑥 = 3.1 Parameter Setting 𝜎, 𝜎𝑦 = 1 . Where 𝜎 is the standard deviation. The resulting distribution has the same behavior of Lévy distribution for large Parameter setting is very crucial for any Nature-Inspired values of the random variables. Mantegna’s algorithm associates Optimization Algorithm (NIOA) and most of the cases it is with faster computational speed in the range 0.75 ≤ α ≤ 1.95 performed from experience. The parameter setting of CS [28]. algorithm is as follows: 𝑝𝑎 = 0.2 , 𝛽 = 1.5 , 𝛼 = 0.01, population StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 51 size (𝑛) = 50. The Stopping Criterion for both CS and K-means [22] is the number of Fitness Evaluations (FEs), and the maximum number of FEs (i.e. MAX_FE) has been taken as K- 1000 × 𝐷 mean . Where, 𝐷 is the number of clusters. In K-means, new s centroid calculation has been considered as Fitness Evaluations (FEs). (d) (e) (f) 3.2 Segmentation Quality Parameters Fig.2. Results of clustering for Fig.1(a): (a)-(c) represent results of CS Segmentation efficiency of the employed methods are judged with using cluster number 4, 6 and 8 respectively; (d)-(f) represent results the help of three well-known image quality assessment parameters of K-means using cluster number 4, 6 and 8 respectively. namely Peak Signal to Noise Ratio (PSNR), Quality Index based on Local Variance (QILV) and Feature Similarity Index (FSIM). No. of Clusters =4 No. of Clusters =6 No. of Clusters =8 QILV is a performance measurement technique proposed by Santiago Aja-Fernandez [31, 32]. QILV is used to measure the structural information of the image. A great amount of the structural information of an image is coded in its local variance distribution. Local variances features of an image can CS assists to compare two images properly. Greater QILV values indicate better segmentation quality. PSNR [33, 34] is a pixel difference measurement (a) (b) (c) technique. This is computed by averaging the squared intensity of original image and output image. Large value of PSNR demonstrates better-segmented image. K- Zhang et al. proposed a new human vision measurement mean technique in 2011 called Feature Similarity Index (FSIM) [35]. s FSIM is mainly designed for gray scale images or luminance component of colour images. This method is a combination of two low level features namely Phase Congruency (PC) and Gradient (d) (e) (f) Magnitude (GM). Greater value of FSIM represents better- Fig.3. Results of clustering for Fig.1(d): (a)-(c) represent results of CS using cluster number 4, 6 and 8 respectively; (d)-(f) represent results segmented image. of K-means using cluster number 4, 6 and 8 respectively. Table 1. Average Quality parameters and other numerical results over 40 images Alg. Cl PSNR QIL FSI Fitnes Time STD. us. V M s 4 25.69 0.98 0.95 0.097 2.003 3.31 CS E-17 6 28.82 0.99 0.96 0.072 2.665 8.37 E-14 (a) (b) 8 30.72 0.99 0.97 0.068 3.108 1.23 E-14 Fig.1 Original breast cancerous histopathology images 4 24.81 0.97 0.90 0.189 45.14 ............ K- No. of Clusters =4 No. of Clusters =6 No. of Clusters =8 mea 6 26.11 0.97 0.91 0.127 50.99 ............ ns 8 27.80 0.98 0.93 0.102 56.84 ............ CS /* Best results obtained are given in bold*/ 3.3. Analysis of the experimental results Performance analysis of the CS and classical K-means algorithms (a) (b) (c) has been performed in the breast histopathology image clustering StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 52 domain by computing their objective (fitness) function analysis: A review. IEEE reviews in biomedical engineering, minimization ability, robustness in term of standard deviation 2, 147. (STD.) and computational time. Segmentation quality parameters [6] Irshad, H., Veillard, A., Roux, L., & Racoceanu, D. (2014). like QILV, PSNR and FSIM are also calculated to judge the Methods for nuclei detection, segmentation, and classification in digital histopathology: a review—current segmentation accuracy of the clustering models over cluster status and future potential. IEEE reviews in biomedical number 4, 6 and 8. CS algorithm based clustering model has been engineering, 7, 97-114. run 40 times for each image. The segmented images [7] Jothi, J. A. A., & Rajam, V. M. A. (2015). Segmentation of corresponding to Figs.1(a)-(b) are given as Figs.2-3 respectively. nuclei from breast histopathology images using PSO-based On the other hand, Table 1 represents the average values of Otsu’s multilevel thresholding. In Artificial Intelligence and fitness, standard deviation (STD.), computational time and quality Evolutionary Algorithms in Engineering Systems (pp. 835- parameters over 40 images. Table 1 shows that CS based 843). Springer, New Delhi. clustering model provide minimized fitness value within less [8] Beevi, S., Nair, M. S., & Bindu, G. R. (2016). Automatic computational time. The standard deviation also proves the segmentation of cell nuclei using Krill Herd optimization significant robustness of CS algorithm. The resultant segmented based multi-thresholding and localized active contour model. Biocybernetics and Biomedical Engineering, 36(4), 584-596. images of CS based model associated with greater QILV, FSIM [9] Shen, P., Qin, W., Yang, J., Hu, W., Chen, S., Li, L., ... & and PSNR over cluster number 4, 6 and 8. Therefore, it can be Gu, J. (2015). Segmenting multiple overlapping Nuclei in said that CS is the better than traditional K-means algorithm with H&E Stained Breast Cancer Histopathology Images based on the MAX_FE based termination condition. an improved watershed. [10] Veta, M., Van Diest, P. J., Kornegoor, R., Huisman, A., Conclusion Viergever, M. A., & Pluim, J. P. (2013). Automatic nuclei segmentation in H&E stained breast cancer histopathology A Cuckoo Search (CS) algorithm based clustering model has been images. PloS one, 8(7), e70221. [11] Wienert, S., Heim, D., Saeger, K., Stenzinger, A., Beil, M., proposed for the proper segmentation of breast histopathology Hufnagl, P., ... & Klauschen, F. (2012). Detection and images. The performance of the CS algorithm based clustering segmentation of cell nuclei in virtual microscopy images: a model has been compared to K-means algorithms in terms of minimum-model approach. Scientific reports, 2, 503. fitness, computational time and quality parameters. Values of [12] Qi, X., Xing, F., Foran, D. J., & Yang, L. (2012). Robust quality parameters indicate that CS based clustering model segmentation of overlapping cells in histopathology provide segmented images with higher QILV, FSIM and PSNR specimens using parallel seed detection and repulsive level compares to K-means based clustering model. Analysis of the set. IEEE Transactions on Biomedical Engineering, 59(3), results also shows that K-means also associates with huge 754-765. computational time when number of clusters increases and this [13] Xu, J., Janowczyk, A., Chandran, S., & Madabhushi, A. time consume problem has been successfully surmounted by using (2011). A high-throughput active contour scheme for segmentation of histopathological imagery. Medical image CS algorithm. analysis, 15(6), 851-862. Several future directions exist of this study such as use of fuzzy [14] Paramanandam, M., Thamburaj, R., Manipadam, M. T., & logic based clustering, rough set based clustering, formulation of Nagar, A. K. (2014, May). Boundary extraction for the multi-objective clustering models, and use these clustering imperfectly segmented nuclei in breast histopathology models for different kinds of images. images–a convex edge grouping approach. In International Workshop on Combinatorial Image Analysis (pp. 250-261). REFERENCES Springer, Cham. [1] Ferlay, J., Soerjomataram, I., Ervik, M., Dikshit, R., Eser, S., [15] Su, H., Liu, F., Xie, Y., Xing, F., Meyyappan, S., & Yang, L. Mathers, C., ... & Bray, F. (2015). GLOBOCAN 2012 v1. 0, (2015, April). Region segmentation in histopathological Cancer Incidence and Mortality Worldwide: IARC breast cancer images using deep convolutional neural CancerBase No. 11. Lyon, France: International Agency for network. In Biomedical Imaging (ISBI), 2015 IEEE 12th Research on Cancer; 2013. International Symposium on (pp. 55-58). IEEE. [2] Elston, C. W., & Ellis, I. O. (1991). Pathological prognostic [16] Naylor, P., Laé, M., Reyal, F., & Walter, T. (2017, April). factors in breast cancer. I. The value of histological grade in Nuclei segmentation in histopathology images using deep breast cancer: experience from a large study with long‐term neural networks. In Biomedical Imaging (ISBI 2017), 2017 follow‐up. Histopathology, 19(5), 403-410. IEEE 14th International Symposium on (pp. 933-936). IEEE. [3] Robbins, P., Pinder, S., De Klerk, N., Dawkins, H., Harvey, [17] Shafique, S., & Tehsin, S. (2018). Computer-Aided J., Sterrett, G., ... & Elston, C. (1995). Histological grading Diagnosis of Acute Lymphoblastic of breast carcinomas: a study of interobserver agreement. Leukaemia. Computational and mathematical methods in Human pathology, 26(8), 873-879. medicine, 2018. [4] Meijer, G. A., Beliën, J. A., Van Diest, P. J., & Baak, J. P. [18] Tosta, T. A. A., Neves, L. A., & do Nascimento, M. Z. (1997). Origins of... image analysis in clinical pathology. (2017). Segmentation methods of H&E-stained histological Journal of clinical pathology, 50(5), 365. images of lymphoma: a review. Informatics in Medicine [5] Gurcan, M. N., Boucheron, L., Can, A., Madabhushi, A., Unlocked, 9, 35-43. Rajpoot, N., & Yener, B. (2009). Histopathological image StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 53 [19] Das, S., & Konar, A. (2009). Automatic image pixel Computer Science Research Conference, University of clustering with an improved differential evolution. Applied Maribor, Slovenia, pp.5-12, 2017. Soft Computing, 9(1), 226-236. [35] Zhang, L., Zhang, L., Mou, X., & Zhang, D. (2011). FSIM: a [20] Omran, M., Engelbrecht, A. P., & Salman, A. (2005). feature similarity index for image quality assessment. IEEE Particle swarm optimization method for image clustering. transactions on Image Processing, 20(8), 2378-2386. International Journal of Pattern Recognition and Artificial Intelligence, 19(03), 297-321. [21] Xin Ye & Yong-Xian Jin (2016) A Fuzzy C-Means Algorithm Based on Improved Quantum Genetic Algorithm,” International Journal of Database Theory and Application, vol. 9-1, pages 227-236. [22] Kapoor, S., Zeya, I., Singhal, C., & Nanda, S. J. (2017). A Grey Wolf Optimizer Based Automatic Clustering Algorithm for Satellite Image Segmentation. Procedia Computer Science, 115, 415-422. [23] Li, H., Zhang, S., Zhang, C., Li, P., & Cropp, R. (2017). A novel unsupervised Levy flight particle swarm optimization (ULPSO) method for multispectral remote-sensing image classification. International Journal of Remote Sensing, 38(23), 6970-6992. [24] Liang, Y., Zhang, M., & Browne, W. N. (2014, December). Image segmentation: a survey of methods based on evolutionary computation. In Asia-Pacific Conference on Simulated Evolution and Learning (pp. 847-859). Springer, Cham. [25] Bong, C. W., & Rajeswari, M. (2012). Multiobjective clustering with metaheuristic: current trends and methods in image segmentation. IET image processing, 6(1), 1-10. [26] De Falco, I., Della Cioppa, A., & Tarantino, E. (2007). Facing classification problems with particle swarm optimization. Applied Soft Computing, 7(3), 652-658. [27] Yang, X. S., & Deb, S. (2009, December). Cuckoo search via Lévy flights. In Nature & Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on (pp. 210-214). IEEE. [28] Yang, X. S. (2010). Nature-inspired metaheuristic algorithms, Luniver press. [29] Gelasca, E. D., Byun, J., Obara, B., & Manjunath, B. S. (2008, October). Evaluation and benchmark for biological image segmentation. In Image Processing, 2008. ICIP 2008. 15th IEEE International Conference on (pp. 1816-1819). IEEE. [30] Gelasca, E. D., Obara, B., Fedorov, D., Kvilekval, K., & Manjunath, B. S. (2009). A biosegmentation benchmark for evaluation of bioimage analysis methods. BMC bioinformatics, 10(1), 368 [31] Aja-Fernandez, S., Estepar, R. S. J., Alberola-Lopez, C., & Westin, C. F. (2006, August). Image quality assessment based on local variance. In Engineering in Medicine and Biology Society, 2006. EMBS'06. 28th Annual International Conference of the IEEE (pp. 4815-4818). IEEE. [32] Dhal, K. G., Sen, M., & Das, S. (2018). Multi-Thresholding of Histopathological Images Using Fuzzy Entropy and Parameterless Cuckoo Search. In Critical Developments and Applications of Swarm Intelligence (pp. 339-356). IGI Global. [33] Suresh, S., & Lal, S. (2017). Multilevel thresholding based on Chaotic Darwinian Particle Swarm Optimization for segmentation of satellite images. Applied Soft Computing, 55, 503-522. [34] Dhal, K. G., Fister Jr., I. & S. Das (2017). Parameterless Harmony Search for image Multi-thresholding. 4th Student StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 54 Time series classification with Bag-Of-Words approach Domen Kavran Faculty of Electrical Engineering and Computer Science Koroska cesta 46 Maribor, Slovenia domen.kavran@um.si ABSTRACT tained through statistical analysis or by calculating features The amount of data generated every day increases each year specifically selected for a given dataset, though expert knowl- and the pace is accelerating with development of Internet edge is needed. Presented alternative approach, derived of Things (IoT). Gathered data solely doesn’t contain much from Bag-Of-Words [17], needs no prior knowledge about information, but with machine learning additional informa- provided data. Main part is the definition of dictionary tions and hidden patterns can be obtained to contribute to words – segments, which are extracted from training time se- time series analysis. ries data and later clustered. Segments of individual time se- ries are then compared with dictionary words and histogram General purpose and problem specific time series feature ex- of word occurances is formed. Histogram is a feature vector traction methods have been developed over the years. New representing individual time series. feature extraction approach, derived from Bag-Of-Words, is presented in this paper. Main part of the approach is obtain- Bag-Of-Words approach was originally intended for docu- ing a dictionary of time series segments – the so-called words. ment and image classification. Same concepts can be applied K-Means clustering is used to form a dictionary containing to time series with great results. Presented approach uses K words, which is then used to define a feature vector of elements of well-known image patch extraction algorithm to an individual time series as a histogram of word occurances obtain overlapping windows or segments, containing parts inside it. Described approach can be used for feature extrac- of time series data. To speed up the training phase and tion of time series without prior knowledge of data’s nature. classification process, discrete wavelet transform was used. Moreover, the approach is robust and produces good clas- The transform is known for its role in data compression and sification results. Highest accuracy of 99.96% was achieved image processing [3]. That provided a suitable way of re- using datasets, presented in Results. ducing each segment’s feature vector dimensionality. Mini Batch K-means clustering was used to speed up the dictio- Keywords nary creation process. time series, classification, machine learning, bag-of-words In second section of the paper, procedure of feature extrac- tion is described. Classification was done by 1-nearest neigh- 1. INTRODUCTION bor algorithm, using Chi-squared distance measure and then Technological progress made in industries, like automotive, compared with the results of support vector machines and healthcare and electronics, over the past years resulted in in- random decision forests in Results. creased amount of produced data. Large complex datasets, often referred to as Big Data, must be analysed quickly and efficiently to reveal additional informations and hidden patterns. Data analysis aids companies with their prod- 2. TIME SERIES CLASSIFICATION uct development, research and customer services [5]. Differ- Classification pipeline is shown on Figure 1. Time series ent technologies and programming libraries have been devel- must be described with features, which appropriately present oped to help engineers in creating pipelines for manipulating occured events in time series and are independent of its data and extracting features. Unsupervised machine learn- length. Beforehand, input time series dataset has to be split ing algorithms are often used for analysing data and finding on training and test datasets. Words inside time series are correlation between variables. Various advanced supervised segments feature vectors, with features being approxima- techniques have been developed to solve regression and clas- tion coefficients of discrete wavelet transform. Dictionary sification tasks. Time series data have an important role in words are the result of clustering segments feature vectors, today’s largest industries and this paper presents a general extracted from training time series set. Feature vector of purpose time series feature extraction approach. each time series is the created histogram of dictionary words occurances. Broader interest in time series classification began at the start of the century [9], which led to development of many Original approach has a name Bag-Of-Words for classifying different feature extraction methods [16]. For machine learn- documents and Bag-Of-Features for image classification [6]. ing algorithms to be successful at classifying time series, Advantage of the approach is its robustness, simplicity and appropriate features must be selected. Features can be ob- good results on real-world data. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.55-59 Ljubljana, Slovenia, 9 October 55 Figure 1: Classification pipeline Histograms are often used in natural language processing number of approximation coefficients [17]. Figure 3 shows and computer vision problems, because local informations of application of discrete wavelet transform on a time series. observed object are presented. Those characteristics justify use of histograms as time series feature vectors. 2.1 Extraction of segments 2.1.1 Segmentation with sliding window algorithm Both training and test time series are split into overlapping segments with sliding window of length Wc and step length tc < Wc. Example of segments extraction is shown on Figure 2. Time series of length 3072 values is split onto segments of length Wc = 256 with step tc = 192. Segments are shown in or- ange color with grey overlapping parts. In most cases, in- dividual segment’s length should not exceed 10% of average time series length, although this percantage can differ be- tween datasets. Selected window length has a big impact on classification accuracy and should be carefully selected. Figure 3: Approximation coefficients of applied db3 discrete wavelet transform with different decomposition levels 2.2 Dictionary words K-means clustering has been applied on a set of segments feature vectors, extracted from training time series in previ- ous step. Result of clustering is K number of clusters with centroids being dictionary words. In terms of speed, K- means algorithm is not suitable for large datasets. Because Figure 2: Segmentation of a time series of the latter fact, alternative algorithm Mini Batch K-means, was used. Algorithm uses subset of the dataset per iteration 2.1.2 Feature extraction and, consequently, less computations are needed. Every segment is described with features being approxima- tion coefficients of discrete wavelet transform (DWT) func- For visualization purposes, conversion of segments multidi- tion for a selected decomposition level. With every increase mensional feature vectors into three dimensional was done, of decomposition level, number of approximation coefficients using principal component analysis (PCA). Mathematical is reduced by nearly a factor of two, but enough informa- transformation converts large number of potentially depen- tion is preserved to reconstruct original data. With selected dant variables to fewer independant variables – principal transform, frequency informations at lower frequencies are components, which hold the most information. Applying analyzed and time informations in higher frequencies are principal component analysis is one of the first steps in anal- gathered [17]. Additional benefit of the transform is data ysis of large, multivariate datasets [13]. Result of clustering noise reduction. Db3 discrete wavelet transform function at PCA output is visible on Figure 4 with individual cluster first decomposition level was used to define segment’s fea- being presented in unique color and have a centroid marked ture vector. That results in almost half of segment’s length with a black dot. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 56 measure and label is determined based on K nearest train- ing samples. Odd number should be selected for parameter K value, because classification label decision-making is done by majority vote [11]. Selection of parameter K value has a big effect on final classification accuracy. The best approach to select appropriate parameter K is by trial and error. Time complexity of the algorithm is large, because most compu- tational operations are being done during classification and not in training phase [10]. Chi-Square distance measure [18] was used, because it can measure differences between histograms. It is frequently used in classification of textures, objects and shapes. Chi- square distance measure takes distribution of values and their frequencies into account and also has an import char- Figure 4: Vizualization of ten clusters as a result of applying acteristic of weighing rarely occured values in histogram [1]. clustering on first three principal components of training Equation of Chi-square distance measure χ is segments feature vectors d 1 X (xik − xjk)2 χ2(xi, xj ) = (1) 2 xik + xjk k=1 Recommended size of dictionary is ranging from 1000 to where: 3500 words. The reason is that classification done with fewer number of words doesn’t reach the highest accuracy possible, x = feature vector but it starts to stabilize with a dictionary size above 1000 i, j = feature vectors indices words [17]. d = length of feature vectors 2.3 Time series features k = feature index Defining time series features starts with segmentation and feature extraction, described in Chapter 2.1. Segments fea- ture vectors are compared with dictionary words using 1- 2.4.2 Support vector machine nearest neighbors algorithm using Euclidean distance as dis- Algorithm is a part of linear classifiers group. It forms an tance measure. Histogram of dictionary word occurances is optimal hyperplane to maximize distance between parallel created and normalized with L2-norm. Example of time se- planes, placed on outer boundaries of training samples fea- ries histogram is shown in Figure 5. ture vectors, based on their labels [12, 15]. Support vector machine (SVM) is a binary classifier, but can also be used for multilabel classification. Multiple binary classifiers are formed, with i-th label being treated as positive and the rest as negative. Described approach is called One-Vs-All [14]. Alternative approach has a name One-Vs-One, where a binary classifier is formed for every pair of labels. One-Vs- One approach is useful at dealing with unbalanced datasets, but that comes at a cost of higher time complexity during training and classification process [8]. 2.4.3 Random forest Training starts by forming a set of decision trees with in- duced randomness. A sample is classified based on majority Figure 5: Normalized histogram based on a dictionary of ten vote of decision trees [7]. Number of trees, their depth, min- words imal number of training samples to split a node and minimal number of samples required to be at leaf node must be ad- Training time series, described with feature vectors, are used justed to optimize classification accuracy. Random forest is to train a classification model. For classification model test- a fast learning and general-purpose classification algorithm, ing, time series from test dataset are used. which is resistant to overfitting at large number of features [4]. To achieve high accuracy, large set of decision trees 2.4 Classification algorithms has to be created, but that also means slower classification Training classification models was done using the following process. described classification models. 3. RESULTS 2.4.1 K-Nearest neighbors Presented feature extraction approach was implemented in K-Nearest neighbors (KNN) algorithm classifies a sample Python using scientific computing library NumPy. Machine based on distance between training samples and unclassified learning library scikit-learn was used for clustering and clas- sample. Euclidean distance is usually used as a distance sification. For discrete wavelet transform, open-source soft- StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 57 ware PyWavelets was used. Training and testing was done 4. CONCLUSION on the following computer hardware: Highest achieved classification accuracy on test datasets was 99.96%, with average across all three classification models being 85.75%. Feature extraction approach is appropriate • Intel Core i7-6700K processor for use in various industry related problems and at analysis • 16GB of DDR4 3200MHz memory of stock market, but medical use is questionable, because achieved accuracy must be at highest level possible to ensure Various open-source time series datasets [2] were used for medical safety. Best such case are classification scores for testing and are described in Table 1. Each dataset contains time series ECG5000, where highest achieved F1 score is time series of equal length and split in two classes or more. 86.89%, much lower than satisfying for critical medical data. Testing was done using 5-fold cross-validation with F1 score as classification accuracy measurement for all classification Parallel computing can be used for extraction of segments algorithms, presented in Chapter 2.4. Dictionaries contain- and at defining time series feature vectors. Presented feature ing 2000 words were used. Parameters W extraction approach is appropriate for integration in real- c and moving step t time systems and IoT devices, however training phase should c were choosen individually for every time series. The rea- son being is that their lengths differ and experimenting with be done separately from working environment. Higher clas- different parameter values was needed to reach best possible sification accuracy could be achieved with use of multivariate classification score. Classification results are presented in time series. Table 2. Table 1: Time series descriptions 5. REFERENCES [1] V. Asha, N. U. Bhajantri, and P. Nagabhushan. Time series Description GLCM based Chi-square Histogram Distance for CBF Simulated time series Automatic Detection of Defects on Patterned ECG signal of a patient Textures. International Journal of Computational ECG5000 having a heart failure Vision and Robotics, 2(4):302–313, 2011. FordA Engine sounds [2] A. Bagnall, J. Lines, W. Vickers, and E. Keogh. The Mallat Simulated time series UEA and UCR Time Series Classification Repository. Binary images contours Available at www.timeseriesclassification.com. ShapesAll distances from center [3] P.M. Bentley and J.T.E. McDonnell. Wavelet Accelerometer data gene- transforms: an introduction. Electronics and UWaveGestureLibraryAll rated during hand movement Communication Engineering Journal, 6(4):175–186, Brightness of astronomical 1994. StarlighCurves objects through time [4] G. Biau. Analysis of a Random Forests Model. Journal Measurements recorded from of Machine Learning Research, 13:1063–1095, 2012. Wafer sensors during the processing [5] Thomas H. Davenport. Big Data at Work. Harvard of silicon wafers Business Review Press, 2014. [6] F. Fang, H. Lu, and Y. Chen. Bag of Features Highest average classification F1 score 91.82% was achieved Tracking. International Conference on Pattern with SVM classification model, followed by random forest Recognition, 2010(46):153–156, 2010. and 1-nearest neighbor using Chi-square distance measure. [7] K. Fawagreh, M. Gaber, and E. Elyan. Random Biggest difference in classification results can be seen at forests: from early developments to recent UWaveGestureLibraryAll, where 1-NN classifier achieved F1 advancements. Systems Science and Control score of 25.53%, opposed to SVM’s score of 80.64%. F1 Engineering, 2(1):602–609, 2014. scores of all classification models are closest at classifying [8] A. Gidudu, G. Hulley, and T. Marwala. Image time series CBF, with a difference of only 0.75% between classification using SVMs: One-Against-One vs them. One-Against-All. Clinical Orthopaedics and Related Table 2: Classification F1(%) results No. of 1-Nearest neighbor, SVM, polynomial Time series Parameters Random forest classes Chi-square distance kernel, degree = 2 CBF 3 Wc=50, tc=5 99.14 99.89 99.35 ECG5000 5 Wc=10, tc=5 77.91 86.89 84.18 FordA 2 Wc=90, tc=5 70.41 89.96 81.92 Mallat 8 Wc=10, tc=5 98.78 99.96 97.08 ShapesAll 60 Wc=100, tc=5 83.31 80.14 62.19 UWaveGestureLibraryAll 8 Wc=50, tc=5 25.53 80.64 57.86 StarlightCurves 3 Wc=220, tc=5 91.47 97.56 96.89 Wafer 2 Wc=10, tc=5 98.52 99.54 99.04 F1 average / / 80.63 91.82 84.81 StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 58 Research, 0711.2914, 2007. [9] Juan J. Rodr Guez and Carlos J. Alonso. Boosting Interval-Based Literals: Variable Length and Early Classification. Series in Machine Perception and Artificial Intelligence, 57:149–171, 2002. [10] G. Guo, H. Wang, D. Bell, Y. Bi, and K. Greer. KNN Model-Based Approach in Classification. On The Move to Meaningful Internet Systems 2003: CoopIS, DOA, and ODBASE, pages 986–996, 2003. [11] E. M. Kamel, M. Wafy, H. M. Ibrahim, and I. A. Badr. Comparison of different classification algorithms for certain weed seeds’ species and wheat grains identification based on morphological parameters. IJCSI International Journal of Computer Science Issues, 12(5):110–116, 2015. [12] G. Oreški and S. Oreški. An experimental comparison of classification algorithm performances for highly imbalanced datasets. Central European Conference on Information and Intelligent, pages 4–11, 2014. [13] M. Richardson. Principal Component Analysis. 2009. [14] R. Rifkin and A. Klautau. In Defense of One-Vs-All Classification. Journal of Machine Learning Research, 5:101–141, 2004. [15] D. Srivastava and L. Bhambhu. Data Classification using support vector machine. Journal of Theoretical and Applied Information Technology, 12(1), 2005. [16] Michele A. Trovero and Michael J. Leonard. Time Series Feature Extraction. 2018. [17] J. Wang, P. Liu, M. F. H. She, S. Nahavandi, and A. Kouzani. Bag-of-words representation for biomedical time series classification. Biomedical Signal Processing and Control, 8(6):634–644, 2013. [18] W. Yang, L. Xu, X. Chen, F. Zheng, and Y. Liu. Chi-Squared Distance Metric Learning for Histogram Data. Mathematical Problems in Engineering, 2015:1–12, 2015. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 59 The problem of quantum computers in cryptography and post-quantum cryptography Dino Vlahek Faculty of Electrical Engineering and Computer Science, Maribor Koroška cesta 46 SI-2000 Maribor, Slovenia dino.vlahek@gmail.com ABSTRACT Cryptography (ECC)) or problem of factoring positive inte- This paper presents the problem that quantum computing gers is an example of (Rivest-Shamir-Adleman (RSA)) the brings to modern cryptography. The basics of post-quantum problems that quantum computers can solve faster and more cryptography and concepts of modern cryptography with an reliably. Despite the fact that there is a few more years (or emphasis on the most useful asymmetric encryption algo- decades) before the emergence of effective physical quan- rithms are shown. The paradigms of post-quantum cryp- tum computers [6], today experts in the field of cryptogra- tographic algorithms, which were implemented in the Open phy and security are already preventively solving the prob- Quantum Safe project and whose effectiveness can be com- lems brought by quantum computing. It is necessary to pared with the most popular modern ones, were explained know and understand which solutions, resistant to quan- and analysed further in this paper. To compare perfor- tum computing, already exist and on which mathematical mances, a test of the time and communication capabili- models they were based. Existing solutions of asymmet- ties of selected algorithms was made, the results of which ric cryptographic algorithms that are resistant to quantum were graphically and descriptively presented. The results of attacks will be compared to existing most popular asymmet- the experiment showed that there is an effective quantum- ric cryptographic algorithms (RSA, DH, ECC). Asymmet- resistant alternative to existing asymmetric encryption al- ric cryptographic algorithms, implemented within the Open gorithms. Quantum Safe project (Open Quantum Safe (OQS)) will be used, the efficiency of which will be compared with RSA, Categories and Subject Descriptors DH and ECC asymmetric encryption algorithms. Efficiency measurements will be made, which will yield the results of E.3 [DATA ENCRYPTION]: Miscellaneous; E.4 [CODING comparing the efficiency of quantum-resistant asymmetric AND INFORMATION THEORY]: Miscellaneous; D.2.8 algorithms (i.e., post-quantum cryptography) and existing [Software Engineering]: Metrics—complexity measures, asymmetric encryption algorithms (RSA, DH, ECC). performance measures 2. ASYMMETRIC CRYPTOGRAPHY General Terms The concept of asymmetric cryptography occurred due to Theory, Experiment an attempt to attack two biggest problems of symmetric cryptography: the problem of key distribution and digital Keywords signing. The key distribution problem in symmetric cryp- cryptography, post-quantum cryptography, quantum com- tography is defined by the way two participants share the puter, asymmetric encryption algorithms, keys same key over an unsecured communication channel. A dig- ital signature gives the recipient a reason to believe that a message has been created by a known sender who can 1. INTRODUCTION not decline the sent message and that the message has not Quantum computer is a computer model that works differ- been changed in the transition. Asymmetric cryptography ently from the classical one. It is based on quantum mechan- is based on two different keys: the encryption key and the ical phenomena, which makes it easier to solve certain prob- decryption key. The basic steps of asymmetric cryptography lems that classical computers can not solve or need for it in- are as follows [11]: finite resources [8]. For example, the problem of discrete log- arithm (Diffie-Hellman Key Exchange (DH), Elliptic-Curve • Each user makes a pair of keys that will be used to encrypt and decrypt the message. • Each user gives one key in a public register or in a publicly accessible file. This key is a public key, and the other is a private key. • Each user makes his own collection of public keys of other users with whom he communicates. If the sender wishes to send a confidential message to the recipient, StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.61-64 Ljubljana, Slovenia, 9 October 61 • Learning with errors based: FRODO Table 1: Use of most popular asymmetric algorithms Algorithm E/D Digital signature Key exchange • Ring learning with errors based: BCNS15, NewHope, RSA Yes Yes Yes MSR LN16 DH No No Yes ECC Yes Yes Yes • Module learning with errors based: Crystals-Kyber DSS No Yes No • Lattice-based based: NTRU • Error-correcting code based: McBits Table 2: The influence of quantum computers on standard cryptographic algorithms [2] Algorithm Type Influence 4. ANALYSIS OF THE EFFICIENCY OF POST- AES symmetric required larger key size QUANTUM CRYPTOGRAPHIC ALGO- SHA-3 hash function requiring larger output RITHMS RSA asymmetric it is no longer safe The experiment examines the efficiency of asymmetric cryp- ECC asymmetric it is no longer safe tographic encryption algorithms compared to existing asym- DSA asymmetric it is no longer safe metric standards (DH, RSA, ECC). Cryptographic algo- rithms implemented within the OQS project are used, the efficiency of which are compared with RSA, DH and ECC the sender encrypts the message using the public key asymmetric encryption algorithms. There is no need to an- of the recipient. alyze symmetric encryption algorithms because the length of the keys in symmetric encryption algorithms provides a higher level of security than in asymmetric ones. Effi- 3. POST-QUANTUM CRYPTOGRAPHY ciency measurements are made to verify the following hy- The most critical parts of the communication protocols were pothesis: there are quantum-resistant encryption asymmet- based mainly on three key cryptographic operations: public ric algorithms that could replace existing classical encryp- key encryption, digital signing and key exchange. These op- tion asymmetric algorithms (RSA, DH, ECC). erations were performed using DH method for key exchange, RSA cryptosystem and cryptosystem of elliptic curves. The The experiment is chosen because of its suitability, which security of these algorithms depends on the complexity of allows us to measure the time of execution of algorithms mathematical problems, such as the search for a common in a controlled environment, thus assessing their effective- factor or discrete logarithm problem. The Shor’s algorithm ness and performance. It is necessary to make a test case efficiently solves these mathematical problems, making all i.e., a test software that will measure the number of it- the public key cryptosystems weak. When we arrive in the erations of selected asymmetric encryption algorithms at quantum computer period, the most useful encryption meth- a given time. Post-quantum asymmetric encryption algo- ods will become obsolete [2]. It is assumed that the prob- rithms are selected from the OQS project,while modern ones ability that the RSA-2048 will get broken i.e., that a suf- are from the Crypto++ library. Selected asymmetric en- ficiently large quantum computer will be build by 2026, is cryption algorithms are [5]: 1/7, and 1/2 by 2031 [7]. Due to the fact that in symmet- ric encryption, with the enhancement of the key size, reli- able protection against quantum computers is also achieved, • OQS project: LWE Frodo recommended, RLWE BCNS15, in the research of the protection of asymmetric encryption RLWE MSR LN16, RLWE NewHope, SIDH MSR p503 the emphasis is on post-quantum cryptography or quantum- and SIDH MSR p751, SIKE MSR p503 and SIKE MSR resistant cryyptography(QRC). There are several sets of meth- p751. ods for post-quantum cryptography: Code-based, SHA-based, multivariate polynomials, the super singular isogenic Diffie- • Crypto++: RSA (1024, 2048, 3072), DH (512, 1024), Hellman, etc. The algorithms are still in the research phase ECC256 and are not guaranteed to be safe [12] [2]. All unnecessary background processes of the computer was 3.1 Open Quantum Safe turned off to minimize the impact of its background activity. The goal of the OQS project is to develop quantum-resistant Executional file (.exe) of tests was prepared and launched. cryptography and integration of existing post-quantum cryp- The time in which iterations of algorithms are performed is tographic asymmetric algorithms into one Libqos library limited to 30 seconds. Each test will be triggered 40 times + [47]. Libqos is an open-source library of quantum-resistant 10% of all tests (40) = 44. A total of 330 minutes or approx- cryptographic algorithms written in C language. The impor- imately 5 hours and 30 minutes is foreseen for performing all tance of the library lies in quantum-resistant cryptographic tests. To reduce the deviation of the number of iterations of asymmetric algorithms that focuses on key exchange [44]. individual algorithms that happens due to unexpected devi- In addition, OQS allows integration of Liboqs library into ations in the work of the computer, it is necessary to repeat OpenSSL [10]. The algorithms that the library includes are: the test numerous times. • 4.1 Working environments, frameworks and Supersingular isogeny Diffie–Hellman based: MSR SIDH algoritem, MSR SIKE algoritem tools StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 62 The main tool for working on the experiment is the Intel R Core TM i7-5500U processor, 8GB RAM and the Windows Table 3: Display of communication between parties 10 Pro version 1709. Post-quantum asymmetric encryption and security bits algorithms were implemented in the Libqos library, written Name A → B (bytes) B → A (bytes) in C, as part of the OQS project. Modern asymmetric en- Frodo 11377 11296 cryption algorithms are implemented within the Crypto++ BCNS15 4096 4096 open source library, written in C++ language. We installed MSR LN16 1824 2048 these libraries for the Visual Studio 2017 development envi- NewHope 1824 2048 ronment, on Windows SDK version 10.0.17134.0, on a 64bit SIDH p503 378 378 platform. Once all tests where performed, the data was ag- SIDH p751 564 564 gregated and analyzed in the Microsoft Excel tool. Graph- SIKE p503 378 402 Pad Prism tool was used to draw graphs that will show the SIKE p751 564 596 results of the experiment. DH-1024 128 128 DH-512 64 64 4.2 Implementation of the experiment ECDH256 32 32 To perform an experiment, i.e., measurements of the effi- RSA-1024 128 128 ciency of individual asymmetric modern and post-quantum RSA-2048 256 256 cryptographic algorithms, two test cases had to be performed: RSA-3072 384 384 One test case for measuring modern asymmetric encryption algorithms and the other for measuring post-quantum asym- metric encryption algorithms. Modern asymmetric encryp- Table 4: Display of classical and quantum security tion algorithms were used from the Crypto++ library ver- bits sion 7.0.0. Test case, the console application, was built in Name Classical bits Quantum bits Release Mode on a 64bit platform. The algorithms selected Frodo 144 130 for measurement were: RSA (1024, 2048, 3072), DH (512, BCNS15 86 87 1024), DH (1024) with predefined parameters, ECC256. Each MSR LN16 128 112 algorithm was running over a time period of 30 seconds, NewHope 229 206 where we measured the number of iterations. The number SIDH p503 192 128 of runs for each algorithm was saved in the .csv file, together SIDH p751 256 192 with the name and spent time. The test case was limited to SIKE p503 192 128 11 repetitions of measurement of each algorithm, each of the SIKE p751 256 192 7 algorithms was run 11 times in 30 seconds. The test case DH-1024 73 - was performed four times. Each lasted about 40 minutes, DH-512 50 - totalling about 2 hours and a half. For RSA, the number of ECDH256 136 - key generation and validation were measured, while for DH RSA-1024 73 - and EEC the number of generations and key aggremments. RSA-2048 103 - Post-quantum asymmetric encryption algorithms were used RSA-3072 128 - from the libqos library, which is part of the OQS prototype project. Test case, the console application was generated in Release Mode on a 64bit platform. The test case is sim- 4.3.1 Communication requirements ilar to the test case for modern cryptographic encryption The communication between the parties, A → B and B → algorithms. The algorithms selected for measurement were: A, was obtained from the program code and the implemen- LWE Frodo recommended, RLWE BCNS15, RLWE MSR tation of algorithms which was verified with data in sources LN16, RLWE NewHope, SIDH MSR p503 and SIDH MSR [10] [12] [3] [4] [1] [5] [6] [9]. The table 3 shows the commu- p751, SIKE MSR p503 and SIKE MSR p751. For each algo- nication requirements between parties, the amount of data rithm, the number of implementations over a time period of exchanged by the parties when the keys were generated and 30 seconds was measured. The number of runs for each algo- the table 4 shows the classical and quantum security bits of rithm was saved in the .csv file, together with the name and the algorithm. spent time. The test case was limited to 11 repetitions of measurement of each algorithm, each of the algorithms was run 11 times in 30 seconds. The test case was performed 4.3.2 Time complexity four times. Each lasted about 4 minutes, totalling about 3 Figure 1 shows the time required for the tested algorithm hours. For all algorithms the number of generation and key is executed once in milliseconds. From the graph, it can be agreements were measured. determined which algorithms are more successful i.e., faster. 4.3 Results and data analysis 4.3.3 Interpretation of results Apart from reliable cryptographic properties, the ideal algo- The most effective post-quantum asymmetric encryption al- rithm for asymmetric encryption should have as little com- gorithms are BCNS15, LN16 and NewHope. LN16 and munication requirements as possible, low memory consump- NewHope were faster than all post-quantum and also of all tion and the least possible execution time. This paper takes classic asymmetric encryption algorithms. The disadvan- into account the speed of execution and communication re- tage of the fastest post-quantum algorithms is relatively high quirements as the main metrics for comparison, while the communication complexity. In generating and distributing memory consumption is ignored. the keys, the LN16 and NewHope algorithms make 3,872 StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 63 communication between parties and the size of the output from the algorithm - key. The experiment has been success- fully performed, with many repetitions for better confidence into the results, which are then analyzed and graphically presented. Some potential candidate algorithms proved to be very promising. The interpretation of the results presents the most successful algorithms in three different domains: time complexity, communication complexity and key size. Today, when online communication is very fast, the differ- ence in communication complexity, given the speed of on- line communication, is negligible, and therefore it is safe to conclude that BCNS15, LN16 and NewHope algorithms, which have proven to be the fastest but have relatively large communication requirements, can become an alternative to RSA, ECC and DH. 6. REFERENCES [1] Alkim, E., Ducas, L., Pöppelmann, T., and Schwabe, P. Post-quantum key exchange - a new hope. IACR Cryptology ePrint Archive 2015 (2015), 1092. [2] Bernstein, D. J., Buchmann, J., and Dahmen, E. Post-quantum cryptography. Springer-Verlag Berlin Heidelberg, Tiergartenstraße 17, 69121 Heidelberg, Figure 1: Display of time complexity Germany, 2009. [3] Bos, J. W., Costello, C., Ducas, L., Mironov, bytes of communication, BCNS15 8,320, and classical algo- I., Naehrig, M., Nikolaenko, V., Raghunathan, rithms ∼ 10 times less (DH-1024, RSA-1024 256 bytes, RSA- A., and Stebila, D. Frodo: Take off the ring! practical, quantum-secure key exchange from lwe. 2048 512 bytes, RSA-3072 768 bytes, ECCDH 64 bytes ). IACR Cryptology ePrint Archive 2016 (2016), 659. Frodo algorithm has average time complexity, but the great- est communication. The algorithms of the super-singular [4] Costello, C., Longa, P., and Naehrig, M. Diffie-Hellman group (SIDH and SIKE) have the smallest Efficient algorithms for supersingular isogeny communication complexity, but are the slowest of all mea- diffie-hellman. IACR Cryptology ePrint Archive 2016 sured post-quantum encryption algorithms. The SIDH and (2016), 413. SIKE keys are comparable to the RSA equivalent. In prac- [5] Crypto++. Crypto++ library 7.0 | free c++ class tice, asymmetric encryption algorithms have predefined pa- library of cryptographic schemes. rameters, which results in faster performance. Figure 1 [6] Mermin, N. D. Quantum Computer Science: An shows that BCNS15, LN16 and NewHope are also faster Introduction. Cambridge University Press, Cambridge than DH-1024, which have predefined parameters. BCNS15, University Press University Printing House LN16 and NewHope do not have predefined parameters in Shaftesbury Road, Cambridge CB2 8BS United our case. RSA, DH and ECC have a smaller, better, com- Kingdom, 2007. munication complexity than most OQS algorithms, except [7] Mosca, M. Cybersecurity in an era with quantum the RSA-3072, which has an imperceptibly worse commu- computers: will we be ready? IACR Cryptology ePrint nication complexity than the SIDH MSR p501 and SIKE Archive 2015 (2015), 1075. MSR p501. When talking about communication complex- [8] Nielsen, M. A., and Chuang, I. L. Quantum ity, RSA, DH and ECC are noticeably more efficient, but Computation and Quantum Information. Cambridge the time complexity is on the BCNS15, LN16 and NewHope University Press, Cambridge University Press side. Of the most effective, the BCNS15 has the smallest University Printing House Shaftesbury Road, keys, the size of 86 bits or 78 quantum bits, the LN16 has a Cambridge CB2 8BS United Kingdom, 2010. pg. 555. size of 128 bits, 112 quantum bits and NewHope size of 229 [9] OQS. Github - open-quantum-safe/liboqs: C library bits, respectively 206 quantum bits. for quantum-resistant cryptographic algorithms. [10] OQS. Github - open-quantum-safe/openssl: Fork of 5. CONCLUSIONS openssl that includes quantum-resistant algorithms The purpose of this paper is the prevention, i.e., to get the and ciphersuites based on liboqs. results of the effectiveness of existing quantum-resistant al- [11] Stallings, W. Cryptography and Network Security: gorithms that can replace classical, non-resistant. The em- Principles and Practice, 5th ed. Prentice Hall Press, phasis was on an experiment that gave the results of com- Upper Saddle River, NJ, USA, 2010. paring the efficiency of post-quantum asymmetric crypto- [12] Stebila, D., and Mosca, M. Post-quantum key graphic algorithms implemented within the OQS project and exchange for the internet and the open quantum safe the existing asymmetric encryption algorithms (RSA, DH, project. In IACR Cryptology ePrint Archive (2016). ECC). For the purposes of the experiment, it was necessary to make a test case that measures certain parameters: time, StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 64 Named Entity Recognition and Classification using Artificial Neural Network Luka Bašek Borko Boškovič Fakulteta za elektrotehniko, računalništvo in Fakulteta za elektrotehniko, računalništvo in informatiko informatiko Koroška cesta 46 Koroška cesta 46 2000 Maribor, Slovenija 2000 Maribor, Slovenija luka.basek@student.um.si borko.boskovic@um.si ABSTRACT entity recognition. In this paper, we will analyze variants of Long-Short Term To solve the problem of Named entity recognition, a variety Memory (LSTM) and Gated Recurrent Unit (GRU) based of machine learning algorithms were used. The set of al- models for sequence tagging, special for Name Entity Recog- gorithms was composed of several statistical models such as nition (NER). The models which will be analyzed include the Hidden Markov Models (HMM) Florian et al. (2003) [4], LSTM network, bidirectional LSTM network (BI-LSTM), Maximal Entropy Models (MaxEnt) Chieu et al. (2003) [1], GRU network and bidirectional GRU network (BI-GRU) Conditional Random Fields (CRF) McCallum et al. (2003) and using pre-trained GloVe vectors 1, Part of speech and [12]. There are some machine learning methods but in this characters embedding for features. We evaluated our models paper, we decide to use deep learning methods. On CoNLL with data set for sequence labeling task CoNLL 2003 corpus. 2003 one of the solutions contain Recurrent Neural Networks We obtain F1 score on this dataset - 86.04% 2. (RNN) with LSTM cells Hammerton (2013) [7] and this is the start point of our work. Keywords The task is to explore deep learning methods in NLP and Natural Language Processing, Named Entity Recognition, more specific for Named Entity Recognition (NER). Back in Neural Network, Recurrent Neural Network, LSTM, GRU, the few years, the neural networks have proved to be effec- Keras, GloVe vectors tive in the NLP area such as Text Classification Zhang et al. (2015) [21], Sentiment Analysis Severyn et al. (2015) [17], 1. INTRODUCTION Part of speech tagging Wang et al. (2015) [19]. In the case of solving the problem of Name Entity Recogni- By developing information technologies, people today have a tion, Hammerton (2003) [7] using RNN with LSTM cells pre- quick and wide access to a large amount of data. Everyday sented by Hochreiter et al. (1997) [8]. Huang et al. (2015) we meet a lot of sources of knowledge such as social net- [9] presents more complex models for NER based on the works, news, reviews, blogs, etc. There is a lot of data but LSTM network, Bi-directional LSTM network, and various the data is simple and raw isolated facts which have some combinations with the CRF layer. meaning [15]. In the world is more and more data every In this paper, we propose a variety of recurrent neural net- day and data have to be analyzed to become a useful infor- works based models which include LSTM networks, bidirec- mation. The computer can quickly process data and store tional LSTM networks (BI-LSTM), GRU networks and bidi- the information. However, the computers without human rectional (BI-GRU) networks. Beside network architectures, presence can’t analyze text and provide information about we include additional features to help neural networks learn text. For this purpose, computer science has developed a about the context of words. We include pre-trained GloVe lot of methods and techniques for analyzing and discover- for word representation, Part of Speech tags and Characters ing knowledge. The field of Natural Language Processing Embedding. We evaluate our models on English data from (NLP) is an interdisciplinary area at the crossroads of com- CoNLL 2003 shared task Sang et al. (2003) [16]. Our best puter science, artificial intelligence and linguistics. Our goal F1 score is 86.05%. Slightly worse than current attractive is Information Retrieval, more specifically the task of Named solutions which have F1 score 91.21%, Xuezhe et al. (2016) 1https://nlp.stanford.edu/projects/glove/ [11] but this is a good starting point for improvements. 2The code of the this project is available at: https://github.com/lbasek/named-entity-recognition 2. MODELS In this section, we describe the models used in this paper: LSTM, BI-LSTM, GRU, BI-GRU. 2.1 LSTM Network For operating sequential data the RNN is the most used ap- proach. RNN takes as input a sequence of vectors 󰂓x = (x1, ..., xn) and return another sequence 󰂓h = (h1, ..., hn) that represents some information about the sequence by one- time unit. Reading articles about RNN, in theory, it works StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.65-70 Ljubljana, Slovenia, 9 October 65 but not in practice. The LSTM have been developed to avoid classic RNN problem about memory-cell and can han- dle the long-range dependencies. zt = σ(Wz ∗ ht−1 + Uf ∗ xt) LSTM was introduced in 1997 by Sepp Hochrieiter and Jür- rt = σ(Wr ∗ ht−1 + Ui ∗ xt) gen Schmidhuber [8]. LSTM cell has three gates: the forget 󰁨h gate, input gate, and output gate. Figure 1 shows the struc- t = tanh (W ∗ [ht−1 ∗ rt] + W ∗ xt) ture of the LSTM cell. All gates contain sigmoid function ht = (1 − zt) ∗ ht−1 + zt ∗ 󰁨 ht where the cell decide how much information will be blocked or passed from the cell. It’s known the sigmoid function takes input and presents the output values in the range [0,1]. where the output from update gate with zt and the output The value 0 means let nothing through, and the value of 1 from the reset gate is calculated with rt at the time t. ht is means let everything through. These gates have own weights the vector which contains information for the current cell at that are adjusted via gradient descent method. the time t and forwards this information into the network. Figure 2: The structure of the GRU cell [13]. 2.3 BI-LSTM / BI-GRU Network Figure 1: The structure of the LSTM cell [13]. In the task of NER, it would be nice to have access to both sides of input features, in our case sentences. Therefore, we using bidirectional LSTM/GRU network as proposed in The LSTM cell is performing by the following formulations Graves et al. (2013) [6]. The shortcoming of the layer with [11]: only LSTM cells is that it is only able to make use of the previous context of words and knowing nothing about the ft = σ(Wf ∗ ht−1 + Uf ∗ xt + bf ) future. The idea of the bidirectional layer is using two sepa- i rated hidden layers which are capture past and future infor- t = σ(Wi ∗ ht−1 + Ui ∗ xt + bi) mation. In the end, the value of output is equal of concate- 󰁨 Ct = tanh (Wc ∗ ht−1 + Uc ∗ xt + bC) nated these two hidden states. The graphic representation C of bidirectional RNN is presented in Figure 3. Using bidi- t = ft ∗ Ct−1 + it ∗ 󰁨 Ct rectional layer we have access to the long-range context in ot = σ(Wo ∗ ht−1 + Uo ∗ xt + bo) both input directions. ht = ot ∗ tanh (Ct) where σ is the element-wise sigmoid function. xt is the input vector at time t. ht is the hidden state vector which storing useful information at time t. Weight matrices are denoted by Ui, Uf , Uc, Uo for input xt and Wi, Wf , Wc, Wo for hidden state ht. Bias vector is denoted by bi, bf , bc, and bo. 2.2 GRU Network Gated Recurrent Unit or GRU is a variant of LSTM memory cell introduced in 2014 by Chung et al.[2]. GRU is a little bit simpler than LSTM, GRU has two gates: update gate z and reset gate r. Figure 2 shows the structure of the GRU cell. The update gate helps the model to determine how much of the past information needs to be passed along to the future while with the reset gate helps to determine how much information has to be forgotten.The GRU cell is Figure 3: Bidirectional layer of Recurrent Neural performing by the following formulations [3]: Network [5]. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 66 3. TRAINING 4. EXPERIMENTS In this section, we will present details about the training pro- In this section will describe the dataset for evaluation and cedure. Our project is created using the Python3 program- our experiments which include graphs and results. ming language and popular library Keras4 for implementing neural networks. For all models, we train our networks us- 4.1 Data Set ing the back-propagation algorithm with categorical cross- We test our model on dataset intended for named entity entropy loss function. For parameter optimization we using recognition. The dataset was introduced in 2003. On CoNLL RMSprop optimizer with learning rate η = 0.001 as rec- conference where was the shared task the language-independent ommended by Keras library documentation. At the output named entity recognition. The dataset was concentrate on layer of neural networks we using the Softmax activation four type of named entities: persons (PER), locations (LOC), function. The Softmax activation function calculates the organizations (ORG), names of miscellaneous entities (MISC) probability distribution over all classes/entities and chooses that don’t belong to previous three groups and no entity to- the class with highest probability for each word. For a vec- ken (O). The line of the dataset contains four fields: the tor z of dimensionality D, the Softmax function is defined word, part of speech tag, chunk tag, and name entity tag. as [10]: Our focus was on name entity tag and the format of named entity tag is IOB (Inside, Outside, Beginning) where tokens are labeled as B-label if the token is the beginning of a named ezi entity, I-label if it is inside a named entity but the first to- σ(zi) = 󰁓 for j = 1,...,D k ken within the named entity, or O otherwise. The tagging ezj j=1 scheme is the IOB scheme originally presented by Ramshaw et al. (1995) [14]. The dataset was contain training, testing and validation data for two languages, English and German To regularize our model we using dropout technique for re- [16]. In this paper, we pick the English language. ducing overfitting in neural networks [18]. We apply dropout The statistics of the dataset are shown in Table 1. We use on each input layer with 0.1 and spatial dropout after con- the true data, without any pre-processing. catenating all inputs with 0.3. Hidden layers contain RNN cells which have own dropout rate and a number of LSTM or GRU units. Hidden layers are configurable, details are Table 1: Dataset statistic, where columns Token and described below. Sentence refers to the number of tokens and sen- Model training and model structure are completely config- tences in the CoNLL 2003 dataset. urable with json file. The example of json file is displayed in Listing 1. Dataset Token Sentence { ”max epochs ” : 1 0 , Training 204567 14987 ” b a t c h s i z e ” : 3 2 , Validation 51578 3466 ” s a v e p a t h ” : ”models / gru−words−pos−c h a r s / ” , ” i n p u t s ” : ”words−pos−c h a r s ” , Testing 46666 3684 ” e m b e d d i n g s t r a i n a b l e ” : f a l s e , ”e m b e d d i n g s t y p e ” : ” g l o v e ” , 4.2 Features ” r n n t y p e ” : ”GRU” , ” r n n n u m l a y e r s ” : 3 , In this paper, we use three types of additional features to ” r n n b i d i r e c t i o n a l ” : t r u e , help our models to improve. To most important features is ” r n n h i d d e n s i z e ” : 1 0 0 , Word Embedding. The main problem of using methods of ”r n n d r o p o u t ” : 0 . 2 , deep learning in processing natural language is how to con- ”model name ” : ”GRU−example ” vert word into numbers. Word embedding is the technique } of creating a language model which mapping words from the vocabulary into a corresponding vector of real numbers. Listing 1: Example of model configuration over json We tried randomly initialized word vectors and pre-trained file. GloVe vectors with 100 dimensions. The results of using GloVe vectors are significantly better than in the case of the random initialization. With json file we made the list of different models and run Word embedding is able to capture syntactic and semantic our experiments. Model training is configurable with a num- information but an example of task like NER is very useful to ber of epochs and batch size for epoch training. The model have morphological and shape information about the word. structure is configurable with input features such as word A lot of NLP system with additional character-level features embedding, part of speech and character embedding. Hid- are reported better results [20]. Based on the good experi- den layers are configurable with RNN cell type, LSTM or ence from other articles, we apply character-level input to GRU, number of cells in the layer, number of hidden lay- one layer with LSTM cells and we notice improvements in ers, use of bidirectional layers and the dropout rate for each results. RNN layer. 4.3 Results 3https://www.python.org/ We were running our two experiments with four different 4https://keras.io/ models (LSTM, GRU, BI-LSTM, BI-GRU). The first exper- StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 67 iment was launched without any additional features and the second experiment was launched with all additional features: pre-trained word embedding, part of speech information and character embedding. All neural network structure contains 3 hidden layers with 100 LSTM/GRU cells and dropout rate 0.2. Neural networks were trained on 10 epoch with batch size 32. Results showed in Tables 2 and 3 are obtained by us- ing macro-averaging. A macro-average computing the met- ric independently for each class and then take the average, whereas a micro-average aggregate all classes and then com- pute the average. The main reason for using macro-average is a large number of tag O, with micro-average, we would have unfair results. The results shown in Table 2 are the results of models with- out any additional features. The best result of the first ex- periment has a BI-GRU where F1 score result is 78.61%. Be- side pre-trained word embedding and character embedding, we use the part of speech (POS) information for additional Figure 4: Epoch-by-epoch model evaluation on the features. validation set with accuracy metric where the model On the second experiment where we’ve included all addi- without any additional features is used. LSTM is tional features like pre-trained word embedding, part of speech shown with the dark blue, GRU with the red, BI- information and character embedding we’ve got the results LSTM with the light blue, and BI-GRU with the shown in Table 3. The best result of the second experiment pink line. has BI-GRU where F1 score result is 86.04%, however, the model BI-LSTM is very close with F1 score result is 84.93%. Table 2: Performance of our first experiment with- out any additional features evaluated on the test set presented by evaluation metrics: Precision, Recall, and F1 score. Model Precision Recall F1 LSTM 0.6487 0.7527 0.6821 GRU 0.6985 0.7589 0.7161 BI-LSTM 0.7995 0.7098 0.7414 BI-GRU 0.8529 0.7372 0.7861 Figure 5: Epoch-by-epoch result of loss function cal- culated on the model without any additional fea- tures. LSTM is shown with the dark blue, GRU Table 3: Performance of our second experiment with with the red, BI-LSTM with the light blue, and BI- additional features like word-embedding, POS infor- GRU with the pink line. mation, and character-embedding, evaluated on the test set presented by evaluation metrics: Precision, Recall, and F1 score. 5. CONCLUSIONS Model Precision Recall F1 In this paper, our focus was on classification and named entity recognition using neural network architectures. Our LSTM 0.8123 0.8162 0.8138 best results with model BI-GRU with additional features achieved satisfactory results compared with previously de- GRU 0.8085 0.8071 0.8056 veloped systems. We have achieved F1 score result 86.04%. BI-LSTM 0.8408 0.8616 0.8493 There is a lot of space for improvement in the future. For example, it’s necessary to explore the Conditional Random BI-GRU 0.8610 0.8604 0.8604 Fields method in cooperation with neural networks output layer which is used in some known NER systems. This would be the good start point for future work. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 68 Named entity recognition through classifier combination. In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003 - Volume 4, CONLL ’03, pages 168–171, Stroudsburg, PA, USA, 2003. Association for Computational Linguistics. [5] A. Graves, N. Jaitly, and A. rahman Mohamed. Hybrid speech recognition with deep bidirectional lstm. In In IEEE Workshop on Automatic Speech Recognition and Understanding (ASRU, 2013. [6] A. Graves, A. Mohamed, and G. E. Hinton. Speech recognition with deep recurrent neural networks. CoRR, abs/1303.5778, 2013. [7] J. Hammerton. Named entity recognition with long short-term memory. In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003 - Volume 4, CONLL ’03, pages Figure 6: Epoch-by-epoch model evaluation on the 172–175, Stroudsburg, PA, USA, 2003. Association for validation set with accuracy metric where the model Computational Linguistics. with all additional features is used. LSTM is shown [8] S. Hochreiter and J. Schmidhuber. Long short-term with the orange, GRU with the dark blue, BI-LSTM memory. 9:1735–80, 12 1997. with the red, and BI-GRU with the light blue line. [9] Z. Huang, W. Xu, and K. Yu. Bidirectional LSTM-CRF models for sequence tagging. CoRR, abs/1508.01991, 2015. [10] D. Jurafsky and J. H. Martin. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1st edition, 2000. [11] X. Ma and E. H. Hovy. End-to-end sequence labeling via bi-directional lstm-cnns-crf. CoRR, abs/1603.01354, 2016. [12] A. McCallum and W. Li. Early results for named entity recognition with conditional random fields, feature induction and web-enhanced lexicons. In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003 - Volume 4, CONLL ’03, pages 188–191, Stroudsburg, PA, USA, 2003. Association for Computational Linguistics. [13] C. Olah. Understanding lstm networks. 2015. Figure 7: Epoch-by-epoch result of loss function cal- [14] L. A. Ramshaw and M. P. Marcus. Text Chunking culated on the model with all additional features. Using Transformation-Based Learning, pages 157–176. LSTM is shown with the orange, GRU with the dark Springer Netherlands, Dordrecht, 1999. blue, BI-LSTM with the red, and BI-GRU with the [15] J. Rowley. The wisdom hierarchy: representations of light blue line. the dikw hierarchy. Journal of Information Science, 33(2):163–180, 2007. [16] E. F. T. K. Sang and F. D. Meulder. Introduction to 6. REFERENCES the conll-2003 shared task: Language-independent [1] H. L. Chieu and H. T. Ng. Named entity recognition named entity recognition. CoRR, cs.CL/0306050, with a maximum entropy approach. In Proceedings of 2003. the Seventh Conference on Natural Language Learning [17] A. Severyn and A. Moschitti. Twitter sentiment at HLT-NAACL 2003 - Volume 4, CONLL ’03, pages analysis with deep convolutional neural networks. In 160–163, Stroudsburg, PA, USA, 2003. Association for Proceedings of the 38th International ACM SIGIR Computational Linguistics. Conference on Research and Development in [2] J. Chung, Ç. Gülçehre, K. Cho, and Y. Bengio. Information Retrieval, SIGIR ’15, pages 959–962, New Empirical evaluation of gated recurrent neural York, NY, USA, 2015. ACM. networks on sequence modeling. CoRR, [18] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, abs/1412.3555, 2014. and R. Salakhutdinov. Dropout: A simple way to [3] R. Dey and F. M. Salem. Gate-variants of gated prevent neural networks from overfitting. J. Mach. recurrent unit (GRU) neural networks. CoRR, Learn. Res., 15(1):1929–1958, Jan. 2014. abs/1701.05923, 2017. [19] P. Wang, Y. Qian, F. Soong, L. He, and H. Zhao. [4] R. Florian, A. Ittycheriah, H. Jing, and T. Zhang. Part-of-speech tagging with bidirectional long StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 69 short-term memory recurrent neural network. 10 2015. [20] T. Young, D. Hazarika, S. Poria, and E. Cambria. Recent trends in deep learning based natural language processing. CoRR, abs/1708.02709, 2017. [21] X. Zhang, J. J. Zhao, and Y. LeCun. Character-level convolutional networks for text classification. CoRR, abs/1509.01626, 2015. StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference Ljubljana, Slovenia, 9 October 70 Context-dependent chaining of heterogeneous data [Extended Abstract] Rok Gomišček Tomaž Curk University of Ljubljana, University of Ljubljana, Faculty of Computer and Information Science Faculty of Computer and Information Science Večna pot 113, Večna pot 113, 1000 Ljubljana, Slovenia 1000 Ljubljana, Slovenia rok.gomiscek@fri.uni-lj.si tomaz.curk@fri.uni-lj.si ABSTRACT Since parallel chains between two indirectly connected ob- A typical heterogeneous data set may contain different types ject types can return different relations, we can see each of objects, where a small subset of direct relations among ob- chain representing a different context which presents a dif- ject types is supported by data. In our research we develop ferent kind of relation. For example, the structure of the methods to predict the relation between indirectly related protein-protein interaction networks, which are used to rep- object types by chaining connections on intermediate object resent functional relations among gene products, may vary types, and methods to discover contexts of indirect relations. greatly across different tissues. We propose to group par- allel chains according to their contexts and change the op- A chain CXZ is a sequence of relations that connect object timization criteria so that similar chains will be clustered types X and Z, while CXZ|T specifies that X and Z are together. We will evaluate various clustering methods, such connected through objects of type T . Two object types can as k-means, k-NN and hierarchical clustering. We will also have multiple parallel chains connecting them, each chain explore various possible data representations for clustering, providing a different prediction. Different chains might re- such as original data, approximations and product of factor sult in different predictions, each correctly describing the matrices on a path. relation, but in a different context. We will validate our model on synthetic and real data. We We wish to ensure that different chains between two indi- will create synthetic data where we will guarantee that the rectly connected object types result in similar predictions, target relation between indirectly connected object types but only when sharing the same context. When predicting can be predicted by a chain of connecting relations. We a new connection between object types using different paths will generate the data by creating relations between object between them, we might obtain different predictions. Our types where transitivity can be applied, that is, if xk 7→ vl proposal on how to deal with this is to group predictions of and vl 7→ zn are true then xk 7→ zn must also be true, different chains together based on their similarity. where 7→ denotes a function that maps objects to objects. This value will be used to evaluate the predictions of our First we will propose a method to improve the results of method by computing the squared Euclidean distance be- chaining matrices on different paths between two indirectly tween the actual data and the prediction. Some values will connected object types. To predict the relation between in- be removed from the data to simulate missing values and directly connected object types matrices on a given chain used for evaluation. We will also validate our model on real are multiplied and then all predictions can be combined to- data where there are multiple parallel paths between two gether. Transitivity of relations tells us that two objects indirectly connected object types. We can find these kind of that belong to two indirectly connected object types are con- data in biological data sets with relations connecting genes, nected if they connect to intermediate objects on some path. proteins, diseases, gene function annotation (gene ontology The number of intermediate objects between two objects can terms), pathways, and other biological entities. vary greatly, but that number is not taken into account. We will propose an approach to normalize the predictions by Keywords accounting for the number of different paths connecting ob- machine learning, matrix factorization, data fusion, chain- jects from the two object types. ing, transitivity StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-26-9.71 Ljubljana, Slovenia, 9 October 71 StuCoSReC University of Primorska Press www.hippocampus.si isbn 978-961-7055-26-9 Document Outline Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2018 5th Student Computer Science Research Conference. Koper: University of Primorska Press, 2018 (Front Cover) Colophone Preface Contents Primož Bencak, Dominik Sedonja, Andrej Picej, Alen Kolman, Matjaž Bogša ◆ Regulacija plovca v zračnem tunelu (zračna levitacija) na osnovi mehke logike Matej Moravec, David Letonja, Jan Tovornik, Borko Boškovič ◆ Razpoznavanje literature v dokumentih in določanje njihovih sklicev v besedilu Dejan Rupnik, Denis Ekart, Gregor Kovačevič, Dejan Orter, Alen Verk, Borko Boškovič ◆ Klasifikacija samomorilskih pisem Gregor Germadnik, Timi Karner, Klemen Berkovič, Iztok Fister ◆ Načrtovanje poprocesorja za pretvorbo NC/ISO G-kode v translacije za 3/5 osnega robota ACMA ABB XR701 Jamolbek Mattiev, Branko Kavšek ◆ Using constrained exhaustive search vs. greedy heuristic search for classification rule learning Aljaž Jeromel ◆ Real-time visualization of 3D digital Earth Melanija Vezočnik, Matjaž Branko Jurič ◆ Towards an enhanced inertial sensor-based step length estimation model Krishna Gopal Dhal, Iztok Fister Jr., Arunita Das, Swarnajit Ray, Sanjoy Das ◆ Breast Histopathology Image Clustering using Cuckoo Search Algorithm Domen Kavran ◆ Time series classification with Bag-Of-Words approach Dino Vlahek ◆ The problem of quantum computers in cryptography and post-quantum cryptography Luka Bašek, Borko Boškovič ◆ Named Entity Recognition and Classification using Artificial Neural Network Rok Gomišček, Tomaž Curk ◆ Context-dependent chaining of heterogeneous data