Controle de inferência para sistemas de base de
dados estatísticos
Erlon Rodrigues Cruz
Roteiro
Privacidade em bases de dados
Base de dados estatísticas
Garantindo a privacidade
Perturbando os dados
Reconstruindo a distribuição
Classificação dos dados em árvore de decisão
Conclusão
Bibliografia
Privacidade em bases de dados
A falta de privacidade na internet e meios de
comunicação em geral pode fazer com que os
usuários da internet se ponham em uma postura
defensiva ao ser questionados em algum tipo de
questionários.
Registros detalhados de cartão de crédito de um
indivíduo podem revelar seu estilo de vida.
Isto prejudicaria não só as empresas mas também
as pessoas que deixariam de receber os avanços
provenientes da mineração de dados.
Privacidade em bases de dados
Quem se importa com privacidade?[Cranor]
17% dos usuários como fundamentalistas
56% concordaria em fornecer dados desde que fosse
mostrada alguma forma para proteção
27% forneceria dados de qualquer forma
Pessoas podem não querer divulgar determinados
dados enquanto não se importam com outros!
Pessoas podem não ter controle ou mesmo não saber
dos dados que são armazenados. Ex. Base de dados
com informações medidas através de exames nos
pacientes, registro de compras de um cartão de
crédito.
A coleta de dados
O quem terá acesso às informações que eu irei fornecer?
Funcionários maliciosos
Venda de informações ou pela empresa, ou por algum de seus
funcionários
A própria organização
Base de dados acessadas por muitos usuários.
Como proteger os dados dos registros e possibilitar que
possa ser extraída alguma informação dos mesmos?
A criação de barreiras legais para prover privacidade pode
fazer com que seja necessário novos mecanismos para se
atingir privacidade.
Meta a ser atingida: Saber a distribuição dos dados e ser
capaz de criar relações entre os dados protegendo os
registros individuais.
Garantindo a privacidade
Formas inibidoras
Auditoria dos acessos à base
Formas restritivas
Controle de acesso as diversas tabelas do banco
Ex. Médicos possuem acessos a dados de todos pacientes
Aos funcionários é dados acesso somente às somas estatísticas destes
dados
Formas não-restritivas
Agregação de valores
Distorção de valores
Dissociação dos dados
Duas técnicas serão mostradas
Criar uma base de dados que proteja
os registros e forneça dados
estatísticos, i.e., distribuição dos
valores, média, soma, etc.
Criar uma base de dados que proteja
os registros e não altere nas
correlações entre os campos.
Base de dados estatística
O objetivo de uma base de dados estatística é prover
freqüências, médias, somas e outras estatísticas referente à
grupos, pessoas e organizações, protegendo os indivíduos
representados na base de dados.
Um exemplo de base de dados estatística:
Questionário econômico financeiro.
Coletando dados
Válido somente para dados numéricos!
Foco nos dados que os usuários não querem
fornecer
Perturbando os dados
Os valores fornecidos devem de alguma forma serem
alterados antes que seja feita sua inserção na base.
Dois métodos para modificação são considerados:
Discretização
Distorção de valor: seja xi o campo a ser alterado
Uniforme: é somado à xi o valor aleatório r є[-α,+ α], sendo
que a distribuição de xi dentro do intervalo é linear.
Gaussiana: é somado à xi o valor aleatório r є[α,+ α], sendo que a distribuição de xi dentro
do intervalo é uma gaussiana
Quantificação da privacidade
Se o valor original x pode ser estimado com uma confiança
de c% implicando que x esteja no intervalo [x1,x2], então a
amplitude do intervalo(x2-x1) quantifica a privacidade
oferecida com c% de confiança.
W = 2α
Aumentando o intervalo α aumentamos o nível de
privacidade
Intervalo de confiança
Distribuição normal
Dados concentrados sobre a média: Menor variância –
Linha Amarela
Dados dados mais dispersos: Maior variância – Linha Azul
Intervalo de confiança
Podemos estimar a probabilidade ‘c’ de que um valor esteja entre –z e z
Reconstrução da distribuição original
A técnica só é útil se pudermos reconstruir a
distribuição dos registros originais a partir dos registros
alterados!!!
Será reconstruída a distribuição e não os registros
individuais.
Definições:
Valores originais: n valores, x1,x2,...,xn.
Amostra aleatória igualmente distribuída: X1,X2,...Xn
Variáveis aleatórias para esconder os dados: Y1,Y2,...Yn.
Fy é a função de distribuição de X1+Y1,X2+Y2,...Xn+Yn
Fx é a função de distribuição original para X.
wi = (xi + yi)
Reconstrução da distribuição original
Uma vez que conhecemos as distribuições de Yi,
e wi e wi = (Yi + Xi), podemos saber a
distribuição de Xi através do Teorema de Bayes
Teorema de Bayes para probabilidade:
Reconstrução da distribuição original
Reconstrução da distribuição original
Reconstrução da distribuição original
Média da função de distribuição para cada Xi:
Após a diferenciação:
Com uma amostragem suficientemente grande,
espera-se que f ’x seja bastante aproximado a
função real fx.
Reconstrução da distribuição original
Portanto, nós conhecemos somente fy, não fx.
Assim, usaremos uma distribuição uniforme como
estimativa inicial para fºx e refinaremos
iterativamente aplicando o seguinte algoritmo:
Critério de parada
O critério de parada da iteração é satisfeito quando
a distribuição reconstruída é estatisticamente igual
à distribuição original. Digamos:
Avaliação
Distorção de valor gaussiana:
Avaliação
Distorção de valor linear:
A inserção de ruídos na base de dados
pode trazer efeitos indesejados
[Zahidul]
Interferência na variância (Tipo A)
Interferências nas correlações entre atributos
confidenciais (Tipo B)
Interferências nas correlações entre atributos
confidenciais e não confidenciais (Tipo C)
A seguinte solução propõe uma forma de alterar os dados
sem criar as interferências referidas acima.
A avaliação é feita sobre árvores de decisão.
Classificação dos dados na árvorede
decisão
Uma árvore de decisão é um discriminador de classes que
recursivamente particiona o conjunto de dados até que
cada partição consista inteira ou dominantemente de
dados da mesma classe.
Cada nó não folha contém um split-point que testa um ou
mais atributos e determina como os dados serão
particionados.
Classificação dos dados na árvorede
decisão
Uma árvore de decisão pode ser usada para delinear o
perfil de futuros aplicadores classificando-os segundo sua
categoria de risco.
Caracterização dos dados utilizados
Neste estudo foi utilizado uma base de dados do
Wisconsin Breast Cancer (WBC).
O conjunto de dados possui 10 atributos numéricos cujo
domínio é são os inteiros entre 1 e 10 e um atributo de
classe ‘2’ ou ‘4’.
O gerador da árvore foi o Quinlan’s C5 nos 349 casos da
base de dados do WBC
Árvore gerada com os dados não
modificados
Passos para modificar os dados
1 – Adicionar ruído aos atributos influentes
(LINAs) de cada folha da árvore através da
técnica Leaf Influential Attribute Perturbation
Technique(LINAPT).
2 – Adicionar ruído aos atributos não influentes
(LIAs) de cada folha da árvore através da técnica
(LINAPT).
3 – Adicionar ruídos aos atributos de classe
através da técnica Randon Perturbation Technique
(RPT).
Definições
A técnica considera que todos os atributos são
sensíveis para evitar a identificação de algum
registro particular.
Divide-se os atributos numéricos em dois tipos:
LIAs e LINAs
Atributos numéricos variam de 1-10
Atributos de classe podem ser 2 ou 4.
Passo 1
Para cada folha da árvore identifica-se os LINAs
da folha. Seja A um LINA.
A’ = A + ε
ε é um ruído discreto com média μ e σ². A
distribuição é escolhida de acordo com a
aplicação.
A’ continua pertencendo ao intervalo definido
pelo valor condicional.
Passo 2
Para cada folha da árvore identifica-se os LIAs da
folha. Seja B um LIA.
B’ = B + ε
ε é um ruído discreto com média μ e σ². A
distribuição é escolhida de acordo com a
aplicação.
μ = 0 e σ = 27.6% do atributo do valor em
questão.
Passo 3
Para cada folha da árvore identifica-se os campos
de classe. Verifica-se se os campos são
heterogêneos.
Converte-se os n casos que pertencem a minoria
para a maioria.
Converte-se aleatoriamente n casos da maioria
para a minoria. σ = 27.6% do atributo do valor
em questão.
Resultados
Em 7 dos 15 experimentos realizados as árvores lógicas com
dados perturbados foram exatamente iguais à original.
Em 5 casos alguns dados diferiram porém a extrutura da árvore
não foi alterada.
Resultados
Em dois casos a extrutura da árvore foi ligeiramente
modificada.
Conclusões
É possível manter a privacidade de um banco de dados
alterando-se aleatóriamente os campos sem perder dados
estatísticos e interrelacionados.
Existem ainda muitas outras técnicas.
Lattice Model
Cell Restriction
Random Sample Queries
Systematic rounding and systematic ranges
Dynamic Databases
Bibliografia
[Agrawal] – “Privacy-preserving Data Mining”
[Fonseca] – “Curso de estatística”
[Denning] – “Inference controls for Statistical Databases”
[Crannor] – “Beyond Concern: Undertanding Internet
User”