Theme 1: Types of entrepreneurs

6.2

Descrição do Algoritmo

O algoritmo proposto é baseado na premissa de que restrições são definidas em relação a um conceito mais abstrato do que o de grupos. Especificamente, grupos são usualmente definidos em termos de similaridades no espaço de atributos. No entanto, em diversas aplicações, restri- ções ML e CL são derivadas de rótulos de classes, ou fornecidas por especialistas de domínio que normalmente não possuem conhecimento sobre a distribuição espacial dos dados. Portanto, nestas aplicações, é esperado que a premissa de um grupo por classe tenha poucas chances de ser válida.

As premissas fundamentais do MCCK são: (i) existe uma bijeção entre classes e chunklets3_; (ii) se um objeto está em um restrição CL, ele está envolvido em pelo menos uma restrição ML. Embora essas possam ser consideradas premissas fortes, pode-se verificar que elas são válidas se todas as restrições forem derivadas de objetos rotulados4 _{e se existirem pelo menos dois} objetos rotulados de cada classe. Com tais premissas e com o conjunto de restrições estendido (e.g., pela regra de transitividade — Seção 4.2), é garantido que cada objeto envolvido em uma restrição também é um membro de um chunklet.

É comum inicializar algoritmos de ADR utilizando chunklets. Por exemplo, em Wagstaff et al. (2001); Bilenko et al. (2004) os protótipos são inicializados pelo centróide do chunklet. Se a premissa de um grupo por classe não é válida, o centróide de um chunklet pode estar em uma região vazia. A Figura 6.1(a) ilustra uma situação em que os centróides dos (dois) chunklets estão próximos do centróide da base de dados, em uma região em que não existem objetos. Para evitar esta deficiência, no MCCK os protótipos são inicializados com objetos selecionados aleatoriamente em cada chunklet. Portanto, o número de grupos inicial, que é ajustado durante o processo de agrupamento, é igual ao número de chunklets/classes.

Para simplificar a explicação do MCCK, considere em conjunto com a notação apresen- tada no Capítulo 4, a representação de restrições de forma matricial. Nesta representação, um conjunto de restrições é representada por uma matriz simétrica RN×N cujos elementos são de- finidos da seguinte forma:

rij =           

1, se existe uma restrição ML entre xi e xj,

−1, se existe uma restrição CL entre xi e xj,

0, caso contrário.

(6.1)

Intuitivamente, se uma restrição é violada quando um objeto é rotulado para um grupo, então o número de grupos (para aquela classe em particular) deve ser insuficiente, e um novo grupo é criado a partir daquele objeto. Esta abordagem também ameniza o efeito outlier, já que as restrições passam a ter um efeito espacial na vizinhança dos objetos envolvidos nas restrições.

3_{A definição de chunklets encontra-se na Seção 4.2.}

Devido ao processo de criar grupos, é necessário um mapeamento de quais grupos pertencem a quais classes. Inicialmente, esse mapeamento tem uma correspondência de 1-para-1 entre chunklets e grupos. Quando novos grupos são criados, este mapeamento é atualizado — este procedimento é descrito em mais detalhes na sequência.

Objetos que não estão envolvidos em restrições são rotulados para os grupos mais próximos. No entanto, objetos envolvidos em restrições apenas são rotulados para um grupo se nenhuma restrição for violada. Como assume-se que uma classe pode ser representada por mais de um grupo, as restrições não são verificadas considerando apenas os objetos de cada grupo. Ao invés disso, são consideradas as classes conjuntamente com seus respectivos grupos. Por exemplo, suponha que xn foi rotulado para um grupo Ck, que rnj = 1 e que cm é o protótipo mais

próximo de xj. Então, xj é rotulado para o grupo Cm apenas se Cm e Ck pertencem à mesma

classe — isto é verificado pelo mapeamento discutido anteriormente. Se os grupos pertencem a classes diferentes, então um novo grupo é criado, com seu protótipo igual a xj. Para atualizar o

mapeamento, inicialmente a classe do chunklet a que xnpertence é identificada. Então, o novo

grupo é adicionado no mapeamento da classe. Pode-se verificar que este processo é sensível a ordem em que os dados são processados. Para amenizar isto, a cada iteração os objetos são processados em ordem aleatória. Depois de todos os objetos serem rotulados para algum grupo, os protótipos (neste caso centróides) são atualizados.

Como a criação dos grupos também é sensível à ordem de apresentação dos objetos, grupos desnecessáriospodem surgir. Considera-se um par de grupos como desnecessários (redundan- tes) quando seus protótipos são vizinhos mais próximos mútuos e eles pertencem à mesma classe. Portanto, após a atualização dos protótipos, é verificado se algum par de grupos atende este critério. Se for o caso, estes grupos são unidos. O protótipo do novo grupo é definido como sendo a média dos dois protótipos unidos. Após essa etapa, o mapeamento entre grupos e classes é atualizado.

Os passos principais do MCCK são apresentados no Algoritmo 15. O Passo 11 verifica se a rotulação irá causar alguma violação. Note que embora as restrições ML não sejam verificadas diretamente, estas estão sendo implicitamente examinadas ao se verificar as classes/chunklets. Como cada grupo pertence a apenas uma classe, as restrições ML não serão violadas, desde que objetos em uma mesma restrição ML pertençam a grupos da mesma classe. Os mesmos critérios de parada utilizados no K-means são adotados, e.g., um número máximo de iterações ou uma distância mínima entre centróides de iterações consecutivas.

Utilizando o resultado do MCCK, o analista de dados pode sumarizar as classes apropriada- mente e analisar suas principais características. Por exemplo, a partir dos grupos que represen- tam cada classe, estatísticas de interesse podem ser derivadas. Adicionalmente, os protótipos dos grupos (i.e., centróides ou objetos representativos) podem ser usados para um melhor enten- dimento dos dados. Tais informações também podem ser usadas para construir classificadores em uma tarefa subsequente — e.g., como dados de entrada para um classificador k-NN (Aha et al., 1991).

6.2 Descrição do Algoritmo 91

Algoritmo 15: Algoritmo MCCK Entrada:_{X conjunto de objetos;}

Rmatriz de restrições;

Saída:_{Hi}gi=1(mapeamento) e {Ci}ki=1(partição dos dados) 1 Encontra g chunklets formados por restrições ML;

2 k ← g // número de grupos inicial igual ao número de chunklets

3 para cadaj ∈ {1, . . . , k} faça

4 Seja x_rum objeto selecionado aleatoriamente do j-ésimo chunklet; 5 c_j ← x_r;

6 Hj ← {j} // Mapeamento entre grupos e chunklets (classes)

7 fim

8 para cada xi ∈ X faça

9 n← arg min_{n∈{1,...,k}}kx_i− c_nk2; 10 Considere que n ∈ H_cn;

11 se{∃a, j, s|(ria =−1) ∧ (xa∈ Cj)∧ (Cj ∈ Hs)∧ (s = cn)} então

12 k← k + 1;

13 Considere que x_i pertence ao l-ésimo chunklet; 14 Hl ← Hl∪ {k}; 15 c_k← x_i; C_k ← {x_i}; 16 senão 17 C_n ← C_n∪ {x_i}; 18 fim 19 fim 20 Atualiza protótipos ;

21 para cada par(C_p, C_q) de grupos faça 22 n← arg min_{n∈{1,...,k}\{p}}kc_p− c_nk2; 23 m← arg min_{m∈{1,...,k}\{q}}kc_q− c_mk2; 24 Considere que p ∈ H_cp; 25 Considere que q ∈ Hcq; 26 sec_p = c_q∧ n = q ∧ m = p então 27 Une grupos C_p e C_q; 28 Atualiza mapeamento Hcp; 29 fim 30 fim