Query Log Topic Detection

Hosseini, M., Abolhassani, H., and Harikandeh, 2007

Författarna försöker klustra sökloggar från AOL med hjälp av en bipartit graf mellan söksträngar och adresser och K-meansklustring i de resulterande komponenterna.

Metod

Metoden innehåller fyra steg:

1. Bygg en bipartit med söksträngar och adresser, där en kant finns om ensökning har föranlett ett klick till adressen.
2. Elimination av skräpkanter, för att kunna få ut komponenter.
3. Dimensionreducering av grannmatrisern i komponentenerna.
4. Klustring med K-means i komponenterna.

Resultat

Testdata är framtagen genom att plocka 40 k slumpvisa sökningar. Dessa klassificeras manuellt till 7 olika kategorier.

Efter de första stegen med den bipartita grafen finns det bara en komponent som är så stor att den är intressant att gå vidare med, och den innehåller 55 % av datan. Den komponenten klustras till fyra delar med K-means.

Resultaten utvärderas genom att precisionen för olika ämnen kontrolleras i varje kluster. Tre av fyra kluster hade något ämne som med betydligt högre precision än de andra.

Relevans för oss

Att klustra i AOL-loggarna är ju precis vad vi håller på med, så det är intressant att se hur de lyckas med. De har dock nöjt sig med att försöka passa in några få jättekluster i förutbestämda kategorier, något som vi bedömmer som ointressant. Något som däremot är intressant är att de har lagt ner ett stort arbete på att manuellt klassificera 40 k sökningar i sju kategorier, vilket ger oss en bild av hur proportionerna mellan dessa borde vara i våra kluster, det är möjligtvis något vi skulle kunna använda för utvärdering.

Att deras initiala steg med komponenter i en bipartit graf bara gav en stor komponent stämmer väl med våra erfarenheter av loggarna,  att det är skräpiga data som är svåra att slå isär.

Sammanfattning av Topic Detection and Tracking using idf-Weighted Cosine Coefficient (J. Michael Schultz, Mark Liberman), 1999
Författarna försöker att med viktade cosine mått (tf-idf) följa (tracking) och upptäcka (detection) nyhetsämnen.

Tracking

Två urval av träningsdata väljs ut, ett som innehåller artiklar om ämnet man är ute efter och ett som inte gör det.

Val av ämneskännetecken

För att kunna göra en cosine-jämförelse mellan ett ämne och en artikel behöver man ta fram ord som kännetecknar ämnet från artiklar i träningsdata. Författarna försökte med fyra olika metoder:

1. Ta alla ord i artiklarna.
2. För alla artiklar tilsammans, ta ut de n vanligaste orden.
3. För varje artikel, ta ut de n vanligaste orden.
4. Som 3, men man lägger iterativt till fler termer om de ger bättre resultat.

Metod fyra gav bäst resultat, men man valde metod tre eftersom den var marginellt sämre och betydligt mindre komplicerad.

Normalisering

Författarna försökte på olika sätt normalisera vektorn som representerar ämnet med hjälp av träningsdata, men gav upp det eftersom resultaten inte blev bättre.

Resultat

Bäst resultat verkade enkla metoder ge och författarna anser att deras resultat är konkurrenskraftiga.

Detection

Man försöker upptäcka ämnen med hjälp av algoritmen Single-linkage clustering och samma likhetsmått som tidigare. Algoritmen ger problematiska kedjefenomen, olika ämnen hålls ihop i samma kluster av enskilda artiklar som behandlar båda ämnena. Författarna verkar vara missnöjda och skyller resultaten på algoritmens brister.

In Understanding the Relationship between Searchers’ Queries and Information Goals Downey, Dumas, Liebling and Horvitz describe an interesting property of users interacting with search engines: the rate of success, that is the likelihood of a user finding what he or she is looking for, is related to the frequency of the query issued and the underlying information goal it is supposed to lead to.

In particular, the best way to find a frequently sought information goal in a search engine is to employ a frequently used query. For example, a good way to find http://www.webmd.com may be to issue the query webmd. In the authors’ study this was a fairly frequent query and information goal. Using the more frequent query medical questions page would yield more results making it more difficult to find the correct website. On the other hand, the much less frequent webmb would probably require the user to perform spelling correction before finding what he or she was looking for.

Note the connection between information goal and website. In their study, the authors have chosen to make these synonymous. Of course this need not be so. It may be true that it is more difficult to get to http://www.webmd.com by using medical questions page than by using webmb, but if the user wasn’t explicitly looking for http://www.webmd.com but instead was interested in finding the answer to a medical question then medical questions page could have been a better query to issue. This is not reflected in the study.

After having submitted a query the action of the user varies depending on the frequency of the query. Frequent queries more often lead to a click in the result list than do rare queries. Rare queries are more often followed by a requery than do frequent queries. Having clicked a frequently clicked result, the chance of clicking another result is smaller than if the clicked result had been rare. Conversely, the likelihood of a user issuing a requery after having clicked a rare result is greater than if he or she had clicked a frequent result.

According to the study, search engines are much better at finding answers to common information goals than they are at resolving rare goals. At first glance this seems reasonable enough.  A successful search engine is one which quickly finds the information that a user requires. Finding what most people want is almost as good as finding what everybody wants. The evidence of this is that for rare information goals, users typically need to reformulate their queries more times than they do for frequent goals.

To sum up, the paper implies that the frequency of the queries and clicked links in a session can help us discern to what degree the user was able to find what he or she was looking for.

Sammanfattning av Query Clustering Using User Logs (JI-RONG WEN,  JIAN-YUN NIE, HONG-JIANG ZHANG), 2002
Författarna försöker klustra sökningar i Encarta med avseende på sökord och klickade dokument.

Tillvägagångssätt

Klustringsprinciper

1. Om två sökningar innehåller samma eller liknande sökord så representerar de samma, eller liknande, informationsbehov.
2. Två sökningar är lika om de leder till vala av samma eller liknande dokument.

Princip ett räcker inte själv eftersom samma sökord kan representera olika behov.  Beräknad likhet innebär inte alltid semantisk likhet, detta gäller särskilt för korta söksträngar.

Princip två har svagheten att användare inte nödvändigtvis bara klickar på relevanta dokument och ett dokument kan innehålla information om flera ämnen.

Implementation

Data

Ur stora mängder loggar tar man ut sessioner som består av en söksträng och de dokument-klick som sökningen gav upphov till.

Algoritm

Man anser sig behöva en algoritm som klarar stora datamängder, inte kräver förutbestämt antal kluster osh som sorterar bort skräp. Valet faller på DBSCAN som har komplxitetetn O(nlogn).

Likhetsmått

För jämförelse av söksträngar kan man använda termlikhet (exempelvis cosine) eller stränglikhet (exempelvis Levenshtein).

Klicklikhet kan göras baserad på överlappande dokument, jämförbart med termlikheten, eller med hjälp av de kategorier som de klickade dokumenten tillhör.

Kombination av olika mått

Genom att kombinera olika mått kan man få bättre resultat än med ett enskilt mått. Man måste då välja parametrar för viktning av olika mått.

Utvärdering

Ur en månads loggar från Encarta, 22 GB, 2,7 M sessioner väljs 20 000 sessioner slumpmässigt för utvärdering.

Fyra olika kombinationer av likhetsmått används:

1. Termlikhet
2. Dokumentöverlapp
3. Termer kombinerat med dokumentöverlapp
4. Termer kombinerat med dokumentkategorier

Resultaten jämförs genom att titta på antal kluster och andel klustrade sessioner, med varierande likhetskrav.

Kvalitet

Kvalitetsutvärderingen sker genom att manuellt granska 100 slumpmässigt utvalda kluster.

Resultat

Resultaten påvisar fördelar med kombinationsmåt, särskilt gällande kvalitet. Kombinationsmåtten ger fler kluster och större andel klustrade sessioner, men karar inte lika höga likhetskrav som de enkla måtten.

Relevans för oss

Frågeställningarna är i stor utsträckning samma som vi ställs inför, men svaren inte alltid riktigt lika, förmodligen beroende på skillnader i datakvalitet.

Vi skulle inte kunna använda sessioner bestående av bara en söksträng och eventuella klick, de skulle bli för små och omöjliga att klustra. Jag tror inte heller att det är så internetanvändare använder en sökmotor, jag tror mer på modellen med flera sammanhängande frågor i jakt på information (Om det inte är en navigationssökning, men då är det ändå ointressant).

Vi har inte lika välformade dokument i klicklistorna och inga kategorier för dokumenten. Internet är väldigt stort och betydligt spretigare än Encarta och vi har bara tillgång till de domäner klicken leder till, inte exakta dokument. Våra metoder blir därför betydligt trubbigare.

Jag upplever att 20 000 sessioner är en ganska liten mängd att göra klustringar på, med det kan bero på att sökningar på Encarta är mer likriktade och möjliga dokument betydligt färre. De får förmodligen betydligt större överlapp även på små mängder sessioner.

Utvärderingsmetoderna är klart intressanta för oss när vi kommer dit förutsatt att vi inte själva kommer på något bättre. Kvalitetsmått genom manuell granskning av 100 kluster känns lite skakigt.

Som Eskil har skrivit om tidigare så är det problematiskt att välja parametrar i DBScan. Resultatet blir oftast antingen att en majoritet av sessionenrna blir markerade som “outliers” eller att ett dominerande kluster sväljer nästan alla sessioner. För att komma åt den här problematiken har vi valt att angripa vår datamängd med en rekursiv implementation av DBScan. Vi utgår från en DBScan-klustring med väldigt lågt satt likhetskrav. I de större av de kluster som då uppstår gör vi samma samma typ av klustring igen, men med ett steg hårdare likhetskrav, och så vidare , tills likhetskravet når ett stoppvärde.

Det innebär att de parametrar som nu behöver sättas är startlikhet, stopplikhet och steglängd. Det sker även en utvärdering av klustringarna i varje steg som kan avgöra om man borde avbryta rekursionen innan stopplikheten är uppnådd, t.ex. på grund av klustrens storlek.

Resultaten ser hittills lovande ut. Ännu är ngen formell utvärdering utförd, men en stor andel av sessionerna klustras, och inget kluster blir så stort att det blir meningslöst. Ett exempel finns här.

Parallellt har Eskil utvecklat en klassifikation av sessioner så att vi kan slänga bort en stor del av de “navigational”-sessioner som vi är ganska ointresserade av. Men förhoppningsvis mer om det senare.