Lab 5b - k-Means para Quantização de Atributos

Os algoritmos de agrupamento de dados, além de serem utilizados em análise exploratória para extrair padrões de similaridade entre os objetos, pode ser utilizado para compactar o espaço de dados.

Neste notebook vamos utilizar nossa base de dados de Sentiment Movie Reviews para os experimentos. Primeiro iremos utilizar a técnica word2vec que aprende uma transformação dos tokens de uma base em um vetor de atributos. Em seguida, utilizaremos o algoritmo k-Means para compactar a informação desses atributos e projetar cada objeto em um espaço de atributos de tamanho fixo.

As células-exercícios iniciam com o comentário # EXERCICIO e os códigos a serem completados estão marcados pelos comentários <COMPLETAR>.

Nesse notebook:

Parte 1: Word2Vec

Parte 2: k-Means para quantizar os atributos

Parte 3: Aplicando um k-NN

Parte 0: Preliminares

Para este notebook utilizaremos a base de dados Movie Reviews que será utilizada para o segundo projeto.

A base de dados tem os campos separados por '\t' e o seguinte formato:

"id da frase","id da sentença","Frase","Sentimento"

Para esse laboratório utilizaremos apenas o campo "Frase".


In [ ]:
import os
import numpy as np

def parseRDD(point):
    """ Parser for the current dataset. It receives a data point and return
        a sentence (third field).
    Args:
        point (str): input data point
    Returns:
        str: a string
    """    
    data = point.split('\t')
    return (int(data[0]),data[2])

def notempty(point):
    """ Returns whether the point string is not empty
    Args:
        point (str): input string
    Returns:
        bool: True if it is not empty
    """   
    return len(point[1])>0

filename = os.path.join("Data","Aula04","MovieReviews2.tsv")
rawRDD = sc.textFile(filename,100)
header = rawRDD.take(1)[0]

dataRDD = (rawRDD
           #.sample(False, 0.1, seed=42)
           .filter(lambda x: x!=header)
           .map(parseRDD)
           .filter(notempty)
           #.sample( False, 0.1, 42 )
           )

print 'Read {} lines'.format(dataRDD.count())
print 'Sample line: {}'.format(dataRDD.takeSample(False, 1)[0])

Parte 1: Word2Vec

A técnica word2vec aprende através de uma rede neural semântica uma representação vetorial de cada token em um corpus de tal forma que palavras semanticamente similares sejam similares na representação vetorial.

O PySpark contém uma implementação dessa técnica, para aplicá-la basta passar um RDD em que cada objeto representa um documento e cada documento é representado por uma lista de tokens na ordem em que aparecem originalmente no corpus. Após o processo de treinamento, podemos transformar um token utilizando o método transform para transformar cada token em uma representaçã vetorial.

Nesse ponto, cada objeto de nossa base será representada por uma matriz de tamanho variável.

(1a) Gerando RDD de tokens

Utilize a função de tokenização tokenize do Lab4d para gerar uma RDD wordsRDD contendo listas de tokens da nossa base original.


In [ ]:
# EXERCICIO
import re

split_regex = r'\W+'

stopfile = os.path.join("Data","Aula04","stopwords.txt")
stopwords = set(sc.textFile(stopfile).collect())

def tokenize(string):
    """ An implementation of input string tokenization that excludes stopwords
    Args:
        string (str): input string
    Returns:
        list: a list of tokens without stopwords
    """
    return <COMPLETAR>

wordsRDD = dataRDD.map(lambda x: tokenize(x[1]))

print wordsRDD.take(1)[0]

In [ ]:
# TEST Tokenize a String (1a)
assert wordsRDD.take(1)[0]==[u'quiet', u'introspective', u'entertaining', u'independent', u'worth', u'seeking'], 'lista incorreta!'
print 'ok!'

(1b) Aplicando transformação word2vec

Crie um modelo word2vec aplicando o método fit na RDD criada no exercício anterior.

Para aplicar esse método deve ser fazer um pipeline de métodos, primeiro executando Word2Vec(), em seguida aplicando o método setVectorSize() com o tamanho que queremos para nosso vetor (utilize tamanho 5), seguido de setSeed() para a semente aleatória, em caso de experimentos controlados (utilizaremos 42) e, finalmente, fit() com nossa wordsRDD como parâmetro.


In [ ]:
# EXERCICIO
from pyspark.mllib.feature import Word2Vec

model = Word2Vec().<COMPLETAR>

print model.transform(u'entertaining')
print model.findSynonyms(u'entertaining', 2)

In [ ]:
dist = np.abs(model.transform(u'entertaining')-np.array([-0.246186971664,-0.127226486802,0.0271916668862,0.0112947737798,-0.206053063273])).mean()
assert dist<1e-6, 'valores incorretos'
print 'ok!'
assert model.findSynonyms(u'entertaining', 1)[0][0] == 'affair', 'valores incorretos'
print 'ok!'

(1c) Gerando uma RDD de matrizes

Como primeiro passo, precisamos gerar um dicionário em que a chave são as palavras e o valor é o vetor representativo dessa palavra.

Para isso vamos primeiro gerar uma lista uniqueWords contendo as palavras únicas do RDD words, removendo aquelas que aparecem menos do que 5 vezes $^1$. Em seguida, criaremos um dicionário w2v que a chave é um token e o valor é um np.array do vetor transformado daquele token$^2$.

Finalmente, vamos criar uma RDD chamada vectorsRDD em que cada registro é representado por uma matriz onde cada linha representa uma palavra transformada.

1

Na versão 1.3 do PySpark o modelo Word2Vec utiliza apenas os tokens que aparecem mais do que 5 vezes no corpus, na versão 1.4 isso é parametrizado.

2

Na versão 1.4 do PySpark isso pode ser feito utilizando o método `getVectors()


In [ ]:
# EXERCICIO
uniqueWords = (wordsRDD
               .<COMPLETAR>
               .<COMPLETAR>
               .<COMPLETAR>
               .<COMPLETAR>
               .collect()
               )

print '{} tokens únicos'.format(len(uniqueWords))

w2v = {}
for w in uniqueWords:
    w2v[w] = <COMPLETAR>
w2vb = sc.broadcast(w2v)       
print 'Vetor entertaining: {}'.format( w2v[u'entertaining'])

vectorsRDD = (wordsRDD
              .<COMPLETAR>
             )
recs = vectorsRDD.take(2)
firstRec, secondRec = recs[0], recs[1]
print firstRec.shape, secondRec.shape

In [ ]:
# TEST Tokenizing the small datasets (1c)
assert len(uniqueWords) == 3332,  'valor incorreto'
print 'ok!'

assert np.mean(np.abs(w2v[u'entertaining']-[-0.24618697, -0.12722649,  0.02719167,  0.01129477, -0.20605306]))<1e-6,'valor incorreto'
print 'ok!'

assert secondRec.shape == (10,5)
print 'ok!'

Parte 2: k-Means para quantizar os atributos

Nesse momento é fácil perceber que não podemos aplicar nossas técnicas de aprendizado supervisionado nessa base de dados:

  • #### A regressão logística requer um vetor de tamanho fixo representando cada objeto
  • #### O k-NN necessita uma forma clara de comparação entre dois objetos, que métrica de similaridade devemos aplicar?

Para resolver essa situação, vamos executar uma nova transformação em nossa RDD. Primeiro vamos aproveitar o fato de que dois tokens com significado similar são mapeados em vetores similares, para agrupá-los em um atributo único.

Ao aplicarmos o k-Means nesse conjunto de vetores, podemos criar $k$ pontos representativos e, para cada documento, gerar um histograma de contagem de tokens nos clusters gerados.

(2a) Agrupando os vetores e criando centros representativos

Como primeiro passo vamos gerar um RDD com os valores do dicionário w2v. Em seguida, aplicaremos o algoritmo k-Means com $k = 200$.


In [ ]:
# EXERCICIO
from  pyspark.mllib.clustering import KMeans

vectors2RDD = sc.parallelize(np.array(w2v.values()),1)
print 'Sample vector: {}'.format(vectors2RDD.take(1))

modelK = KMeans.<COMPLETAR>

clustersRDD = vectors2RDD.<COMPLETAR>
print '10 first clusters allocation: {}'.format(clustersRDD.take(10))

In [ ]:
# TEST Amazon record with the most tokens (1d)
assert clustersRDD.take(10)==[134, 126, 209, 221, 401, 485, 197, 269, 296, 265], 'valor incorreto'
print 'ok'

(2b) Transformando matriz de dados em vetores quantizados

O próximo passo consiste em transformar nosso RDD de frases em um RDD de pares (id, vetor quantizado). Para isso vamos criar uma função quantizador que receberá como parâmetros o objeto, o modelo de k-means, o valor de k e o dicionário word2vec.

Para cada ponto, vamos separar o id e aplicar a função tokenize na string. Em seguida, transformamos a lista de tokens em uma matriz word2vec. Finalmente, aplicamos cada vetor dessa matriz no modelo de k-Means, gerando um vetor de tamanho $k$ em que cada posição $i$ indica quantos tokens pertencem ao cluster $i$.


In [ ]:
# EXERCICIO
def quantizador(point, model, k, w2v):
    key = <COMPLETAR>
    words = <COMPLETAR>
    matrix = np.array( <COMPLETAR> )
    features = np.zeros(k)
    for v in matrix:
        c = <COMPLETAR>
        features[c] += 1
    return (key, features)
    
quantRDD = dataRDD.map(lambda x: quantizador(x, modelK, 500, w2v))

print quantRDD.take(1)

In [ ]:
# TEST Implement a TF function (2a)
assert quantRDD.take(1)[0][1].sum() == 5, 'valores incorretos'
print 'ok!'

Part 3: Aplicando k-NN

Nessa parte, vamos testar o algoritmo k-NN para verificar se a base quantizada é capaz de capturar a semelhança entre documentos.

(4a) Pré-calcule a norma dos vetores

Da mesma forma que no Lab 4c, calcule a norma dos vetores de quantRDD.


In [ ]:
dataNorms = quantRDD.map(lambda rec: (rec[0],np.sqrt(rec[1].dot(rec[1]))))
dataNormsBroadcast = sc.broadcast(dataNorms.collectAsMap())

(4b) Calcule a similaridade do cosseno entre pares de registros

Complete a função cosineSim que receberá um par ( (doc1, vec1), (doc2, vec2) ) para calcular a similaridade do cosseno entre esses dois documentos.

  • #### Usando o índice invertido, agrupe a base pela chave (token) e aplique a função genList que deve gerar uma lista de tuplas (token, ((doc1,tfidf),(doc2,tfidf)) de todos os pares de documentos com essa token em comum exceto nos casos doc1==doc2.
  • #### Em seguida, gere tuplas do tipo ( (doc1, doc2), tfidf1tfidf2/(norma1norma2) ) a reduza para realizar a somatória desses valores sob a mesma chave.

Dessa forma teremos os registros de pares de documentos que possuem similaridade não nula com sua similaridade calculada.


In [ ]:
# EXERCICIO
from itertools import product

def calcsim(rec):
    items = list(rec[1])
    return <COMPLETAR>
    
newRDD = (quantRDD
          .<COMPLETAR>
          .<COMPLETAR>
          .<COMPLETAR>
          .<COMPLETAR>
          .<COMPLETAR>
          .cache()
          )

newcount = newRDD.count()
print newcount

In [ ]:
assert newcount==11796442, 'incorrect value'
print 'ok'

(4f) k-NN

Vamos gerar agora a lista dos k documentos mais similares de cada documento.

  • #### Gere uma RDD partindo da commonTokens de tal forma a ter ( id1, (id2, sim) )
  • #### Agrupe pela chave e transforme a RDD para ( id1, [ (id,sim) ] ) onde a lista deve ter k elementos

In [ ]:
# EXERCICIO
def genklist(rec,k):
    """ Generate the list of the k most similar documents to the key
    Args:
        record: a pair, (doc, [(doc,sim)])
        k: number of most similar elements
    Returns:
        pair: (doc, [(doc,sim)])
    """
    <COMPLETAR>
    return (key, docs[:k])
    
def knn(simRDD, k):
    """ Generate the knn RDD for a given RDD.
    Args:
        simRDD: RDD of ( (doc1,doc2), sim)
        k: number of most similar elements
    Returns:
        RDD: RDD of ( doc1, [docs, sims])
    """

    ksimRDD = (simRDD
               .<COMPLETAR>
               .<COMPLETAR>
               .<COMPLETAR>
              )
    return ksimRDD

ksimReviewsRDD = knn(newRDD, 3)
ksimReviewsRDD.take(3)

In [ ]:
print dataRDD.filter(lambda x: x[0] in [55300,39009,130973,66284]).collect()