Page 6 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2016 3rd Student Computer Science Research Conference. Koper: University of Primorska Press, 2016
P. 6
rame in potem se primerjajo ˇstevilo unikatnih ter ujema- kjer so N (.) n-grami. Cˇ e je vrednost C(si|d) nad doloˇce-
joˇcih n-gramov. Veˇcje je ujemanje, veˇcja je verjetnost priso- nim pragom, potem je si klasificiran kot plagiat. Z uˇcenjem
tnosti plagiata. Slabost tega pristopa je, da se iˇsˇce podob- na oznaˇceni uˇcni mnoˇzici smo poiskali prag za doloˇcene n-
nost oz. primerjava celotnega dokumenta in ne posameznih grame.
manjˇsih delov. Obstajajo tudi posebne metode pri katerih
dejansko ne iˇsˇcemo ujemanja celotnih stavkov oz. besedila, 3.2 Izboljšana metoda
ampak samo ujemanje doloˇcenih besed. V Stamatatos-ovem
[3] sistemu se uporablja iskanje ujemanje tako imenovanih Referenˇcna metoda za ugotavljanje plagiata uporablja n-
prekinitvenih besed, ki so seznam frekvenˇcno zelo veliko- grame fiksne velikosti in tako ne upoˇsteva manjˇsih n-gramov.
krat uporabljenih besed v besedilu. Izkaˇze se, da lahko z Pri veˇcjih n-gramih zato pade uˇcinkovitost algoritma, saj so
ujema-njem teh prekinitvenih besed zelo dobro ugotavljamo moˇznosti enakih zelo majhne. Zato smo dodali pri ugota-
plagiate, tudi ko so besedila zelo spremenjena. vljanju vsebnosti algoritem Stupid Backoff [2] s katerim smo
zaˇceli upoˇstevati tudi manjˇse n-grame.
Sami smo se odloˇcili, da bomo uporabili metodo, ki so jo
uporabili v originalnem ˇclanku [1], to je uporaba srednje Predlagan algoritem ima prva dva koraka enaka kot refe-
poti med PPChecker in Ferret metodama. Namesto, da bi renˇcni, nato pa sledijo:
primerjali n-grame celotnega dokumenta, se dokument naj-
prej razdeli na manjˇse dele, to je povedi, in nato se nad njimi 1. Referenˇcni dokument d razdelimo na vse n-grame pri
ugotavlja ujemanje z referenˇcnim korpusom. ˇcemer je n ∈ {1, 2, ..n}.
3. METODA 2. Vsak n-gram povedi si pri izbranem n testiramo vseb-
nost z enaˇcbo (2). Cˇ e je n-gram vsebovan priˇstejemo
Z naslednjimi metodami smo poskuˇsali odgovoriti na vpra- 1, drugaˇce pa rekurzivno preverjamo manjˇse n-grame.
ˇsanje, ali je poved si plagiat glede na dokument d iz korpusa.
Najprej smo implementirali referenˇcno metodo iz ˇclanka, 3. Naredimo vsoto vsebnosti vseh n-gramov povedi, jo
nato pa smo jo poskusili izboljˇsati s pomoˇcjo algoritma Stu- normaliziramo in nato preverimo glede na prag, ali je
pid Backoff. poved plagiat ali ne.
3.1 Originalna metoda C(bii−k+1) = 1, f (bii−k+1) > 0
0.4C (bii−k+2 ), else
Imamo dokument r, za katerega sumimo, da je plagiat. r
razdelimo na povedi si. Imamo tudi referenˇcni korpus D, ki (2)
je sestavljeni iz dokumentov d. Torej nas zanima ali je po-
ved si plagiat, ki izvira iz dokumenta d. Prepisane povedi so C(bi) = 1, f (bi) > 0
lahko spremenjene oz. se je kopiral samo del povedi, posa- 0, else
mezne prepisane besede pa so lahko v pomeˇsanem vrstnem
redu, kar pa oteˇzi samo ugotavljanje plagiata. Ta problem Pri ˇcemer je bii−k+1 iskan n-gram in f (bii−k+1) frekvenca
smo reˇsili z uporabo n-gramov, kajti malo verjetno je, da se iskanega n-grama.
bodo n-grami iz razliˇcnih dokumentov ujemali. Verjetnost
seveda pada z viˇsanjem n-ja. Ker pa so prepisane povedi se- 4. REZULTATI IN DISKUSIJA
stavljene iz delˇckov besedila iz razliˇcnih delov originalnega
dokumenta pa smo celotni dokument r razdeliti na n-grame V sledeˇcem podpoglavju opiˇsemo zgradbo in obliko izbra-
in ne na povedi. nega korpusa. Nato sledi podpoglavje v katerem podrobneje
predstavimo eksperimentalne rezultate.
Postopek algoritma je naslednji:
1. Dokument, ki vsebuje plagiate razdelimo na posame- 4.1 Korpus
zne povedi si.
Za potrebe testiranja algoritmov smo uporabili METER kor-
2. Poved si je razdeljena na n-grame, ki sedaj predsta- pus, ki je zgrajen za analizo po-uporabe besedila. Na voljo
vljajo poved. je v veˇc razliˇcnih formatih, mi smo uporabili korpus v for-
matu XML. Podatki v korpusu so deljeni na dva dela. Prvi
3. Referenˇcni dokument d je razdeljen na n-grame brez del vsebuje 771 novic, ki jih je napisala Press Association
predhodnega deljenja na povedi, saj lahko plagiat vse- (PA) in veˇcinoma vsebuje ˇclanke o dogajanjih na sodiˇsˇcih.
buje razliˇcne dele originalnega besedila. Drugi del korpusa so ˇclanki razliˇcnih Britanskih novic [8].
Britanski ˇclanki so v korpusu razdeljeni na povedi, ki so nato
4. S primerjanjem n-gramov povedi si z dokumentom oznaˇceni z rewrite, verbatim ali new. Te oznake nam povedo,
ugotovimo ali je poved plagiat, kot je opisano v na- ali je del povedi prepisan, povzet ali na novo napisan glede
daljevanju. na referenˇcne PA ˇclanke. Za posamezno poved velja, da je
plagiat, ˇce je veˇcji del besed oznaˇcen kot prepisan ali pov-
Za preverjanje plagiata, smo primerjali dobljene n-grame s zet. Na sploˇsno se uporablja enaˇcba |siV ∪ siR| > 0.4|si| pri
tistimi iz referenˇcnega besedila s pomoˇcjo enaˇcbe (1). ˇcemer siV in siR predstavljata ˇstevilo povzetih in prepisanih
besed, si pa ˇstevilo vseh besed v povedi. Vse skupaj je v
C (si |d) = |N (si) ∩ N (d)| (1) korpusu 3600 povedi Britanskih novic, od tega jih je po tem
|N (si)| pravilu 61% oznaˇcenih kot plagiat.
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 6
Ljubljana, Slovenia, 12 October
joˇcih n-gramov. Veˇcje je ujemanje, veˇcja je verjetnost priso- nim pragom, potem je si klasificiran kot plagiat. Z uˇcenjem
tnosti plagiata. Slabost tega pristopa je, da se iˇsˇce podob- na oznaˇceni uˇcni mnoˇzici smo poiskali prag za doloˇcene n-
nost oz. primerjava celotnega dokumenta in ne posameznih grame.
manjˇsih delov. Obstajajo tudi posebne metode pri katerih
dejansko ne iˇsˇcemo ujemanja celotnih stavkov oz. besedila, 3.2 Izboljšana metoda
ampak samo ujemanje doloˇcenih besed. V Stamatatos-ovem
[3] sistemu se uporablja iskanje ujemanje tako imenovanih Referenˇcna metoda za ugotavljanje plagiata uporablja n-
prekinitvenih besed, ki so seznam frekvenˇcno zelo veliko- grame fiksne velikosti in tako ne upoˇsteva manjˇsih n-gramov.
krat uporabljenih besed v besedilu. Izkaˇze se, da lahko z Pri veˇcjih n-gramih zato pade uˇcinkovitost algoritma, saj so
ujema-njem teh prekinitvenih besed zelo dobro ugotavljamo moˇznosti enakih zelo majhne. Zato smo dodali pri ugota-
plagiate, tudi ko so besedila zelo spremenjena. vljanju vsebnosti algoritem Stupid Backoff [2] s katerim smo
zaˇceli upoˇstevati tudi manjˇse n-grame.
Sami smo se odloˇcili, da bomo uporabili metodo, ki so jo
uporabili v originalnem ˇclanku [1], to je uporaba srednje Predlagan algoritem ima prva dva koraka enaka kot refe-
poti med PPChecker in Ferret metodama. Namesto, da bi renˇcni, nato pa sledijo:
primerjali n-grame celotnega dokumenta, se dokument naj-
prej razdeli na manjˇse dele, to je povedi, in nato se nad njimi 1. Referenˇcni dokument d razdelimo na vse n-grame pri
ugotavlja ujemanje z referenˇcnim korpusom. ˇcemer je n ∈ {1, 2, ..n}.
3. METODA 2. Vsak n-gram povedi si pri izbranem n testiramo vseb-
nost z enaˇcbo (2). Cˇ e je n-gram vsebovan priˇstejemo
Z naslednjimi metodami smo poskuˇsali odgovoriti na vpra- 1, drugaˇce pa rekurzivno preverjamo manjˇse n-grame.
ˇsanje, ali je poved si plagiat glede na dokument d iz korpusa.
Najprej smo implementirali referenˇcno metodo iz ˇclanka, 3. Naredimo vsoto vsebnosti vseh n-gramov povedi, jo
nato pa smo jo poskusili izboljˇsati s pomoˇcjo algoritma Stu- normaliziramo in nato preverimo glede na prag, ali je
pid Backoff. poved plagiat ali ne.
3.1 Originalna metoda C(bii−k+1) = 1, f (bii−k+1) > 0
0.4C (bii−k+2 ), else
Imamo dokument r, za katerega sumimo, da je plagiat. r
razdelimo na povedi si. Imamo tudi referenˇcni korpus D, ki (2)
je sestavljeni iz dokumentov d. Torej nas zanima ali je po-
ved si plagiat, ki izvira iz dokumenta d. Prepisane povedi so C(bi) = 1, f (bi) > 0
lahko spremenjene oz. se je kopiral samo del povedi, posa- 0, else
mezne prepisane besede pa so lahko v pomeˇsanem vrstnem
redu, kar pa oteˇzi samo ugotavljanje plagiata. Ta problem Pri ˇcemer je bii−k+1 iskan n-gram in f (bii−k+1) frekvenca
smo reˇsili z uporabo n-gramov, kajti malo verjetno je, da se iskanega n-grama.
bodo n-grami iz razliˇcnih dokumentov ujemali. Verjetnost
seveda pada z viˇsanjem n-ja. Ker pa so prepisane povedi se- 4. REZULTATI IN DISKUSIJA
stavljene iz delˇckov besedila iz razliˇcnih delov originalnega
dokumenta pa smo celotni dokument r razdeliti na n-grame V sledeˇcem podpoglavju opiˇsemo zgradbo in obliko izbra-
in ne na povedi. nega korpusa. Nato sledi podpoglavje v katerem podrobneje
predstavimo eksperimentalne rezultate.
Postopek algoritma je naslednji:
1. Dokument, ki vsebuje plagiate razdelimo na posame- 4.1 Korpus
zne povedi si.
Za potrebe testiranja algoritmov smo uporabili METER kor-
2. Poved si je razdeljena na n-grame, ki sedaj predsta- pus, ki je zgrajen za analizo po-uporabe besedila. Na voljo
vljajo poved. je v veˇc razliˇcnih formatih, mi smo uporabili korpus v for-
matu XML. Podatki v korpusu so deljeni na dva dela. Prvi
3. Referenˇcni dokument d je razdeljen na n-grame brez del vsebuje 771 novic, ki jih je napisala Press Association
predhodnega deljenja na povedi, saj lahko plagiat vse- (PA) in veˇcinoma vsebuje ˇclanke o dogajanjih na sodiˇsˇcih.
buje razliˇcne dele originalnega besedila. Drugi del korpusa so ˇclanki razliˇcnih Britanskih novic [8].
Britanski ˇclanki so v korpusu razdeljeni na povedi, ki so nato
4. S primerjanjem n-gramov povedi si z dokumentom oznaˇceni z rewrite, verbatim ali new. Te oznake nam povedo,
ugotovimo ali je poved plagiat, kot je opisano v na- ali je del povedi prepisan, povzet ali na novo napisan glede
daljevanju. na referenˇcne PA ˇclanke. Za posamezno poved velja, da je
plagiat, ˇce je veˇcji del besed oznaˇcen kot prepisan ali pov-
Za preverjanje plagiata, smo primerjali dobljene n-grame s zet. Na sploˇsno se uporablja enaˇcba |siV ∪ siR| > 0.4|si| pri
tistimi iz referenˇcnega besedila s pomoˇcjo enaˇcbe (1). ˇcemer siV in siR predstavljata ˇstevilo povzetih in prepisanih
besed, si pa ˇstevilo vseh besed v povedi. Vse skupaj je v
C (si |d) = |N (si) ∩ N (d)| (1) korpusu 3600 povedi Britanskih novic, od tega jih je po tem
|N (si)| pravilu 61% oznaˇcenih kot plagiat.
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 6
Ljubljana, Slovenia, 12 October
