Add Feature
Choose from the Features:
OK CANCEL
Settings
Set Up the Feature Balance:
OK CANCEL
Profile
OK
Dokumentation

Einf├╝hrung

Das Projekt TweetRank ist im Rahmen des Hauptseminars "Data Science" an der Ludwig-Maximilians-Universität (LMU) im Wintersemester 2015/16 entstanden.

Ein kurzer Auszug der Seminarbeschreibung:

Data Science is the extraction of knowledge from large volumes of data that are structured or unstructured, which is a continuation of the field data mining and predictive analytics, also known as knowledge discovery and data mining (KDD). This seminar aims at providing hands-on experience in this area of research, focusing on social media analysis, especially microblogging platforms.

Im Fall von Twitter gibt es noch zahlreiche Problemfelder die noch nicht erschlossen sind. Die über 300 Millionen Nutzern gernerieren auf Twitter täglich eine unglaubliche Menge an Daten; in Zahlen sind das etwa 500 Mio. Tweets.
Diese Tweets enthalten neben ihrer eigentlichlichen Nachricht und den Namen des Nutzers, welcher diesen Tweet abgesetzt hat, noch weit mehr Informationen in Form von Meta-Daten. So werden beispielsweise auch die Retweet- oder Reply-Relations gespeichert, die Geo-Informationen und weitere Angaben.

Hierdurch eignet sich Twitter hervoragend als Kandidat für die Erschließung verschiedener Problemstellungen die im Zusammenhang mit dem Thema Big Data stehen.

Motivation

Die Idee für das Projekt TweetRank resultierte aus dem Problem heraus die Informationsflut - welche man als Nutzer jedes mal bewältigen muss - so zu reduzieren, dass man sich schnell einen Überblick über die wichtigsten Tweets verschaffen kann - selbst wenn man mal mehrere Stunden oder Tage nicht auf Twitter aktiv war.

Ziel

Am Ende des Seminars sollte ein Webportal entwickelt sein, auf welchem man sich mit verschiedenen Features eine möglichst perfekte Ordnung seiner neuesten Tweets erreicht. Ein Feature stellt dabei eine Sortierfunktion dar, nach welcher die Tweets sortiert und bewertet werden. Durch die Kombination verschiedener solcher Features können am Ende individuelle Sortierprioritäten festgelegt werden.

TweetRank

Dataset

Das Projekt stützt sich auf ein Datenset von 413.000 Tweets.

Dabei wurde als Beispielnutzer das offizielle Barack Obama Profil und etwa 3.000 seiner Twitter Freunde berücksichtigt. Ein Twitter Freund von Barack Obama stellt in unserem Fall Nutzer dar, welche dem Profil von Barack Obama folgen und gleichzeitig von Barack Obama gefolgt werden.

Search API

def TCU(user_name):

""" Returns a collection of the most recent Tweets posted by the user indicated by the screen_name or user_id parameters.

"""

  # load  API credentials

  config = {'consumer_key':'setConsumerKay',

              'consumer_secret':'setConsumerSecret',

              'access_key':'setAccessKey',

              'access_secret':'setAccessSecret'}

  # create twitter API object

  twitter = Twitter(auth = OAuth(config["access_key"],

                                 config["access_secret"],

                                 config["consumer_key"],

                                 config["consumer_secret"]))

  results = twitter.statuses.user_timeline(screen_name = user_name, count=1000)

  UserInfo = dict()

  UserTweets = dict()

  for i, status in enumerate(results):

      TweetInfo = {"tweet_id":status["id"],

                   "text":status["text"],

                   "retweet_count":status["retweet_count"],

                   "created_at":status["created_at"],

                   "in_reply":status["in_reply_to_user_id"],

                  "reply_s":status["in_reply_to_user_id_str"]}

                

      UserTweets[ i ] = TweetInfo

      UserStats = {"user_id":status["user"]['id'],

                   "follow":status["user"]["followers_count"],

                   "friends":status["user"]["friends_count"],

                   "location":status["user"]["location"],

                   "img":status["user"]["profile_image_url"],

                   "name":status["user"]["name"]}

                

    UserInfo[user_name] = {"user_stats":UserStats, "user_tweets":UserTweets}


 

def TCUF(user_name):

  ''' Loading information about friends of a given user (username)

  '''

  # load  API credentials 

  config = {'consumer_key':'setConsumerKey',

            'consumer_secret':'set ConsumerSecret',

            'access_key':'setAccsessKey',

            'access_secret':'setAccessSecret'}

  # create twitter API object

  twitter = Twitter(auth = OAuth(config["access_key"], 

                                 config["access_secret"], 

                                 config["consumer_key"], 

                                 config["consumer_secret"]))    

  screen_names = []

  query = twitter.friends.ids(screen_name = user_name)

  return query

Filter

Features oder Filter stellen die jeweiligen Sortierfunktionen dar, welche im Rahmen des Projektes implementiert wurden.

Jedes Feature errechnet pro Tweet einen RankingValue welcher als Vergleichswert dient um unterschiedliche Features zu kombinieren und zu gewichten.

Text Similarity

Das Text Similarity Feature berechnet sich aus den textuellen Ähnlichkeiten der Tweets zueinander. Die Motivation hinter diesem Feature ist, dass ein Tweet, der vielen anderen Tweets ähnlich ist, inhaltlich gesehen ein zentrales Thema behandelt.

Die Idee für dieses Feature stammt aus (Erkan & Radev, 2004). Dieses Paper stellt ein System zur Zusammenfassung von natürlichsprachigen Texten namens LexRank vor. LexRank repräsentiert Texte als Graphen, in denen Sätze als Knoten und deren Ähnlichkeiten untereinander als Kantengewichte dargestellt werden. Durch Anwendung von PageRank auf diesen vollständigen Graphen wird dann ein Ranking von Sätzen berechnet.

Zur Ermittlung der Satzähnlichkeiten kann eine beliebige Metrik zum Einsatz kommen, die die Ähnlichkeit zweier beliebiger Sätze zueinander quantifiziert. Im Kontext von TweetRank kam der Jaccard-Koeffizient zum Einsatz, der in vielen Bereichen zur Berechnung der Ähnlichkeit zweier Mengen verwendet wird. Im Bereich des Natural Language Processing werden Sätze in vielen Anwendungen als Mengen von Wörtern verstanden und daher kann auch hier der Jaccard-Koeffizient verwendet werden.

Zur Berechnung des PageRanks über den Satzgraphen wurde die Python-Bibliothek networkx verwendet. Eine Implementierung des in TweetRank verwendeten Text Similarity Features kann in folgendem Github-Repository betrachtet werden: https://github.com/sir-sure-e-nuff/TweetRank

Reply Relation

Dem Reply Relation Feature liegt die Reply-Beziehung zwischen Tweets zugrunde. Wie beim Text Similarity Feature wird auch hier ein Graph erzeugt, wobei die Knoten wieder für Tweets stehen, die Kanten aber diesmal gerichtet sind und ausdrücken, ob ein Tweet T1 ein Reply auf einen anderen Tweet T2 ist. In diesem Fall wird in den Graphen eine gerichtete Kante von T1 zu T2 eingefügt.

Aus algorithmischer Sicht ist das Reply Relation Feature identisch mit dem Text Similarity Feature: Auf den Tweet-Graphen wird auch hier PageRank angewendet. Eine Implementierung des Reply Relation Features kann im oben genannten Github-Repository begutachtet werden.

Hashtag User Similarity

Die Idee hinter dem Hashtag Similarity Filter ist, dass die User mit ähnlichen Hashtags höchstwahrscheinlich auch ähnliche Interessen haben. 

Wenn ein User sich z.B. für Data Science interessiert und oft zu Hashtags wie #DataScience#MachineLearning oder #NIPS postet, dann ist für ihn der User mit den Hashtags #DeepLearning und #Conference interessanter und relevanter als der User mit den Hashtags #Travelling und #Adventures.

In dem Projekt wurde der Twitter Account von Barack Obama und seiner Twitter-Freunde untersucht, ob sie mit ihm gleiche/ähnliche Hashtags haben. Falls das zutraf, dann wurde für jeden User und seine Hashtag die Gewichte berechnet, indem man die Anzahl der Tweets mit den entsprechenden Hashtags durch die Anzahl aller Tweets des Users teilt. Dadurch erhält man für jeden User einen Vektor mit den Hashtag Gewichten. Durch ein Ähnlichkeitsmaß (L2-Norm) wurden anschließend die Ähnlichkeit eines Users zu Barack Obama bestimmt. Die User die am ähnlichsten zu Barack Obama sind, werden bei der Sortierung höher gestuft.

# Reading data

files = os.listdir('user_data/')


 

def hashtag_extraction( data ):

''' Preprocessing tweets and extracting hashtags

Returns: list with all hashtags

'''

    user_name = data.keys()[0] # first entry is user_name

    hashtags = []

    for k, v in data[user_name]['user_tweets'].iteritems():

        t = v['text']

        if '#' in t:

            tokens = t.split(' ')

            for token in tokens:

                if token.startswith('#'):

                    for p in string.punctuations:

                        if p in token:

                            token = token.replace(str(p), '')

                    hashtags.append( token )


 

# Reading Barack Obama Tweets -> Extract Most Common Hashtags

for i, f in enumerate(files):

    if "BarackObama" in f:

        print i, f

        ObamaNumber = i

with open('user_data/'+files[ ObamaNumber ], 'r') as f:

    data = json.load( f ) 

 

ObamaTweetsCount = len(data['@BarackObama']['user_tweets'])

MostCommonHashtags = hashtag_extraction( data )

ObamaHashtagCount = dict()

 

# Computing weights for each hashtag

for obama_hashtag, hashtag_count in sorted(MostCommonHashtags.iteritems()):

    ObamaHashtagCount[ obama_hashtag ] = float(hashtag_count) / ObamaTweetsCount

Obama_Vector = ObamaHashtagCount.values()


 

#  Extracting Barack Obama's Friends Hashtags

UserHashtags = dict()

UserCountTweets = dict()

for i, f in enumerate(files):

    if not "BarackObama" in f:

        with open('user_data/' + f, 'r') as f:

            d = json.load( f )

        friend = d.keys()[0]

        len_tw = len(d[ friend ]['user_tweets'])

        UserCountTweets[ friend ] = len_tw

        MCH = hashtag_extraction( d )

        if MCH:

            UserHashtags[ friend ] = MCH

 

# Define relevant users ( users with commont interests)

UserOfInterest = dict()

for user, inner_dict in sorted(UserHashtags.iteritems()):

    for k, v in sorted(inner_dict.iteritems(), key=lambda (k, v):(v, k), reverse=True):

        if k in MostCommonHashtags.keys():

            try:

                UserOfInterest[user] += v

            except:

                UserOfInterest[user] = v

 

UserOfInterestHashtagCount = dict()

for user in sorted(UserOfInterest.keys()):

# we do not observe users with _OFA prefix, because the are just news pages and retweet Obamas tweets

    if not 'OFA' in user:

        D = UserCountTweets[ user ]

        UserOfInterestHashtagCount[ user ] = dict()

        for MCH in MostCommonHashtags.keys():

            UserOfInterestHashtagCount[ user ][ MCH ] = 0

        for user_hashtag, hashtag_count in UserHashtags[user].iteritems():

            if user_hashtag in MostCommonHashtags.keys():

                UserOfInterestHashtagCount[ user ][ user_hashtag ] = float(hashtag_count) / D


 

# Computing similarity between BO and user with l2 norm

UHR_ltwo = dict()

for user, r in UserOfInterestHashtagCount.iteritems():

    User_Vector = r.values()

    ltwo = pairwise_distances(Obama_Vector, User_Vector, metric='l2')

    UHR_ltwo[ user ] = ltwo[0][0]


 

# Ranking users

RankResults = dict()

for user, score in sorted(UHR_ltwo.iteritems(), key=lambda (k, v):(v, k), reverse=False ):

    RankResults[ score ] = user

Retweet Count Relation

Die Retweet Count Relation sortiert die Tweets anhand der Häufigkeit, wie oft ein Tweet retweeted wurde.
Tweets welche häufig retweeted wurden, gelten dabei als interessanter als Tweets welche kaum oder gar nicht retweeted wurden.

Der Vergleichwert (RankingValue) ergibt sich dabei aus der relativen Anzahl von Retweets pro Tweet im Verhältnis zu dem Tweet mit den häufigsten Retweets (im gewählten Zeitraum).

// (Array) Liste aller Tweets im gewählten Zeitraum
$list_tweets;

// (Int) Maximale Retweet Anzahl im gewählten Zeitraum
$max_retweet_count;

foreach($list_tweets as $tweet)
   $rel_val = $tweet->retweet_count * 100 / $max_retweet_count;

Technologien

Folgende Technologien wurden eingesetzt:

Laufzeitumgebung
DebianApache Server 

Frontend
Frontend

Backend
Python

Datenbank
MySQL

Ausblick

Das Projekt hat gezeigt, dass man mittels der Kombination verschiedener Features sehr gute Resultate erzielen kann bzgl. der Reihenfolgen-Qualität der letzten Tweets.

Als Ausblick wäre es daher interessant zu sehen, wie weit man die Qualität zusätzlich verbessern kann wenn man noch weitere Features hinzufügt. Zudem wäre eine Studie sehr interessant um zu ermitteln ob verschiedene User mit unterschiedlichen Interessen ähnliche oder gleiche Feature-Kombinationen wählen um die für sie beste Sortierung zu erhalten sodass man möglicherweise eine Generalisierung anstreben kann und weitere Aussagen bzgl. der Features treffen kann.

Downloads

Finale Präsentation: TweetRank Data Science Final.pdf

Zwischenpräsentation: Paper Presentation.pdf

OK