Embed Size (px)
Citation preview
Mestrado em Análise de Dados e Sistemas de Apoio à Decisão
Disciplina: Extracção e conhecimento de dados I
Trabalho nº2: Comparação de métodos de classificação recorrendo aos
softwares R e Weka
Data: 18 de Novembro de 2005
Aluna: Elisabeth Silva Fernandes
Nº 050414012
2
Índice
1- Introdução
1.1- Objectivo e enunciado do trabalho………….………………………………3
1.2- Análise preliminar dos dados…….…………………………………………4
2- Classificação
2.1-O que é uma árvore de decisão?
2.1.1- Construção de uma árvore de decisão 2.1.2- Como segmentar ou
dividir um nó?
2.1.3- A Poda
2.1.4- Relação Custo-Complexidade- Regra 1-SE
2.2- Análise descriminante………………………………………………………9
3- Aplicação de alguns métodos de classificação ao conjunto de treino ………………10
3.1-Aplicação de alguns métodos de classificação em Weka
3.1.1- Árvore de decisão- Método J48- C 0.25 _M 2
3.1.2- Discriminante Logístico………………………………………….13
3.1.3- Arvore de decisão vs Descriminante logístico…………………...14
3.2- Aplicação de alguns métodos de classificação em R……………………...15
3.2.1- Árvores de decisão
3.2.2- Discriminante linear
3.2.3- Arvores de decisão vs Discriminante Linear
4- Previsão……………………………………………………………………………...22
5- Conclusão……………………………………………………………………………23
Biblografia
Anexos
3
1 –Introdução
1.1-Objectivo e enunciado do trabalho
O objectivo do trabalho consiste em seleccionar um classificador a partir do conjunto de
treino e com o modelo obtido classificar os exemplos do conjunto de teste.
O trabalho consiste em:
1. Estimar a taxa de erro de dois classificadores utilizando um método de
amostragem:
o árvores de decisão,
o discriminante linear.
3. Estudar o efeito do parametro c no J48 (Weka).
4. Estudo comparativo da taxa de erro entre a árvore de decisão do R (rpart)
e o discriminante linear (lda) do R.
2. Escolher um classificador para classificar os exemplos do conjunto de teste.
4
1.2- Análise preliminar dos dados
O quadro de dados em estudo tem 620 indivíduos e 15 variáveis sendo a última
variável a classes a que cada individuo pertence.
O quadro seguinte mostra o comportamento das variáveis:
A azul estão representados os indivíduos da classe 0 e a vermelho os da classe 1.
As variáveis 1,4,11,12 só apresentam valores discretos entre 1 e 3, poderão ser variáveis
nominais, logo não fará muito sentido calcular estatísticas destas variáveis no entanto
fiz um summary para ver como se comportam as variáveis em estudo.
Antes da escolha dos classificadores o método de amostragem que utilizei foi a
validação cruzada porque é o método mais fiável uma vez que o número de indivíduos
não é muito elevado. Com a validação cruzada o que o método faz é dividir os dados em
10 partes, selecciona uma parte constrói um classificador com as 9 partes restantes e
testa a classificação com a parte seleccionada, o processo é repetido 10 vezes.
5
2- Classificação
O objectivo da análise discriminante é determinar uma regra de classificação que
permite afectar um indivíduo a uma de várias classes especificadas a priori com base
nos valores observados de p variáveis associadas ao individuo.
Neste trabalho estuda-se uma pequena parte da classificação, as árvores de
decisão e os descriminantes linear e logístico, para obter as classificações utilizei os
softwares Weka e R.
2.1-O que é uma árvore de decisão?
Uma árvore de decisão utiliza uma estratégia de “dividir-para-conquistar”:
- um problema complexo é decomposto em sub-problemas mais simples;
- recursivamente a mesma estratégia é aplicada a cada sub-problema.
A árvore de decisão é usada para a dedução da classe de um conjunto de
atributos (objecto não-classificado), que possui as seguintes propriedades:
- um nó folha representa uma única classe, mas uma classe pode estar
representada em mais de um nós folha;
- um nó interno é chamado de nó-decisão pois representa em teste sobre o
valor de um atributo do conjunto de dados;
- cada aresta que sai de um nó de decisão até um dos seus nós filhos
representa um dos possíveis resultados do teste sobre o valor do atributo.
Podemos considerar o conjunto de todos os objectos possíveis como pontos num
espaço n-dimensional – com um eixo para cada atributo, enumerando todos os valores
possíveis para o mesmo. Assim, nota-se que cada nó divide o espaço de objectos em k
partições, onde k é o número de arestas que partem o nó. Cada nó da árvore representa
um sub-espaço. O nó-raiz representa o próprio espaço de objectos. Os nós-filho de um
nó representam as partições da partição do espaço representado pelo nó-pai. Os nós-
folha representam as partições em que, pelo menos teoricamente, só estão contidos
elementos da mesma classe.
2.1.1- Construção de uma árvore de decisão:
A ideia base consiste em
- escolher um atributo;
- estender a árvore adicionando um ramo para cada valor do atributo;
- passar os exemplos para as folhas (tendo em conta o valor do atributo
escolhido);
6
- para cada folha: se todos os exemplos são da mesma classe, associar essa classe
à folha; senão repetir os passos anteriores.
As regras derivadas das árvores – especialmente árvores grandes – são muitas
vezes um pouco complicadas e devem ser reduzidas para uma ajuda interpretativa. É
possivel aumentar a árvore tão grande quanto queiramos, maxT , e obter erro zero (ou
seja, em cada folha está uma observação), mas pode não ser bom para avaliar o futuro
objecto a classificar. Este método é muito mau para avaliar outros valores porque esta
árvore não dá bons resultados num conjunto independente de observações.
O que é que se faz?
Para resolver esta questão existem duas estratégias
1ª- Parar de crescer a árvore mais cedo (nunca deu bons resultados porque
ninguém sabe onde parar!);
2ª- Podar a árvore maxT .
2.1.2- Como segmentar ou dividir um nó?
Para cada nó t vamos escolher a divisão que diminui a impureza, ou seja o
objectivo é que os “filhos sejam mais puros que os pais”. Torna-se então necessário
definir uma medida de impureza de um nó.
1 2( ) ( , ,..., )ki t i p p p
onde ( \ )i ip P t , a qual deve satisfazer:
i) (1,0,...,0) (0,0,...,1) 0i i ;
ii) 1 1 1
, ,...,ik k k
máxima;
A mais popular medida é a Entropia.
Critério da Entropia
Este critério é o que o R usa.
A Entropia é um conceito estabelecido na Teoria da Informação para medir o
grau de aleatoriedade dos valores que uma variável aleatória X pode assumir ou,
fazendo a analogia com o conceito físico, o grau de desordem no sistema considerado:
1
( ) ( ).log ( )n
i i
i
i t p X x p X x
7
Quanto maior a entropia, maior a aleatoriedade dos valores que X pode assumir,
ou seja, a entropia máxima é encontrada numa variável aleatória de distribuição
uniforme.
Critério de Gini
Este critério é o que o Weka usa e consiste numa generalização da impuridade
da variância, aplicado para duas ou mais categorias.
( ) | . |i j
i j
i t p C c t p C c t
A função dada tem um mínimo igual a zero quando a partição do nó t contém
apenas instâncias da classe j, e um máximo igual a 2
1 1/ 1/n n n - para valores
grandes de n – quando todas as classes foram igualmente frequentes.
2.1.3- A Poda
Após construir a Árvore de Decisão é possível que ela esteja muito ajustada ao
conjunto de treino utilizado e não classifique bem os objectos do conjunto de teste
(overfitting). Para evitar esta situação, os algoritmos indutores acrescentam uma fase de
poda da árvore construída, ou seja, a remoção de alguns nós da árvore aumentando a
generalização da mesma.
A poda pode ser:
- Pré-Poda: executada durante o processo de indução da árvore, impõe um
threshold para a proporção da classe mais frequente para o qual um nó é forçado
ser folha, não prosseguindo o particionamento por este ramo
- Pós-Poda: é executada após a árvore ter sido construído, apartir dos nós-folha, a
sub-árvore formada por eles e seu nó-pai são analisados. Se a taxa de erros de
classificação for reduzida perante uma substituição da sub-árvore por um único
nó terminal, então a árvore é podada nesta parte.
Neste trabalho o tipo de poda usado foi Pós-poda.
8
2.1.4-Relação Custo-Complexidade- Regra 1-SE
A técnica mais conhecida de podar árvores é a de Breiman & al.(1984)
Seja ( )R t uma medida de qualidade da árvore:
onde T é o conjunto de folhas, ( )p t a probabilidade de atingir a folha e ( )r t o erro na
folha t. O tamanho de T, que se designa por tam(T), pode ser, por exemplo, o número de
folhas de uma árvore.
O que este autores propuseram foi que se escolhe a sub-árvore de maxT que
minimize:
.t T
R T R T tam T R T
em que R T é uma medida de qualidade
da árvore e .tam T é a penalização segundo o tamanho da árvore, ou seja,
penalizam-se as árvores grandes.
Se 0 então não há penalização e a subárvore óptima é a maxT .
À medida que vai crescendo a sub-árvore óptima é constituída só pela raiz. Breiman
& al.(1984) demonstraram que o subconjunto de árvores ( )T verificam:
max 1
0 1
...
........
T T raiz
isto é, 1,i i a subárvore óptima é iT .
Após a poda obtém-se
max 0 1 2 1... ( )KT T T T T T t raiz
correspondentes a
0 1 2 ... K
em que
1 min ,l l
l lt T T
g t T
e portanto 1 max 1l lT T
1: , ,l l l lt T g s T s T antepassado de t .
Temos que obter um estimador do erro de cada árvore da sequência, lR T , e
escolher a que tem menor erro. Os autores de CART sugeriram o Método de Validação
Cruzada.
9
2.2- Análise descriminante
O objectivo da análise descriminante é reconhecer a classe a que pertence um
dado objecto, de forma a que a classe encontrada maximize a probabilidade de um dado
pertencer a essa classe. Para isso assumimos um determinado modelo para as funções
densidade de probabilidade, isto é, supõem-se que kjxff jjj ,,1),,( , onde j
são parâmetros desconhecidos, sendo necessário estima-los. Estes parâmetros,
normalmente, são estimados pelo método de máxima verosimilhança.
Sejam então os parâmetros estimados k̂ . Têm-se )ˆ,(ˆˆjjj xff . Estimemos
agora as probabilidades à posteriori para cada classe:
)(ˆ
)(ˆˆ)\(ˆ
xf
xfxcP kk
k
(2.4.1)
onde kf é a função densidade de probabilidade para a classe kc e k̂ é a probabilidade
à priori da classe kc e é dada por n
ni , onde jn representa o número de dados
pertencentes à classe j e n o número total de dados.
Depois de calculadas as probabilidades à posteriori usamos a regra de Bayes de
erro mínimo
jxc )(ˆ se )\(ˆmax)\(ˆ xcPxcP ii
j
Ou seja, pretende-se encontrar a classe que maximiza a probabilidade de um
dado pertencer a essa classe.
De acordo com o tipo de fronteiras (linear ou quadrática) vamos ter dois tipos de
modelos: o modelo normal homocedástico (ou melhor regra linear) e o modelo normal
heterocedástico (ou melhor regra quadrática).
10
3-Aplicação de alguns métodos de classificação ao dados de treino
3.1- Em Weka
3.1.1- Árvore de decisão- Método J48- C 0.25 _M 2
As vantagens do algoritmo de árvores de decisão estão na grande capacidade de
descrição das árvores para um grande número de dados, o que leva a que seja fácil de
interpretar. Como não assume nenhuma distribuição permite a construção modelos para
qualquer função desde que o número de exemplos de treino seja suficiente. E é robusto
à presença de pontos extremos e atributos irrelevantes.
Os problemas que surgem estão relacionados com o sobre-ajustamento da árvore
ao conjunto de treino o que leva a que para novos indivíduos as classificações sejam
péssimas. No caso de se alterar o conjunto de treino podemos obter uma árvore
completamente diferente o que mostra a instabilidade deste método.
O objectivo principal deste método é obter um modelo de decisão que faça boas
previsões para o futuro.
Este método obtêm estimativas fiáveis do erro a partir do conjunto de treino e
poda com base numa estimativa do erro no conjunto de treino, neste caso, assume uma
distribuição binomial para os exemplos de um nó, isto é, vai estimar o erro a população
e usa as estimativas para podar a árvore.
No conjunto de treino em estudo a árvore que obtive tem 41 folhas, quanto ao
número de instâncias bem classificadas foram 524, correspondendo a uma boa
percentagem de 84.5% dos dados de treino. O erro obtido foi de 15.48%.
O valor de c é de 0.25 e o de M é 2, estes são os valores que o weka apresenta
por defeito sendo possível alterá-los, o c permite aumentar e diminuir o intervalo de
confiança para o erro, e o M dá o valor máximo de indivíduos por folha.
11
A árvore obtida foi a seguinte:
=== Stratified cross-validation ===
=== Summary ===
Correctly Classified Instances 524 84.5161 %
Incorrectly Classified Instances 96 15.4839 %
Kappa statistic 0.6857
Mean absolute error 0.188
Root mean squared error 0.3575
Relative absolute error 38.0509 %
Root relative squared error 71.9302 %
Total Number of Instances 620
Os valores do quadro seguinte são calculados da seguinte forma:
FNTP
TPTPRate
;
TNFP
FPFPRate
;
i classe da linha da somarelevantes atributos #
i classe à atribuídos são que atributos#Re call ;
i classe da coluna da somarelevantes atributos #
i classe à atribuídos são que atributos#Pr ecision ;
FNFPTP
TPMeasureF
*2
*2 ;
em que :TP-True positive; FN-False negative; TN- True negative; FP-False Positive.
=== Detailed Accuracy By Class ===
TP Rate FP Rate Precision Recall F-Measure Class
0.872 0.188 0.852 0.872 0.862 0
0.812 0.128 0.836 0.812 0.824 1
=== Confusion Matrix ===
a b <-- classified as
300 44 | a = 0
52 224 | b = 1
Por exemplo, FP é quando o resultado é incorrectamente previsto, ou seja, foi
atribuído positivo quando de facto é negativo. A classe 1 apresenta um maior número de
indivíduos aos quais a classe foi mal atribuída.
12
Estudo do nível de confiança fixado para o erro.
O nível de confiança fixado é o parâmetro c, logo o intervalo de confiança
obtido para o erro é para (1-c)100%.
Este método poda a árvore com base numa estimativa do erro no conjunto de
treino, e como assume uma binomial para os exemplos do nó podemos obter o intervalo
de confiança para c como mostro a seguir.
Seja N
errosf , esta variável pode ser aproximada por uma normal
estandardizada uma vez que 30N , logo:
)1,0(~)1(
N
N
pp
pfX
Então o intervalo de confiança é obtido da seguinte forma: czXP , z é um
valor tabelado.
Na tabela seguinte é possível observar os valores de c, os erros de classificação
obtidos e o número de folhas:
Método J48
Valores de c
% Instâncias mal
classificadas
Nº de
folhas
0,05 15,6452% 21
0,1 14,8387% 29
0,2 14,6774% 29
0,25 15,4839% 41
0,3 15,9677% 67
0,5 17,2581% 73
0,7 18,0645% 89
Neste exemplo o erro converge para 18.065%.
Quanto maior for o valor de c maior vai ser o ajustamento da árvore aos dados
de treino, logo a percentagem de instâncias mal classificadas aumenta, ou seja o erro
aumenta à medida que se aumenta o número de nós.
Quando a poda é pouco severa a árvore está muito ajustada aos dados de treino
logo para novos valores o erro de classificação irá ser maior.
13
3.1.2- Discriminante Logístico
Uma vez que o Weka não tem implementado o discriminante linear decidi
experimentar o discriminante logístico.
Este método consiste em obter um modelo para as probabilidades à posteriori.
O discriminante logístico é linear e contrói hiperplanos da forma:
)|(
)|(log
1 xP
xPxH iT
iii
Para estimar os valores i e i utiliza o método da máxima verosimilhança.
xCPxCPL n
nl
ln |...|,..., 11
Os resultados obtidos para o caso em estudo foram os seguintes (ver anexo2):
=== Stratified cross-validation ===
=== Summary ===
Correctly Classified Instances 539 86.9355 %
Incorrectly Classified Instances 81 13.0645 %
Kappa statistic 0.7371
Mean absolute error 0.1956
Root mean squared error 0.3195
Relative absolute error 39.596 %
Root relative squared error 64.291 %
Total Number of Instances 620
=== Detailed Accuracy By Class ===
TP Rate FP Rate Precision Recall F-Measure Class
0.858 0.116 0.902 0.858 0.879 0
0.884 0.142 0.833 0.884 0.858 1
=== Confusion Matrix ===
a b <-- classified as
295 49 | a = 0
32 244 | b = 1
Neste método obtive uma percentagem superior de instâncias bem classificadas, a classe
0 apresenta um maior número de instâncias mal atribuídas.
14
3.1.3- Arvore de decisão vs Descriminante logístico
No quadro seguinte apresento alguns valores que mostram valores obtidos nos
dois métodos:
MAE RMSE RAE RRSE
Taxa de
acerto
J 48 0,188 0,3575 38,05% 71,93% 84,52%
D.Logistico 0,1956 0,3195 39,60% 64,29% 86,94%
O discriminante logístico tem maior taxa de acerto, e apresenta maior valor de
erro médio quadrático, logo apesar de ter maior acerto a distância entre as classes
atribuídas e as classes verdadeiras é maior ( ver anexo tabela1).
15
3.2- Aplicação de alguns métodos de classificação em R.
3.2.1- Árvores de decisão
A ferramenta do R utilizada para obter a árvore de decisão foi o rpart, que se
encontra na biblioteca rpart. Factorizei as variáveis em que os valores são discretos pois
o R assumia que estas tomavam todos os valores entre os valores discretos, usando o
comando factor o R assume que estas variáveis só tomam os valores por exemplo 0, 1,
2. Ao conjunto de treino denominie-o por A.
library(rpart)
>A<-read.table('D:/economia/extrconhdados/trabalho2/treino.txt');
> A$V1 <- factor(A$V1)
> A$V15 <- factor(A$V15)
> A$V4 <- factor(A$V4)
> A$V8 <- factor(A$V8)
> A$V9 <- factor(A$V9)
> A$V11 <- factor(A$V11)
> A$V12 <- factor(A$V12)
> arvore<-rpart(V15~.,A)
> text(arvore, use.n=TRUE)
A arvore obtida foi a seguinte:
> arvore
n= 620
node), split, n, loss, yval, (yprob)
* denotes terminal node
1) root 620 276 0 (0.55483871 0.44516129)
2) V8=0 296 21 0 (0.92905405 0.07094595) *
3) V8=1 324 69 1 (0.21296296 0.78703704)
6) V9=0 124 51 1 (0.41129032 0.58870968)
12) V5< 8.5 77 36 0 (0.53246753 0.46753247)
24) V13>=111 50 17 0 (0.66000000 0.34000000)
48) V6< 6.5 37 9 0 (0.75675676 0.24324324) *
49) V6>=6.5 13 5 1 (0.38461538 0.61538462) *
25) V13< 111 27 8 1 (0.29629630 0.70370370) *
13) V5>=8.5 47 10 1 (0.21276596 0.78723404) *
7) V9=1 200 18 1 (0.09000000 0.91000000) *
|V8=a
V9=a
V5< 8.5
V13>=111
V6< 6.5
0
0 1 1
1
1
Pode ainda obter-se uma representação mais sofisticada da árvore da seguinte
forma:
> plot(arvore,uniform=T,branch=0.2,margin=0.1,compress=T)
>text(arvore,fancy=T,cex=0.57,font=08,fwidth=0.3,fheight=0.3,use.n=T,all=T,dig
its=2,pretty=1)
16
“Através da informação seguinte é possível obter, para cada valor do
parâmetro de cost complexity pruning (CP), qual o valor do erro relativo no conjunto
de treino, bem como o erro estimado por validação cruzada e o respectivo erro padrão
desta estimativa. A cada valor de CP corresponde uma sub-àrvore, sendo a última linha
da tabela a árvore retornada pela função rpart, e a primeira linha uma sub-árvore
formada unicamente por uma folha.”[5]
> printcp(arvore)
Classification tree:
rpart(formula = V15 ~ ., data = A)
Variables actually used in tree construction:
[1] V13 V5 V6 V8 V9
Root node error: 276/620 = 0.44516
n= 620
CP nsplit rel error xerror xstd
1 0.673913 0 1.00000 1.00000 0.044836
2 0.019324 1 0.32609 0.32609 0.031780
3 0.010870 4 0.26812 0.30797 0.031030
4 0.010000 5 0.25725 0.31522 0.031334
17
cp
X-v
al R
ela
tive
Err
or
0.2
0.4
0.6
0.8
1.0
Inf 0.11 0.014 0.01
1 2 5 6
size of tree
Após análise destes outpus penso que a melhor poda desta árvore é ficar só com
2 testes, em vez de 4. Para tal usei os seguintes comandos.
> Poda<-prune(arvore,cp=0.033)
> plot(Poda,uniform=T,branch=0.2,margin=0.1,compress=T)
>text(Poda,fancy=T,cex=0.57,font=08,fwidth=0.3,fheight=0.3,use.n=T,all
=T,digits=2,pretty=1)
E obtive a árvore podada seguinte:
“Uma outra forma de podar a árvore com base em estimativas por validação cruzada é
escolher a menor árvore apresentada pela função printcp que tenha um erro dentro
do intervalo ERR , em que ERR é o erro menor dos erros estimados por validação
cruzada e o respectivo desvio padrão. Esta regra é conhecida como regra 1-SE” (ver
2.1.4). [5]
18
> arvore.grande<-rpart(V15~.,A,cp=0)
> valcruz.Poda<-function(treino, se =1){
linha.min.erro<- which.min(arvore$cptable[,4])
erro.total<-
arvore$cptable[linha.min.erro,4]+arvore$cptable[linha.min.erro,5]
linha<-which(arvore$cptable[,4]<=erro.total)[1]
prune.rpart(arvore,cp=arvore$cptable[linha,1]+1e-7)
}
> arvore.final<-valcruz.Poda(arvora.grande)
> plot(arvore.final,uniform=T,branch=0.2,margin=0.1,compress=T)
>text(arvore.final,fancy=T,cex=0.57,font=08,fwidth=0.3,fheight=0.3,use
.n=T,all=T,digits=2,pretty=1)
A árvore obtida foi a seguinte:
> arvore.final
n= 620
node), split, n, loss, yval, (yprob)
* denotes terminal node
1) root 620 276 0 (0.55483871 0.44516129)
2) V8=0 296 21 0 (0.92905405 0.07094595) *
3) V8=1 324 69 1 (0.21296296 0.78703704) *
|
V8=0
V8=1
0
3.4e+02/2.8e+02
0
2.8e+02/21
1
69/2.6e+02
19
Previsão dos valores de treino e estudo dos erros
No caso da Validação cruzada obtêm-se o intervalo de confiança para o erro
calculando a média e o desvio padrão dos erros obtidos em cada iteração.
No quadro seguinte é possível observar o procedimento usado para obter o intervalo de
confiança.
O algoritmo seguinte foi retirado do trabalho [6], em anexo descrevo passo a passo o
que este faz pois não fiz uma cópia sem perceber o que estava a fazer!
valcruz<-function(treino,k){
library(rpart)
Ncol<-nrow(treino)
permutar<-sample(620)
dim(permutar)<-c(k,as.integer(num/k))
erro<-rep(0,10)
for (i in 1:k){
teste<-treino[permutar[i,],]
Treino<-treino[-permutar[i,],]
arvore<-rpart(V15~.,treino)
arvore.final<-valcruz.Poda(arvore)
Arvore.prev<-predict(arvore.final,teste,type="class")
m.conf<-table(teste$V15,Arvore.prev)
elem.nao.diag<-col(m.conf)!=row(m.conf)
perc.erro<-100*sum(m.conf[elem.nao.diag])/sum(m.conf)
erro[i]<-perc.erro}
print(erro)
print(summary(erro))
mean(erro)}
Os resultados obtidos foram os seguintes:
> valcruz(A,10)
[1] 9.67742 11.29032 17.74194 19.35484 11.29032 12.90323 20.96774
12.90323 12.90323 16.12903
Min. 1st Qu. Median Mean 3rd Qu. Max.
9.677 11.690 12.900 14.520 17.340 20.970
[1] 14.51613
A média dos erros é de 14.5% e desvio padrão 4.507.
Se efectuar este procedimento 100 vezes obtenho que o erro médio é de 14.52%.
20
3.2.2- Discriminante linear
Para cada classe o discriminante linear é um hiper-plano que é combinação linear dos
atributos:
i
T
ii xH em que ii 1 e i
T
iii Cp 12/1log
O objectivo é encontrar a classe j que maximiza )(ˆ
)(ˆˆ)|(ˆ
xf
xfxcP kk
k
, que é
equivalente a maximizar apenas )(ˆˆ xf kk , porque )(ˆ xf é igual para todas as classes.
Mas maximizar )(ˆˆ xf kk é equivalente a maximizar ))(ˆˆln( xf kk .
))(ˆˆln(max xf kk
j
T
jpj xx
ˆˆ2
1exp
)2(
1lnˆlnmax 1
22
1
= ˆln2
1ˆlnmax j -
j
T
j XXp
ˆˆ2
1)2ln(
2
1
Maximizar esta expressão é equivalente a minimizar a seguinte função linear:
jj
T
jj X ˆln2ˆˆˆˆ2 11
è com esta expressão que se encontra a melhor regra linear.
O algoritmo utilizado para determinar o discriminante linear foi o lda da
biblioteca MASS de R (ver anexo) . Assume-se igual probabilidade, á priori, para
ambas as classes.
> val.cruz.descrmin.linear(A,10)
[1] 19.35484 14.51613 19.35484 17.74194 9.67742 11.29032 9.67742
17.74194 16.12903
[10] 11.29032
Min. 1st Qu. Median Mean 3rd Qu. Max.
9.677 11.290 15.320 14.680 17.740 19.350
[1] 14.67742
O primeiro vector contém os erros de cada uma das partições sendo a média dos
erros é 14.67742% e o desvio padrão 3.47. O erro médio do erro no discriminante linear
é de 14.19%.
21
3.2.3- Arvores de decisão vs Discriminante Linear
Na árvore de decisão a média dos erros é de 14.5% e desvio padrão 4.507 e o
erro médio é de 14.52%.
No discriminante linear a média dos erros é 14.67%, o desvio padrão 3.47 e o
erro médio é de 14.65%.
Logo para este quadro de dados parece-me que o melhor modelo é a árvore de decisão.
Cálculo do Intervalo de confiança
> errodislin<-c(19.35484, 14.51613, 19.35484, 17.74194, 9.67742,
11.29032, 9.67742, 17.74194, 16.12903, 11.29032)
> erroArv<-c(9.67742, 11.29032, 17.74194, 19.35484, 11.29032,
12.90323, 20.96774, 12.90323, 12.90323, 16.12903)
> t.test(errodislin,erroArv,paired=T)
Paired t-test
data: errodislin and erroArv
t = 0.0885, df = 9, p-value = 0.9314
alternative hypothesis: true difference in means is not equal to 0
95 percent confidence interval:
-3.961297 4.283877
sample estimates:
mean of the differences
0.16129
Como o p-value =0.9314> 0.05 concluo com 95% de confiança que os dois modelos são
bastante semelhantes para este caso, logo para escolher o método para classificar o
conjunto de teste vou olhar para os erros médios. Como no discriminante linear o erro é
superior decido a árvore de decisão
22
4- Previsão
Para prever as classes a que pertencem os indivíduos do conjunto de teste utilizo
a função predict do R.
Como escolhi a árvore de decisão como sendo o melhor método para este caso
uso o seguinte procedimento:
teste<-read.table('D:/economia/extrconhdados/trabalho2/teste.txt');
Arvore.prev<-predict(arvore.final,teste)
Neste derradeiro passo surgiu-me um problema que não consegui perceber, é que cada
vez que tentei fazer a previsão o R desliga-se acusando um erro.
23
5- Conclusão
Dos métodos utilizados no Weka o discriminante logístico apresenta maior taxa
de acerto que a árvore de decisão. Para o Caso em estudo a árvore de decisão apresenta-
se como sendo o método que melhor classificaria o conjunto de teste.
Este trabalho não me permite tirar conclusões do género “ o melhor método é…”
porque tudo depende dos casos. Cada método tem características que o tornam melhor
ou pior para classificar determinado quadro de dados.
Por exemplo a árvore de decisão obtida pelo R pode ser melhor ao pior que a
árvore obtida pelo J48,uma vez que usam medidas de partição diferentes, tudo depende
das características do conjunto de dados.
24
Bibliografia
[1]- Acetatos das aulas teóricas
[2]- “Data Mining” – Ian H. Witten, Eibe Frank;
[3]- “Análise de Algoritmos de Classificação”- Carla Sofia Figueiredo Carvalho;
[4]- “Machine Learning” – Tom M. Mitchell;
[5]- Guia prático-“Árvores de regressão”- do Professor Luís Torgo
[6]- Análise de algoritmos de Classificação-Carla Sofia Figueiredo Carvalho
25
Anexo 1 – Árvore de decisão J48
=== Run information ===
Scheme: weka.classifiers.trees.J48 -C 0.25 -M 2
Relation: treino_conj
Instances: 620
Test mode: 10-fold cross-validation
=== Classifier model (full training set) ===
J48 pruned tree
------------------
atr8 <= 0
| atr3 <= 0.165
| | atr5 <= 6: 0 (10.0)
| | atr5 > 6
| | | atr6 <= 4
| | | | atr2 <= 21.92: 0 (6.0/1.0)
| | | | atr2 > 21.92: 1 (9.0/2.0)
| | | atr6 > 4: 1 (2.0)
| atr3 > 0.165: 0 (269.0/11.0)
atr8 > 0
| atr9 <= 0
| | atr14 <= 445
| | | atr6 <= 5
| | | | atr13 <= 383
| | | | | atr4 <= 1
| | | | | | atr12 <= 1: 1 (3.0/1.0)
| | | | | | atr12 > 1: 0 (13.0/2.0)
| | | | | atr4 > 1
| | | | | | atr5 <= 9
| | | | | | | atr13 <= 112
| | | | | | | | atr14 <= 14: 1 (13.0/1.0)
| | | | | | | | atr14 > 14: 0 (4.0/1.0)
| | | | | | | atr13 > 112
| | | | | | | | atr14 <= 13: 0 (27.0/8.0)
| | | | | | | | atr14 > 13: 1 (3.0)
| | | | | | atr5 > 9: 1 (8.0)
| | | | atr13 > 383: 0 (8.0)
| | | atr6 > 5
| | | | atr14 <= 101
26
| | | | | atr4 <= 1
| | | | | | atr2 <= 36.75: 1 (5.0/1.0)
| | | | | | atr2 > 36.75: 0 (2.0)
| | | | | atr4 > 1
| | | | | | atr7 <= 4.335
| | | | | | | atr7 <= 1.665: 1 (6.0/1.0)
| | | | | | | atr7 > 1.665: 0 (3.0)
| | | | | | atr7 > 4.335: 1 (7.0)
| | | | atr14 > 101: 1 (3.0)
| | atr14 > 445: 1 (19.0/1.0)
| atr9 > 0: 1 (200.0/18.0)
Number of Leaves : 21
Size of the tree : 41
27
Anexo 2- Descriminante logistico-Weka
=== Run information ===
Scheme: weka.classifiers.functions.Logistic -R 1.0E-8 -M -1
Relation: treino_conj
Instances: 620
Test mode: 10-fold cross-validation
=== Classifier model (full training set) ===
Logistic Regression with ridge parameter of 1.0E-8
Coefficients...
Variable Coeff.
1 0.0844
2 -0.0085
3 0.0466
4 -0.6768
5 -0.1869
6 -0.0794
7 -0.0793
8 -3.3029
9 -0.4786
10 -0.1059
11 0.1902
12 -0.5434
13 0.0018
14 -0.0004
Intercept 6.5928
Odds Ratios...
Variable O.R.
1 1.088
2 0.9916
3 1.0477
4 0.5082
5 0.8295
6 0.9237
7 0.9238
8 0.0368
9 0.6196
10 0.8995
11 1.2095
12 0.5808
13 1.0018
14 0.9996
28
Anexo 3- Validação cruzada em R
Explicação detalhada do algoritmo
valcruz<-function(treino,k){
library(rpart)
Contagem do número de indivíduos no conjunto de treino A
Ncol<-nrow(A)
Geração de números aleatórios
permutar<-sample(num)
Divisão dos números aleatórios nos k=10 conjuntos para a amostragem
dim(permutar)<-c(k,as.integer(num/k))
Vector com os erros obtidos nos k conjuntos
erro<-rep(0,10)
Ciclo que vai obter os erros das k=10 repetições de teste da árvore obtida com os k-1=9
conjuntos
for (i in 1:k){
O subconjunto de treino possui as k-1=9 partições do conjunto de treino A.
teste<-treino[permutar[i,],]
Treino<-treino[-permutar[i,],]
Árvore de decisão que obtêm o modelo dos indivíduos de A cuja classe está na coluna
V15
arvore<-rpart(V15~.,treino)
Árvore podada
arvore.final<-valcruz.Poda(arvore)
Previsão dos individuos do conjunto de treino
Arvore.prev<-predict(arvore.final,teste,type="class")
Cálculo do erro de classificação
m.conf<-table(teste$V15,Arvore.prev)
elem.nao.diag<-col(m.conf)!=row(m.conf)
perc.erro<-100*sum(m.conf[elem.nao.diag])/sum(m.conf)
erro[i]<-perc.erro}
print(erro)
print(summary(erro))
mean(erro)}
29
Repetição do algoritmo anterior 100 vezes
Rep.100<-function(dados,k,n){
erro<-rep(0,n)
for(i in 1:n)
erro[i]<-valcruz(dados,k)}
summary(erro))}
Anexo4 - Discriminante Linear
val.cruz.descrmin.linear<-function(dados,k){
library(MASS)
num<-nrow(dados)
indices<-sample(num)
dim(indices)<-c(k,as.integer(num/k))
erros<-rep(0,10)
for(i in 1:k){
teste<-dados[indices[i,],]
treino<-dados[-indices[i,],]
disc<-lda(V15~.,treino,prior=c(1,1)/2,tol=1.0e-37)
previsao<-predict(disc,teste)$class
m.conf<-table(teste$V15,previsao)
elem.nao.diag<-col(m.conf)!=row(m.conf)
perc.erro<-100*sum(m.conf[elem.nao.diag])/sum(m.conf)
erros[i]<-perc.erro}
print(erros)
print(summary(erros))
mean(erros)
}
Rep.100<-function(dados,k,n){
erro<-rep(0,n)
for(i in 1:n)
erro[i]<-val.cruz.descrmin.linear(dados,k)}
summary(erro))}
30
Anexo – Tabela 1
“Data Mining”- Ian H. Witten
