Clustering ensembles: a hedonic game theoretical approach [Digital]
Tese
Português
681.3:004.8
Fortaleza, 2018.
Clustering ensembles (CE) é uma abordagem que se aproveita de um conjunto de cluster-
ings, conhecidos como partições-base, para produzir uma partição consenso. A literatura
tem demonstrado que a qualidade das partições obtidas pela abordagem CE é geralmente
superior à qualidade das partições-base,... Ver mais Clustering ensembles (CE) é uma abordagem que se aproveita de um conjunto de cluster-
ings, conhecidos como partições-base, para produzir uma partição consenso. A literatura
tem demonstrado que a qualidade das partições obtidas pela abordagem CE é geralmente
superior à qualidade das partições-base, quando consideradas individualmente. Este tra-
balho aborda o problema de CE sob a perspectiva dos jogos hedônicos. No jogo cooperativo
formulado, os pontos (instâncias ou objetos) são vistos como jogadores, enquanto os clus-
ters são encarados como coalizões. As preferências de cada jogador são armazenadas em
uma matriz de similaridade, obtida através das partições-base, que contém propriedades
que garantem a existência de pelo menos uma estrutura de coalizão Nash estável. Ou seja,
uma estrutura de coalizão em que os jogadores não possuem o incentivo de mudar de suas
próprias coalizões para outra coalizão existente. Para alcançar esse tipo de solução, nós
propusemos o algoritmo HGCE (Hedonic Game based Clustering Ensemble) que é baseado
na abordagem de best response dynamics. Inicialmente, cada jogador está em uma coalizão
com um elemento, composta por ele mesmo. Depois disso, em cada iteração, cada jogador
pode se mover para uma nova coalizão, caso ele obtenha um payoff melhor. Este processo
se repete até um equilíbrio ser alcançado, em que nenhum jogador se beneficia em mudar
de coalizão. Pelo fato de diferentes estruturas de coalizão emergirem de acordo com a
ordem dos jogadores, nós também desenvolvemos uma versão do algoritmo HGCE que é
independente da ordem dos jogadores. Experimentos empíricos conduzidos em diversos
conjuntos de dados mostram que a estrutura de coalizão obtida pelo algoritmo HGCE,
em grande parcela dos casos, é uma solução de clustering melhor quando comparada
com soluções obtidas por outros algoritmos que também adotam a abordagem de CE.
Os experimentos mostram que o HGCE é computacionalmente eficiente e se demonstra
resiliente a perturbações nas partições-base utilizadas como entrada do algoritmo.
Palavras-chave: Clustering, Clustering ensembles, Coalizão, Jogos hedônicos, Teoria dos
jogos cooperativos.
Ver menos
ings, conhecidos como partições-base, para produzir uma partição consenso. A literatura
tem demonstrado que a qualidade das partições obtidas pela abordagem CE é geralmente
superior à qualidade das partições-base,... Ver mais Clustering ensembles (CE) é uma abordagem que se aproveita de um conjunto de cluster-
ings, conhecidos como partições-base, para produzir uma partição consenso. A literatura
tem demonstrado que a qualidade das partições obtidas pela abordagem CE é geralmente
superior à qualidade das partições-base, quando consideradas individualmente. Este tra-
balho aborda o problema de CE sob a perspectiva dos jogos hedônicos. No jogo cooperativo
formulado, os pontos (instâncias ou objetos) são vistos como jogadores, enquanto os clus-
ters são encarados como coalizões. As preferências de cada jogador são armazenadas em
uma matriz de similaridade, obtida através das partições-base, que contém propriedades
que garantem a existência de pelo menos uma estrutura de coalizão Nash estável. Ou seja,
uma estrutura de coalizão em que os jogadores não possuem o incentivo de mudar de suas
próprias coalizões para outra coalizão existente. Para alcançar esse tipo de solução, nós
propusemos o algoritmo HGCE (Hedonic Game based Clustering Ensemble) que é baseado
na abordagem de best response dynamics. Inicialmente, cada jogador está em uma coalizão
com um elemento, composta por ele mesmo. Depois disso, em cada iteração, cada jogador
pode se mover para uma nova coalizão, caso ele obtenha um payoff melhor. Este processo
se repete até um equilíbrio ser alcançado, em que nenhum jogador se beneficia em mudar
de coalizão. Pelo fato de diferentes estruturas de coalizão emergirem de acordo com a
ordem dos jogadores, nós também desenvolvemos uma versão do algoritmo HGCE que é
independente da ordem dos jogadores. Experimentos empíricos conduzidos em diversos
conjuntos de dados mostram que a estrutura de coalizão obtida pelo algoritmo HGCE,
em grande parcela dos casos, é uma solução de clustering melhor quando comparada
com soluções obtidas por outros algoritmos que também adotam a abordagem de CE.
Os experimentos mostram que o HGCE é computacionalmente eficiente e se demonstra
resiliente a perturbações nas partições-base utilizadas como entrada do algoritmo.
Palavras-chave: Clustering, Clustering ensembles, Coalizão, Jogos hedônicos, Teoria dos
jogos cooperativos.
Ver menos
Clustering ensembles (CE) is an approach that takes advantage of a set of clusterings,
known as base partitions, to generate a consensus solution. The related literature has
shown that usually the consensus partition has better quality in comparison with the
single base partitions. This work tackles... Ver mais Clustering ensembles (CE) is an approach that takes advantage of a set of clusterings,
known as base partitions, to generate a consensus solution. The related literature has
shown that usually the consensus partition has better quality in comparison with the
single base partitions. This work tackles the CE problem from a hedonic game theoretical
perspective. In the formulated cooperative game, the points (instances or objects) are
viewed as players, while clusters are regarded as coalitions. The preferences of each player are stored in an evidence-accumulation matrix, obtained through the base partitions, which has properties that guarantee the existence of at least one Nash stable coalition structure.
That is, a coalition structure where players do not have the incentive to move from their
own coalition to another existent coalition. To achieve this kind of solution, we proposed
the HGCE (Hedonic Game based Clustering Ensemble) algorithm, which is based on the
best dynamics approach. Initially each player is in a singleton coalition, composed by itself.
After that, in each iteration, each player has the option to switch to a new coalition where
it will obtain a better payoff. This process repeats itself until it reaches an equilibrium,
where players do not benefit anymore by changing coalitions. Because different coalition
structures may emerge due to the order of the playes, we also developed a version of HGCE
where the final solution is independent of the players ordering. Empirical experiments
conducted on several data sets have shown that the coalition structure obtained by HGCE
is frequently a better clustering solution in comparison with clusterings generated from
others well known CE algorithms. The experiments also show that HGCE is computational
efficient and resilient to random perturbations on the base partitions used as input of the
algorithm.
Keywords: Clustering, Clustering ensemble, Coalition, Hedonic games, Cooperative game
theory. Ver menos
known as base partitions, to generate a consensus solution. The related literature has
shown that usually the consensus partition has better quality in comparison with the
single base partitions. This work tackles... Ver mais Clustering ensembles (CE) is an approach that takes advantage of a set of clusterings,
known as base partitions, to generate a consensus solution. The related literature has
shown that usually the consensus partition has better quality in comparison with the
single base partitions. This work tackles the CE problem from a hedonic game theoretical
perspective. In the formulated cooperative game, the points (instances or objects) are
viewed as players, while clusters are regarded as coalitions. The preferences of each player are stored in an evidence-accumulation matrix, obtained through the base partitions, which has properties that guarantee the existence of at least one Nash stable coalition structure.
That is, a coalition structure where players do not have the incentive to move from their
own coalition to another existent coalition. To achieve this kind of solution, we proposed
the HGCE (Hedonic Game based Clustering Ensemble) algorithm, which is based on the
best dynamics approach. Initially each player is in a singleton coalition, composed by itself.
After that, in each iteration, each player has the option to switch to a new coalition where
it will obtain a better payoff. This process repeats itself until it reaches an equilibrium,
where players do not benefit anymore by changing coalitions. Because different coalition
structures may emerge due to the order of the playes, we also developed a version of HGCE
where the final solution is independent of the players ordering. Empirical experiments
conducted on several data sets have shown that the coalition structure obtained by HGCE
is frequently a better clustering solution in comparison with clusterings generated from
others well known CE algorithms. The experiments also show that HGCE is computational
efficient and resilient to random perturbations on the base partitions used as input of the
algorithm.
Keywords: Clustering, Clustering ensemble, Coalition, Hedonic games, Cooperative game
theory. Ver menos
Sandes, Nelson Carvalho
Autor
Coelho, Andre Luis Vasconcelos
Orientador
Coelho, Andre Luis Vasconcelos
Banca examinadora
Dória Neto, Adrião Duarte
Banca examinadora
Faceli, Katti
Banca examinadora
Maia, José Everardo Bessa
Banca examinadora
Nepomuceno, Napoleão Vieira
Banca examinadora