import json import math import string from collections import OrderedDict import itertools import logging logger = logging.getLogger(__name__) hdlr = logging.FileHandler('analysis.log') formatter = logging.Formatter('%(levelname)s %(message)s') hdlr.setFormatter(formatter) logger.addHandler(hdlr) logger.setLevel(logging.WARNING) def normalize_tag_term(tag, exclude_punctuation=False): """a little naive in stripping all punctuation. stemming would deal with sementically identical syntax variations: electronic, electronica, electro""" tag = tag.strip().lower() if exclude_punctuation: tag = tag.translate(dict.fromkeys(map(ord, string.punctuation))) return tag def load_tags_data(raw_tags_stream): artist_artist_id = OrderedDict() # artists -> artist_id tag_tag_id = OrderedDict() # tags -> artist_id artist_tags = dict() # artist_id -> {tag} tag_artists = dict() # tag -> {artist_id} tag_artist_count = dict() # tag -> artist_id -> count # load data for line in raw_tags_stream: # decode json tags = json.loads(line) try: top_tags = tags['toptags'] except KeyError: logger.warn('artist not found: %s:', tags) # artists (documents) store only unique artists try: artist = top_tags['@attr']['artist'] except KeyError: logger.warn('no tags for artist: %s', top_tags['artist']) artist = top_tags['artist'] top_tags['tag'] = [] artist_id = artist_artist_id.setdefault(artist, len(artist_artist_id)) # tag name and count (terms and frequency) raw_tags = top_tags['tag'] raw_tags = raw_tags if isinstance(raw_tags, list) else [raw_tags] for raw_tag in raw_tags: tag = normalize_tag_term(raw_tag['name']) # skip empty tags if not tag: logger.warn('skipping empty tag [raw: "%s"]', raw_tag['name']) continue # store only unique tags tag_id = tag_tag_id.setdefault(tag, len(tag_tag_id)) # store tag counts for each artist count = int(raw_tag['count']) tag_artist_count.setdefault(tag_id, dict())[artist_id] = count # store artist tag sets artist_tags.setdefault(artist_id, set()).add(tag_id) # store tag artist sets tag_artists.setdefault(tag_id, set()).add(artist_id) return (artist_artist_id, tag_tag_id, artist_tags, tag_artists, tag_artist_count) # ##### local tag (term) weight [ normalized term frequency ] # looks like they've already normalized local weights 'count' is always between # 0-100 zero-based nature of that normalization may cause issues with rest of # the analysis might be worth experinenting and normalizing it further with log def build_local_tag_weights(tag_artist_count): ret = dict() for tag, artist_count in tag_artist_count.iteritems(): for artist, count in artist_count.iteritems(): ret.setdefault(tag, dict())[artist] = (math.lgamma(count + 1) + .1) # ret.setdefault(tag, dict())[artist] = count + 1 return ret # ##### global tag (term) weight (inverse document frequency) # penalize generic tags def idf(n_docs, n_docs_with_term): return math.log(float(n_docs) / n_docs_with_term) def build_global_tag_weights(n_artists, tag_artists): """returns dict tag -> weight""" ret = dict() for tag, artists in tag_artists.iteritems(): ret[tag] = idf(n_artists, len(artists)) return ret # ##### compensate for document length (artist tag count) differences using # ##### cosine normalization # used to correct discrepancies in document lengths. # E.g. In case of tagging systems, a resource that has been given more tags, # will be favoured if weights are not normalized. # Since it is not always true that a resource that has been given more tags # is more relevant than a resource with lesser number of tags. # Hence, it is useful to normalize the document vectors so that documents are # not favoured based on their lengths. def cos_norm(global_local_tag_weights): return 1. / math.sqrt(sum((gtw * ltw)**2 for gtw, ltw in global_local_tag_weights)) def build_normalized_artist_weights(artist_tags, local_tag_weights, global_tag_weights): """returns dict artist_id -> combined_weight""" ret = dict() for artist_id, tags in artist_tags.iteritems(): gtw_ltw = ((global_tag_weights[tag], local_tag_weights[tag][artist_id]) for tag in tags) ret[artist_id] = cos_norm(gtw_ltw) return ret # ##### combined weights (artists and tags) def combined_weight(local_tag_weight, global_tag_weight, normalized_artist_weight): return local_tag_weight * global_tag_weight * normalized_artist_weight def build_combined_weights(tag_artists, local_tag_weights, global_tag_weights, normalized_artist_weights): """return dict tag -> artist -> weight""" ret = dict() for tag, artists in tag_artists.iteritems(): for artist in artists: weight = combined_weight(local_tag_weights[tag][artist], global_tag_weights[tag], normalized_artist_weights[artist]) weight = int(weight * 1e3) if weight: ret.setdefault(tag, dict())[artist] = weight return ret # ##### dice similarities def build_weighted_dice_similarities(tag_artists, combined_weights): n_tags = len(tag_artists) tag_artists = tuple(artists for _, artists in sorted(tag_artists.iteritems())) ret = dict() # weighted dice similarity calc for tag_i in xrange(n_tags): artists_i = tag_artists[tag_i] for tag_j in xrange(tag_i + 1, n_tags): artists_j = tag_artists[tag_j] # common artists; if none, will be zero, hence skip common_artists = artists_i & artists_j if not common_artists: continue # sum of element-wise multiplication of weights for tag_i & tag_j # for common artists; skip zeros sum_common = 0 for common_artist in common_artists: cwi = combined_weights.get(tag_i, {}).get(common_artist, 0) cwj = combined_weights.get(tag_j, {}).get(common_artist, 0) sum_common += cwi * cwj if sum_common == 0: continue # calc weight sums for tag_i and tag_j across all artists sum_i = sum(combined_weights[tag_i].itervalues()) sum_j = sum(combined_weights[tag_j].itervalues()) similarity = sum_common // (sum_i + sum_j) if similarity == 0: continue ret.setdefault(tag_i, dict())[tag_j] = similarity return ret def build_artist_similarties(tag_weights, artist_tags, tag_artist_count): n_artists = len(artist_tags) ret = dict() for artist_i in xrange(n_artists): rd = ret.setdefault(artist_i, dict()) for artist_j in xrange(artist_i + 1, n_artists): sim = 0 if artist_i in artist_tags and artist_j in artist_tags: tags_i = set(artist_tags[artist_i]) tags_j = set(artist_tags[artist_j]) # intersections get a very high score sim += len(tags_i & tags_j) * 100 # disjoints need similarity scores disjoint = tags_i ^ tags_j # remove singles disjoint = {t for t in disjoint if tag_artist_count[t] > 1} for tx, ty in itertools.combinations(sorted(disjoint), 2): if tx in tag_weights and ty in tag_weights[tx]: sim += tag_weights[tx][ty] rd[artist_j] = sim return ret def analyze_tags(raw_tags_stream): artist_artist_id, tag_tag_id, artist_tags, tag_artists, tag_artist_count = \ load_tags_data(raw_tags_stream) import ipdb; ipdb.set_trace() artist_names = tuple(artist_artist_id.iterkeys()) tag_names = tuple(tag_tag_id.iterkeys()) # build weights global_tag_weights = build_global_tag_weights(len(artist_names), tag_artists) local_tag_weights = build_local_tag_weights(tag_artist_count) normalized_artist_weights = build_normalized_artist_weights( artist_tags, local_tag_weights, global_tag_weights) combined_weights = build_combined_weights(tag_artists, local_tag_weights, global_tag_weights, normalized_artist_weights) # build tag similarities weighted_dice_similarities = build_weighted_dice_similarities( tag_artists, combined_weights) # build artist similarities artist_similarities = build_artist_similarties( weighted_dice_similarities, artist_tags, tag_artist_count) return (weighted_dice_similarities, artist_names, tag_names, artist_similarities)