MAGISTRSKO DELO

(1)

UNIVERZA V LJUBLJANI PEDAGOŠKA FAKULTETA

JOŠT MLINARI ˇ C

PRIMER GEOMETRIJSKE OBRAVNAVE BESEDIŠ ˇ CA

MAGISTRSKO DELO

L

^JUBLJANA

, 2019

(2)

(3)

UNIVERZA V LJUBLJANI PEDAGOŠKA FAKULTETA

ŠTUDIJSKI PROGRAM: DVOPREDMETNI U ˇCITELJ SMER: FIZIKA - MATEMATIKA

KANDIDAT:

JOŠT MLINARI ˇ C

MENTOR:PROF

.

DR

. MATIJA CENCELJ

SOMENTOR:DOC

.

DR

. BOŠTJAN GABROVŠEK

PRIMER GEOMETRIJSKE OBRAVNAVE BESEDIŠ ˇ CA

MAGISTRSKO DELO

L

^JUBLJANA

, 2019

(4)

(5)

Zahvala

Iskreno se zahvaljujem mentorju prof. dr. Matiju Cenclju in somentorju doc. dr. Boštjanu Gabrovšku iz Fakultete za strojništvo, za vse nasvete in ideje, pomoˇc pri programiranju, za vodenje skozi magistrsko delo in za vse, s ˇcimer sta pripomogla k nastanku magistrskega dela.

Zahvala gre tudi partnerici, hˇcerki, staršem, sestri ter babici, za vso potrpežljivost in pod- poro, ki so mi jo izkazali v vseh letih študija in me spodbujali vse do konca.

(6)

(7)

POVZETEK

Pojem razdalje je eden izmed najosnovnejših pojmov v geometriji, ki ga spoznamo pri geometriji, že v nižjih razredih osnovne šole. Razdaljo pojmujemo kot numeriˇcno vrednost, pridobljeno z merjenjem. V magistrskem delu sta predstavljeni dve funkciji razdalje med besedami, ki temeljita na številu pojavitev besed v besedilih. Za nekaj množic besed izvedemo gruˇcenje z upoštevanjem definiranih funkciji razdalje.

Kljuˇcne besede:razdalja, gruˇcenje, jezik

(8)

ABSTRACT

The concept of distance is one of the basic geometric concepts, taught already at the early stages of elementary school. It is perceived as a numerical value obtained by measurement with a gauge. Here two distance functions between words are introduced, based on statistics of incidence in samples of texts. We cluster some sets of words in Slovenian language accor- ding to the two distance functions.

Keywords:distance, cluster, language

AMS MSC(2010): 51K05, 91C20

(9)

Kazalo

Kazalo slik 1

Kazalo programov 2

1 Uvod 3

2 Razdalja 4

2.1 Razliˇcni primeri razdalj . . . 4

2.2 Razdalja v evklidski geometriji . . . 4

2.3 Metrika . . . 5

2.3.1 Metriˇcni prostor . . . 6

2.3.2 Manhattanska ali taksi metrika (1-norma) . . . 7

2.3.3 Evklidska metrika (2-norma) . . . 7

2.3.4 Cebišova metrika (∞-norma) . . . .ˇ 8 2.3.5 P-ta metrika (p-norma) . . . . 8

2.3.6 Diskretna metrika . . . 8

2.3.7 Urejevalniška razdalja . . . 9

2.4 Matrika razdalj . . . 9

2.4.1 Evklidska matrika razdalj . . . 10

2.4.2 Poljubna matrika razdalj . . . 10

2.5 Razliˇcne metrike in matrike razdalj . . . 11

3 Gruˇcenje podatkov 14 4 Algoritmi 14 4.1 Algoritemk- means . . . 14

4.2 Algoritem DBSCAN . . . 15

4.2.1 Osnova za algoritem . . . 16

4.2.2 Originalni algoritem . . . 17

4.2.3 Prednosti DBSCAN algoritma . . . 20

4.2.4 Slabosti DBSCAN algoritma . . . 20

5 DBSCAN algoritem in razliˇcne metrike 22 5.1 Evklidska metrika . . . 22

5.2 Taksi metrika . . . 22

5.3 Šahovska metrika . . . 23

5.4 Ugotovitve . . . 24

6 Geometrijska obravnava jezika 26 6.1 Aplikacija Sketch Engine . . . 26

6.2 Iskanje in zapisovanje števila pojavitev . . . 26

6.3 Razdalja med dvema besedama . . . 29

6.3.1 Razdalja kot koliˇcnik preseka in unije števila pojavitev . . . 29

(10)

6.3.2 Razdalja kot koliˇcnik preseka in minimalnega števila pojavitev posame-

zne besede . . . 29

6.4 Lastnosti definirane razdalje . . . 30

6.5 Matrika razdalj . . . 30

6.6 Implementacija DBScan algoritma . . . 32

6.7 Program PAJEK . . . 35

7 Primeri razdalj in gruˇc za razliˇcne nabore besed 36 7.1 Primerjava rezultatov za razliˇcno definirani razdalji . . . 36

7.3 Primerjava gruˇcenja z razdaljo MIN in z razdaljo urejanja. . . 41

7.3.1 Doloˇcanje razdalje urejanja . . . 41

7.3.2 Primerjava rezultatov gruˇcenja . . . 42

7.5 Gruˇcenje sopomenk . . . 45

7.6 Analiza dveh skupin sorodnih besed . . . 47

7.7 Analiza razliˇcnih oblik besed . . . 48

8 Zakljuˇcek 51

Literatura 52

(11)

Kazalo slik

1 Razdalja med toˇckama A in B s pomoˇcjo Pitagorovega izreka. . . 5

2 Manhattanska razdalja oziroma geometrija taksijev - veˇc krajših možnih poti. . 8

3 Kralj stoji na polju F6, številke na posameznih poljih pa prikazujejo ˇCebiševo razdaljo med posameznim poljem in poljem F6. . . 9

4 ToˇckeA, BinCv ravnini s pripadajoˇcimi koordinatami in razdaljami. . . 11

5 Taksi razdalja med toˇckami A, B in C ter dolžine posameznih razdalj. S ˇcrno barvo so narisane tudi daljice oziroma evklidske razdalje. . . 12

6 Razliˇcne toˇcke. . . 18

7 Toˇcka A kot jedro in njena okolica². . . 18

8 Okolice toˇck znotraj gruˇce. . . 19

9 Okolica novih dveh toˇck gruˇce. . . 19

10 Okolica toˇckeG. . . . 20

11 Na levi strani je prikazana okolica dane toˇcke, na desni pa izvajanje DBSCAN algoritma in iskanje okolic posameznih toˇck z uporabo evklidske metrike. Ob pogojuminPts = 3, dobimo gruˇco treh toˇck (modra barva). . . . 22

12 Levo je prikazana taksi okolica toˇcke, desno pa je prikazano izvajanje DBSCAN algoritma in iskanje okolic posameznih toˇck z uporabo taksi metrike. Ob upo- števanju pogojaminPts = 3, ne obstaja nobena gruˇca. . . . 23

13 Levo je prikazana okolica toˇcke z uporabo šahovske metrike, desno pa je za isto metriko predstavljeno izvajanje DBSCAN algoritma in iskanje okolic posameznih toˇck. Ob upoštevanju pogojaminPts = 3dobimo gruˇco vseh toˇck (toˇcke znotraj modrih okolic). . . 24

14 Okolice za vse tri metrike: rdeˇca - taksi, ˇcrna - evklidska in zelena - šahovska. Toˇcka A leži v okolici ne glede na izbiro metrike, toˇcka B ne leži v okolici za taksi metriko, toˇckaC pa leži le v okolici za šahovsko metriko. . . 24

15 Zaˇcetni zaslon aplikacije Sketch Engine, kjer lahko izberemo eno izmed osnovnih funkcij na podlagi naših potreb. . . 27

16 Slika zaslona iskalnika v aplikaciji Sketch Engine. . . 27

17 Izpis podatkov o gruˇcah na zaslon. . . 36

18 Diagram prikazuje besede ter z neposrednimi povezavami oznaˇci tiste, ki sestavljajo gruˇco za²=0.87 inmi nP t s=3. . . 36

19 Diagram gruˇc besed z uporabo razdalje MIN. . . 37

20 Diagram gruˇc besed z uporabo razdalje PU. . . 37

24 Diagram gruˇc besed z uporabo razdalje PU. . . 40

25 Diagram gruˇc besed z uporabo razdalje PU. . . 40 26 Diagram gruˇce z razdaljo urejanja, za vhodna parametra²=0.6 inmi nP t s=3. 43 27 Diagram gruˇce z razdaljo urejanja, za vhodna parametra²=0.8 inmi nP t s=3. 43

(12)

28 Diagram gruˇce z razdaljo MIN za vhodna parametra²=0.941 inmi nP t s=3. . 44

31 Diagram gruˇce z razdaljo MIN za vhodna parametra²=0.93 inmi nP t s=4. . . 46

32 Diagram gruˇce z razdaljo PU za vhodna parametra²=0.99 inmi nP t s=4. . . 47

33 Diagram prikazuje dve skupini besed. V prvi skupini so besede oziroma posamezna podroˇcja znanosti, v drugi skupini pa so besedne vrste. . . 48

34 Prva najdena skupina besedseminvidel. . . . 49

35 Skupina besedsem, videlinšel. . . . 49

36 Skupina besedsem, bil, šelinvidel. . . . 50

Kazalo programov

1 Originalni DBSCAN algoritem. . . 17

2 Zapis števila elementov v matriko 8×8. . . 28

3 Doloˇcanje min(M(A), M(B))in zapis podatkov v matriko. . . 30

4 Izraˇcun razdalj med posameznimi besedami in zapis matrik razdalj. . . 31

5 Zapis besed v matriko (za izris diagrama in neposrednih povezav v programu Pajek). . . 32

6 Vhodna pogoja²inminPts. . . . 32

7 Iskanje toˇck, ki predstavljajo jedra. . . 33

8 Iskanje toˇck toˇck v okolici posameznih toˇck. . . 34

9 Del kode za izpis potrebnih podatkov na zaslon. . . 35

10 Dolocanje urejevalniške razdalje. . . 41

(13)

1 Uvod

V vsakdanjem življenju se neprestano sreˇcujemo s pojmom razdalje, ˇceprav se tega sploh ne zavedamo. Naj gre za urejanje prostora, velikost televizijskega ekrana, hojo, vožnjo z avtom, uˇcenjem v šoli, vedno je prisotna razdalja. Obstajajo razliˇcne definicije razdalje, nam naj- bližja pa je evklidska razdalja, ki predstavlja dolžino najkrajše poti med zaˇcetno in konˇcno toˇcko. Nas bo zanimala razdalja med posameznimi besedami, na podlagi katere bomo besede združevali v skupine. Pri slovenšˇcini so posamezne besede razdeljene v družine na podlagi korenov besed. Besedno družino tvorijo besede s skupnim korenom, to je skupna osnovna pomenska sestavina. Besedno družino na primer sestavljajomatematika,mate- matiˇcen, matematik, matematizirati, saj imajo skupen koren besedematemati. Z vidika slovenšˇcine besedne družine tvorimo na preprost naˇcin. Nas pa bo zanimalo, kako obliko- vati družino oziroma gruˇco besed, kot bomo besedno družino v nadaljevanju imenovali mi, z matematiˇcnimi operacijami in postopki. Izkaže se, da je iz vidika matematike tvorjenje besednih družin mnogo težje in zahteva veliko veˇc dela, kot tvorjenje s koreni besed. Poleg definicij razdalj oziroma metrik bomo poskušali zapisati ustrezne metrike in matrike razdalj med besedami, s katerimi bomo lahko doloˇcili razdalje med izbranimi besedami in na osnovi le teh besede združevali v skupine.

(14)

2 Razdalja

2.1 Razliˇcni primeri razdalj

Razdalja je številˇcni podatek, ki na podlagi meritev pove oddaljenost dveh toˇck, predmetov v ravnini ali prostoru. V matematiki je razdaljna funkcija, ki ji pravimo metrika, posplošitev pojma razdalje. To je funkcija, ki je odvisna od razliˇcnih pravil in opisuje elemente znotraj razliˇcnih prostorov, opredeli ali so si elementi blizu ali ne. Obstaja veliko razliˇcnih razdalj, poglejmo si nekatere definicije razdalj, ki jih lahko izmerimo:

• Razdalja doloˇcena kot dolžina najkrajše poti med dvema toˇckama (npr. navigacija).

• Razdalja doloˇcena kot dolžina poti med zaˇcetno in konˇcno toˇcko ter nazaj do zaˇcetne toˇcke (npr. kroženje Zemlje okoli Sonca).

• Razdalja kot najkrajša možna pot med dvema toˇckama v prostoru, ˇce predpostavimo, da med toˇckama ni nobenih ovir. Taki razdalji pogosto reˇcemoevklidska razdalja.

• Razdalja Manhattan ali taksi razdalja.

Poleg razdalj, ki jih lahko izmerimo, pa obstajajo tuditeoretiˇcne razdalje.V današnjih ˇcasih, se pogosto v raˇcunalništvu uporablja besedna zvezaurejevalniška razdalja("edit distance”) med dvema besedama, ki predstavlja razdaljo med razliˇcnimi besedami ali drugaˇce reˇceno doloˇci, kako povezani sta si dve besedi. Pri urejevalniški razdalji ne gre za povezanost besed v pomenu, temveˇc gre za število ˇcrk v katerih se dve besedi loˇcita, zato ta razdalja ni primerna za doloˇcanje sorodnosti besed na osnovi pomena. Na primer, ˇce vzamemo besedipesinpet.

Na prvi pogled bi rekli, da se ti dve besedi razlikujeta le v zadnji ˇcrki, urejevalniška razdalja je torej 1. Na podlagi urejevalniške razdalje lahko trdimo, da sta ti besedi sorodni, saj se razlikujeta le v eni ˇcrki. A po premisleku, oziroma na podlagi iger asociacij, bi hitro ugotovili, da besedipesinpetnista pretirano povezani, saj tudi nista sorodni besedi. Ugotovimo pa, da je besedapesveliko bližje besedimaˇcka, saj se ti besedi velikokrat pojavita skupaj in tudi na primer pri igri asociacij lahko ugotovimo, da si pogosto sledita, saj sta sorodni besedi, poleg tega pa velikokrat koristimo besedi skupaj, na primerKOT PES IN MA ˇCKA. Primer teh treh besed nam nazorno prikaže, da z uporabo urejevalniške razdalje ne moremo govoriti o sorodnosti besed na podlagi pomena, saj majhna urejevalniška razdalja ne pomeni, da sta dve besedi po pomenu sorodni.

2.2 Razdalja v evklidski geometriji

V geometriji loˇcimo razdalje v ravnini, kjer so toˇcke definirane oziroma natanko doloˇcene z dvema koordinatamaT(x,y)in razdalje v prostoru, kjer so toˇcke natanko doloˇcene s tremi koordinatamiT(x,y,z). V analitiˇcni geometriji razdaljo med toˇckama A(x₁,y₁) inB(x₂,y₂) v ravniniR²definiramo:

d(A,b)= q

(∆x)²+(∆y)²= q

(x₂−x₁)²+(y₂−y₁)². (1)

(15)

Razdalja med toˇckama je definirana s pravokotnim trikotnikom, v katerem veljaPitagorov izrek. Razliki medx- koordinatama iny- koordinatama predstavljata kateti pravokotnega trikotnika, sama razdalja med toˇckama pa predstavlja hipotenuzo. Da bo bralcu lažje razumljivo, si poglejmo primer v ravnini s pomoˇcjo slike 1.

Slika 1: Razdalja med toˇckama A in B s pomoˇcjo Pitagorovega izreka.

Na sliki je z rdeˇco barvo oznaˇcena razdalja med toˇckamaA(x₁,y₁) inB(x₂,y₂). Pod razdaljo narišemo pravokotni trikotnik tako, da je ena kateta vzporedna abscisi, druga pa ordinati.

Katetak₁predstavlja razdaljo med koordinatamax₂inx₁, katetak₂pa predstavlja razdaljo med koordinatama y2 in y1. Razdaljad(A,B) predstavlja hipotenuzo pravokotnega trikotnika, zato lahko razdaljo zapišemo kot Pitagorov izrek v enaˇcbi (1).

Podobno lahko razdaljo definiramo tudi v prostoruR³med toˇckamaA(x₁,y₁,z₁) inB(x₂,y₂,z₂):

d(A,B)= q

(∆x)²+(∆y)²+(∆z)²= q

(x₂−x₁)²+(y₂−y₁)²+(z₂−z₁)². (2)

2.3 Metrika

Metrika je v matematiki posplošitev pojma razdalje. Metrika podaja oddaljenost med elementi dane množice. Množici, v kateri obstaja metrika, v matematiki reˇcemo metriˇcni prostor.

Definicija. Metrika je preslikava, ki poljubnemu paru elementov x,y iz dane množice priredi realno število d(x,y) z naslednjimi lastnostmi:

(16)

1. d(x,y)≥0 (nenegativnost),

2. d(x,y) = 0, ˇce in samo ˇce x = y, (enakost nerazdeljivosti)

3. d(x,y) = d(y,x) (simetriˇcnost),

4. d(x,z)≤d(x,y) + d(y,z) (trikotniška neenakost).

2.3.1 Metriˇcni prostor

Metriˇcni prostor je v matematiki množica, v kateri je doloˇcena metrika - to je razdalja med njenimi elementi, ki jim pravimo tudi toˇcke. Nam najbližje je 3-razsežni evklidski prostor.

V njem obstaja evklidska metrika, ki razdaljo med dvema toˇckama doloˇca kot dolžino daljice, ki ju povezuje. Geometrija prostora je odvisna od izbrane metrike, zato lahko z izbiro razliˇcnih metrik konstruiramo tudi neevklidske prostore.

Definicija. Metriˇcni prostorM je množica toˇck s pripadajoˇco metriko d d: M×M−→R,

kjer jeRmnožica realnih števil.

Poglejmo si nekaj metriˇcnih prostorov:

• Rje metriˇcen prostor, ˇce definiramo razdaljod(A,B) kotd(A,B)= |A−B|.

• Cje metriˇcen prostor zad(z,w)= |z−w|.

• Pozitivna realna številaR⁺predstavljajo metriˇcni prostor, ˇce razdaljo definiramo kot d(A,B)=

¯

¯ l og

µB A

¶¯

¯

Vsaka podmnožicaY metriˇcnega prostoraX, ki ima enako definirano razdaljo kotX, je tudi metriˇcni prostor, ki mu pravimo metriˇcni podprostor prostoraX. Poglejmo si nekaj prime- rov metrik.

Definicija. Naj bo X vektorski prostor nad obsegom K. Funkcija || · ||: X →R¹₊ je norma na vektorskem prostoru X, X=(X,|| · ||)pa normiran prostor nad obsegom

K

, ˇce so za poljubna elementa x,y∈X in poljubenα∈Kizpolnjeni aksiomi normiranega pro- stora:

(N1) ||x|| ≥0in||x|| =0, ˇce in samo ˇce je x=0,

(N2) ||αx|| = |α| · |x| (homogenost),

(17)

(N3) ||x+y|| ≤ ||x|| + ||y|| (trikotniška neenakost).

Bralca opomnimo, da zapisR¹₊pomeni pozitivna realna števila.

Nam najbolj znana je 2-norma, ki ji reˇcemo tudievklidska norma. Vn-razsežnem evklidskem prostoruRⁿje dolžina vektorja−→x =(x₁,x₂, ...,x_n) doloˇcena z:

||x|| = q

x²₁+x₂²+...+x_n².

Poleg 2-norme obstajajo tudi druge, zato si splošno poglejmo kako je definirana p-norma.

To je posebna skupina norm, ki je zap≥1 razdalja definirana kot:

||x||p= µ _n

X

i=1

|xi|^p

¶_p¹ .

Kot vidimo je od številap odvisna stopnja potence in korena. Iz norme na naraven naˇcin dobimo metriko po formulid(A,B)= ||A−B||.

2.3.2 Manhattanska ali taksi metrika (1-norma)

Manhattanska razdalja je razdalja, poimenovana po ulicah v predelu New York City-ja. Gre za število blokov vzhod, zahod, sever in jug, ki jih mora taksi prevoziti, da bi prišel iz zaˇcetne toˇckeAdo konˇcne toˇckeB. Pri tem se taksi lahko premika le gor, dol, levo in desno. Naj bon- razsežen prostorRⁿin naj bo toˇcka A(a1,a2, ...,an) zaˇcetna, toˇckaB(b1,b2, ...,bn) pa konˇcna toˇcka. Potem je metrika oziroma razdalja medAinB definirana kot:

d(A,B)= |b1−a₁| + |b2−a₂| +...+ |bn−an|. (3) Ne glede na to, po katerih "ulicah"potuje taksi, je razdalja vedno enaka, kar je razvidno iz spodnje slike.

Z razliˇcnimi barvami, so izmerjene razliˇcne poti (rdeˇca, modra, rumena in zelena). Vidimo, da je izmerjena razdalja vedno enaka, ne glede na to, po kateri poti gremo od toˇcke A(0, 0) do toˇckeB(5, 5). Sedaj izraˇcunajmo še taksi metriko po enaˇcbi (3):

d(A,B)= |b1−a1| + |b2−a2| = |5−0| + |5−0| =5+5=10.

Ugotovimo, da se izraˇcunana razdaljad(A,B) ujema z vsemi izmerjenimi razdaljami na sliki 2.

2.3.3 Evklidska metrika (2-norma)

Obiˇcajna razdalja v evklidski geometriji jeevklidska metrika, oziromaevklidska razdalja.

Evklidsko metriko v 2- in 3-dimenzionalnem prostoru smo že zapisali z enaˇcbama (1) in (2), sedaj pa enaˇcbo zapišimo še za razdaljo vn-razsežnem evklidskem prostoruRⁿ med toˇc- kamaA(a₁,a₂, ...,a_n) inB(b₁,b₂, ...,b_n):

d(A,B)= q

(b₁−a₁)²+(b₂−a₂)²+...+(b_n−a_n)². (4)

(18)

Slika 2: Manhattanska razdalja oziroma geometrija taksijev - veˇc krajših možnih poti.

2.3.4 Cebišova metrika (ˇ ∞-norma)

Cebišova metrika oziroma razdalja je znana tudi kot šahovska razdalja. Metrika je defini-ˇ rana v vektorskem prostoru, razdalja med vektorjema oziroma dvema toˇckama, je definirana kot najveˇcja razlika posameznih koordinat. Naj bostaA(a1,a2, ...,an) in toˇckaB(b1,b2, ...,bn) toˇcki v prostoru. Šahovska razdalja med toˇckamaAinB je definirana kot:

D(A,B)=max

i (|bi−ai|), (5)

kjer je vrednosti med 1 inn. Poglejmo si, kako je s ˇCebiševo razdaljo pri šahu. Številke v poljih predstavljajo razdaljo (najveˇcja razlika posameznih koordinat) med položajem kralja in posameznega polja, kar je razvidno na spodnji sliki.

2.3.5 P-ta metrika (p-norma)

Ce v enaˇcbi (4) kvadriranje nadomestimo sˇ p-to potenco in kvadratni koren s p-tim kore- nom, dobimop-to metriko, ki izhaja izp-te norme v vektorskem prostoru:

d_p(A,B)=p^p

|b₁−a₁|^p+ |b₂−a₂|^p+...+ |b_n−a_n|^p, (6) kjer jep≥1, saj v nasprotnem primeru ne gre za metriko, saj ne velja trikotniška neenakost.

2.3.6 Diskretna metrika

Diskretna metrika je najpreprostejša, najmanj natanˇcna in zato tudi najmanj uporabna metrika, za katero velja:

(19)

Slika 3: Kralj stoji na polju F6, številke na posameznih poljih pa prikazujejo ˇCebiševo razdaljo med posameznim poljem in poljem F6.

1.d(x,y)=0, ˇce in samo ˇcex=y, 2.d(x,y)=1, v vseh ostalih primerih.

Predstavljene metrike z izjemo diskretne metrike veljajo samo vevklidskem prostoru, ne pa tudi v drugih množicah.

2.3.7 Urejevalniška razdalja

Urejevalniška razdalja med dvema besedama je razdalja, ki nam pove minimalno število potrebnih operacij, da besedi postaneta enaki. Te operacije sozamenjava, izbrisindodajanje ˇcrke. Besediribainrabatimata urejevalniško razdaljod=2, saj moramo zamenjati drugo ˇcrko ter besediribadodati oziroma besedirabatodvzeti zadnjo ˇcrko. Da bo lažje razumljivo, si poglejmo zgled dveh enako dolgih besed.

Razdaljo urejanja uporabimo v primeru dveh besed. Kot smo že omenili na zaˇcetku, se be- sedipesinpetrazlikujeta v eni ˇcrki. Torej je razdalja urejanjad(pes,pet)=1, saj moramo v besedipetzamenjati le ˇcrkots ˇcrkos, da dobimo besedopes.

2.4 Matrika razdalj

Kadar imamo veˇc kot dva elementa, razdalje med posameznimi elementi najlažje predsta- vimo z matriko, ki ji pravimomatrika razdalj.

(20)

2.4.1 Evklidska matrika razdalj

Zantoˇck v evklidskem prostoru je evklidska matrika razdalj matrika velikostin×n, katere elementi so razdalje med temi toˇckami. Naj bo D evklidska matrika razdalj in naj bodo x₁,x₂, ...,x_ndefinirane kot toˇcke vm-dimenzionalnem prostoru, potem lahko elemente ma- trikeDzapišemo oziroma definiramo kot:

D=(di j), d_{i j}² = ||x_i−x_j||²₂,

kjer|| ||2predstavlja 2-normo v prostoruR^m. Evklidsko matriko razdaljDpotem zapišemo kot:

D=







0 d₁₂² d₁₃² . . . d_1n² d₂₁² 0 d₂₃ . . . d_2n² d₃₁² d₃₂² 0 . . . d_3n² ... ... ... . .. ... d_n1² d_n2² d_n3² . . . 0





 .

Za lažje razumevanje zapisa v obliki matrike si poglejmo, kaj posamezen zapis predstavlja.

Vidimo, da ima matrika po diagonali vrednosti 0. Niˇcla v prvi vrstici pomeni, da je razdalja med dvema enakima elementoma enaka 0. ˇCe pogledamo po stolpcih, v prvem stolpcu prva vrednost d₂₁² predstavlja razdaljo med 1. in 2. elementom in je po definiciji seveda enaka razdaljid₁₂² , saj se razdalja ne spremeni, ˇce merimo razdaljo medAinBali ˇce merimo razdaljo medBinA. Na splošno v zapisua_{i j}, vrednosti predstavlja zaporedno številko vrstice, vrednost j pa številko stolpca. Zaradi prej omenjene definicije razdalje, da velja enakost d(A,B)=d(B,A), je matrika simetriˇcna.

2.4.2 Poljubna matrika razdalj

Ker obstajajo razliˇcno definirane razdalje, obstajajo tudi razliˇcne matrike razdalj. Tudi mi bomo pri praktiˇcnem delu magistrskega dela, razdalje zapisali v obliki matrike. Ta izgleda podobno kot evklidska matrika razdalj.

D=







0 d₁₂ d₂₃ . . . d_1n d₂₁ 0 d₂₃ . . . d_2n d₃₁ d₃₂ 0 . . . d3n

... ... ... . .. ... d_n1 d_n2 d_n3 . . . 0





 .

V osnovi gre podobno kot pri evklidski matriki razdalj¹, razdalje niso doloˇcene na podlagi evklidske razdalje po enaˇcbi (1), ampak bomo postopek doloˇcanja razdalj opisali in pojasnili kasneje, pri praktiˇcnem delu. Tako kot pri evklidski matriki razdalj, so tudi tukaj elementi

1Pri evklidski matriki razdalj navadno razdalje kvadriramo, zaradi lažjega izraˇcuna (predvsem na raˇcunal- niku), pri poljubni matriki razdalj, pa vnesemo nekvadrirane razdalje.

(21)

razporejeni enako v vrstice in stolpce in jih zapišemo kotd_{i j}. Zapisd₁₂torej oznaˇcuje razdaljo med prvim in drugim elementom, ki je po definiciji razdalje enaka razdaljid₂₁, ki ozna- ˇcuje razdaljo med drugim in prvim elementom. Na splošno zapisd_{i j} predstavlja razdaljo medi-tim inj-tim elementom. Tudi tukaj so na diagonali matrike vrednosti enake 0, saj velja enako kot prej, torejd(A1,A1)=0, prav tako je matrika prezrcaljena preko diagonale, saj veljad(A1,A2)=d(A2,A1). V tej obliki bomo podali tudi razdalje med razliˇcnimi besedami.

2.5 Razliˇcne metrike in matrike razdalj

Evklidska metrika

Slika 4: ToˇckeA, BinCv ravnini s pripadajoˇcimi koordinatami in razdaljami.

Razdalje doloˇcimo oziroma izraˇcunamo po enaˇcbi (1):

d(A,B)=d(B,A)=p

(5−0)²+(3−0)²=p

25+9=p 34 .

=5, 83 d(A,C)=d(C,A)=p

(4−0)²+(5−0)²=p

16+25=p 41 .

=6, 40 d(B,C)=d(C,B)=p

(4−5)²+(5−3)²=p

1+4=p 5 .

=2, 24

V poglavju 2.4.1 smo zapisali, da vnašamo v matriko kvadrirane razdalje, zato lahko razdalje zapišemo kot:

d²(A,B)=34, d²(A,C)=41, d²(B,C)=5.

Doloˇcili smo torej razdalje med posameznimi toˇckami. Po definiciji o razdalji, seveda velja d(A,A)=0, d(B,B)=0 ind(C,C)=0. Sedaj, ko imamo doloˇcene vse razdalje, lahko zapi- šemo evklidsko matriko razdalj.

D=







0 34 41

34 0 5

41 5 0







Vidimo, da je matrika simetriˇcna in ima po diagonali vrednosti 0. Ker smo zapisali evklidsko matriko razdalj treh toˇckA,B inC, je matrika razsežnosti 3×3.

(22)

Taksi metrika

Izraˇcunali bomo taksi metriko za toˇcke A, B inC iz slike 4 in zapisali matriko razdalj. Kot smo ugotovili, ni pomembno po kateri poti potujemo med dvema toˇckama, zato sem med toˇckami izbral najbolj preproste poti, kar je razvidno na sliki 5. Izraˇcunajmo še taksi razdalje

Slika 5: Taksi razdalja med toˇckami A, B in C ter dolžine posameznih razdalj. S ˇcrno barvo so narisane tudi daljice oziroma evklidske razdalje.

med toˇckamiA(0, 0),B(5, 3) inC(4, 5):

d(A,B)= |5−0| + |3−0| =5+3=8, d(A,C)= |4−0| + |5−0| =4+5=9, d(B,C)= |4−5| + |5−3| =1+2=3.

Ce upoštevamo definicijo razdalje, lahko zapišemo matriko razdaljˇ D:

D=







0 8 9 8 0 3 9 3 0





.

Šahovska razdalja

Po enaˇcbi (5) izraˇcunamo šahovsko razdaljo za toˇckeA,B inC iz slike 4:

d(A,B)=max(|5−0|,|3−0|)=max(5, 3)=5, d(A,C)=max(|4−0|,|5−0|)=max(4, 5)=5, d(B,C)=max(|4−5|,|5−3|)=max(1, 2)=2.

Ob upoštevanju definicije razdalje, lahko zapišemo matriko razdaljD:

D=







0 5 5 5 0 2 5 2 0





.

(23)

Diskretna metrika

Kot smo rekli, sta pri diskretni metriki dve možnosti. Kadar veljax=y, je razdaljad(x,y)=0, v vseh ostalih primerih pa je razdalja enakad(x,y)=1. Torej lahko matriko razdalj med toˇckamiA,B inC zapišemo kot:

D=







0 1 1 1 0 1 1 1 0





.

Ugotovitve

Primerjajmo posamezne matrike razdalj. Sledijo si evklidska, taksi, diskretna in šahovska:







0 34 41

34 0 5

41 5 0





6=







0 8 9 8 0 3 9 3 0





6=







0 1 1 1 0 1 1 1 0





6=







0 5 5 5 0 2 5 2 0





.

Uporabili smo iste toˇckeA,B inC, a pri primerjavi vseh štirih matrik razdalj ugotovimo, da so razliˇcne. Ugotovimo torej, da so razdalje med posameznimi toˇckami in poslediˇcno matrike razdalj odvisne od izbrane metrike oziroma kako smo definirali razdaljo.

Poudariti je potrebno, da izbira metrike za obravnavo konkretnega primera ni povsem poljubna. Potrebno je preuˇciti problem, ki ga želimo razrešiti in temu primerno izbrati ustrezno metriko.

Na primer, ˇce želimo pri šahu izraˇcunati razdaljo in prešteti potrebno število premikov kralja, do poljubnega polja, ne bomo uporabili evklidske ali taksi metrike, ampak bomo uporabili šahovsko metriko, saj nam prvi dve metriki ne pomagata rešiti problema, ki nas zanima. Prav tako pri vožnji po pravokotnih in vzporednah cestah ne bomo izbrali evklidske ali šahovske metrike, saj je temu primeru primerna taksi metrika. Evklidsko metriko pa uporabljamo v geometriji v osnovni šoli, kadar želimo izraˇcunati razdaljo med dvema toˇckama, daljicama, premicama,...

Vidimo torej, da moramo dobro poznati problem in vedeti, kaj želimo doseˇci, da temu primerno izberemo ustrezno metriko, da bodo naši izraˇcuni in ugotovite uporabne in natanˇcne.

(24)

3 Gruˇcenje podatkov

Gruˇcenje podatkov je postopek oziroma proces, s katerim objekte razporedimo v skupine, glede na skupne znaˇcilnosti. Torej, objekti znotraj iste skupine oziroma gruˇce imajo veˇc skupnih lastnosti v primerjavi z objekti, ki so zunaj. Gruˇcenje podatkov je glavni proces, s katerim znotraj veˇcje koliˇcine podatkov odkrivamo doloˇcene vzorce s skupnimi lastnostmi oziroma znaˇcilnostmi. Postopek se uporablja na številnih podroˇcjih, kot so prepoznavanje iskalnih vzorcev v raˇcunalništvu, prepoznavanje vzorcev, analiziranje slik, krˇcenju velikosti podatkov, raˇcunalniški grafiki,...

Gruˇcenje podatkov samo po sebi ni specifiˇcen algoritem, s katerim bi analizirali podatke, ampak je to naša osnovna naloga oziroma problem, ki ga želimo rešiti. Zato obstaja veˇc spe- cifiˇcnih algoritmov, s katerimi lahko analiziramo podatke. Vsi algoritmi niso primerni za vse vrste podatkov, zato ima vsak algoritem svoje znaˇcilnosti, prednosti in slabosti, zaradi ˇcesar je vsak primeren za svojo vrsto podatkov. Algoritmi temeljijo na preuˇcevanju razdalj med podatki, gostoto podatkov v danem obmoˇcju. Ker so razliˇcni algoritmi primerni za doloˇceno vrsto podatkov, to ni avtomatiˇcni proces, ampak je potrebno dovolj znanja o podroˇcju oziroma podatkih za analizo, da lahko izberemo ustrezen algoritem, da bodo naši rezultati za doloˇcen problem ˇcimbolj natanˇcni in uporabni. Poglejmo si nekaj najbolj znanih algoritmov.

4 Algoritmi

Algoritme gruˇcenja razlikujemo glede na naˇcin povezovanja ali razvršˇcanja toˇck. In sicer loˇcimo med modeli gruˇcenja, ki temeljijo na:

• doloˇcanju središˇc grup,

• povezovanju glede na razdalje med toˇckami,

• gostoti toˇck,

• porazdelitvi toˇck,

• toˇckah in atributih toˇck,

• pravilih povezovanja,

• na grafih.

Obstaja veliko razliˇcnih algoritmov, pa si na kratko poglejmo nekatere izmed njih.

4.1 Algoritem k - means

Gre za metodo kvantizacije, algoritem pa uvršˇcamo med particijske algoritme. Algoritem se uporablja pri rudarjenju podatkov. Podatke razvršˇca vkrazredov, na osnovi vsote oddalje- nosti podatkov od središˇc gruˇc tako, da je ta minimalna. Poglejmo si definicijo argumenta minimuma.

(25)

Definicija. Naj bo X poljubna množica in f : X →Rfunkcija, ki preslika elemente množice X.

Potem je funkcija

argmin

x∈S⊆X

f(x)={x|x∈S∧ ∀y∈S:f(y)≥f(x)}. (7) funkcija, ki vrne element iz podmnožie S⊆X , za katerega je vrednost funkcije najmanjša.

Algoritemk-means sedaj lahko zapišemo kot minimizacijski problem:

argmin

S k

X

i=1

X

xj∈Si

||x_j−µi||². S- množica gruˇc,

k- število gruˇc, i- indeks gruˇce, x_j - toˇcka j gruˇceS_i,

µi - središˇce gruˇce i (središˇca so znana v naprej).

Leta 1957 je idejo za algoritem razvil Hugo Steinhaus, standardni algoritem pa je istega leta prviˇc predstavil Stuart Lloyd. Ime algoritmak- means, pa se prviˇc uporabi 10 let kasneje, ko je leta 1967 James McQueen poimenoval algoritemk- means. Za prvo uradno obavo algoritmak- means je bilo potrebnih 25 let, saj je bil za javnost objavljen šele leta 1982, ˇceprav je že leta 1965 E. W. Forgy objavil algoritem, a ne pod istim imenom. Zaradi razliˇcnih objav, algoritem velikokrat omenjamo Lloyd - Forgy algoritem. Poleg teh dveh obstaja še veliko drugih algoritmov.

Omenimo dve pomembni slabosti algoritmak- means. Prva izmed slabosti je, da moramo kot vhodni parameter navesti število gruˇc, kar pa ni preprosto, saj v splošnem ne vemo, ko- liko gruˇc je optimalnih. Druga slabost, ki jo je vredno omeniti pa je, da algoritem ne zazna gruˇc, ki so znotraj drugih gruˇc.

4.2 Algoritem DBSCAN

Algoritem DBSCAN (Density-based spatial clustering of applications with noise) bomo pri analiziranju podatkov uporabili tudi mi, zato si ga bomo ogledali podrobneje. Leta 2014 je na vodilnem kongresu rudarjenja podatkov prejel nagrado "Test of time", ki jo prejme izbran algoritem, ki je najpogosteje uporabljen tako v teoriji kot tudi v praktiˇcnih namenih.

Tako kotk- means, tudi algoritem DBSCAN uvršˇcamo med particijske algoritme in je eden izmed najpogosteje uporabljenih algoritmov.

Algoritem preiskuje sosešˇcine oziroma okolice toˇck. Drugi pomemben kriterij oziroma parameter pa je minimalno število toˇck v okolici. ˇCasovna zahtevnost algoritma je odvisna od ˇcasovne zahtevnosti preiskovanja okolice posamezne toˇcke, kar lahko zmanjšamo z uporabo matrike razdalj, kar pa bistveno poveˇca potrebe po pomnilniku. Prednosti algoritma sta, da nismo omejeni s številom gruˇc ter njihovo obliko.

Omenili smo, da algoritem DBSCAN potrebuje dva vhodna parametra:

(26)

1. Okolica²- podaja maksimalno razdaljo okoli jedra, znotraj katere mora biti zadostno število toˇck.

2. Minimalno število toˇck (minPts) - število toˇck (skupaj z jedrom), ki so potrebne za obstoj gruˇce.

4.2.1 Osnova za algoritem

V osnovi gre pri algoritmu DBSCAN za razvršˇcanje posameznih toˇck (objektov) v množice, na podlagi skupnih znaˇcilnosti. Toˇcke so opredeljene in klasificirane kot:

• jedro,

• neposredno dosegljive toˇcke (glede na oddaljenost znotraj gruˇce) oziroma mejne toˇcke,

• toˇcke, ki ležijo izven gruˇce.

1. Toˇckapje toˇcka jedra, ˇce v njeni²-okolici leži najmanjminPtstoˇck (znotraj metriˇcne krogle z radijem²in središˇcemp).

2. Toˇckaqje neposredno dosegljiva iz toˇckep, ˇce leži znotraj²-okolice toˇckepin ˇce je toˇcka pdefinirana kot jedro.

3. Vse toˇcke, ki niso neposredno dosegljive iz toˇcke p, oziroma ne ležijo v njeni²-okolici so toˇcke, ki ležijo izven gruˇce z jedromp.

Potrebno se je zavedati, da jedro gruˇc ni isto kot središˇce krogle, okolica pa ni enaka radiju sfere, zato tudi mejne toˇcke niso kar toˇcke na metriˇcni sferi.

(27)

4.2.2 Originalni algoritem

Program 1: Originalni DBSCAN algoritem.

1 DBSCAN(DB, distFunc , eps, minPts ) {

2 C = 0 % s t e t j e mnozic grucenja

3 f o r each point P in database DB {

4 i f l a b e l ( P ) = ! undefined then continue % p r e j uporabljene tocke v n o t r a n j i zanki

5 Neigbors N = RangeQuery (DB, distFunc , P , eps) % i s k a n j e sosedov

6 i f |N| < minPts then { % p r e v e r j a n j e gostote tock

7 l a b e l ( P ) = Noise % dodelitev zunanje tocke

8 continue

9 }

10 C = C + 1 % p r e v e r j a n j e naslednjega

11 l a b e l ( P ) = C % oznaka zacetne tocke

12 Seed s e t S = N \ { P } % r a z s i r i t e v sosedov

13 f o r each point Q in S { % pregled vseh tock z n o t r a j mnozice S

14 i f l a b e l (Q) = Noise then l a b e l (Q) = C % d o l o c i t e v mejne tocke

15 i f l a b e l (Q) = ! undefined then continue % p r e j uporabljene tocke

16 l a b e l (Q) = C % d o l o c i t e v soseda

17 Neigbors N = RangeQuery (DB, distFunc , Q, eps) % i s k a n j e sosedov

18 i f |N| > minPts then { % p r e v e r j a n j e gostote tock

19 S = s j o i n N% dodajanje soseda v mnozico S

20 }

21 }

22 }

23 }

Za lažje razumevanje DBSCAN algoritma, lahko postopek algoritma oziroma namen zapi- šemo po korakih:

1. Najprej poišˇcemo toˇcko, ki ima v svoji okolici²minimalno število toˇck. Jedra so vse toˇcke, ki imajo v svoji okolici²veˇc kot minimalno število toˇck (minPts).

2. Ko dobimo jedro in toˇcke v njeni okolici, za vsako toˇcko znotraj gruˇce preverimo, ˇce ima v svoji okolici²vsaj minimalno število toˇck. ˇCe ima zadostno število toˇck, nastopa kot jedro gruˇce, drugaˇce pa je to mejna toˇcka.

3. Ko dodajamo nove toˇcke v gruˇco, zopet preverimo, ˇce ima v svoji okolici vsaj minimalno število toˇck.

4. Ko pridemo do toˇcke, ki je znotraj gruˇce, a v svoji okolici nima dovolj toˇck, je to mejna toˇcka.

(28)

5. Vse ostale toˇcke, ki niso jedra ali mejne toˇcke, so toˇcke izven gruˇce oziroma toˇcke, ki niso neposredno dosegljive iz gruˇce.

Da bo bralcu lažje razumljivo, si postopek algoritma DBSCAN poglejmo še s pomoˇcjo slik.

Poleg množice toˇck, doloˇcimo še parametra²=1 inmi nP t s=4. Torej, toˇcka je jedro, ˇce so vsaj še 3 toˇcke od nje oddaljene manj kot 1 enoto, saj za minimalno število toˇck štejemo tudi jedro. Uporabili bomo evklidsko razdaljo, torej je okolica²doloˇcena s krožnico.

Slika 6: Razliˇcne toˇcke.

Naj bo toˇcka Aprvo potencialno jedro gruˇce. Preverimo, ˇce v njeni okolici leži dovolj toˇck, da ustreza pogojumi nP t s=4 (slika 7).

Slika 7: Toˇcka A kot jedro in njena okolica².

Vidimo, da poleg toˇcke A v njeni okolici ležijo še 3 toˇcke. Torej je toˇcka A res jedro gruˇce.

Sedaj, ko smo dobili gruˇco, preverimo za vse toˇcke v okolici jedra, ˇce imajo v svoji okolici zadostno število toˇck, da predstavljajo jedro (slika 8).

(29)

Slika 8: Okolice toˇck znotraj gruˇce.

Vidimo, da je v okolici obeh rdeˇcih toˇck vsaj minimalno število toˇck, zato sta tudi ti dve toˇcki jedri. V okolici toˇckeE, pa ni dovolj toˇck, torej pogoj o minimalnem številu toˇck ni izpolnjen.

Taki toˇcki reˇcemomejna toˇcka, saj leži v gruˇci, a ne predstavlja jedra. Sedaj preverimo še okolici novih dveh toˇck.

Slika 9: Okolica novih dveh toˇck gruˇce.

Iz slike je razvidno, da je v okolici rdeˇce toˇcke dovolj toˇck, da postane jedro, v okolici toˇcke Fpa ni dovolj toˇck, zato je tudi toˇckaF mejna toˇcka (slika 9). Ostane nam še toˇckaG. Preve- rimo okolico toˇckeG(slika 10)

(30)

Slika 10: Okolica toˇckeG.

Vidimo, da v okolici toˇckeGni nobene toˇcke, prav tako pa toˇckaGni v okolici²nobene izmed toˇck znotraj gruˇce. Zato toˇckaGne pripada gruˇci in ji reˇcemotoˇcka izven gruˇce.

Torej, gruˇco sestavljajo rdeˇce toˇcke in vijoliˇcni toˇcki E inF. Za vse toˇcke znotraj gruˇce velja, da so neposredno dosegljive iz jedra. Iz toˇckEinF, ne moremo nadaljevati naprej, saj v njunih okolicah ne leži dovolj toˇck, zato sta ti dve toˇcki mejni. V toˇckoGpa ne moremo priti neposredno iz jedra, zato je to toˇcka izven gruˇce.

4.2.3 Prednosti DBSCAN algoritma

• V nasprotju sk- means algoritmom, DBSCAN ne potrebuje specifiˇcnega števila gruˇc.

• Algoritem prepozna poljubno oblikovane gruˇce, prepozna celo gruˇco, ki je v celoti znotraj neke druge gruˇce.

• Ima definiran pojem motenj in strogo loˇci toˇcke izven gruˇce, kar pomeni, da ni nujno, da poljubna toˇcka pripada katerikoli gruˇci.

• Algoritem potrebuje le dva parametra in velja za enega najobˇcutljivejših algoritmov za obdelavo podatkov.

• ParametraminPtsin²lahko poljubno spreminjamo, seveda ˇce dobro razumemo podatke.

4.2.4 Slabosti DBSCAN algoritma

• Ni popolnoma deterministiˇcen algoritem, kar pomeni, da lahko neka toˇcka pripada veˇc kot eni gruˇci. ˇCe mejne toˇcke opredelimo kot motnje oziroma toˇcke izven gruˇce, lahko to slabost nekoliko reduciramo.

(31)

• Kvaliteta gruˇcenja je odvisna od merjenja oziroma doloˇcanja razdalj. Najpogosteje se uporablja Evklidska razdalja, problem pa nastane pri veˇcdimenzionalnih podatkih.

• ˇCe ne razumemo dobro podatkov, je zelo težko ali skoraj nemogoˇce doloˇciti okolico².

(32)

5 DBSCAN algoritem in razliˇcne metrike

Sam algoritem DBSCAN se seveda pri spremembi metrike ne spremeni. Algoritem raziskuje toˇcke in njihove okolice, doloˇca jedra, mejne toˇcke in toˇcke izven gruˇce. Edino, kar se spremeni, so oblike okolic okoli posameznih toˇck, odvisno od metrike, ki jo izberemo.

5.1 Evklidska metrika

Evklidsko metriko smo si ogledali že v prejšnjem poglavju, kjer smo si s pomoˇcjo slik ogledali, kako DBSCAN algoritem sploh deluje. Torej, okolica toˇcke pri evklidski metriki v ravnini ima obliko kroga, saj je krog množica toˇck, ki so od središˇca oddaljene za najveˇc polmer. Torej gre za krog s polmeromr =². Poglejmo si na spodnji sliki.

Slika 11: Na levi strani je prikazana okolica dane toˇcke, na desni pa izvajanje DBSCAN algoritma in iskanje okolic posameznih toˇck z uporabo evklidske metrike. Ob pogojuminPts = 3, dobimo gruˇco treh toˇck (modra barva).

5.2 Taksi metrika

Pri taksi metriki v ravnini ne raˇcunamo razdalje tako kot pri evklidski metriki, paˇc pa je razdalja med dvema toˇckama enaka vsoti razlik v koordinatahxiny, kar je predstavljeno v enaˇcbi (3).

Ce spremenimo samo eno koordinato središˇcne toˇcke naenkrat, se seveda ta lahko spremeniˇ za±². Torej, ˇce ima poljubna toˇcka koordinati (x,y), imajo 4 toˇcke, ki ležijo ravno na robu okolice²koordinate: (x+²,y), (x−²,y), (x,y+²) in (x,y−²). ˇCe povežemo te štiri toˇcke, dobimo okolico v obliki kvadrata (zasukanega za 45°okrog preseˇcišˇca diagonal). Poglejmo si na spodnji sliki obliko okolice za manhattansko metriko in prikaz iskanja okolic z algoritmom DBSCAN.

(33)

Slika 12: Levo je prikazana taksi okolica toˇcke, desno pa je prikazano izvajanje DBSCAN algoritma in iskanje okolic posameznih toˇck z uporabo taksi metrike. Ob upoštevanju pogoja minPts = 3, ne obstaja nobena gruˇca.

5.3 Šahovska metrika

Omenili smo, da se šahovska razdalja izraˇcuna kot najveˇcja razlika posameznih koordinat, kar je definirano v enaˇcbi (5). Po premisleku so torej v okolici toˇcke s koordinatama (x,y) vse toˇcke, katerim se koordinati spremenita za najveˇc², torej imajo robne koordinatex±²in y±². Izberimo si štiri toˇcke s koordinatami, ki so najbolj oddaljene od toˇcke (x,y): (x−²,y−

²), (x−²,y+²), (x+²,y+²) in (x+²,y−²). Po premisleku ugotovimo, da so te štiri toˇcke oglišˇca kvadrata, ki predstavlja okolico²toˇcke (x,y). Za lažje razumevanje si poglejmo na spodnji sliki.

(34)

Slika 13: Levo je prikazana okolica toˇcke z uporabo šahovske metrike, desno pa je za isto metriko predstavljeno izvajanje DBSCAN algoritma in iskanje okolic posameznih toˇck. Ob upoštevanju pogojaminPts = 3dobimo gruˇco vseh toˇck (toˇcke znotraj modrih okolic).

5.4 Ugotovitve

Vidimo, da se z izbiro metrike spremeni oblika okolice². Torej poleg izbire množice toˇck, okolice²in minimalnega števila toˇckmi nP t s, na obliko gruˇce in njene elemente, moˇcno vpliva tudi izbira ustrezne metrike. ˇCe primerjamo izvajanje algoritma DBSCAN z razliˇcnimi metrikami, ugotovimo, da se pri popolnoma enakih vhodnih pogojih, obstoj oziroma velikost gruˇce spremeni glede na izbiro metrike, kar je razvidno na slikah 11, 12 in 13. Da bo lažje razumljivo, si poglejmo še sliko 14, na kateri so prikazane okolice za vse tri metrike.

Slika 14: Okolice za vse tri metrike: rdeˇca - taksi, ˇcrna - evklidska in zelena - šahovska. Toˇcka Aleži v okolici ne glede na izbiro metrike, toˇckaB ne leži v okolici za taksi metriko, toˇckaC pa leži le v okolici za šahovsko metriko.

(35)

Kot smo omenili že pri poglavju o metrikah, je tudi pri izvajanju algoritma potrebno izbrati ustrezno metriko na podlagi problema oziroma naloge, saj so od tega odvisne smiselnost, natanˇcnost in uporabnost naših rezultatov.

(36)

6 Geometrijska obravnava jezika

Ustreznost definicij razdalj med besedami bomo preizkusili tudi praktiˇcno. Najprej si bomo izbrali osem besed:matematika, algebra, množenje, seštevanje, enaˇcba, geometrija, premica indaljica.Naša naloga je, doloˇciti besede med katerimi so razdalje dovolj majhne, da tvorijo gruˇco oziroma so med seboj sorodne.

V osnovi, bomo razdaljo doloˇcili na podlagi število najdenih besed, s pomoˇcjo spletne apli- kacijeSketch Engine. Spletna aplikacija na spletu poišˇce število pojavitev iskanih besed na spletnih straneh, ki so v bazi aplikacije, odvisno od izbranega kriterija.

6.1 Aplikacija Sketch Engine

Aplikacija Sketch Engine je uporabno orodje na podroˇcju raziskovanja jezika. Ponuja nam velik izbor funkcij, s katerimi lahko raziskujemo besedišˇce na spletu v razliˇcnih jezikih, tudi v slovenšˇcini. S funkcijo "Thesaurus" lahko poišˇcemo besede, ki so sorodne iskani besedi.

Poleg števila iskane besede, nam aplikacija ponudi število pojavitev, ki vsebujejo sorodne besede. Poleg tega, lahko hkrati išˇcemo in primerjamo število ustreznih pojavitev za dve besedi hkrati. Med kriteriji iskanja je veliko možnosti, išˇcemo lahko besedo, frazo, posamezno ˇcrko, lemo,... Poleg tega lahko izberemo tudi besedno vrsto, torej ali se beseda pojavlja kot samostalnik, pridevnik, prislov itd. Mi bomo uporabili kriterijlema. Pri iskanju s kriterijem beseda, aplikacija poišˇce število pojavitev, kjer je beseda zapisana identiˇcno, kot jo mi vpi- šemo v iskalnik, v primeru da išˇcemo s kriterijemlema, pa aplikacija upošteva tudi zadetke, kjer je beseda zapisana z razliˇcnimi konˇcnicami. Torej ne išˇce na primer samo besedemate- matika, ampak tudi oblikematematike, matematiki,.... Potrebno je opozoriti, da tukaj ne gre za matematiˇco lemo. Pri iskanju dveh besed hkrati, lahko definiramo tudi ali morata biti dve besedi sosedni, torej v besedilu stojita ena za drugo, lahko pa tudi doloˇcimo maksimalno število besed, ki stojijo v besedilu med iskanima besedama. Pri uporabi funkcije Concor- dancelahko izberemo naprednejše iskanje, kjer z ukazi lahko išˇcemo s podrobnimi pogoji, da dobimo samo število pojavitev, ki ustrezajo našim željam oziroma potrebam.

6.2 Iskanje in zapisovanje števila pojavitev

Pri iskanju bomo uporabili tri pogoje: dve besedi hkratiinvsaj ena od dveh besedinena be- seda. Število pojavitev s pogojemdve besedi hkratibomo v nadaljevanju omenjali kotpresek, število pojavitev s pogojemvsaj ena od dveh besedpa kot unijo.

Število pojavitev bi lahko vpisovali v dve razliˇcni matriki, a pri izbiri osmih besed je potrebno vpisati kar 64 razliˇcnih podatkov. Zato bomo število pojavitev zapisovali v dve tekstovni datoteki, s programskim jezikom Octave pa bomo zapisali program, ki bo na podlagi teh dveh datotek izraˇcunal posamezni matriki, s katerima bomo kasneje izraˇcunali razdalje.

Podatke vpišemo enega pod drugim. Ne glede na to, ali želimo zapisati matriko razdalj za število pojavitev za presek ali unijo, je postopek enak. V eni datoteki zapisujemo podatke za

(37)

Slika 15: Zaˇcetni zaslon aplikacije Sketch Engine, kjer lahko izberemo eno izmed osnovnih funkcij na podlagi naših potreb.

Slika 16: Slika zaslona iskalnika v aplikaciji Sketch Engine.

presek, v drugi pa za unijo. Izbrali smo si osem besed, zato bomo najprej eno pod drugim zapisali število pojavitev posamezne besede v relaciji² z besedo matematika. Prvih osem podatkov predstavlja v našem primeru število pojavitev v preseku za besedomatematika z vsemi ostalimi besedami (besede po vrsti so: matematika, algebra, množenje, seštevanje, enaˇcba, geometrija, premicaindaljica). Najprej torej zapišemo število pojavitev, kjer se poja-

2Z besedo relacijo mislimo torej presek ali unijo. Torej število objav, v katerih se dve besedi pojavita skupaj oziroma število objav, kjer se pojavlja vsaj ena od obeh besed. Kot smo že omenili, je postopek zapisovanja popolnoma enak v obeh primerih.

(38)

vita besedimatematikainmatematika, v drugi vrstici je število pojavitev za besedimatema- tika, algebra. Ko zapišemo v našem primeru vseh osem števil, ki se navezujejo na primerjavo števila pojavitev z besedomatematikain ostalimi besedami, zaˇcnemo vpisovati število pojavitev za besedoalgebrain ostale besede. Ker smo število pojavitev za besedimatematikain algebrazapisali že v iskanju števila posameznih besed v relaciji z besedomatematika, nam ni potrebno ponovno vpisati. Na splošno nam ni potrebno dvakrat vpisati razdaljo med dvema istima besedama, saj bo na podlagi teh dveh datotek program zapisal simetriˇcni matriki. To lahko storimo, saj smo že veˇckrat omenili, da je po definiciji razdalja medAinBenaka razdalji medB inA. Za vsako naslednjo besedo moramo torej zapisati en podatek manj, saj je ekvivalenten podatek bil vpisan že prej. Torej, ˇce smo na primer že zapisali število pojavitev obeh besedmatematikainenaˇcba, nam ni potrebno zapisati še števila pojavitev v preseku besedenaˇcbainmatematika, saj na število pojavitev ne vpliva vrstni red iskanih besed.

Razumljiv je, da je število pojavitev dveh istih besed enako v obeh primerih. Ko zapišemo število pojavitev tako za unijo, kot tudi za presek besed, lahko te podatke zapišemo v matriko dimenzije 8×8. Poglejmo si kodo programa in pojasnimo bistvene dele programa.

Program 2: Zapis števila elementov v matriko 8×8.

1 c l c

2 c l e a r a l l

3 A = importdata (’ or . t x t ’,’ ’ , 0 ) ; % nalozimo podatke i z izbrane datoteke

4 m = s i z e(A , 1 ) ; % v e l i k o s t matrike

5 n = 8 ; % 8 besed bo t v o r i l o matriko 8 x 8

6 U = [ ] ;

7 s t = 1 ; % zaporedno s t e v i l o elementa i z datoteke , k i smo jo n a l o z i l i kot matriko A

8 f o r i = 1 : n % v r s t i c e v matriki

9 VR = [ ] ; % posamezna v r s t i c a koncne matrike unije a l i preseka

10 f o r j = 1 : n % v s i s t o l p c i v matriki

11 i f 1 <= j % za vse podatke , k i j i h se nismo v p i s a l i v matriko

12 VR = [VR, A( s t ) ; ] ;

13 s t = s t + 1 ;

14 e l s e % ce j e podatek ze b i l vpisan v matriko U, ga prepisemo i z matrike U same

15 VR = [VR, U( j , i ) ] ;

16 endif

17 endfor

18 U = [U; VR ] ; % posamezno v r s t i c o dodamo v matriko U

19 endfor

20 U

21 save unija . mat U% shranimo matriko U

Najprej naložimo ustrezno datoteko, glede na to, ali želimo matriko števila podatkov za presek ali unijo dveh besed (3. vrstica). Podatki se zapišejo v matrikoAdimenzije 1×n, kjer je nštevilo izbranih besed. Nadaljni postopek je enak v obeh primerih, na koncu le shranimo

(39)

matriko pod imenompresekaliunija. Vfor zankimed vrsticama 9 in 26, program prebira posamezne elemente iz matrike A in jih postavlja na ustrezno mesto v vrsticiV R, kasneje pa vrstico doda v matrikoU (24. vrstica). V vrstici 13 imamo pogoj, torej ˇce podatka nismo še zapisali v matrikoU, ustrezen podatek prepiše iz matrikeA.V kolikor pa smo podatek že zapisali v matrikoU, potem ustrezen podatek program prepiše kar iz matrikeUsame. S tem smo si olajšali delo, saj nam ni bilo potrebno podatkov zapisovati v matriko roˇcno in dvakrat za razliˇcen vrstni red dveh besed, saj je to namesto nas naredil program, ki smo ga zapisali.

Sedaj, ko imamo dve matriki moramo doloˇciti še razdaljo med dvema besedama.

6.3 Razdalja med dvema besedama

V tem poglavju bomo definirali dve razdalji med besedami.

6.3.1 Razdalja kot koliˇcnik preseka in unije števila pojavitev

Ker besede nimajo koordinat na podlagi katerih bi lahko doloˇcili razdaljo, bomo razdaljo besed definirali kot:

d(A,B)=1−|M(A)∩M(B)|

|M(A)∪M(B)|, (8)

kjer jeM(A) množica pojavitev besedeAinM(B) množica pojavitev besedeB. TorejM(A)∩ M(B) predstavlja presek obeh množic, kjer se skupaj pojavita obe besedi,M(A)∪M(B) pa unijo obeh množic, torej vsebuje objave, kjer se pojavi vsaj ena od obeh besed. Koliˇcnik preseka in unije odštejemo od števila 1 zato, ker želimo, da je razdalja manjša v primeru, kadar ima koliˇcnik veˇcjo vrednost – veˇckrat kot se besedi pojavita skupaj, tem manjša je razdalja med dvema besedama.

Po enaˇcbi (8) bomo izraˇcunali razdalje med posameznimi besedami in zapisali matriko razdalj. Ker je to dokaj zamudno, bomo uporabili program, ki smo ga zapisali. V nadaljevanju bomo razdaljo definirano z enaˇcbo (8) imenovali na kratko karrazdalja PU.

6.3.2 Razdalja kot koliˇcnik preseka in minimalnega števila pojavitev posamezne besede Omenili smo, da bomo definirali dve razdalji in primerjali rezultate med seboj. Ob pred- postavki, da se število pojavitev moˇcno razlikuje glede na iskano besedo, bodo po enaˇcbi (8) razdalje med dvema besedama, kjer se ena pojavi velikokrat (npr. matematika- 22190 pojavitev), druga pa malokrat (algebra- 659 pojavitev), razdalje zelo majhne. Zato bomo definirali razdaljo kot koliˇcnik preseka in minimalnega števila pojavitev posamezne besede:

d_m(A,B)=1− |M(A)∩M(B)|

min(|M(A)|,|M(B)|). (9)

V primeru besedmatematikainalgebrabo torej v števcu število pojavitev besede algebra.

Enako kot prej bomo število pojavitev posameznih besed vpisali v tekstovno datoteko .txtin zapisali programsko kodo, ki bo na podlagi podatkov doloˇcila minimalno število pojavitev med posameznima besedama in zapisala matriko. V nadaljevanju bomo razdaljo iz enaˇcbe (9) imenovali na kratko karrazdalja MIN.

(40)

Program 3: Doloˇcanje min(M(A), M(B))in zapis podatkov v matriko.

1 c l c

2 c l e a r a l l

3 A = importdata (’ 2 skupini . t x t ’,’ ’ , 0 ) ;

4 n = s i z e(A , 1 ) ;

5 S = [ ] ;

6 f o r i = 1 :n % v r s t i c e v matriki

7 VR = [ ] ; % posamezna v r s t i c a koncnce matrike unije a l i preseka

8 f o r j = 1 : n %v s i s t o l p c i v matriki

9 VR = [VR,min(A( i ) ,A( j ) ) ] ;

10 endfor

11 S = [ S ; VR ] ; % posamezno v r s t i c o dodamo matriki

12 endfor

13 save 2 skupini . mat S ;

6.4 Lastnosti definirane razdalje

Naša definicija razdalje ni metrika, saj dopušˇcamo možnost, da ne velja trikotniška neenakost temveˇc:

d(A,C)>d(A,B)+d(B,C). (10) V primerih, ki smo jih obravnavali ni prišlo do neenakosti (10), prav tako nisem uspel najti treh besed, za katere bi veljala. A po premisleku se lahko zgodi, da za besedeA, BinCvelja, da je na primer razdaljad(A,B)=0.5,d(A,C)=1 ind(B,C)=0.25. V tem primeru bi seveda veljala neenakost (10), kar pomeni da ne gre za metriko, ampaksemimetriko. Semimetrika ima razen trikotniške neenakosti vse ostale lastnosti metrike. Ne glede na to za kakšno metriko in razdaljo gre, še vedno lahko govorimo o sorodnosti besed in sorodnosti pomenov razliˇcnih besed. Poudariti je potrebno, da v našem primeru ne gre za semantiˇcno razdaljo, saj ima neka beseda lahko veˇc pomenov, temveˇc za neko statistiˇcno razdaljo, doloˇceno na podlagi analize besedišˇca.

6.5 Matrika razdalj

Poglejmo si kodo programa (4), s katerim bomo na podlagi dveh matrik števila pojavitev do- loˇcili razdalje med posameznimi besedami in zapisali matriko razdalj.

(41)

Program 4: Izraˇcun razdalj med posameznimi besedami in zapis matrik razdalj.

1 c l c

2 c l e a r a l l

3 U = importdata (’ 2 skupini . mat ’,’ ’, 0 ) ; % v matriko U nalozimo s t . p o j a v i t e v unije

4 P = importdata (’ presekskupin . mat ’,’ ’ , 0 ) ;% v matriko P n a l o i m o s t . p o j a v i t e v preseka

5 n = s i z e(U, 1 ) ;

6 D = [ ] ;

7 f o r i =1:n

8 V = [ ] ;

9 f o r j =1:n

10 V = [ V,1−(P ( i , j ) /U( i , j ) ) ] ; % izracun r a z d a l j e po enacbi in zapis v matriko r a z d a l j

11 endfor

12 D = [D; V ] ;

13 endfor

14 D

15 save razdaljeSKUP . mat D

Kot je razvidno v programu 4, najprej naložimo podatke za presek in unijo množic pojavitev parov izbranih besed. V 10. vrstici izraˇcunamo razdaljo po enaˇcbi (8) in posamezne razdalje vpisujemo v matriko razdalj. Ko se program izvede, dobimo matriko razdalj, na podlagi katere bomo z algoritmom DBSCAN iskali gruˇce besed. V primeru obeh razdalj je program popolnoma enak, razlika je le v matrikiU, glede na izbrano razdaljo uporabimo razliˇcno datoteko. Torej ˇce bo v imenovalcu unija dveh besed, bomo naložili datoteko, v katero smo vpisali matriko unije posameznih besed, v primeru, da bo v imenovalcu minimalno število pojavitev, pa bomo naložili datoteko, v katero smo zapisali matriko minimalnega števila pojavitev med posameznima besedama. Najprej si oglejmo matriko razdalj za razdaljo kot ko- liˇcnik preseka in unije pojavitev:

D=







0.00000 0.95873 0.96207 0.94106 0.92343 0.96314 0.96738 0.98200 0.95873 0.00000 0.97359 0.98469 0.93018 0.93926 0.97531 0.98984 0.96207 0.97359 0.00000 0.73359 0.86712 0.92936 0.85124 0.86851 0.94106 0.98469 0.73359 0.00000 0.87000 0.90934 0.91761 0.94355 0.92343 0.93018 0.86712 0.87000 0.00000 0.87406 0.76084 0.88174 0.96314 0.93926 0.92936 0.90934 0.87406 0.00000 0.91584 0.94944 0.96738 0.97531 0.85124 0.91761 0.76084 0.91584 0.00000 0.89983 0.98200 0.98984 0.86851 0.94355 0.88174 0.94944 0.89983 0.00000





 .

Oglejmo si še matriko za razdaljo kot koliˇcnik preseka in minimalnega števila pojavitev:

(42)

Dm=







0.00000 0.27618 0.89970 0.88209 0.92754 0.81449 0.96929 0.96778 0.27618 0.00000 0.98179 0.98331 0.83156 0.78149 1.00000 0.99848 0.89970 0.98179 0.00000 0.72847 0.94732 0.98278 0.99291 0.98044 0.88209 0.98331 0.72847 0.00000 0.97052 0.98715 0.99169 0.99655 0.92754 0.83156 0.94732 0.97052 0.00000 0.97005 0.89706 0.94591 0.81449 0.78149 0.98278 0.98715 0.97005 0.00000 0.92734 0.94476 0.96929 1.00000 0.99291 0.99169 0.89706 0.92734 0.00000 0.65017 0.96778 0.99848 0.98044 0.99655 0.94591 0.94476 0.65017 0.00000





 .

Kot vidimo, sta obe matriki razdalj Dsimetriˇcni in imata po diagonali vrednosti 0. Torej ustrezata obliki poljubne matrike razdalj in bosta v nadaljevanju uporabljeni za osnovo iskanja elementov gruˇc z algoritmom DBSCAN.

Prav tako opazimo, da so razdalje razmeroma velike, kar je posledica velikih razlik pri šte- vilu pojavitev posameznih besed in dveh besed hkrati.

6.6 Implementacija DBScan algoritma

Doloˇcili smo razdalje med besedami in zapisali dobljeno matriko razdalj za naš konkreten primer. Matriko razdalj lahko uporabimo za gruˇcenje podatkov z DBSCAN algoritmom.

Program 5: Zapis besed v matriko (za izris diagrama in neposrednih povezav v programu Pajek).

1 s t = s i z e (D, 1 ) ;

2 besede = [’ * Vertices 10 ’;’ 1 "matematika" ’; ’ 2 " algebra " ’; ’ 3 "mnozenje" ’; ’ 4 "

sestev anje " ’; ’ 5 "enacba" ’;’ 6 " geometrija " ’;’ 7 "premica" ’;’ 8 " d a l j i c a " ’;’ * Arcs ’] ;

S pomoˇcjo zgornje kode (Program 5) smo torej uporabili ustrezno matriko razdalj, na podlagi katerih bo algoritem iskal jedra gruˇc. Predno izvedemo algoritem DBSCAN, moramo definirati še vhodna pogoja, to sta okolica²in minimalno število toˇckminPts, kar je vidno na spodnji kodi programa 6.

Program 6: Vhodna pogoja²inminPts.

1 epsilon = 0 . 9 ;

2 minPts = 4 ;

(43)

Program 7: Iskanje toˇck, ki predstavljajo jedra.

1 function [ IDX , i s n o i s e ]=DBSCAN(D, epsilon , MinPts )

2

3 C = 0 ;

4 n = s i z e(D, 1 ) ;

5 IDX = zeros( n , 1 ) ;

6 7

8 v i s i t e d = f a l s e (n , 1 ) ;

9 i s n o i s e = f a l s e ( n , 1 ) ;

10

11 f o r i = 1 : n

12 i f ~ v i s i t e d ( i )

13 v i s i t e d ( i ) = true ;

14 Neighbors = RegionQuery ( i ) ;

15 i f numel ( Neighbors ) < MinPts % ce ni dovolj tock v o k o l i c i , tocka ni vsebovana v gruci

16 i s n o i s e ( i ) = true ;

17 e l s e

18 C = C + 1 ;

19 ExpandCluster ( i , Neighbors , C) ; % pregledamo se okolice vsebovanih tock v gruci s fu n k c i j o ExpandCluster

20 endif

21 endif

22 endfor

Program 7 vkljuˇcuje funkcijo za iskanje jeder gruˇc. Definirali smo toˇcke izven gruˇce s spre- menljivkoisnoise. V vrstici številka 12 program zaˇcne pregledovati matriko razdalj in pre- verja ali je v okolici posamezne toˇcke dovolj toˇck, da postane jedro. V kolikor ni dovolj toˇck v okolici izbrane toˇcke, program zaˇcne preverjati novo toˇcko (vrstica 17 - toˇcka je definirana kot motnja in zato ni jedro). ˇCe pa je v okolici dovolj toˇck, program zažene funkcijoExpan- dCluster, ki bo za vse toˇcke v okolici jedra preverila, ali imajo tudi same zadostno število toˇck v svoji okolici. Kot smo že omenili pri razlagi DBSCAN algortima s pomoˇcjo slik, bo program sedaj v gruˇco dodajal še ostale toˇcke, ki ustrezajo pogojema²inminPts.