Número:_________________ Nome: _________________________________________

1

--------------------------------------------------------------------------------------------------------------

INSTITUTO SUPERIOR TÉCNICO Sistemas de Apoio à Decisão

Exame: 1 1 Julho 2015

-------------------------------------------------------------------------------------------------------------- 1. (6 pts) Algumas perguntas fáceis para começar

1) DW (2 pts) Assinale as seguintes frases como verdadeiras (V) ou falsas (F). Cada resposta correcta corresponde a uma cotação de +0.5 valor. Resposta errada -0,25. Se não responder, a cotação é 0. (Indicate the question with (V) for true and (F) for false. Every correct answer has a value +0.5. False answer has a value -0.25. No answer the value 0.)

a. (0.5pts) (V)

median() é uma função de agregação holística median() is a holistic aggregation function) b. (0,5pts) (F) Em um esquema da “snowflake “as tabelas não são normalizadas (In snowflake schema tables are not normalized) c. (0.5pts) (F) (1+2)*(1+3)*2=3*4*2*2=48

Supor que um DW consiste em quatro dimensões: o tempo, a geografia, o produto, o cliente e umas medidas contam, onde a contagem é o número de produtos vendidos. Supor que o dimensão tempo tem a hierarquia mês, dia. Supor que o dimensão a geografia tem a hierarquia: continente, país, cidade. Então o número de cobóis é 40

Suppose that a DW consists of four dimensions: time, geography, product, customer and a measures count, where count is the number of sold products. Suppose that the dimension time has the hierarchy: day, month Suppose that the dimension geography has the hierarchy continent, country, city. Then the number of cuboids is 40

d. (0.5pts) (F) Supor que as dimensões não tem nenhuma hierarquia, nos podemos construir um cubo usando um comando SQL. (Suppose the dimensions have no hierarchies, we can build a cube using one SQL command.) command cube() by involves more than one command …. SELECT S#, P#, SUM ( QTY ) AS TOTQTY FROM SP GROUP BY CUBE ( S#, P#) ; if some one mentioned the command cube(), he got full point

Número:_________________ Nome: _________________________________________

2

2) DM (4pts) Assinale as seguintes frases como verdadeiras (V) ou falsas (F). Cada resposta correcta corresponde a uma cotação de +1 valor. Resposta errada -0,5. Se não responder, a cotação é 0. (Indicate the question with (V) for true and (F) for false. Every correct answer has a value +1. False answer has a value -0.5. No answer the value 0.) (a) (1pts) (V)

A algoritmo RBF pode “overfit”

(The algorithm RBF can overfit.) (b) (1pts) (F)

Os algoritmos 3-Nearest neighbor e 5-Nearest neighbor retornam sempre o mesmo resultado. (3-Nearest neighbor e 5-Nearest neighbor return always the same results.) (c) (1pts) (F) The use of kernel functions can turn any algorithm that only depends on dot

product into a nonlinear algorithm, Radial basis function kernel

€

e−! x −! y 2

2σ 2 is an exemple of

such a kernel function

Uma Support Vector Machine com o kernel

€

e−! x −! y 2

2σ 2 só pode classificar problemas linearmente separáveis.

(Support vector machine with the kernel

€

e−! x −! y 2

2σ 2 can only classify linear seperable

problems) (d) (1pts) (V) sigmoid activation function is non linear

O Perceptrão Multinível (Multilátera Perceptron) com um nível escondidos e com função de cativação

mais poderoso que um perceptrão com dois nível escondido e com função activação linear

(Multilayer Perceptron with one hidden layers and the activation function

is more powerful then a Perceptron with two hidden layer and a linear activation function .)

€

f (x) =σ (x) =1

1+ e(−2⋅x )

€

f (x) =σ (x) =1

1+ e(−2⋅x )

Número:_________________ Nome: _________________________________________

3

2. (3 pts) Cube Supor que um DW consiste em quatro dimensões, tempo, geografia, produto, cliente e one measure count. Supor que o dimensão tempo tem a hierarquia: ano, semana, mês, dia. Supor que o dimensão a geografia tem a hierarquia: continente, país, cidade. Supor dimensão produto definido pelo attribute color. Suppose that a data warehouse consists of four dimensions, time, geography, product, , customer and one measure count. Suppose that the dimension time has the hierarchy: day, week, month, year. Suppose that the dimension geography has the hierarchy continent, country, city. Suppose the product e is defined by the attribute color. (a) (1pts) Apresente o modelo em estrela para esta DW. Present a Star schema for a DW (b) (1pts) Apresente o modelo “Snowflake” para esta DW. Presen a Snowflake schema for a DW (c) (1pts) Quantos cuboids existem dentro deste cubo? How many cuboids are present in this cube? (a)

Número:_________________ Nome: _________________________________________

4

(b)

(c ) 2*2*(1+4)*(1+3)=4*5*4=80

Número:_________________ Nome: _________________________________________

5

3. (3 pts) ) EM Clustering

Dado o conjunto de dados !x j =11

!

"#

$

%&, 0

4

!

"#

$

%&, 3

0

!

"#

$

%&

'()

*)

+,)

-) com µ1 =

10

!

"#

$

%&,µ2 =

01

!

"#

$

%& e

€

Σ1 =1 00 1#

$ %

&

' ( ,Σ2 =

1 00 1#

$ %

&

' ( e P(C=i)=1/2 α=1. Execute um passo do algoritmo de clustering EM. Quais

são os novos valores de

€

µi,Σi,wi?

Given the data !x j =11

!

"#

$

%&, 0

4

!

"#

$

%&, 3

0

!

"#

$

%&

'()

*)

+,)

-) withµ1 =

10

!

"#

$

%&,µ2 =

01

!

"#

$

%& e

€

Σ1 =1 00 1#

$ %

&

' ( ,Σ2 =

1 00 1#

$ %

&

' ( and P(C=i)=1/2 α=1. Preform on step of EM clustering algorithm.

What are the values of

€

µi,Σi,wi? By Bayes’ rule pij=αP(xj|C=i)P(C=i)

pij=αP(xj|C=i)P(C=i) pij=α/2P(xj|C=i) pij=1/2P(xj|C=i) Because we initialize our parameters arbitrary, we set P(C=i)=1/2 α=1, with the given data we can simplify d=2, and because of

€

Σ1 =1 00 1#

$ %

&

' ( ,Σ2 =

1 00 1#

$ %

&

' (

we get

€

P(x |C = i) =1

(2π )d / 2 ΣC= i

1/ 2 exp −12x −µC= i( )tΣC= i

−1 x −µC= i( )%

& ' (

) *

€

P(x |C = i) =1(2π )

exp − 12x −µC= i( )t x −µC= i( )

$

% & '

( )

€

pij =1(4π )

exp − 12x j −µC= i( )

tx j −µC= i( )

$

% & '

( )

Número:_________________ Nome: _________________________________________

6

(We using Mathematica notation) p11= 1/(4*Pi)*Exp[-1/2*(x1 - u1).(x1 - u1)]= 0.0482662 p12= 1/(4*Pi)*Exp[-1/2*(x2 - u1).(x2 - u1)]= 0.0000161915 p13= 1/(4*Pi)*Exp[-1/2*(x3 - u1).(x3 - u1)]= 0.0107696 p21= 1/(4*Pi)*Exp[-1/2*(x1 - u2).(x1 - u2)= 0.0482662 p22= 1/(4*Pi)*Exp[-1/2*(x2 - u2).(x2 - u2)]= 0.000884026 p23=1/(4*Pi)*Exp[-1/2*(x3 - u2).(x3 - u2)]= 0.000536189 p1=0.0482662 + 0.0000161915 + 0.0107696=0.059052 p2=0.0482662 + 0.000884026 + 0.000536189=0.0496864 µ1=(0.0482662*x1 + 0.0000161915*x2 + 0.0107696*x3)/0.059052=(1.36448, 0.818448)’ µ2=(0.0482662*x1 + 0.000884026*x2 + 0.000536189*x3)/0.0496864=(1.00379, 1.04259)’

µ1 =1.364480.818448

!

"#

$

%&,µ2 =

1.003791.04259

!

"#

$

%&

Σ1= (0.0482662*Transpose[x1].x1 + 0.0000161915*Transpose[x2].x2 + 0.0107696*Transpose[x3].x3)/0.059052=

2.45872 0.8173510.817351 0.821738

Σ2=(0.0482662*Transpose[x1].x1 + 0.000884026*Transpose[x2].x2 + 0.000536189*Transpose[x3].x3)/0.0496864=

1.06854 0.9714170.971417 1.25609

€

pi = pijj=1

n

∑

€

µi ←pij! x j

pij=1

n

∑

€

Σi ←pij! x j! x j

T

pij=1

n

∑

Número:_________________ Nome: _________________________________________

7

4. (3 pts) Belief Networks

Calcule a probabilidade de “WatsoCalls” dado “Earthquake”, “Buglary” serem falso, ”Alarm e”, RadioNews” serem desconhecidos. (Determine the probability of “WatsoCalls” given “Earthquake”, “Buglary” are false, ” Alarm”, “RadioNew” and are unknown) 𝑃 𝑊 ¬𝑒,¬𝑏 = 𝛼 ∗ 𝑃 𝑊 𝑎 ∗ 𝑃 ¬𝑒 ∗ 𝑃(

!

𝑎 ¬𝑒,¬𝑏 ∗ 𝑃 ¬𝑏

𝑃 𝑊 ¬𝑒,¬𝑏 = 𝛼 ∗ 𝑃 ¬𝑒 ∗ 𝑃 ¬𝑏 ∗ 𝑃 𝑊 𝑎 ∗ 𝑃(

!

𝑎 ¬𝑒,¬𝑏

𝑃 𝑊 ¬𝑒,¬𝑏= 𝛼 ∗ 𝑃 ¬𝑒 ∗ 𝑃 ¬𝑏 ∗ (𝑃 𝑊 𝑎 ∗ 𝑃  (𝑎 ¬𝑒,¬𝑏 + 𝑊 ¬𝑎 ∗ 𝑃  (¬𝑎 ¬𝑒,¬𝑏 ) 𝑃 𝑤 ¬𝑒,¬𝑏 =  𝛼 ∗(0.999*0.9*(0.95*0.1+0.1*0.9))= 0.166334 𝑃 ¬𝑤 ¬𝑒,¬𝑏 =  𝛼 ∗(0.999*0.9*(0.05*0.1+0.9*0.9))= 0.732767 𝑃 𝑤 ¬𝑒,¬𝑏 = 0.185 ¬𝑤 ¬𝑒,¬𝑏 =0.815

Número:_________________ Nome: _________________________________________

8

5. (2 pts) Decision Tree Cluster

F1 F2 F3 F4 Output

a a b a t c a b a n a a b a t a b b a f a b b a f a b b a f

Calcule a árvore de decisão para este conjunto de exemplos com target “Output” usando o algoritmo ID3. Indique os seus cálculos. Determine the decision tree using the ID3 algorithm with the target “Output”. Indicate the calculation. p(t)=2/6=1/3 p(n)=1/6, p(f)=3/6=1/2 Log2[x]= Log[x]/Log[2] I(table)= -1/3*Log2[1/3] - 1/6*Log2[1/6] - 1/2*Log2[1/2]= 1.45915 bits

F1 Ca=(t,t,f,f,f), Cc=(n), I(Ca)= -2/5*Log2[2/5] - 3/5*Log2[3/5]= 0.970951 bits I(Cc)= 0 bits E(F1)= 5/6*0.970951 =0.809126 Gain(F1)= 0.650024 F2 Ca=(t,n,t) Cb=(f,f,f) I(Ca)= -2/3*Log2[2/3] - 1/3*Log2[1/3]= 0.918296 bits I(Cb)= 0 bits E(F2)= 3/6*0.918296 =0.459148 Gain(F2)= 1 Gain(F3)=Gain(F4)=0 We chose F2 as the root, the remaining table is

€

E(P) =|Ci ||C |i=1

n

∑ I(Ci)

€

gain(P) = I(C) − E(P)

Número:_________________ Nome: _________________________________________

9

F1 F3 F4 Output

a b a t c b a n a b a t

We then chose F1 since Gain(F3)=Gain(F4)=0

Número:_________________ Nome: _________________________________________

10

6. 3. (3 pts) Neuronal Network NN

Dados os w1={w11=0.1,w12=0.1,w13=0.1,w14=0.1,w15=0.1} w2={w21=0.1,w22=0.1,w23=0.1,w24=0.1,w25=0.1} w3={w31=0.1,w32=0.1,w33=0.1,w34=0.1,w35=0.1} W1={W11=0,W12=0,W13=0} W2={W21=0,W22=0,W23=0} e a função de activação Faça um gradiente descendente estocástico com η=1 para o vector de entrada x={0,0,0,0,0}; e alvo (target) t={0,0}, determine

€

Δw jk e

€

ΔWij para o primeiro passo de adaptação. netj=net1=net2=net3=0 V1= V2 =V3=1/(1 + Exp[-2*0])= 0.5

Output layer neti=net1=net2=net3 =0 O1= O2 =1/(1 + Exp[-2*0])= 0.5

€

f (x) =σ (x) =1

1+ e(−2⋅x )

Número:_________________ Nome: _________________________________________

11

𝑓! 𝑥 = 2 ∙ 𝜎(𝑥) ∙ (1− 𝜎 𝑥 ) neti=net1=net2=net3 =0 𝛿! =    𝛿! =(0-0.5)*2*1/(1 + Exp[-2*0])*(1-1/(1 + Exp[-2*0]))=-0.25 ΔWij = δiVj Because of symetry (all weights are the same in a layer) ∆𝑊!"=-0.25*0.5=-0.125 𝑊!"

!"# = 0− 0.125 = −0.125

Hidden layer netj=net1=net2=net3=0 f’(netj)= 2*1/(1 + Exp[-2*0])*(1 - 1/(1 + Exp[-2*0]))=0.5 δ1=δ2=δ3=-0.25*0*0.5+0.25*0*0.5=0

=0

𝑤!"!"# = 0.1+ 0 = 0.1

€

ΔWij = (ti − oi) f' (neti)V j

€

f (x) =σ (x) =1

1+ e(−2⋅x )

€

Δw jk = δii=1

2

∑ ⋅Wij f' (net j ) ⋅ xk

€

Δw jk = δ j ⋅ xk