<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
Step2:  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 &lt;COMPLETAR&gt;.
 Nesse notebook
Step4:  Parte 1
Step5:  (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.
Step6:  (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()
Step7:  Parte 2
Step8:  (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$.
Step9:  Part 3
Step10:  (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.
Step13:  (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
<ASSISTANT_TASK:>
Python Code:
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])
Explanation: 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 &lt;COMPLETAR&gt;.
 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".
End of explanation
# 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]
# 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!'
Explanation: 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.
End of explanation
# EXERCICIO
from pyspark.mllib.feature import Word2Vec
model = Word2Vec().<COMPLETAR>
print model.transform(u'entertaining')
print model.findSynonyms(u'entertaining', 2)
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!'
Explanation: (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.
End of explanation
# 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
# 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!'
Explanation: (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()
End of explanation
# 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))
# 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'
Explanation: 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$.
End of explanation
# 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)
# TEST Implement a TF function (2a)
assert quantRDD.take(1)[0][1].sum() == 5, 'valores incorretos'
print 'ok!'
Explanation: (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$.
End of explanation
dataNorms = quantRDD.map(lambda rec: (rec[0],np.sqrt(rec[1].dot(rec[1]))))
dataNormsBroadcast = sc.broadcast(dataNorms.collectAsMap())
Explanation: 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.
End of explanation
# 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
assert newcount==11796442, 'incorrect value'
print 'ok'
Explanation: (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.
End of explanation
# 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)
print dataRDD.filter(lambda x: x[0] in [55300,39009,130973,66284]).collect()
Explanation: (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
End of explanation
<END_TASK>