Upload
ngokhuong
View
218
Download
0
Embed Size (px)
Citation preview
Topicos
1. Pre-Processamento dos Dados
2. Conceitos Basicos
3. Representacao Textual
4. Padroes Recorrentes
5. Padronizando e Normalizando os Atributos
6. Paralelizando o Pre-Processamento
1
Data Sets
Conjunto de objetos de dados.
Objeto de dados e uma entidade:
• funcionario de uma empresa
• medicoes da atividade cerebral em um paciente
• descricao de uma ocorrencia policial
2
Atributos Nominais
Sımbolos ou nomes descritivos:
• Descreve uma caracterıstica
• Nao apresentam relacao de ordem, apenas igualdade
Ex.: ocupacao, cor dos olhos, etc.
5
Atributos Binarios
Atributo nominal com apenas dois valores possıveis: 0 ou 1.
Ex.: resultado de um exame, genero, etc.
6
Atributos Ordinais
Valores que apresentam ordem, mas nao possuem relacao de magnitude.
Ex.: {pessimo, ruim, regular, bom, otimo}
7
Atributos Intervalares
Atributo numerico com relacao de ordem e magnitude.
Ex.: Temperatura de 20◦C e 10 unidades mais quente do que 10◦C .
Nao podemos dizer que 20◦C e duas vezes mais quente do que 10◦C .
8
Atributos Intervalares
O 0 absoluto em Celsius esta em −273.15◦C .
20◦C esta a 293.15 de nenhum calor, o dobro desse calor seria 586.30 ou
313.15◦C .
9
Atributos de Razoes
Atributos numericos com a mesmas propriedades do intervalar, mas com
um ponto-zero.
• Altura
• Contagem de palavras
• Temperatura em Kelvin
10
Representando Objetos
Precisamos de uma representacao numerica.
• Dados numericos: ok! (ou quase sempre ok)
• Dados nominais: vetor binario
• Dados ordinais: rank
11
Representando Objetos
Tabela 1: Base de Dados.
Profissao Conceito Nota
Engenheiro A 9.5
Professor B 8.4
Engenheiro A 7.3
Gerente D 9.1
12
Atributos Categoricos → Binarios
Tabela 2: Base de Dados.
Engenheiro Professor Gerente Conceito Nota
1 0 0 A 9.5
0 1 0 B 8.4
1 0 0 A 7.3
0 0 1 D 9.1
13
Atributos Ordinais → Numericos
# conceitos = 5
Rank: 5, 4, 3, 2, 1
z = (rank−1)#−1
Tabela 3: Base de Dados.
Engenheiro Professor Gerente Conceito Nota
1 0 0 1 9.5
0 1 0 0.75 8.4
1 0 0 1 7.3
0 0 1 0.25 9.1
14
Leitura da Base de Dados
data Profissao = Engenheiro | Professor | Gerente | Estudante
deriving (Show, Read, Eq, Enum, Bounded)
data Conceito = F | D | C | B | A
deriving (Show, Read, Enum)
type Nota = Double
type Objeto = (Profissao, Conceito, Nota)
type Objeto’ = [Double]
15
Leitura da Base de Dados
parseFile :: String -> [Objeto]
parseFile file = map parseLine (lines file)
where
parseLine l = toObj (words l)
toObj [w1, w2, w3] = (read w1 :: Profissao,
read w2 :: Conceito,
read w3 :: Nota)
A funcao words separa uma string em uma lista de strings cortando nos
caracteres de espaco.
16
Leitura da Base de Dados
parseFile :: String -> [Objeto]
parseFile file = map parseLine (lines file)
where
parseLine l = toObj (words l)
toObj [w1, w2, w3] = (read w1 :: Profissao,
read w2 :: Conceito,
read w3 :: Nota)
A funcao words separa uma string em uma lista de strings cortando nos
caracteres de espaco.
16
Leitura da Base de Dados
transformData :: [Objeto] -> [Objeto’]
transformData data = map parseObj data
where
parseObj (prof, conc, nota) = (binariza prof)
++ [rank conc, nota]
17
Leitura da Base de Dados
transformData :: [Objeto] -> [Objeto’]
transformData data = map parseObj data
where
parseObj (prof, conc, nota) = (binariza prof)
++ [rank conc, nota]
17
Leitura da Base de Dados
binariza :: Profissao -> [Double]
binariza p = map bool2double [p == p’ | p’ <- profissoes]
where
profissoes = [minBound..] :: [Profissao]
bool2double True = 1.0
bool2double _ = 0.0
18
Leitura da Base de Dados
binariza :: Profissao -> [Double]
binariza p = map bool2double [p == p’ | p’ <- profissoes]
where
profissoes = [minBound..] :: [Profissao]
bool2double True = 1.0
bool2double _ = 0.0
18
Leitura da Base de Dados
rank :: Conceito -> Double
rank co = (fromEnum’ co) / (fromEnum’ A)
where
fromEnum’ = fromIntegral . fromEnum
19
Leitura da Base de Dados
rank :: Conceito -> Double
rank co = (fromEnum’ co) / (fromEnum’ A)
where
fromEnum’ = fromIntegral . fromEnum
19
Fluxo dos Dados
A leitura e transformacao dos dados segue um fluxo bem definido. E facil
perceber que, enquanto uma linha do arquivo esta sendo processada pela
funcao transformData, outra pode ser processada pela funcao parseFile.
Arquivo parseFile transformData
20
Exercıcio
Classifique os seguintes atributos em Nominal, Binario, Ordinal,
Intervalar, Razao:
Variavel
1. Brilho medido por um medidor de luz
2. Brilho medido pelo julgamento pessoal de uma
pessoa
3. Medalhas de Ouro, Prata e Bronze de uma
competicao
4. Altura acima do nıvel do mar
5. Tipo de moradia (casa, apartamento, mansao,
duplex, cobertura)
6. Hora em um relogio de ponteiros
Resposta
1. Razao
2. Ordinal
3. Ordinal
4. Razao
5. Nominal
6. Intervalar
21
Exercıcio
Classifique os seguintes atributos em Nominal, Binario, Ordinal,
Intervalar, Razao:
Variavel
1. Brilho medido por um medidor de luz
2. Brilho medido pelo julgamento pessoal de uma
pessoa
3. Medalhas de Ouro, Prata e Bronze de uma
competicao
4. Altura acima do nıvel do mar
5. Tipo de moradia (casa, apartamento, mansao,
duplex, cobertura)
6. Hora em um relogio de ponteiros
Resposta
1. Razao
2. Ordinal
3. Ordinal
4. Razao
5. Nominal
6. Intervalar
21
Mineracao de Textos
Documentos de textos:
• Nao possuem representacao vetorial
• Interdependencia dos atributos
• Tamanho variavel
22
Textos como conjuntos
Se representarmos os documentos de textos como o conjunto de suas
palavras:
D1 = ”Estou assistindo a uma aula de Big Data, mas tudo que aprendi
foi Haskell durante a aula!”
D2 = ”Hoje aprendi Haskell na aula, sera que o que aprendi sera util na
minha vida?”
23
Textos como conjuntos
Se representarmos os documentos de textos como o conjunto de suas
palavras:
D1 = {Estou, assistindo, a, uma, aula, de,Big ,Data,mas, tudo, que, aprendi ,
foi ,Haskell , durante, aula!}
D2 = {Hoje, aprendi ,Haskell , na, aula, ser a, que, o, util ,minha, vida?}
24
Textos como conjuntos
Calculando a similaridade de Jaccard, temos:
D1 ∩ D2 = {que, aprendi ,Haskell}
D1 ∪ D2 = {Estou, assistindo, a, uma, aula, de,Big ,Data,mas, tudo, que, aprendi ,
foi ,Haskell , durante, aula!,Hoje, na, aula, ser a, o, util ,minha, vida?}
J(D1,D2) =3
24= 0.125
Essa representacao e conhecida como Bag-of-Words, em que geramos os
atributos do texto como atributos categoricos.
25
Normalizacao do Texto
Pode ser interessante padronizar a forma do texto para termos serem
considerados como um elemento unico do conjunto independente de
como e escrito.
Por exemplo: Estou, estou, esTou, aula!, aula, aula?, util, util.
D1 = {estou, assistindo, a, uma, aula, de, big , data,mas, tudo, que, aprendi ,
foi , haskell , durante, aula}
D2 = {hoje, aprendi , haskell , na, aula, sera, que, o, util ,minha, vida}
J(D1,D2) =4
23= 0.17
26
Eliminacao de atributos irrelevantes
Podemos eliminar palavras que nao apresentam significado sozinhas:
D1 = {estou, assistindo, aula, big , data, tudo, aprendi , haskell , durante, aula}
D2 = {hoje, aprendi , haskell , aula, sera, util ,minha, vida}
J(D1,D2) =4
14= 0.28
27
Bag-of-Words
type Doc = String
type Token = String
bagofwords :: [Doc] -> [[Token]]
bagofwords docs = naoVazio $ map tokeniza docs
where
tokeniza doc = nub
$ filter maisDe2
$ map normaliza (words doc)
normaliza palavra = map toLower
$ filter isAlphaNum
palavra
maisDe2 palavra = (length palavra) > 2
naoVazio xs = filter (not . null) xs
28
Bag-of-Words
type Doc = String
type Token = String
bagofwords :: [Doc] -> [[Token]]
bagofwords docs = naoVazio $ map tokeniza docs
where
tokeniza doc = nub
$ filter maisDe2
$ map normaliza (words doc)
normaliza palavra = map toLower
$ filter isAlphaNum
palavra
maisDe2 palavra = (length palavra) > 2
naoVazio xs = filter (not . null) xs
28
Bag-of-Words
A funcao toLower converte um caractere maiusculo para minusculo, e a
funcao isAlphaNum retorna verdadeiro se o caractere e uma letra do
alfabeto ou um numero.
29
Fluxo dos Dados
O fluxo dos dados pode ser descrito com o seguinte fluxograma:
map tokeniza words map normaliza filter isAlphaNum map toLower
filter maisDe2nubnaoVazio
30
Term-Frequency
Se um termo aparece repetidas vezes em um documento, isso significa
que ele pode ter uma importancia maior do que os outros termos.
No nosso exemplo, a repeticao do termo Haskell indica um dos temas dos
nossos documentos.
31
Term-Frequency
A informacao de frequencia pode ser importante para a representacao de
nossos documentos. Podemos fazer entao:
fn(t, d) =f (t, d)
|d |,
com f (t, d) sendo a frequencia do termo t no documento d e |d | a
quantidade de termos no documento d .
32
Term-Frequency
A ideia para computar os vetores TF e primeiro representar cada
documento como uma lista (token, 1.0) e, em seguida:
• Ordenar essa lista pelo token
• Agrupar os itens com mesmo token
• Somar os valores em cada grupo
• Dividir os valores pelo numero de tokens
33
TF
type Freq = Double
tf :: [Doc] -> [[(Token, Freq)]]
tf docs = naoVazio $ map tokeniza docs
where
tokeniza doc = fn $ map normTupla (words doc)
normTupla w = (normaliza w, 1.0)
34
TF
type Freq = Double
tf :: [Doc] -> [[(Token, Freq)]]
tf docs = naoVazio $ map tokeniza docs
where
tokeniza doc = fn $ map normTupla (words doc)
normTupla w = (normaliza w, 1.0)
34
TF
fn :: [(Token, Double)] -> [(Token, Freq)]
A partir desse momento trabalharemos frequentemente com bases de
dados representadas como listas de tuplas.
Essas tuplas devem ser encaradas como chave e valor, respectivamente.
Para tornar o codigo mais legıvel, vamos definir as funcoes mapByKey,
foldByKey, groupByKey, sortByKey
35
mapByKey
mapByKey aplica a funcao g apenas no valor da tupla, deixando a chave
intacta:
mapByKey g = map (\(k,v) -> (k, g v))
36
foldByKey
foldByKey’ assume uma lista de tuplas chave-valor em que todas as
chaves sao iguais.
Essa funcao aplica foldl1’ apenas nos valores das tuplas, resultando em
uma tupla (k , v) em que k e a chave de todas as tuplas e v o resultado
da operacao fold:
foldByKey’ g = foldl1’ (\(k1,v1) (k2,v2) -> (k1, g v1 v2))
37
sortByKey
sortByKey ordena uma lista de tuplas pela chave:
sortByKey = sortBy ordenaTupla
ordenaTupla :: (Ord a) => (a, t) -> (a, t) -> Ordering
ordenaTupla (a1,b1) (a2,b2)
| a1 < a2 = LT
| a1 > a2 = GT
| a1 == a2 = EQ
38
groupByKey
groupByKey agrupa uma lista ordenada de tuplas gerando uma lista de
listas, com cada lista agrupando as tuplas de mesma chave:
groupByKey = groupBy agrupaTupla
agrupaTupla :: (Eq a) => (a, t0) -> (a, t0) -> Bool
agrupaTupla (a1, b1) (a2, b2) = a1==a2
groupByKey [(1,0.1), (1,0.2), (2,0.1)]
== [ [(1,0.1),(1,0.2)], [2,0.1] ]
39
TF
fn :: [(Token, Double)] -> [(Token, Freq)]
fn tokens = mapByKey (/n)
$ map (foldByKey’ (+))
$ groupByKey
$ sortByKey
tokens
where
n = length’ tokens
40
TF
fn :: [(Token, Double)] -> [(Token, Freq)]
fn tokens = mapByKey (/n)
$ map (foldByKey’ (+))
$ groupByKey
$ sortByKey
tokens
where
n = length’ tokens
40
Fluxo dos Dados
O fluxo dos dados pode ser descrito com o seguinte fluxograma:
map tokeniza words map normaliza sortByKey groupByKey
map foldByKeymapByKey
41
Inverse Document Frequency
Algumas palavras aparecem com uma frequencia muito superior as
demais, como: e, que, ou, etc.
Essas palavras nao costumam apresentar um significado discriminatorio e,
portanto, podem ter um peso menor. Para isso podemos multiplicar o TF
por:
idf (t) = log|D|
|{d ∈ D : t ∈ D}|
42
TF-IDF
Como veremos mais adiante, e possıvel pensar no vetor IDF como uma
matriz associativa. Para isso utilizaremos o HashMap do Haskell.
idf :: [[(Token, Freq)]] -> M.HashMap Token Freq
idf corpus = M.fromList
$ mapByKey (\v -> log (n/v))
$ map (foldByKey’ (+))
$ groupByKey
$ sortByKey
$ map (\ (k,v) -> (k,1))
$ concat corpus
where
n = length’ corpus
43
TF-IDF
Como veremos mais adiante, e possıvel pensar no vetor IDF como uma
matriz associativa. Para isso utilizaremos o HashMap do Haskell.
idf :: [[(Token, Freq)]] -> M.HashMap Token Freq
idf corpus = M.fromList
$ mapByKey (\v -> log (n/v))
$ map (foldByKey’ (+))
$ groupByKey
$ sortByKey
$ map (\ (k,v) -> (k,1))
$ concat corpus
where
n = length’ corpus
43
HashMap
-- importa a biblioteca HashMap.Strict apelidade de M
import qualified Data.HashMap.Strict as M
-- cria um mapa M.HashMap Integer Double da lista de tuplas
mapa = M.fromList [(1, 0.1), (2, 0.3), (3, 0.04)]
mapa M.! 2 -- retorna 0.3
concat [ [1,2], [3,4] ] = [1,2,3,4]
44
TF-IDF
tfidf :: [[(Token, Freq)]]
-> M.HashMap Token Freq
-> [[(Token, Freq)]]
tfidf tf’ idf’ = map multIDF tf’
where
multIDF = mapByKey (\(k,v) -> (k, v * (idf’ M.! k)) )
45
TF-IDF
tfidf :: [[(Token, Freq)]]
-> M.HashMap Token Freq
-> [[(Token, Freq)]]
tfidf tf’ idf’ = map multIDF tf’
where
multIDF = mapByKey (\(k,v) -> (k, v * (idf’ M.! k)) )
45
Fluxo dos Dados
O fluxo dos dados pode ser descrito com o seguinte fluxograma:
map multIDF mapByKey concat map sortByKey
groupByKeymap foldByKeymapByKeyfromList
46
Exercıcio
Dada as tabelas abaixo, calcule a similaridade de cosseno entre os
documentos 1 e 2 com a representacao tf e tf-idf:
A B C D
D1 30 5 0 1
D2 60 0 4 10
D3 10 2 0 0
D4 40 0 4 8
47
Exercıcio
tf A B C D
D1 0.83 0.14 0.00 0.03
D2 0.81 0.00 0.05 0.13
D3 0.6 0.4 0.00 0.00
D4 0.77 0.00 0.08 0.15
idf = [0.00, 0.69, 0.69, 0.29]
tf-idf A B C D
D1 0.00 0.10 0.00 0.01
D2 0.00 0.00 0.04 0.04
D3 0.00 0.28 0.00 0.00
D4 0.00 0.00 0.05 0.04
dtf = [1.40, 1.49, 1.45]
dtfidf = [11.42, 37.21, 7.89]
48
Padroes de sequencia de funcoes
Nos exemplos anteriores, podemos perceber um padrao recorrente de
chamada de funcoes utilizadas em diversas solucoes:
map (foldByKey’ (+)) $ groupByKey $ sortByKey
Esse padrao precede a chamada de uma funcao map que transforma um
valor em uma tupla chave-valor (k , v).
49
Padroes de sequencia de funcoes
Basicamente esse padrao combina os valores das tuplas com a mesma
chave utilizando uma funcao (nos exemplos utilizamos (+)). E
interessante, entao, criar a funcao:
combine :: Ord k
=> (v -> v -> v) -> [(k, v)] -> [(k, v)]
combine f xs = map (foldByKey’ f) $ groupByKey $ sortByKey xs
Com isso, muitas funcoes se tornam sequencias de combine . map.
50
fn
fn :: [(Token, Double)] -> [(Token, Freq)]
fn tokens = mapByKey (/n)
$ combine (+)
tokens
where
n = length’ tokens
51
fn
fn :: [(Token, Double)] -> [(Token, Freq)]
fn tokens = mapByKey (/n)
$ combine (+)
tokens
where
n = length’ tokens
51
idf
Como veremos mais adiante, e possıvel pensar no vetor IDF como uma
matriz associativa. Para isso utilizaremos o HashMap do Haskell.
idf :: [[(Token, Freq)]] -> M.HashMap Token Freq
idf corpus = M.fromList
$ mapByKey (\v -> log (n/v))
$ combine (+)
$ mapByKey (\v -> 1)
$ concat corpus
where
n = length’ corpus
52
idf
Como veremos mais adiante, e possıvel pensar no vetor IDF como uma
matriz associativa. Para isso utilizaremos o HashMap do Haskell.
idf :: [[(Token, Freq)]] -> M.HashMap Token Freq
idf corpus = M.fromList
$ mapByKey (\v -> log (n/v))
$ combine (+)
$ mapByKey (\v -> 1)
$ concat corpus
where
n = length’ corpus
52
Padronizacao
Muitos algoritmos de Aprendizado de Maquina supoem que os valores
dos atributos seguem N(0, 1).
Se um atributo nao segue esse padrao, pode dominar a funcao-objetivo e
se tornar importante demais.
53
Padronizacao
Dado uma matriz de dados X , podemos padronizar os valores de cada
um de seus elementos como:
Xi,j =Xi,j − Xi,j
σj
54
Padronizacao
padroniza :: [[Double]] -> [[Double]]
padroniza x = mapColunas padroniza’ x
padroniza’ :: [Double] -> [Double]
padroniza’ x = devMedia ./ sigma
where
media xs = (sum xs) / n
devMedia = x .- (media x)
sigma = sqrt $ media $ devMedia .** 2
n = length’ x
55
Padronizacao
padroniza :: [[Double]] -> [[Double]]
padroniza x = mapColunas padroniza’ x
padroniza’ :: [Double] -> [Double]
padroniza’ x = devMedia ./ sigma
where
media xs = (sum xs) / n
devMedia = x .- (media x)
sigma = sqrt $ media $ devMedia .** 2
n = length’ x
55
Padronizacao
padroniza :: [[Double]] -> [[Double]]
padroniza x = mapColunas padroniza’ x
padroniza’ :: [Double] -> [Double]
padroniza’ x = devMedia ./ sigma
where
media xs = (sum xs) / n
devMedia = x .- (media x)
sigma = sqrt $ media $ devMedia .** 2
n = length’ x
55
Padronizacao
padroniza :: [[Double]] -> [[Double]]
padroniza x = mapColunas padroniza’ x
padroniza’ :: [Double] -> [Double]
padroniza’ x = devMedia ./ sigma
where
media xs = (sum xs) / n
devMedia = x .- (media x)
sigma = sqrt $ media $ devMedia .** 2
n = length’ x
55
Fluxo dos Dados
O fluxo dos dados pode ser descrito com o seguinte fluxograma:
mapColunas padroniza’ media devMedia ./ .** 2
media
56
Escalonamento
Algoritmos baseados em metodos de gradiente tendem a se beneficiar
quando os atributos estao entre [0, 1].
Xi,j =Xi,j −minX:,j
maxX:,j −minX:,j
57
Padronizacao
maxminScale :: [[Double]] -> [[Double]]
maxminScale x = mapColunas maxminScale’ x
maxminScale’ :: [Double] -> [Double]
maxminScale’ x = map scale x
where
scale xi = (xi - minimum x) / (maximum x - minimum x)
58
Padronizacao
maxminScale :: [[Double]] -> [[Double]]
maxminScale x = mapColunas maxminScale’ x
maxminScale’ :: [Double] -> [Double]
maxminScale’ x = map scale x
where
scale xi = (xi - minimum x) / (maximum x - minimum x)
58
Padronizacao
maxminScale :: [[Double]] -> [[Double]]
maxminScale x = mapColunas maxminScale’ x
maxminScale’ :: [Double] -> [Double]
maxminScale’ x = map scale x
where
scale xi = (xi - minimum x) / (maximum x - minimum x)
58
Padronizacao
maxminScale :: [[Double]] -> [[Double]]
maxminScale x = mapColunas maxminScale’ x
maxminScale’ :: [Double] -> [Double]
maxminScale’ x = map scale x
where
scale xi = (xi - minimum x) / (maximum x - minimum x)
58
Normalizacao
Finalmente podemos normalizar cada amostra da base utilizando a
normalizacao de vetores:
Xi,j =Xi,j
‖Xi‖p
59
Padronizacao
normaliza :: [[Double]] -> [[Double]]
normaliza x = map normaliza’ x
where
normaliza’ xi = xi ./ (norma xi)
norma xi = sqrt . sum $ xi .^ 2
60
Padronizacao
normaliza :: [[Double]] -> [[Double]]
normaliza x = map normaliza’ x
where
normaliza’ xi = xi ./ (norma xi)
norma xi = sqrt . sum $ xi .^ 2
60
Exercıcio
Calcule o vetor padronizado, normalizado e escalonado de
[1, 3, 2, 5, 4, 6, 3]
vp = [−1.4,−0.25,−0.83, 0.91, 0.33, 1.50,−0.25]
vn = [0.1, 0.3, 0.2, 0.5, 0.4, 0.6, 0.3]
ve = [0, 0.4, 0.2, 0.8, 0.6, 1, 0.4]
61
Exercıcio
Calcule o vetor padronizado, normalizado e escalonado de
[1, 3, 2, 5, 4, 6, 3]
vp = [−1.4,−0.25,−0.83, 0.91, 0.33, 1.50,−0.25]
vn = [0.1, 0.3, 0.2, 0.5, 0.4, 0.6, 0.3]
ve = [0, 0.4, 0.2, 0.8, 0.6, 1, 0.4]
61
Paralelizando chunks
Conforme vimos na aula anterior, ao paralelizar um programa
objetivamos minimizar o numero de sparks e tentar distribuir a tarefa de
forma homogenea entre as threads.
62
Paralelizando chunks
Para isso adotamos a estrategia de dividir nossos dados em pedacos
(denominados chunks), processar cada chunk em paralelo e, em seguida,
juntar os resultados.
63
Paralelizando chunks
Vamos continuar utilizando o tipo ChunksOf definido anteriormente para
representar nossos arquivos distribuıdos entre diversas maquinas.
64
Paralelizando Leitura dos Dados
Com isso, nossa funcao de processamento dos dados em paralelo
simplesmente aplica a funcao transformData em cada um dos chunks em
paralelo.
transformDataPar :: ChunksOf [Objeto] -> ChunksOf [Objeto’]
transformDataPar chunks = (map transformData chunks
‘using‘ parList rdeepseq)
Note que nenhuma alteracao e necessaria para a funcao transformData
que continuara recebendo o tipo [Objeto] e retornando [Objeto’].
65
Paralelizando a Padronizacao
Na padronizacao, nao podemos calcular as tres partes da equacao em
paralelo. Alem disso, temos um outro desafio, recebemos pedacos de
linhas, mas temos que trabalhar com as colunas:
padroniza :: [[Double]] -> [[Double]]
padroniza x = mapColunas padroniza’ x
padroniza’ :: [Double] -> [Double]
padroniza’ x = (x .- media) ./ sigma
where
media = (sum x) / n
sigma = sqrt $ sum $ (x .- media) .** 2
n = fromIntegral $ length x
66
Paralelizando a Padronizacao
Primeiro, vamos alterar a assinatura da funcao para sabermos onde
queremos chegar:
padronizaPar :: ChunksOf [[Double]] -> ChunksOf [[Double]]
padronizaPar chunks = parmap padroniza chunks
where
padroniza = map (\xi -> (xi .-. media) ./. desvio)
media = mapReduce id (.+.) chunks
desvio = map (\x -> sqrt (x/n))
$ mapReduce desvQuad (.+.) chunks
desvQuad xi = (xi .-. media).**2
n = sum $ map length’ chunks
67
Paralelizando a Padronizacao
Primeiro, vamos alterar a assinatura da funcao para sabermos onde
queremos chegar:
padronizaPar :: ChunksOf [[Double]] -> ChunksOf [[Double]]
padronizaPar chunks = parmap padroniza chunks
where
padroniza = map (\xi -> (xi .-. media) ./. desvio)
media = mapReduce id (.+.) chunks
desvio = map (\x -> sqrt (x/n))
$ mapReduce desvQuad (.+.) chunks
desvQuad xi = (xi .-. media).**2
n = sum $ map length’ chunks
67
Paralelizando a Normalizacao
A implementacao paralela de normaliza pode ser feita diretamente
aplicando a versao sequencial em cada chunk.
normalizaPar :: ChunksOf [[Double]] -> ChunksOf [[Double]]
normalizaPar chunks = parmap normaliza chunks
normaliza :: [[Double]] -> [[Double]]
normaliza x = map normaliza’ x
where
normaliza’ xi = xi ./ (norma xi)
norma xi = sqrt . sum $ xi .^ 2
68
Paralelizando a Normalizacao
A implementacao paralela de normaliza pode ser feita diretamente
aplicando a versao sequencial em cada chunk.
normalizaPar :: ChunksOf [[Double]] -> ChunksOf [[Double]]
normalizaPar chunks = parmap normaliza chunks
normaliza :: [[Double]] -> [[Double]]
normaliza x = map normaliza’ x
where
normaliza’ xi = xi ./ (norma xi)
norma xi = sqrt . sum $ xi .^ 2
68
Paralelizando o TF
Da forma que organizamos o algoritmo de TF, utilizando map e combine,
basta aplicar a funcao tf em cada chunk.
tfPar :: ChunksOf [Doc] -> ChunksOf [[(Token, Freq)]]
tfPar chunks = parmap tf chunks
tf :: [[Token]] -> [[(Token, Freq)]]
tf docs = map normFreq docs
where
normFreq doc = fn $ map (\w -> (w, 1.0)) doc
69
Paralelizando o TF
Da forma que organizamos o algoritmo de TF, utilizando map e combine,
basta aplicar a funcao tf em cada chunk.
tfPar :: ChunksOf [Doc] -> ChunksOf [[(Token, Freq)]]
tfPar chunks = parmap tf chunks
tf :: [[Token]] -> [[(Token, Freq)]]
tf docs = map normFreq docs
where
normFreq doc = fn $ map (\w -> (w, 1.0)) doc
69
Paralelizando a o IDF
Para paralelizar o IDF, precisamos calcular a contagem de quantos
documentos contem cada token em cada chunk. Em seguida, e necessario
combinar os resultados de cada chunk para entao calcular o idf.
idfPar :: ChunksOf [[(Token, Freq)]] -> M.HashMap Token Freq
idfPar chunks = M.fromList
$ mapByKey (\v -> log (n/v))
$ combine (+) $ concat
$ (map idf chunks ‘using‘ parList rdeepseq)
where
n = sum $ map length’ chunks
idf :: [[(Token, Freq)]] -> [(Token, Freq)]
idf corpus = combine (+)
$ map (\(k,v) -> (k,1) )
$ concat corpus
70
Paralelizando a o IDF
Para paralelizar o IDF, precisamos calcular a contagem de quantos
documentos contem cada token em cada chunk. Em seguida, e necessario
combinar os resultados de cada chunk para entao calcular o idf.
idfPar :: ChunksOf [[(Token, Freq)]] -> M.HashMap Token Freq
idfPar chunks = M.fromList
$ mapByKey (\v -> log (n/v))
$ combine (+) $ concat
$ (map idf chunks ‘using‘ parList rdeepseq)
where
n = sum $ map length’ chunks
idf :: [[(Token, Freq)]] -> [(Token, Freq)]
idf corpus = combine (+)
$ map (\(k,v) -> (k,1) )
$ concat corpus
70
Padrao de paralelismo
Note que o padrao de paralelismo do calculo do IDF difere dos anteriores
pois e necessario o uso do combine no lugar de foldl1’ e a aplicacao de
concat na saıda do map.
71
Padrao de paralelismo
Uma funcao generica pode ser escrita da seguinte forma e aplicada em
muitas situacoes em que trabalhamos com lista de tuplas:
mapReduceByKey :: (NFData k, NFData v, Ord k)
=> (a -> (k, v)) -> (v -> v -> v) -> ChunksOf [a] -> [(k, v)]
mapReduceByKey f g xs = combine g
$ concat
$ (map f’ xs
‘using‘ parList rdeepseq)
where
f’ xi = combine g $ map f xi
72
Padrao de paralelismo
Nossa funcao idfPar ficaria:
idfPar :: ChunksOf [[(Token, Freq)]] -> M.HashMap Token Freq
idfPar chunks = M.fromList
$ mapByKey (\v -> log (n/v))
$ mapReduceByKey (\(k,v) -> (k,1)) (+)
$ parmap concat chunks
where
n = sum $ map length’ chunks
73
Exercıcio
Escreva uma funcao utilizando mapReduceByKey que receba ChunksOf
[(k,v)] e retorne [(k, media v)].
74