Comment trouver des poids pour une mesure de dissimiliarité

9

Je veux apprendre (déduire) les poids d'attribut pour ma mesure de dissimilarité que je peux utiliser pour le clustering.

J'ai quelques exemples de paires d'objets qui sont "similaires" (devraient être dans le même cluster), ainsi que quelques exemples ( c i , d i ) de paires d'objets qui ne sont "pas similaires" "(ne doit pas être dans le même cluster). Chaque objet a un certain nombre d'attributs: si vous le souhaitez, nous pouvons considérer chaque objet comme un vecteur d'entités en d dimensions, où chaque entité est un entier non négatif. Existe-t-il des techniques pour utiliser de tels exemples d'objets similaires / dissemblables pour estimer à partir d'eux des poids de caractéristiques optimaux pour une mesure de dissimilarité?(ai,bi)(ci,di)d

Si cela aide, dans mon application, il serait probablement raisonnable de se concentrer sur l'apprentissage d'une mesure de dissimilarité qui est une norme pondérée L2:

d(x,y)=jαj(x[j]y[j])2.

où les poids ne sont pas connus et doivent être appris. (Ou, une sorte de mesure de similitude cosinus pondérée pourrait également être raisonnable.) Existe-t-il de bons algorithmes pour apprendre les poids α j pour une telle mesure? Ou existe-t-il d'autres méthodes d'apprentissage d'une mesure de similitude / dissimilarité que je devrais envisager?αjαj

Le nombre de dimensions est malheureusement très important (des milliers ou plus; il est dérivé des fonctionnalités du sac de mots). Cependant, j'ai plusieurs dizaines de milliers d'exemples. J'ai ensuite des centaines de milliers d'objets que je souhaite regrouper, il est donc important de généraliser à partir des exemples pour apprendre une bonne métrique de dissimilarité.

Je suppose que cela tombe dans la rubrique du clustering semi-supervisé, et il semble que cela pourrait être de la veine "d'adaptation de la similitude", mais je n'ai pas été en mesure de trouver des descriptions claires des algorithmes à utiliser à cette fin.

DW
la source
Problème très intéressant. Si je comprends bien votre problème, vous obtenez une matrice principalement vide avec ses éléments codant la similarité ou la dissimilarité par paire. Certains éléments sont complétés mais la plupart sont manquants. J'essaierais d'abord de remplir cette matrice (par exemple en utilisant l'hypothèse de bas rang par exemple).
Vladislavs Dovgalecs
@xeon, ce serait une approche, mais elle ignore les fonctionnalités. Mon hypothèse est que certaines fonctionnalités sont très pertinentes et que certaines fonctionnalités ne sont pas pertinentes, et que l'examen de la différence entre les fonctionnalités pertinentes donne une métrique de dissimilarité raisonnable - mais comment pouvons-nous trouver cette métrique? Le simple fait d'essayer de compléter la matrice comme vous le suggérez ignore cette structure et ne tire donc pas pleinement parti des données dont nous disposons.
DW
Quel est votre objectif final? Ce n'est pas seulement pour apprendre la métrique de distance, non? Vous voulez classer les points de données, n'est-ce pas?
Vladislavs Dovgalecs
1
Il y a des choses que je pense que vous n'avez pas élucidées très clairement. L'ensemble des paires d'exemples forme-t-il une matrice binaire complète (1 = similaire; 0 = dissemblable) ou certaines informations sur les cellules manquent-elles? La matrice est-elle "non contradictoire" - c'est-à-dire que les exemples d'objets se répartissent en classes non superposées? Notez également qu'aucune méthode d'apprentissage ne peut (ou ne devrait être utilisée) pour vous conseiller sur le type de mesure (comme la norme L2 ou L1, par exemple) car ce choix est théorique (cela dépend du type d'attributs, de la conceptualisation de la caractéristique espace, méthode de clustering que vous allez utiliser ensuite).
ttnphns
Ceci est trop large pour être raisonnablement répondu ici. Il existe une grande quantité de littérature consacrée à la fois à la pondération des caractéristiques, à la sélection et à l'apprentissage des fonctions de distance. Je pense que j'ai même vu une conférence sur l'apprentissage de la similitude ou plus!
A QUIT - Anony-Mousse

Réponses:

6

C'est un gros problème dans certains domaines de l'apprentissage automatique. Je ne le connais pas aussi bien que je le souhaiterais, mais je pense que cela devrait vous aider à démarrer.

L2

David J. Harris
la source
QA
Je ne vois pas pourquoi vous ne pouviez pas inclure cette restriction. Je ne sais pas si le modèle résultant a un nom, cependant.
David J. Harris
1

ai1/wi

En d'autres termes, vous posez des questions sur le prétraitement et la mise à l'échelle des données. C'est trop large pour être bien répondu en une seule question. Chercher:

  • sélection de fonctionnalité
  • pondération des fonctions
  • normalisation
  • réduction de la dimensionnalité
  • autres techniques de projection
  • autres fonctions de distance
  • "apprendre à classer"

Il existe une quantité considérable de littérature et même des pistes de conférence dédiées à cela. Quelques méthodes pour vous aider à démarrer:

A QUIT - Anony-Mousse
la source