Clustering com base em pontuações de similaridade

17

Assume-se que temos um conjunto de elementos de E e uma similaridade ( não distância ) função SIM (EI, ej) entre dois elementos ei, ej ∈ E .

Como poderíamos (eficientemente) agrupar os elementos de E usando sim ?

k significa, por exemplo, requer um determinado k , o Canopy Clustering requer dois valores limite. E se não quisermos parâmetros predefinidos?

Observe que esse sim não é necessariamente uma métrica (ou seja, a desigualdade do triângulo pode ou não se mantém). Além disso, não importa se os clusters são disjuntos (partições de E ).

clustering algorithms similarity vefthym
fonte
2
Eu me pergunto por que você enfatizou que não tem distância. Não sou especialista aqui, mas me pergunto se não seria possível converter essa semelhança em uma distância, se necessário, basicamente considerando sua inversa. Independentemente disso, duvido que haja algoritmos de agrupamento completamente livres de parâmetros, portanto, provavelmente será necessário algum ajuste em todos os casos. Quando você considerou k-Means, pode-se supor que você tenha propriedades com valor real (particularmente, que você pode usar a "média" de vários elementos)?
Marco13
4
Você não precisa saber k para executar k significa. Você pode agrupar com diferentes ke verificar a variação do agrupamento para encontrar o ideal. Como alternativa, você pode optar por modelos de mistura gaussianos ou outro processo de restauração, como itens para ajudá-lo a se agrupar.
Cwharland
2
Fiz as perguntas por um motivo específico: se você pudesse aplicar o k-Means, mas o único problema fosse encontrar o "k" inicial, considere um en.wikipedia.org/wiki/Self-organizing_map como uma alternativa. Ele possui algumas boas propriedades e basicamente se comporta "semelhante" ao k-Means, mas não requer que o "k" inicial seja definido. Provavelmente não é uma solução pronta para uso, porque possui parâmetros de ajuste adicionais (e o treinamento pode ser computacionalmente caro), mas vale a pena dar uma olhada.
Marco13
2
A escolha inicial de k influencia os resultados do cluster, mas você pode definir uma função de perda ou, mais provavelmente, uma função de precisão que informa sobre cada valor de k que você usa para agrupar, a relativa semelhança de todos os assuntos nesse cluster. Você escolhe o k que minimiza a variação nessa semelhança. O GMM e outros processos dirichlet cuidam muito bem do problema do não-saber-k. Um dos melhores recursos que eu já vi sobre isso é o tutorial de Edwin Chen .
Cwharland 17/05
4
Apenas um pensamento: se sua pontuação de similaridade for normalizada para 1 , então 1-sim(ei, ej) = Distance. Com a métrica de distância, você pode aplicar, por exemplo, cluster hierárquico. Ao descer da raiz, você verá em que nível de clusters de granularidade faria sentido para o seu problema específico.
Olexandr Isayev

Respostas:

8

  1. Eu acho que vários algoritmos de clustering que normalmente usam uma métrica, na verdade não dependem das propriedades da métrica (exceto a comutatividade, mas acho que você teria isso aqui). Por exemplo, o DBSCAN usa bairros epsilon em torno de um ponto; não há nada lá que diga especificamente que a desigualdade do triângulo é importante. Portanto, você provavelmente pode usar o DBSCAN, embora seja necessário fazer algum tipo de índice espacial fora do padrão para fazer pesquisas eficientes no seu caso. Sua versão do bairro epsilon provavelmente será sim> 1 / epsilon, e não o contrário. Mesma história com k-means e algoritmos relacionados.

  2. Você pode construir uma métrica a partir da sua semelhança? Uma possibilidade: dist (ei, ej) = min (sim (ei, ek) + sim (ek, ej)) para todos os k ... Como alternativa, você pode fornecer um limite superior para que sim (ei, ej) <sim (ei, ek) + sim (ek, ej) + d, para todos k e alguma constante positiva d? Intuitivamente, grandes valores de sim significam mais próximos: 1 / sim é semelhante à métrica? E quanto a 1 / (sim + constante)? E quanto a min (1 / sim (ei, ek) + 1 / sim (ek, ej)) para todos os k? (esse último é garantido como uma métrica, btw)

  3. Uma construção alternativa de uma métrica é fazer uma incorporação. Como primeiro passo, você pode tentar mapear seus pontos ei -> xi, de modo que xi minimize a soma (abs (sim (ei, ej) - f (dist (xi, xj)))), para algumas funções adequadas m e métricas dist. A função f converte a distância na incorporação em um valor semelhante à similaridade; você teria que experimentar um pouco, mas 1 / dist ou exp ^ -dist são bons pontos de partida. dimensão para xi A partir daí, você pode usar o cluster convencional no xi. A idéia aqui é que você pode quase (no melhor sentido) converter suas distâncias na incorporação em valores de similaridade, para que eles se agrupem corretamente.

  4. No uso de parâmetros predefinidos, todos os algoritmos têm algum ajuste. O DBSCAN pode encontrar o número de clusters, mas você ainda precisa fornecer alguns parâmetros. Em geral, o ajuste exige várias execuções do algoritmo com valores diferentes para os parâmetros ajustáveis, juntamente com alguma função que avalia a qualidade do clustering (calculada separadamente, fornecida pelo próprio algoritmo de clustering ou apenas com os olhos :) :) Se o caractere de seus dados não mudam, você pode ajustar uma vez e depois usar esses parâmetros fixos; se mudar, você precisará ajustar para cada execução. Você pode descobrir isso ajustando cada execução e comparando o quão bem os parâmetros de uma execução funcionam em outra, em comparação com os parâmetros especificamente ajustados para isso.

Alex I
fonte
7

Alex fez vários pontos positivos, embora eu possa ter que recuar um pouco sobre sua implicação de que o DBSCAN é o melhor algoritmo de clustering usado aqui. Dependendo da sua implementação, e se você está usando índices acelerados (muitas implementações não), sua complexidade de tempo e espaço será O(n2), o que está longe de ser o ideal.

Pessoalmente, meus algoritmos de clustering são OpenOrd para clustering vencedor leva tudo e FLAME para clustering fuzzy. Ambos os métodos são indiferentes se as métricas usadas são semelhança ou distância (o FLAME em particular é quase idêntico em ambas as construções). A implementação do OpenOrd no Gephi é O(nlogn)e é conhecida por ser mais escalável do que qualquer outro algoritmo de agrupamento presente no pacote Gephi.

O FLAME, por outro lado, é ótimo se você estiver procurando por um método de agrupamento difuso. Embora a complexidade do FLAME seja um pouco mais difícil de determinar, uma vez que é um processo iterativo, mostrou-se sub-quadrático e semelhante em velocidade de execução a knn.

indico
fonte
4

O DBSCAN (consulte também: DBSCAN generalizado) não requer distância. Tudo o que precisa é de uma decisão binária . Geralmente, seria usado "distance <epsilon", mas nada diz que você não pode usar "similarity> epsilon". Desigualdade de triângulo, etc., não são necessárias.

A propagação de afinidade, como o nome diz, usa semelhanças.

O cluster hierárquico, exceto talvez o vínculo de Ward, não faz nenhuma suposição. Em muitas implementações, você pode usar distâncias negativas quando tiver semelhanças, e isso funcionará bem. Porque tudo o que é necessário é min, max e <.

O k-means do kernel pode funcionar SE a sua semelhança for uma boa função do kernel. Pense nisso como computação k-means em um espaço vetorial diferente, onde a distância euclidiana corresponde à sua função de similaridade. Mas então você precisa saber k.

PAM (K-medoids) deve funcionar. Atribua cada objeto ao medóide mais semelhante, depois escolha o objeto com a maior semelhança média com o novo medóide ... nenhuma desigualdade de triângulo é necessária.

... e provavelmente muitos mais. Existem literalmente centenas de algoritmos de agrupamento. A maioria deve funcionar IMHO. Muito poucos parecem realmente exigir propriedades métricas. O K-means tem provavelmente os requisitos mais fortes: minimiza a variação (não a distância ou a semelhança) e você deve poder calcular os meios.

Anony-Mousse -Reinstate Monica
fonte