Edizioan oinarritutako distantziak

• Hamming \(d_{hamming}\)
  method = "hamming"
• generalized Levenshtein \(d_{lv}\)
  method = "lv"
  Beste inplementazio bat dago r-core paketean: adist()
• Longest Common Substring \(d_{lcs}\)
  method = "lcs"
• optimal string alignment \(d_{osa}\) by default
  method = "osa"
• generalized Damerau-Levenshtein \(d_{dl}\)
  method = "dl"
  Damerauk birplanteatu zuen Levenshteinen algoritmoa, baina kokapen trukaketa ikuskera zabalagotik ulertzen du.

Levenshtein eta Damerrau-Levenshtein distantzien arteko alderaketa

stringdist("ab", "bca", method = "lv")

## [1] 3

stringdist("ab", "bca", method = "dl")

## [1] 2

# Zein bi kate multzoen artean dago distantzia handiagoa
stringdist("hortorrinogarinlologo", "otorrinonaringologo", method = "lv") ; stringdist('jai', 'gin', method = "lv")

## [1] 4

## [1] 3

q-grametan oinarritutakoak

q-gram neurriak beti daude 0 eta 1 artean, 0 litzateke alderik ez duena eta 1 erabat bestelakoa.

Edozein kate > 0 dela, berori sortzen duten q luzerako zenbait grametan. Lehengo jai hori izango da, q=2 hartzen badugu, ja eta ai.

q-gram distantzia kalkulatzeko alderatzen dira kate bitan ematen diren q-gramak eta zenbatzen dira elkarrekin ez dituzten qgram kopurua. Esate baterako:

stringdist('leia', 'leela', method = "jaccard", q=2)

## [1] 0.8333333

Horren azalpena honela ulertu behar da: \(Q('leia';2)=\{'le', 'ei', 'ia'\}\) eta \(Q('leela';2)=\{'le','ee','el','la'\}\) batera ez datozenak 6 dira, beraz: \(1-\frac{1}{6}\approx 0.83\).

Beraz, emaitzak qren tamainaren araberakoa izango da:

stringdist('leia', 'leela', method = "jaccard", q=1); 

## [1] 0.25

stringdist('leia', 'leela', method = "jaccard", q=3)

## [1] 1

Lehen edizioan oinarritutako distantzietarako alderatu ditugun elementuak q-grametan alderatuta honela ikusiko lirateke:

stringdist("hortorrinogarinlologo", "otorrinonaringologo", method = "jaccard", q=2); stringdist('jai', 'gin', method = "jaccard", q=2)

## [1] 0.4210526

## [1] 1

• q-gram \(d_{qgram}\)
  method = "qgram"
  Honek dio zenbat q-gram ez duten komun alderatzen diren kateek
• Jaccard \(d_{jaccard}\)
  method = "jaccard"
  Honek aurrekoaren antzera, baina komun dituztenak kontuan izanda, halan 0 eta 1en arteko balioak hartzen ditu
• cosine \(d_{cos}\)
  method = "cosine"
  Honek kosinuaren kalkulua hartzen du oinarri. Geometrian oinarritutako neurria da: alderatzen diren s eta t kate bi hartuta, v(s;q) eta v(t;q) ulertu behar dira. Bektore bien arteko anguluaren kosinua da d_cos hori.

Heuristic ikuspegikoak

Ez zaizkigu interesatzen, horregatik aipatu baino ez dir aegiten

• Jaro
• Jaro-Winkler

Gure interes eta asmoen arabera begiratu beharrekoak:

• Distantzia era desberdinen araberako hurrenkerak eregi, teorian oinarrituta horien doikuntza aztertzeko.
• Aztertu literaturan zelan agertzen diren distantzion erabilerak.
• Aztertu distantzion araberako sailkapenak koherenteak diren (cluster analisa)

Sintaxia

Paketearen oinarrizko aginduak dira stringdist, elementu bien arteko distantzia kalkulatzen duena, eta stringdistmatrix matriz biko elementuak alderatzen dituena.

Aztertzeko erabiliko ditudan datuak:

# Datuak aukeratu
datuak <- read.table('datuak', 
                     sep = ',', 
                     stringsAsFactors = F)
datuak <- datuak[,-1]
colnames(datuak) <- datuak[1,]
rownames(datuak) <- datuak[,1]
datuak <- datuak[-1, -1]

knitr::kable(datuak[2,20])

knitr::kable(datuak[c(3:12),20])

stringdist(datuak[2,20], datuak[c(3:12),20])

##  [1] 0 0 0 3 3 0 0 0 3 3

Matrizeak alderatzeko aginduarekin:

table(datuak[,20], datuak$Adin.tartea)

##             
##              adineko EI gazte heldu
##   lenarte          4  1     1     2
##   lenaurarte       0  0     2     2

x <- stringdistmatrix(datuak[,20], method = "cosine", q=2)
round(x,3)

##        1     2     3     4     5     6     7     8     9    10    11
## 2  0.000                                                            
## 3  0.000 0.000                                                      
## 4  0.000 0.000 0.000                                                
## 5  0.000 0.000 0.000 0.000                                          
## 6  0.184 0.184 0.184 0.184 0.184                                    
## 7  0.184 0.184 0.184 0.184 0.184 0.000                              
## 8  0.000 0.000 0.000 0.000 0.000 0.184 0.184                        
## 9  0.000 0.000 0.000 0.000 0.000 0.184 0.184 0.000                  
## 10 0.000 0.000 0.000 0.000 0.000 0.184 0.184 0.000 0.000            
## 11 0.184 0.184 0.184 0.184 0.184 0.000 0.000 0.184 0.184 0.184      
## 12 0.184 0.184 0.184 0.184 0.184 0.000 0.000 0.184 0.184 0.184 0.000

plot(hclust(x), labels = datuak$Adin.tartea)

Matrizearen itxuran erakusteko, aurreko datuak:

xm <-as.matrix(round(x,3))
knitr::kable(xm)

Erreferentziak

Downey, S. S., Sun, G., & Norquest, P. (2017). alineR: an R Package for Optimizing Feature-Weighted Alignments and Linguistic Distances. The R Journal, 9(1), 138–152.

Loo, M. P. J. van der. (2014). The stringdist package for approximate string matching. The R Journal, 6(1), 111–122. *