Quelle est la différence entre knn et k-means

La différence entre knn et k-means : 1. L'algorithme [k-means] est un algorithme de clustering typique basé sur la distance. Il utilise la distance comme indice d'évaluation de similarité, c'est-à-dire que plus la distance entre les deux est proche. deux objets sont, plus la similarité est grande ; 2. L'algorithme knn n'a pas de processus de pré-entraînement évident. Lorsque le programme démarre, l'ensemble de données est chargé dans la mémoire et la classification commence.

La différence entre knn et k-means :

1. Et le principe

l'algorithme k-means (algorithme de clustering k-means) est un algorithme de partitionnement de base avec un nombre connu de catégories de cluster. Il s’agit d’un algorithme de clustering typique basé sur la distance, qui utilise la distance comme indice d’évaluation de similarité. Autrement dit, on considère que plus la distance entre deux objets est proche, plus la similarité est grande. Elle est mesurée à l'aide de la distance euclidienne (une compréhension simple est la distance en ligne droite entre deux points. La distance euclidienne normalise simplement la définition de cette distance et l'étend à N dimensions). Il peut gérer de grands ensembles de données et est efficace. Le résultat du regroupement est k ensembles de données divisés en k catégories. Selon la méthode d'expression des résultats de regroupement, il peut être divisé en algorithme de k-moyennes dures (H CM), algorithme de k-moyennes floues (F CM) et algorithme de probabilité k-moyennes (P CM).

1.1.Idée de base

Il est basé sur une fonction objectif de clustering donnée. L'algorithme utilise une méthode de mise à jour itérative se déroule dans le sens d'une diminution de la fonction objectif. Le résultat du regroupement permet à la fonction objectif d'obtenir la valeur minimale et d'obtenir un meilleur effet de classification

1.2 Principe

L'algorithme original des k-moyennes sélectionne d'abord au hasard k points comme centre de regroupement initial, puis calcule le distance entre chaque objet de données et chaque centre de cluster, et classer l'objet de données dans la classe du centre de cluster le plus proche de lui ; Calculer le nouveau centre de cluster pour la nouvelle classe ajustée. Si les centres de cluster sont adjacents deux fois, il n'y a aucun changement, indiquant. que l'ajustement de l'objet de données est terminé et que la fonction de critère de regroupement f a convergé. A chaque itération, il faut vérifier si la classification de chaque échantillon est correcte. Si elle n'est pas correcte, elle doit être ajustée. Une fois toutes les données ajustées, le centre du cluster est modifié et l'itération suivante est saisie. Si tous les objets de données sont correctement classés dans un algorithme itératif, il n'y aura aucun ajustement et il n'y aura aucun changement au centre du cluster, ce qui indique que f a convergé et que l'algorithme se termine.

1.3 Organigramme de l'algorithme

1.4 Comment choisir le point initial de l'algorithme ?

1) Sélectionnez K points dans le lot qui sont aussi éloignés que possible

Sélectionnez d'abord au hasard un point comme premier point central initial du cluster, puis sélectionnez le point le plus éloigné du point As le point central du deuxième cluster initial, puis sélectionnez le point ayant la plus grande distance la plus proche des deux premiers points comme point central du troisième cluster initial, et ainsi de suite jusqu'à ce que K points centraux du cluster initial soient sélectionnés.

2) Utilisez le clustering hiérarchique ou l'algorithme Canopy pour le clustering initial, puis utilisez les points centraux de ces clusters comme points centraux initiaux du cluster de l'algorithme K-Means.

Comment choisir k dans l'algorithme 1.5 ?

Tant que le nombre de clusters que nous supposons est égal ou supérieur au nombre réel de clusters, l'indicateur augmentera lentement, et une fois que nous essaierons d'obtenir moins que le nombre réel de clusters, l'indicateur augmentera augmenter fortement. L'index de cluster sert d'index de référence important.

Le diamètre d'un cluster fait référence à la distance maximale entre deux points quelconques du cluster.

Le rayon d'un cluster fait référence à la distance maximale entre tous les points du cluster et le centre du cluster.

1.6 Avantages, inconvénients et comment s'améliorer ?

Il est simple à utiliser car il utilise un élément aléatoire, il n'est donc pas garanti de trouver la meilleure classe. Il n’est pas nécessaire d’initialiser raisonnablement le nombre de clusters : c’est-à-dire que K doit être initialisé.

2. Algorithme de classification du K-plus proche voisin (K N N)

2.1 Introduction au problème

Idée K N N : D'après l'image ci-dessus, nous pouvons voir que les données définies dans l'image sont de bonnes données, c'est-à-dire qu'elles ont été étiquetées. Un type est un carré bleu, l'autre est un triangle rouge et le cercle vert est ce que nous attendons. pour. Données classifiées. Si K=3, alors il y a 2 triangles rouges et 1 carré bleu les plus proches du point vert. Ces 3 points votent, donc le point vert à classer appartient au triangle rouge. Si K=5, alors il y a 2 triangles rouges. et 1 carré bleu le plus proche du point vert. Il y a 2 triangles rouges et 3 carrés bleus récemment. Ces 5 points votent, donc le point vert à classer appartient au carré bleu, c'est à dire si un échantillon est parmi les k les plus. échantillons adjacents dans l'espace des fonctionnalités, la plupart d'entre eux appartiennent à une certaine catégorie, alors l'échantillon appartient également à cette catégorie. On voit que KNN repose essentiellement sur une méthode statistique ! En fait, de nombreux algorithmes d’apprentissage automatique s’appuient également sur des statistiques de données.

2.2 Algorithme K N N

Introduction

K N N signifie K-Nearest Neighbour, qui est une sorte d'apprentissage basé sur la mémoire, également appelé apprentissage basé sur les instances, et appartient à l'apprentissage paresseux. C'est-à-dire qu'il n'y a pas de processus de pré-entraînement évident. Au lieu de cela, lorsque le programme démarre, après avoir chargé l'ensemble de données dans la mémoire, aucune formation n'est requise et la classification peut être lancée. K N N est également un algorithme d'apprentissage supervisé. Il calcule la distance entre les valeurs des caractéristiques des nouvelles données et les données d'entraînement, puis sélectionne K (K>=1) voisins les plus proches pour la classification (méthode de vote) ou la régression. Si K=1, la nouvelle donnée est simplement affectée à la classe de son plus proche voisin.

Étapes

1) Calculez la distance entre les données de test et chaque donnée d'entraînement, vous pouvez utiliser la formule de distance euclidienne pour calculer.

2) Trier selon le rapport croissant de distance

3) Sélectionnez les K points avec la plus petite distance (la valeur k est déterminée par vous-même)

4) Déterminer la fréquence d'apparition de la catégorie où se trouvent les K premiers points ;

5) Renvoyez la catégorie avec la fréquence d'occurrence la plus élevée parmi les K premiers points comme classification prévue des données de test.

Caractéristiques

Méthode statistique non paramétrique : Pas besoin d'introduire la sélection du paramètre K : Lorsque K = 1, l'échantillon à classer est classé dans la classe de l'échantillon le plus proche de lui . Lorsque K = | K doit être sélectionné de manière raisonnable. S'il est trop petit, il sera facilement perturbé, et s'il est trop grand, cela augmentera la complexité du calcul. La complexité de l'algorithme : la malédiction de la dimensionnalité. Lorsque le nombre de dimensions augmente, le nombre d'échantillons d'apprentissage requis augmente fortement. La réduction de la dimensionnalité est généralement utilisée.

2.3 Avantages et inconvénients de l'algorithme

Avantages : simple et efficace

Inconvénients : grande quantité de calcul. Le résultat n'est pas très interprétable. Tous les échantillons de formation doivent être stockés.

3. La différence entre K N N et k-means

Recommandations d'apprentissage gratuites associées : programmation php (Vidéo)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!