Circuito digital

Um algoritmo de agrupamento baseado em conectividade gráfico

Análise de agrupamento, ou clustering, é o nome dado para o grupo de técnicas computacionais cujo propósito consiste em separar objetos em grupos, baseando-se nas características que estes objetos possuem. A idéia básica consiste em colocar em um mesmo grupo objetos que sejam similares de acordo com algum critério pré-determinado.

Neste artigo apresentamos um novo algoritmo de clustering. A abordagem apresentada

aqui é gráfico teórico . A semelhança de dados é utilizado para formar um gráfico similaridade em que os vértices correspondem a elementos e bordas conectar elementos com similaridade valores dade acima de certo valor . Nesse gráfico , clusters são altamente conectado subgraphs , definida como sub-gráficos cuja conectividade borda ultrapassar a metade do númerico de vértices . Usando algoritmos de cortes mínimos tais subgráficos pode ser calculado de forma eficiente . Provamos que

O algoritmo foi implementado e testado intensamente sobre a expressão do gene dados simulados e foi demonstrado que dão bons resultados mesmo na presença de níveis relativamente altos de ruído, e para superar um algoritmo anterior, para a probabilidade . Foi também obtido resultados promissores em um

teste cego com dados de expressão de genes experimental.

O artigo apresentou um algoritmo de agrupamento baseado em alta conectividade em gráficos, e demonstrou que gera soluções com propriedades desejáveis ​​para clustering. O algoritmo tem baixa complexidade polinomial. Ele também é eficiente na prática: A nossa implementação inicial, depois de algumas melhorias heurísticos como descrito no artigo lida com problemas bem com até milhareis de elementos em um tempo de computação razoável. Como observado na introdução, conectividade gráfico tem sido utilizado anteriormente para o agrupamento. nosso romance definição de subgráficos altamente ligados dá um parar critério, através da definição de grupos como subgraficos com conectividade que está acima de metade do número de vértices. Isto tem várias vantagens: Dá aglomerados com boas propriedades demonstráveis, e evita a necessidade de saber com antecedência ou adivinhar o número de aglomerados como.

O algoritmo HCS gera aglomerados com diâmetros dois. Este é um forte indício de homogeneidade, como quaisquer dois vértices são ou adjacente ou partilhar uma ou

vizinhos mais comuns. Esta propriedade não está satisfeito por as soluções Revista no artigo. Além disso, um caminho de comprimento arbitrário é um aglomerado de acordo com os exemplo mostrado no artigo, cortes mínimos nos subgraficos menores que eram obtido por remoção das bordos anterior de mincut partições. Parece que a forma de computação HCS

mincuts é mais apropriada para o agrupamento, porque o mincut bordas de divisórias anteriores correspondem as bordas erradas que ligam entidades enganodos clusters diferentes, por isso não há razão para toma-los em conta novamente em partições subsequentes. Para

exemplo.

Aluno: Marcos Felipe Coutinho Cruz

...