Return to search

A comparison of clustering techniques for short social text messages / En jämförelse av tekniker för klustring av korta sociala textmeddelanden

The amount of social text messages authored each day is huge and the information contained within is potentially very valuable. Software that can cluster and thereby help analyze these messages would consequently be helpful. This thesis explores several ways of clustering social text messages. Two algorithms and several setups with these algorithms have been tested and evaluated with the same data as input. Based on these evaluations, a comparison has been conducted in order to answer the question which algorithm setup is best suited for the task. The two clustering algorithms that have been the main subjects for the comparison are K-means and agglomerative hierarchical. All setups were run with 3-grams as well as with only single words as features. The evaluation measures used were intra-cluster distance, inter-cluster distance and silhouette value. Intra-cluster distance is the distance between data points in the same cluster while inter-cluster is the distance between the clusters. Silhouette value is another more general evaluation measure that is often used to estimate the quality of a clustering. The results showed that if running time is a high priority, using K-means without 3-grams is preferred. On the other hand, if the quality of the clusters is important and performance is less so, introducing 3-grams together with any of the two algorithms will suit your needs better. / Mängden sociala textmeddelanden som skrivs varje dag är enorm och informationen i dessa kan vara mycket värdefull. Mjukvara som kan klustra och på så sätt analysera dessa meddelanden kan därmed vara användbar. Denna avhandling utforskar flera sätt att klustra sociala textmeddelanden. Två algoritmer och flera konfigureringar med dessa algoritmer har testats och utvärderats med samma indata. Baserat på dessa utvärderingar har en jämförelse utförts för att kunna svara på frågan vilken av dessa konfigureringar som är bäst anpassad för sitt syfte. De två klustringsalgoritmerna som i första hand har jämförts är K-means och agglomerative hierarchical. Alla konfigureringar kördes både med och utan 3-gram som komplement till endast enstaka ord. Utvärderingsmetoderna som användes var intra-cluster distance, inter-cluster distance och silhouette value. Intra-cluster distance är avståndet mellan datapunkterna i samma kluster medan inter-cluster distance är avståndet mellan de olika klustrena. Silhouette value är annan, mer generell, utvärderingsmetod som ofta används för att uppskatta kvaliten på en klustring. Resultaten visade att K-means utan 3-gram är att föredra om kravet på körningstid inte är högst prioriterat. Å andra sidan, om kvaliten på klustringen är viktigare än prestandan på algoritmen, så bör 3-gram användas tillsammans med vilken som av de två algoritmerna.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-196735
Date January 2016
CreatorsRanby, Erik
PublisherKTH, Skolan för datavetenskap och kommunikation (CSC)
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageSwedish
TypeStudent thesis, info:eu-repo/semantics/bachelorThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0023 seconds