Manual de Utilizaç˜ao do sistema UOR

Manual de Utilização do sistema
UOR
Projecto oRANKI - Detecção de Casos Raros
usando Recursos Limitados.
Relatório oRANKI 2010/03
Luis Torgo - [email protected]
Rita P. Ribeiro - [email protected]
Projecto oRANKI - Detecção de Casos Raros usando Recursos Limitados
2
Conteúdo
1 Introdução
3
2 O método UOR
2.1 Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Saı́da . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
4
4
3 Exemplos de utilização
3.1 Exemplo 1: algae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Exemplo 2: sales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
5
7
Luı́s Torgo, Rita P. Ribeiro - LIAAD/INESC Porto LA
Projecto oRANKI - Detecção de Casos Raros usando Recursos Limitados
1
3
Introdução
O objectivo deste manual é descrever os objectivos e a forma de utilizar o programa UOR. O
principal objectivo deste programa é possibilitar a obtenção de rankings de utilidade. Dado um
conjunto de casos este programa vai fornecer um ranking dos mesmos de acordo com a utilidade
esperada de inspeccionar cada um deles.
Em problemas de detecção de fraude com recursos limitados de inspecção, é necessário atribuir
esses recursos aos casos mais promissores. Estes casos não são necessariamente aqueles que são
mais provavelmente fraudes. De facto, há outros factores a ter em conta. Concretamente, há a
considerar o custo da inspecção, que poderá não ser idêntico para todos os casos, e também o
resultado da inspecção se se confirmar o caso como fraudulento. Poderão existir casos que têm
maior probabilidade de serem fraudulentos mas que, ou por serem casos com baixo retorno ou
por existirem outros casos que custem bastante menos a serem inspeccionados, seja preteridos em
relação a outros com menor probabilidade. Neste contexto, propõem-se usar noções da teoria da
utilidade para obter rankings de utilidade de inspecção - que é o objectivo do programa UOR.
A utilidade de inspecção de um caso é estimada por,
E[Ui ] = P̂i · u(B̂i − Ĉi ) + (1 − P̂i ) · u(−Ĉi )
(1)
em que P̂i é a probabilidade estimada de i ser uma fraude, B̂i é o resultado esperado para a
inspecção do caso i se confirmado como fraude, Ĉi é o custo estimado da inspecção de i, e u(.) é
uma função de utilidade.
Mais informação sobre a metodologia pode ser obtida em Torgo e Lopes [3].
2
O método UOR
O método UOR implementa o Algoritmo 1 destinado a obter os valores envolvidos na Equação 1.
Algorithm 1 High-level description of the methodology.
1: procedure UOR(HistD, InspCand)
B em que HistD = {hx1 , · · · , xp , C, Bi},
InspCand = {hx1 , · · · , xp i},
and x1 , · · · , xp são variáveis descrevendo cada caso
2:
3:
4:
5:
B Passo 1 - Obter modelos de Custos e Benefı́cios
DSC ← {hx1 , · · · , xp , Ci ∈ HistD}
DSB ← {hx1 , · · · , xp , Bi ∈ HistD}
Cmodel ← RegressionT ool(DSC )
Bmodel ← RegressionT ool(DSB )
6:
B Passo 2 - Obter probabilidades de outlier para InspCand
P ← OutlierP robEstimator(HistD, InspCand)
7:
8:
9:
10:
11:
12:
13:
B Passo 3 - Estimar Utilidades
for all i ∈ InspCand do
Ci ← P redict(Cmodel , i)
Bi ← P redict(Bmodel , i)
EUi = Pi · u(Bi − Ci ) + (1 − Pi ) · u(−Ci )
end for
B Passo 4 - Obter rankings de utilidade (solução)
return InspCand ordenado por EUi decrescente
end procedure
Luı́s Torgo, Rita P. Ribeiro - LIAAD/INESC Porto LA
Projecto oRANKI - Detecção de Casos Raros usando Recursos Limitados
4
O método foi implementado na linguagem R [1]. A função UOR() implementa o Algoritmo 1 e
possui a seguinte descrição:
UOR(HD, ID, regrLearner, outLearner, uf = function(x) x,
descrCols=1:(ncol(HD)-3), costCol=ncol(HD)-2, benCol=ncol(HD)-1)
2.1
Parâmetros
A função UOR() tem uma série de parâmetros que são descritos em seguida:
ˆ HD - um data frame contendo dados históricos sobre inspecções efectuadas no passado. Para
cada linha é incluı́da informação sobre os descritores do caso, mas também o custo e a
resultado da inspecção.
ˆ ID - um data frame contendo os casos para os quais pretendemos um ranking the utilidade. Estes casos são descritos somente pelos descritores do problema uma vez que ainda
desconhecemos quer os custos quer os resultados das inspecções.
ˆ regrLearner - o nome de uma função do R que implementa um algoritmo de aprendizagem
de modelos de regressão múltipla.
ˆ outLearner - o nome de uma função do R que implementa um algoritmo de obtenção de
probabilidades de outliers.
ˆ uf - o nome de uma função de utilidade. Este parâmetro tem como valor por omissão uma
função de utilidade igual a u(x) = x, ou seja a função identidade.
ˆ descrCols - um vector com as colunas do data frame HD que são os descritores. Por omissão
serão todas as colunas menos as 3 últimas (que se assume conterem o custo, benefı́cio e
utilidade).
ˆ costCol - a coluna de HD com o custo. Por omissão será a 3 a contar do fim.
ˆ benCol - a coluna de HD com o benefı́cio. Por omissão será a 2 a contar do fim.
2.2
Saı́da
A função UOR() dá como resultado uma lista com as seguintes componentes:
ˆ EU - um vector com os valores estimados da utilidade para cada um dos casos em ID,
apresentados na ordem das linhas desse data frame.
ˆ EUrank - um vector com os mesmos valores de utilidade mas agora na ordem do rank
decrescente por valor de utilidade.
ˆ EC - um vector com os custos estimados para cada um dos casos em ID, apresentados na
ordem das linhas desse data frame.
ˆ EB - um vector com os resultados (benefı́cios) estimados para cada um dos casos em ID,
apresentados na ordem das linhas desse data frame.
ˆ outP - uma lista com duas componentes. A componente com o nome rank contêm um vector
com a posição no ranking de cada caso do data frame ID, na ordem original das linhas deste.
A componente com o nome score contêm um outro vector com o mesmo tamanho com as
probabilidades estimadas de ser outlier para cada linha de ID, apresentados na ordem das
linhas desse data frame.
Luı́s Torgo, Rita P. Ribeiro - LIAAD/INESC Porto LA
Projecto oRANKI - Detecção de Casos Raros usando Recursos Limitados
3
5
Exemplos de utilização
Os exemplos a seguir ilustram a forma de utlização da função UOR(). Eles usam diferentes
abordagens para a atribuição de benefı́cios e custos na identificação de outliers, e que estão
inerentes ao domı́nio do problema.
3.1
Exemplo 1: algae
O primeiro exemplo usa o conjunto de dados algae disponı́vel no package DMwR [2] que inclui o
registo de valores de concentração de 7 micro-algas nocivas em vários rios europeus. Cada registo
corresponde a uma amostra de água e é descrito por 11 variáveis, 3 contextuais para a identificação
da referida amostra (estação do ano, tamanho e velocidade do rio) e 8 parâmetros fı́sico-quı́micos
obtidos por testes feitos à qualidade da água da amostra. A recolha destes parâmetros para todas as
amostra de água é feita de forma automática. No entanto, a avaliação dos valores de concentração
de cada uma das micro-algas presentes na amostra, requer uma análise manual da mesma. O
objectivo deste problema consiste em prever/identificar o aparecimento da concentração excessiva,
também designada por blooms, destas algas nocivas. Estes blooms ainda que raros trazem sérios
impactos para a qualidade da água, tornando-a imprópria para consumo e inviabilizando os rios
como fonte de abastecimento de água potável.
Vamos aplicar o método de detecção de outliers baseado em utilidade, apresentado na Secção 2,
para identificar os top 20 outliers segundo o critério de utilidade para uma das 7 micro-algas, por
exemplo a alga a1. Pelo facto do método que iremos usar para ranking de outliers se basear no
cálculo de distâncias entre os casos, optámos por nos restringir aos dados numéricos, isto é, aos
valores dos 8 parâmetros fı́sico-quı́micos.
>
>
>
>
>
>
>
>
>
>
>
>
>
library(DMwR)
library(e1071)
source('DataAndCode/UOR.R')
source('DataAndCode/auxFunc.R')
data(algae)
a <- 1
descrVars <- 4:11
targetVar <- 11+a
algae <- na.omit(algae)
Algae <- algae[,descrVars]
AlgaeV <- algae[,targetVar,drop=F]
n <- NCOL(Algae)
m <- as.numeric(rownames(Algae))
Vamos agora dividir o conjunto de dados em dois conjuntos diferentes: um que guardará toda
a informação relacionada com o registo da concentração da micro-alga (histData) e outro onde
essa informação será omitida para possibilitar a inspecção dos blooms da micro-alga (inspData).
No conjunto histData foram incluı́dos 80% dos casos para a aprendizagem supervisionada e no
conjunto inspData, os restantes 20% dos casos para a aprendizagem não supervisionada. Sobre
os dados constantes no histórico, assumimos que os custos e os benefı́cios são definidos em função
valor de concentração da micro-alga a1 e da distância ao valor médio observado (thr). Os custos
são definidos por uma função sigmóide decrescente (cf) com centro em thr. nos dados de histórico.
Os benefı́cios são definidos por uma funcão sigmoı́de crescente (bf) com centro em thr.
>
>
>
>
>
>
>
percSup <- 0.8
set.seed(1)
supCases <- as.character(sample(m,as.integer(length(m)*percSup)))
inspCases <- as.character(m[!(m %in% supCases)])
thr <- mean(AlgaeV[supCases,1])
cf <- function(x) (1/(1+exp((x-thr)*thr)))
bf <- function(x) x*(1/(1+exp((thr-x)*thr)))
Luı́s Torgo, Rita P. Ribeiro - LIAAD/INESC Porto LA
Projecto oRANKI - Detecção de Casos Raros usando Recursos Limitados
>
>
>
+
>
>
6
c <- sapply(AlgaeV[supCases,1],cf)
b <- sapply(AlgaeV[supCases,1],bf)
histData <- as.data.frame(cbind(Algae[supCases,],
cost=c,benef=b,util=b-c))
descrVars <- 1:n
inspData <- as.data.frame(Algae[inspCases,descrVars])
Como algoritmo de regressão para a aprendizagem dos benefı́cios e custos, escolhemos as support
vector machines implementadas pela função svm disponı́vel no package e1071 [2]. Para a detecção
de outliers, escolhemos o método de ranking baseado nas diferenças dos grupos, implementado pela
função outliers.ranking, também disponı́vel no package DMwR [2]. Finalmente, como função de
utilidade usamos a função identidade definida por defeito.
> rm <- learner('svm',pars=list())
> om <- learner('orhCall',pars=list())
> urank <- UOR(histData,inspData,regrLearner=rm,outLearner=om)
De seguida, listamos os primeiros 20 outliers obtidos pelo algoritmo UOR.
>
>
>
+
+
+
>
>
uor.idx <- urank$EUrank[1:20]
idx <- as.numeric(names(urank$EU[uor.idx]))
uor.ds<-cbind(idx,AlgaeV[as.character(idx),1],
urank$EU[uor.idx],
urank$EC[uor.idx],urank$EB[uor.idx],
urank$outP$score[uor.idx])
colnames(uor.ds)<-c('idx','a1','EU','EC','EB','P(ORh)')
rownames(uor.ds)<- 1:20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
idx
53
29
15
111
22
19
46
68
177
115
153
20
35
51
89
193
108
155
133
160
a1
81.900
17.100
52.200
64.300
15.500
50.600
29.500
64.200
39.700
18.100
2.200
0.000
5.300
0.000
0.000
2.200
23.700
2.800
0.000
0.000
EU
EC
19.219 -0.126
14.133 0.071
13.416 0.124
12.294 0.339
11.842 0.132
9.790 0.317
9.670 0.638
8.396 0.227
7.400 0.283
7.031 0.421
5.596 0.840
4.361 0.845
3.714 0.864
3.694 0.631
3.669 0.854
3.468 0.522
3.281 0.804
2.897 0.826
2.826 0.881
2.514 0.711
EB P(ORh)
38.185
0.500
30.774
0.462
27.080
0.500
26.670
0.474
25.278
0.474
16.845
0.600
14.056
0.733
20.122
0.429
29.196
0.263
17.887
0.417
6.951
0.926
6.767
0.769
5.951
0.769
10.091
0.429
6.400
0.707
14.872
0.268
5.782
0.707
8.233
0.452
5.246
0.707
12.020
0.268
Tabela 1: Rankings de outliers do conjunto de dados algae para os valores de concentração da alga
a1
Por fim, para estes primeiros 20 outliers, podemos obter o ganho de utilidade, em percentagem,
que o método UOR apresentou face ao ranking de outliers que seria fornecido pelo método ORh,
apenas baseado nas probabilidades estimadas.
Luı́s Torgo, Rita P. Ribeiro - LIAAD/INESC Porto LA
Projecto oRANKI - Detecção de Casos Raros usando Recursos Limitados
UOR(ORh)
149.21001
7
P(ORh)
96.20206
O ganho de utilidade de UOR(ORh) face a P(ORh) é de
55.1 %.
O resultado confirma que ao escolhermos inspeccionar os casos sugeridos pelo algoritmo UOR
baseados na utilidade, obtemos um ganho claro comparativamente àquele que seria obtido se
fossem inspeccionados os casos sugeridos apenas por uma técnica de ranking de outliers standard.
3.2
Exemplo 2: sales
O segundo exemplo usa o conjunto de dados sales disponı́vel no package DMwR [2]. Neste conjunto
estão registadas vendas de vários produtos. O objectivo aqui é identificar transacções potencialmente fraudulentas para um dado produto ('p1000'), tendo em conta todas as transacções desse
produto. Existem transacções que já foram analisadas e identificados como ”fraude”ou ”ok”. Estas
transacções constituem o conjunto de histórico de transacções (histSales) sobre as quais será
feita a aprendizagem dos custos e benefı́cios e, portanto, da utilidade associada a cada transacção.
As restantes transacções integram o conjunto de transacções a inspeccionar (inspSales) com o
propósito de identicar outliers.
>
>
>
>
>
>
>
>
>
library(DMwR)
library(e1071)
library(dprep)
source('DataAndCode/UOR.R')
source('DataAndCode/auxFunc.R')
data(sales)
s <- sales[sales$Prod == 'p1000',c("Val","Quant","Insp")]
histSales <- na.omit(s[s$Insp != "unkn",])
inspSales <- na.omit(s[s$Insp == "unkn",-3])
Vamos aplicar o método de detecção de outliers baseado em utilidade, apresentado na Secção 2,
para identificar os top 20 outliers segundo o critério de utilidade. Neste contexto, começamos
por definir os custos e os benefı́cios associados às transacções já inspeccionadas. Começamos por
assumir que o trabalho de inspecção de uma transacção tem um custo fixo igual ao valor do número
de horas de trabalho envolvido, por exemplo 150. Contudo, o benefı́cio está dependente do conjunto
tı́pico de transacções do produto 'p1000'. Em concreto, estabeleceu-se que uma transacção será
potencialmente mais fraudulenta, e portanto a sua inspecção mais benéfica, quanto mais o preço
unitário envolvido (uPrice) se distanciar do preço unitário tı́pico (tPrice) obtido pela mediana
dos preços unitários, tendo em conta o intervalo de preços observados para 50% das transacções
(iqrPrice). Adicionalmente, quanto maior for o volume de vendas envolvido nestas transacções
fraudulentas, mais benéfica deverá ser a sua identificação. Em resumo, o benefı́cio da inspecção
de uma transacção é dado por uma espécie de outlying factor do preço (oPrice) calculado pela
funcção de benefı́cios (bf) abaixo definida. A utilidade é o resultado da diferença entre os benefı́cios
e os custos.
>
>
>
>
histSales$uPrice <- histSales$Val/histSales$Quant
tPrice <- median(histSales[histSales$Insp != "fraud", "uPrice"])
iqrPrice <- IQR(histSales[histSales$Insp != "fraud", "uPrice"])
cat('tPrice = ',tPrice,' iqrPrice = ',iqrPrice,"\n")
tPrice =
4.589007
iqrPrice =
2.016054
> bf <- function(x) {
+
if(x["Insp"] == "fraud")
+
oPrice <- (abs(as.numeric(x["uPrice"]) - tPrice)/iqrPrice) * as.numeric(x["Quant"])
+
else
+
oPrice <- 0
Luı́s Torgo, Rita P. Ribeiro - LIAAD/INESC Porto LA
Projecto oRANKI - Detecção de Casos Raros usando Recursos Limitados
8
+ }
> b <- apply(histSales,1,bf)
> histSales <- data.frame(Quant=histSales$Quant,Val=histSales$Val,
+
cost=150,benef=b,util=b-150)
À semelhança do que fizemos no exemplo anterior, escolhemos como algoritmo de regressão
para a aprendizagem dos benefı́cios e custos as support vector machines implementadas pela
função svm() disponı́vel no package e1071 [2]. Para a detecção de outliers, escolhemos o método
de ranking baseado nas diferenças dos grupos, implementado pela função outliers.ranking(),
também disponı́vel no package DMwR [2]. Finalmente, como função de utilidade usamos a função
identidade definida por defeito.
> rm <- learner('svm',pars=list())
> om <- learner('orhCall',pars=list())
> urank <- UOR(histSales,inspSales,regrLearner=rm,outLearner=om)
Na Tabela 2 estão listadas as 20 primeiras transacções identificadas pelo algoritmo UOR, por
ordem decrescente de utilidade. A fim de comprovar que o algoritmo UOR é capaz de fornecer um
ranking de transacções a inspeccionar potencialmente mais útil do que aquele que seria fornecido
pelo método standard de ranking de outliers.
>
>
>
>
>
+
+
+
+
+
+
>
+
>
uor.idx <- urank$EUrank[1:20]
idx <- names(urank$EU[uor.idx])
uPrice <- as.numeric(inspSales[idx,"Val"]/inspSales[idx,"Quant"])
oPrice <- abs(uPrice - tPrice) * inspSales[idx,"Quant"]
uor.ds<-cbind(as.numeric(idx),
inspSales[idx,"Quant"],inspSales[idx,"Val"],
uPrice,oPrice,
urank$EU[uor.idx],
urank$EC[uor.idx],
urank$EB[uor.idx],
urank$outP$score[uor.idx])
colnames(uor.ds)<-c('idx','Quant','Val','uPrice','oPrice',
'EU','EC','EB','P(ORh)')
rownames(uor.ds)<- 1:20
Podemos observar que para os primeiros 20 casos, o ranking de outliers produzido pelo algoritmo UOR() é diferente daquele que seria produzido pelo algoritmo outliers.ranking().
Para além disso, e face aos critérios de utilidade por nós estabelecido, o algoritmo UOR() leva à
identificação das 20 transacções suspeitas com maior volume de vendas envolvido o que se traduz
num ganho de utilidade é de cerca 34%, conforme mostram os resultados abaixo.
UOR(ORh)
P(ORh)
58305.95 43498.61
O ganho de utilidade de UOR(ORh) face a P(ORh) é de
34 %.
Luı́s Torgo, Rita P. Ribeiro - LIAAD/INESC Porto LA
9
Projecto oRANKI - Detecção de Casos Raros usando Recursos Limitados
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
idx Quant
Val uPrice
oPrice
290867
2794
2455
0.879 10366.686
362786
1627
9100
5.593 1633.686
128802
2161
4235
1.960 5681.844
362810
655
5420
8.275 2414.200
362769
213
1990
9.343 1012.542
290818
213
1990
9.343 1012.542
178906
3600
7565
2.101 8955.425
362746
1600
9655
6.034 2312.589
178907
3433
7075
2.061 8679.061
39730
3433
7185
2.093 8569.061
178908
2336 10365
4.437
354.920
290795
213
1990
9.343 1012.542
39714
916
4810
5.251
606.470
5153
922
5105
5.537
873.936
80475
6425 21980
3.421 7504.370
128793
266
2325
8.741 1104.324
178919
1588
1835
1.156 5452.343
39703
627
5515
8.796 2637.693
290784
213
1990
9.343 1012.542
178911
1416
1860
1.314 4638.034
EU
3685.232
3141.386
3128.074
3007.194
2997.460
2927.516
2927.263
2918.077
2915.828
2913.045
2871.312
2842.030
2802.095
2800.334
2765.886
2746.166
2738.995
2737.627
2735.172
2705.256
EC
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
150.000
EB P(ORh)
4572.777
0.839
4114.233
0.800
4370.765
0.750
3946.492
0.800
3846.895
0.818
3846.895
0.800
4615.895
0.667
4090.769
0.750
4598.742
0.667
4594.567
0.667
4229.837
0.714
3846.895
0.778
4025.585
0.733
4023.183
0.733
3887.848
0.750
3861.555
0.750
4248.522
0.680
3937.674
0.733
3846.895
0.750
4198.907
0.680
Tabela 2: Rankings de outliers do conjunto de dados sales para as transacções do produto p1000.
Referências
[1] R Development Core Team. R: A Language and Environment for Statistical Computing. R
Foundation for Statistical Computing, 2008. ISBN 3-900051-07-0.
[2] L. Torgo. Data Mining with R, learning with case studies. Chapman and Hall/CRC, 2010.
[3] L. Torgo and E. Lopes. Utility-based fraud detection. In T. Walsh, editor, Proceedings of
22th International Joint Conference on Artificial Intelligence (IJCAI’2011), pages 1517–1522.
AAAI Press, 2011.
Luı́s Torgo, Rita P. Ribeiro - LIAAD/INESC Porto LA