december 27, 2003
Bloggidentifiering (Blog Identification)
Inpirerad av idéerna i Automatisk identifikation av språk (språkidentifiering), Automatisk bloggning? (Blog Markov) samt Markov av svenska bloggar har jag nu skapat ett program för att automatiskt identifera bloggar: Blog Identification.
Inparameter till programmet är en URL, t.ex. till en blogg. Sedan jämförs texten (se nedan) med olika bloggar, som jag synnerligen subjektivt valt ut bland några av mina dagligen besökta bloggar samt de flesta av bloggarna som finns med i Internetworld-artiklarna Världens bästa bloggar samt Bästa svenska bloggarna. (Tyvärr kommer min dator inte åt vissa bloggar, t.ex. Rymdimperiet, så jag har inte lyckats skapa en "profil" för dessa bloggar. Sorry.)
Programmet använder en n-gram metrik för att avgöra hur nära en text är de andra texterna, och använder metoden (nästan rakt av) som finns beskrivet i papret N-Gram Based Text Categorization skrivet av William B. Cavnar och John M. Trenkle. Metoden bygger på att man skapar en "profil" av de 300 mest frekventa n-grammen som sedan jämförs med en ny profil skapas från den webbsida som ska identifieras.
För att testa programmet körde jag alla bloggar som input till programmet för att se hur bra de kunde identifieras. Tanken är att en blogg ska vara sig själv närmast. Som man ser i sammanställningen lyckas det rätt bra. Idealet vore att avståndet för en sådan "självtest" är 0 (noll) men av olika skäl når man inte riktigt detta när det webbaserade programmet körs. Efterhand bloggarnas innehåll förändras kommer också resultatet att förändras, och jag vet inte riktigt hur ofta jag kommer att skapa nya profiler att jämföra med.
I slutet av sammanställningen finns en summering av placeringarna i testet. Den som fick lägst totalsumma (i körningen förmiddag 27 December 2003). Det är lite problematiskt att jämföra på detta sätt eftersom språk, ämne, HTML-layout etc påverkar resultatet. Jag vet inte riktigt vilka slutsatser man ska dra av att bajs.se har lägst totalpoäng och The church Of Me har högst.
Det finns några idéer till varianter och utvidgningar som jag nog kommer att testa inom den närmsta framtiden.
METOD
För intresserade beskrivs den metod som används, vilket i princip är en summering av ovan nämnda paper.
Skapa profil
- läs in texten
- strippa bort allt som inte är relevant. (För närvarande tar jag först bort all HTML-kod samt allt som inte är vanliga bokstäver. Detta kan ändras i framtiden.)
- skapa profilen:
- skapa en tom hashtabell
- för n=1..5:
- skapa n-grammen för n och lägg in dessa i hashtabellen
- skapa n-grammen för n och lägg in dessa i hashtabellen
- skapa en tom hashtabell
- sortera hashtabellen i frekvensordning
- spara de F (=300) mest frekventa n-grammen i frekvensordning till en fil
Så här kan en profil se ut för hakank.blogg, fast här sparas frekvensen i stället för ranknumret (eftersom ranken helt enkelt är positionen i filen). Möjligen kommer frekvensen att användas i senare versioner av distansmetrik.
Blogg identifiering
- läs in texten som ska identifieras, och skapa en profil (målprofilen)
för denna text (se ovan, men spara inte i fil)
- läs in samtliga sparade profiler
- för samtliga sparade profiler:
- jämför profilen med målprofilen m.h.a. n-gram-distans/avstånd
- spara n-gram-avståndet
- vikta avståndet (Jag har delat avståndet med 300, dvs det värde som man använder i n-gram-distans/avstånd när n-grammet G saknas i den jämförda profilen P.)
- jämför profilen med målprofilen m.h.a. n-gram-distans/avstånd
- sortera de erhållna avstånden i stigande ordning, dvs lägst avstånd (=störst likhet) först
- presentera bloggnamn etc i avståndsordning
n-gram distans/likhet
Givet: målprofil (MP) och den profil (P) som ska jämföras
- För samtliga n-gram (G) i MP:
- slå upp ranknummer (R1) för G i MP.
- slå upp ranknumret (R2) för G i P.
Om G saknas i P, tilldela R2 ett högt tal (här 300)
- räkna ut differensen mellan de två rankvärdena: abs(R1 - R2)
- slå upp ranknummer (R1) för G i MP.
- summera samtliga differenser. Detta är n-gram-avståndet mellan MP och P..
Posted by hakank at december 27, 2003 12:11 EM Posted to Blogging | Machine learning/data mining | Program
Comments
Det där ser riktigt spännande ut. Jag har funderat på att erbjuda lite renare format av mina texter i något text- eller XML-format för att enkelt kunna ner filer för säkerhetskopiera mina texter samt erbjuda folk att laborera med texterna. Finns det förslag på något smart format?
Posted by: David Pettersson at december 27, 2003 08:43 EM
En sak som jag skulle uppskatta är plain text, dvs ingen HTML-kod, inga länkar, ingen reklam, ingenting förutom den rena texten.
Vad gäller format är RSS/RDF rätt bra eftersom det är tillräckligt strukturerat så det är enkelt att filtrera den information man vill ha. (I mitt program valde jag att gå den enkla vägen att ta HTML-texten och filtrera den, främst eftersom det är den man kan läsa och jämföra med; det är ju ansiktet utåt, på ett sätt som en RSS-fil inte är.)
Något som jag upptäckte som skulle vara bra är om det fanns någon taggning för vilket språk ett avsnitt är skrivet i, t.ex <sve>...</sve>, <eng>...</eng>. Det skulle underlätta vissa typer av analyser. Men det är ingen standardtagg. Ännu. :-)
Säkerhetskopior för bloggen: Tänk på att alla länkar, bloggpost-nummer etc ska vara med så det är enkelt att befolka om din databas (om du använder sådan) om det skulle behövas.
Jag tror också att det bör vara olika filer för dessa olika ändamål och behov: textmanipulation, strukturerad information, säkerhetskopia.
Posted by: Håkan Kjellerstrand at december 29, 2003 01:32 FM
Hmm, det har du nog rätt i. Jag borde nog sluta med att skjuta upp säkerhetskopiefrågan. Det vore inte så roligt att upptäcka att webbhotellet klantat bort databasen.
Posted by: David Pettersson at januari 2, 2004 09:27 EM