Partage
  • Partager sur Facebook
  • Partager sur Twitter

Classement des plus éloignés dans une matrice 2D

Recherche des éléments les plus éloignés dans une matrice en 2D

    2 mars 2021 à 9:50:46

    Bonjour,

    Je vous explique mon problème.

    J'ai un algorithme qui calcul l'unicité de différents textes entre eux. Derrière ça me ressort une matrice avec des pourcentages à l'intérieur :

    Cette matrice peut aller jusqu'à 5000.

    J'aimerai faire en sorte de trier les textes par unicité : me faire un classement des textes les plus uniques en premiers pour les récupérer.

    J'aimerai que mes textes soit tous un peu similaires entre eux, mais pas qu'il y ait 2 textes qui soit vraiment trop proches.

    Je ne sais pas si il y a une formule mathématique ou un moyen de trouver ça et de faire ce classement de "pertinence".

    J'espère que vous avez compris ma demande et que vous aurez peut-être une réponse !

    Merci à vous et bonne journée

    • Partager sur Facebook
    • Partager sur Twitter
      2 mars 2021 à 13:13:12

      Bonjour ! Que signifient les pourcentages ? 100 % --> les deux textes sont identiques (ou utilisent exactement les mêmes mots), 0 % --> les deux fichiers n'ont strictement rien en commun. C'est ça ?

      Une méthode possible serait de faire la somme des pourcentages de chaque colonne. Celui qui a la somme la plus petit est celui qui a le moins de choses en commun avec l'ensemble des autres textes. (Une somme par ligne. On peut l'afficher dans une nouvelle colonne, et il restera à trier les valeurs de cette colonne.)

      -
      Edité par robun 2 mars 2021 à 13:13:58

      • Partager sur Facebook
      • Partager sur Twitter
        2 mars 2021 à 15:45:29

        Les pourcentages sont le taux d'unicité d'un texte par rapport à un autre.
        Texte 1 par rapport à texte 2 est 78% unique (donc 22% similaire)
        Texte 2 par rapport à texte 3 est 87% unique
        etc ...
        Mais en soit je peux faire l'inverse.
        Le problème, c'est que j'ai besoin de récupérer plusieurs textes, donc faire le classement sur plusieurs.
        Je ne dois pas avoir un texte qui a une somme basse, mais qui par exemple avec un pourcentage de 10% unique avec un certain texte. Ou alors faut que ce texte soit classé en tout dernier
        Je ne sais pas si tu vois ce que je veux dire ?
        • Partager sur Facebook
        • Partager sur Twitter
          2 mars 2021 à 18:31:17

          Donc tu confirmes que si les deux textes sont complètement différents le taux est de 0 % ? (Ma demande de précision était précise, non ?)

          Donc tu ne cherches pas à évaluer un texte par rapport à l'ensemble des autres textes, mais juste par rapport à un autre texte donné ?

          Ou alors tu cherches les plus faibles pourcentages dans le tableau ? Ah oui, je crois que je comprends : tu cherches les cas où deux textes sont complètement différents l'un par rapport à l'autre ? En fait tu ne cherches pas des textes mais des couples de textes, donc ?

          Pour être sûr d'être clair, prenons comme exemple les 4 premiers textes de ton tableau :

                 78 %   93 %   80 %
          78 %          87 %   94 %
          93 %   87 %          91 %
          80 %   94 %   91 %
          

          Et tu veux détecter que les textes 1 et 2 sont différents (parce que 78 % est le plus petit pourcentage) ? Et ensuite 1 et 4. Si ce n'est pas ça, indique sur cet exemple ce qu'il faut détecter.

          -
          Edité par robun 2 mars 2021 à 18:32:26

          • Partager sur Facebook
          • Partager sur Twitter
            2 mars 2021 à 19:52:41

            Taux d'unicté d'un texte par rapport à un autre ... ce n'est pas clair.

            Question 1 : tu as 5000 textes. Pour fixer un peu les idées, un texte est par exemple un document de 500 mots ? Beaucoup plus, beaucoup moins ?

            Question 2 : 78%unique=22%similaire ... Si tu veux bien, je vais plutôt dire 78%différent=22%similaire.

            Question 3 : Ici, toutes les différences sont élevées (56% le plus petit nombre si je vois bien), mais imaginons des nombres plus petits.

            Si distance(texte1,texte2)=18% et distance(texte2,texte3)=40%, j'imagine que l'inégalité triangulaire est vérifiée, et distance(texte1,texte3)<= 58% 

            Si oui, la fonction utilisée est bien une distance, et ça permet de faire des choses.

            Pour moi, on est dans ce cadre là : http://larmarange.github.io/analyse-R/classification-ascendante-hierarchique.html#:~:text=Le%20principe%20de%20la%20CAH,identiques%20auront%20une%20distance%20nulle. 

            On peut aussi voir la chose ainsi.

            Je prends mes 2 premiers textes TX1 et TX2, je connais leur distance. Je peux donc les placer sur une droite, avec une certaine distance.

            Je prends le 3ème texte TX3, je le place dans le plan, de façon à ce que les distances soient respectées.

            Je prends le 4ème texte, je le place dans l'espace (4 points, donc dimension 3), de façon à ce que les distances soient respectées.

            A l'arrivée, avec 5000 points, on a un nuage de points en dimension 4999. J'imagine que ce que tu cherches, ce sont les points les plus éloignés du centre de gravité (ce n'est pas clair, je ne sais pas ce que tu cherches en fait)

            Dimension 4999 ... ça nous change de notre univers en 3 dimensions ! Il faut une bonne capacité d'abstraction pour comprendre l'idée.

            Cette démarche, c'est ce qui est fait dans le cadre d'une C.A.H (Classification ascendante hiérarchique). On a le nuage de points en dimension 5000, on recherche le plan qui donne une forme la plus étendue possible, et on projette tous les points sur ce plan, et on a un beau nuage de points en dimension 2, et on va remarquer que tous les textes qui sont voisins sont des textes avec une thématique commune.

            • Partager sur Facebook
            • Partager sur Twitter
              3 mars 2021 à 15:56:07

              robun a écrit:

              Donc tu confirmes que si les deux textes sont complètement différents le taux est de 0 % ? (Ma demande de précision était précise, non ?)

              Donc tu ne cherches pas à évaluer un texte par rapport à l'ensemble des autres textes, mais juste par rapport à un autre texte donné ?

              Ou alors tu cherches les plus faibles pourcentages dans le tableau ? Ah oui, je crois que je comprends : tu cherches les cas où deux textes sont complètement différents l'un par rapport à l'autre ? En fait tu ne cherches pas des textes mais des couples de textes, donc ?

              Pour être sûr d'être clair, prenons comme exemple les 4 premiers textes de ton tableau :

                     78 %   93 %   80 %
              78 %          87 %   94 %
              93 %   87 %          91 %
              80 %   94 %   91 %
              

              Et tu veux détecter que les textes 1 et 2 sont différents (parce que 78 % est le plus petit pourcentage) ? Et ensuite 1 et 4. Si ce n'est pas ça, indique sur cet exemple ce qu'il faut détecter.

              -
              Edité par robun il y a environ 20 heures

              Non, si les deux textes sont complètement différnt on est à 100%. Mais ça c'est juste une question de paramétrage.

              Je ne cherche pas un texte par rapport à un autre ni des couples.

              1
              2
              3
              4
                     90 %   85 %   24 %
              90 %          87 %   94 %
              85 %   87 %          91 %
              24 %   94 %   91 %

              Dans ce tableau, le classement serait : Texte 4, Texte 2, Texte 3 puis texte 1. Le texte 1 en dernier car il est beaucoup trop proche du texte 4. Le texte 4 en premier car par rapport au texte 2 et au texte 3 il a la plus forte valeur + le fait que le texte 2 a aussi un bon pourcentage avec le texte 2.

              Si le texte 2 avait eu un trop faible pourcentage avec le texte 3, il aurait été troisième.

              Est-ce que tu arrives à visualisé ? Il ne faut pas que j'ai 2 textes trop proches dans mon classement.

              tbc92 a écrit:

              Taux d'unicté d'un texte par rapport à un autre ... ce n'est pas clair.

              Question 1 : tu as 5000 textes. Pour fixer un peu les idées, un texte est par exemple un document de 500 mots ? Beaucoup plus, beaucoup moins ?

              Question 2 : 78%unique=22%similaire ... Si tu veux bien, je vais plutôt dire 78%différent=22%similaire.

              Question 3 : Ici, toutes les différences sont élevées (56% le plus petit nombre si je vois bien), mais imaginons des nombres plus petits.

              Si distance(texte1,texte2)=18% et distance(texte2,texte3)=40%, j'imagine que l'inégalité triangulaire est vérifiée, et distance(texte1,texte3)<= 58% 

              Si oui, la fonction utilisée est bien une distance, et ça permet de faire des choses.

              Pour moi, on est dans ce cadre là : http://larmarange.github.io/analyse-R/classification-ascendante-hierarchique.html#:~:text=Le%20principe%20de%20la%20CAH,identiques%20auront%20une%20distance%20nulle. 

              On peut aussi voir la chose ainsi.

              Je prends mes 2 premiers textes TX1 et TX2, je connais leur distance. Je peux donc les placer sur une droite, avec une certaine distance.

              Je prends le 3ème texte TX3, je le place dans le plan, de façon à ce que les distances soient respectées.

              Je prends le 4ème texte, je le place dans l'espace (4 points, donc dimension 3), de façon à ce que les distances soient respectées.

              A l'arrivée, avec 5000 points, on a un nuage de points en dimension 4999. J'imagine que ce que tu cherches, ce sont les points les plus éloignés du centre de gravité (ce n'est pas clair, je ne sais pas ce que tu cherches en fait)

              Dimension 4999 ... ça nous change de notre univers en 3 dimensions ! Il faut une bonne capacité d'abstraction pour comprendre l'idée.

              Cette démarche, c'est ce qui est fait dans le cadre d'une C.A.H (Classification ascendante hiérarchique). On a le nuage de points en dimension 5000, on recherche le plan qui donne une forme la plus étendue possible, et on projette tous les points sur ce plan, et on a un beau nuage de points en dimension 2, et on va remarquer que tous les textes qui sont voisins sont des textes avec une thématique commune.


              Hello,

              Sinon on peut dire taux de duplication, derrière j'ai juste à inverser ma formule de calcul.

              Q1 : j'ai 500 textes d'en moyenne 500 mots. Parfois 200, parfois 1500 mais plus rarement.

              Q2 : je veux bien pas de problèmes :D

              Q3 : non il n'y a pas d'inégalité triangulaire de ce que j'ai compris...

              Voilà une matrice pour 10 qui est un peu plus espacé. Les croix veulent dire que les 2 textes sont trop proches donc ils ne pourront pas être proche dans le classement final.
              Pour le reste je ne sais pas comment le matérialisé pour expliquer et pour faire un classement. 
              Il faut que tous les textes en premier dans mon classement soient éloignés entre eux. Plus on va descendre dans le classement plus on aura des textes similaires à notre haut de classement.

              -
              Edité par Gnolls 3 mars 2021 à 16:13:10

              • Partager sur Facebook
              • Partager sur Twitter
                3 mars 2021 à 19:12:22

                J'ai l'impression que les dendogrammes (cf mon message précédent) correspondent à ton besoin. 

                Mais qu'il faudrait prendre la mesure inverse. Au lieu des valeurs 90, 85, 24 ..., il faudrait prendre les compléments 10, 15, 76 ...

                Tout ça n'est pas très clair.  

                • Partager sur Facebook
                • Partager sur Twitter
                  4 mars 2021 à 9:44:06

                  Gnolls a écrit:

                  Je ne cherche pas un texte par rapport à un autre ni des couples.

                  1
                  2
                  3
                  4
                         90 %   85 %   24 %
                  90 %          87 %   94 %
                  85 %   87 %          91 %
                  24 %   94 %   91 %

                  Dans ce tableau, le classement serait : Texte 4, Texte 2, Texte 3 puis texte 1. Le texte 1 en dernier car il est beaucoup trop proche du texte 4. Le texte 4 en premier car par rapport au texte 2 et au texte 3 il a la plus forte valeur + le fait que le texte 2 a aussi un bon pourcentage avec le texte 2.

                  Si le texte 2 avait eu un trop faible pourcentage avec le texte 3, il aurait été troisième.

                  Est-ce que tu arrives à visualisé ? Il ne faut pas que j'ai 2 textes trop proches dans mon classement.

                  Ce n'est pas évident parce que tu mets le texte 1 en dernier à cause des 24 % (il est beaucoup trop proche du texte4), or le texte 4 aussi a un 24 % (il est beaucoup trop proche du texte 1) et pourtant tu le mets en premier. Donc apparemment c'est le 94 % qui compte le plus.

                  Du coup, un truc simple serait d'affecter à chaque texte le pourcentage maximal, puis de les trier par ce pourcentage :

                  • texte4 = 94 % (puis 91 %)
                  • texte2 = 94 % (puis 90 %)
                  • texte3 = 91 %
                  • texte1 = 90 %
                  Si le critère le plus important est « il ne faut pas 2 textes trop proches », on peut classer par rapport au minimum :
                  • texte2 = 87%
                  • texte3 = 85 %
                  • texte4 = 24 % (puis 91 %)
                  • texte1 = 24 % (puis 85 %)
                  • Partager sur Facebook
                  • Partager sur Twitter
                    4 mars 2021 à 11:28:45

                    Merci à vous deux pour vos réponses.

                    J'ai essayé de reprendre mes explications au plus clair et en simplifiant les choses avec des exemples.

                    Ce que je cherche à faire c'est un classement des textes les plus éloignés entre eux (donc le plus possible avec un faible pourcentage entre chacun d'entre eux).

                    Dans mon classement, je préfère avoir beaucoup de textes moyennement proches les uns entre les autres que peu de textes très éloignés.

                    J'ai essayé de calculer des moyennes de similitude en enlevant les valeurs les plus éloignées, des calculs sur les pourcentages + les occurrences, mais je ne trouve jamais un classement cohérent et je suis presque sûr qu'il y a une formule ou une manière de faire.

                    Voilà un exemple de matrice :


                    0 1 2 3 4 5
                    1 100% 19% 37% 12% 20%
                    2 19% 100% 48% 34% 26%
                    3 37% 48% 100% 49% 18%
                    4 12% 34% 49% 100% 4%
                    5 20% 24% 18% 4% 100%

                    Dans ce cas là, mon ordre personnel serait 5, 4, 1, 2, 3. Mais c'est sans calcul ...

                    D'une manière générale, il faut que le 4 et le 3 soient éloignés cars 49% similaire. Mais il faut aussi que le 2 et le 3 soient éloignés. Pour le reste, c'est un classement des plus petits pourcentages entre eux. 5 et 4 parce qu'ils n'ont que 4%. Ensuite j'ai regardé lequel avait le moins de pourcentage avec et le 5 et le 4 -> le 1.
                    Par contre si le 1 avait 50% avec le 5 et 5% avec le 4 et que le 2 avait 27% avec le 5 et 25% avec le 4, j'aurais préféré le 2. Car il est certes plus similaire avec les 2 mais il n'y a pas un gros écart. Le texte 1 fausserait tout avec un aussi gros pourcentage de similarité.


                    Si on prend un deuxième exemple :

                    0 1 2 3 4 5
                    1 100% 8% 14% 20% 11%
                    2 8% 100% 19% 4% 6%
                    3 14% 19% 100% 21% 6%
                    4 20% 4% 21% 100% 15%
                    5 11% 6% 6% 15% 100%

                    Ici mon classement serait : 5, 2, 4, 1, 3

                    Mais encore une fois c'est sans calculs et je pense qu'il y a une manière de calculer ça précisément.

                    L'idéal serait d'avoir des données et des statistiques comme ces courbes :

                    https://www.zupimages.net/viewer.php?id=21/09/mlti.png


                    En indiquant un certain nombre de textes, indiqué quel serait le taux de similitude maximal.


                    Mon but est d'exporter un maximum de textes avec le moins de pourcentage de similitude possible.


                    J'espère que c'est un peu plus clair :/

                    • Partager sur Facebook
                    • Partager sur Twitter
                      4 mars 2021 à 12:22:20

                      La question derrière la question ... Quand quelqu'un exprime un besoin, il faut lui demander pourquoi ... et généralement , il faut 5 pourquoi successifs pour avoir le vrai besoin.

                      Tu veux classer tes textes, selon un certain critère. Mais, en fait , pourquoi veux-tu les classer ?

                      Tu viens d'y répondre partiellement. Tu veux utiliser ce tri, pour garder uniquement une certaine partie des textes, et éliminer les textes qui font double-emploi. En fait, c'était plus ou moins dit dans le premier message, mais on est passé au travers.

                      Si 2 textes se ressemblent beaucoup, tu veux en garder uniquement 1.

                      Si un texte ressemble un peu trop à tous les autres, tu ne veux pas le garder.

                      On a beaucoup avancé !

                      Dans un tri classique, qu'on trie en montant ou en descendant, du premier au dernier, ou du dernier aupremier, peu importe, il y a symétrie.

                      Ici, il n'y a pas de symétrie. 

                      On peut imaginer quelque chose comme ça :

                      - dans le process, on avance étape par étape. On classe un par un les textes de 'Disponible' vers 'Gardé' (ou vers 'Rejeté' parce que doublon). Dans mon cas, on va les classer un par un vers 'Gardé' ... et tous ceux qui ne sont pas Gardés sont Rejetés.

                      - Etape 1, on Garde 1 seul texte, selon des règles à définir.

                      - Puis à chaque étape, on va regarder les distances de tous les textes en suspens avec les textes 'Gardés' uniquement. Et c'est sur cette partie de la matrice qu'on va garder un texte de plus.

                      - A chaque nouveau texte que tu 'Gardes', tu sais dire que ce nouveau texte a une note plus ou moins élevée, calculée par rapport aux textes déjà gardés. Tu peux donc faire une courbe plus ou moins intéressante, du type de celles que tu as montrées. Et ces courbes pourront aider à dire : A partir du texte n° 2000, les textes supplémentaires font vraiment double-emploi avec ceux déjà sélectionnés.

                      Pour garder le 1er texte, tu peux choisir celui pour lequel Somme (distances) renvoie le plus grand nombre. Ou, tu peux tester des variantes ; sum(racine(distance)) me parait mieux.

                      Et à chaque nouveau texte que tu veux intégrer , pareil. Le texte que tu ajoutes et qui arrive en position i, c'est le texte qui maximise la fonction sum(racine(distance)), sauf que maintenant, tu fais cette somme en utilisant uniquement les textes 'Gardés'.

                      • Partager sur Facebook
                      • Partager sur Twitter
                        8 mars 2021 à 9:06:58

                        Hello,

                        Merci pour ta réponse.

                        Je vais me pencher de ce côté-là

                        Si j'ai des questions ou des avancées je te tiens au courant, merci beaucoup !

                        • Partager sur Facebook
                        • Partager sur Twitter

                        Classement des plus éloignés dans une matrice 2D

                        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                        • Editeur
                        • Markdown