Cet article décrit l'algorithme KNN implémenté en Java. Partagez-le pour votre référence, comme suit:
Tout le monde devrait être familier avec les algorithmes KNN, et ils sont l'un des dix premiers algorithmes classiques pour l'exploration de données.
L'idée de l'algorithme est de regrouper et de classer les données inconnues pour le groupe qui a été classé dans l'ensemble de données de formation. Parmi eux, la distance est calculée sur la base du point inconnu et du point de ses données de formation, le point avec la distance la plus courte est calculé, et la catégorie où elle est classée à ce point.
Jetons un coup d'œil à l'ingénierie de l'algorithme:
1. Préparez les données et préparez les données
2. Sélectionnez la structure de données appropriée pour stocker les données de formation et tester les tuples
3. Définir les paramètres, tels que k
4. Maintenir une file d'attente prioritaire de la taille K, de grande à petite, en fonction de la distance, pour stocker les tuples de formation des voisins les plus proches. Sélectionnez au hasard les tuples K dans le tuple d'entraînement comme tuple le plus proche du voisin, calculez la distance entre le tuple de test et ces k tuples, et stockez l'étiquette de tuple d'entraînement et la distance dans la file d'attente prioritaire.
5. Iréatiser le jeu de tuple de formation, calculer la distance entre le tuple d'entraînement actuel et le tuple d'essai et diviser la distance résultante L à la distance maximale Lmax dans la file d'attente prioritaire.
6. Faites une comparaison. Si l> = lmax, le tuple est jeté et le tuple suivant est traversé. Si l <lmax, supprimez le tuple avec la plus grande distance dans la file d'attente prioritaire et stockez le tuple de formation actuel dans la file d'attente prioritaire.
7. Une fois la traversée terminée, calculez la majorité des tuples K dans la file d'attente prioritaire et utilisez-les comme catégorie du tuple d'essai.
8. Une fois l'ensemble de tubiles de test testé, calculez le taux d'erreur, continuez à définir différentes valeurs K et se recycler, et enfin d'obtenir la valeur k avec le plus petit taux d'erreur.
Selon le processus d'algorithme, nous mettons en œuvre la langue Java:
package KNN;/** * Coordinates of points x and y * @author Administrator * */public class PointBean {int x;int y;public int getX() { return x;}public void setX(int x) { this.x = x;}public int getY() { return y;}public void setY(int y) { this.y = y;}public PointBean(int x, int y) { super(); this.x = x; this.y = y;} public PointBean () {super ();} @ OverRidepublic String toString () {return "PointBean [x =" + x + ", y =" + y + "]";}}Algorithme KNN
Package KNN; Importer java.util.arrayList; / ** * Méthodes d'implémentation KNN * @Author Administrator * * / public class Knnmain {public double getPointLength (ArrayList <PointBean> List, PointBean BB) {int b_x = bb.getx (); int b_y = bb.gety (); double temp = (b_x -list.get (0) .getx ()) * (b_x -list.get (0) .getx ()) + (b_y -list.get (0) .gety ()) * (b_y -list.get (0) .gety ()); // trouver la distance minimale pour (int i = 1; i <list.size (); i ++) {if (temp <((b_x -list.get (i) .getx ()) * (b_x -list.get (i) .getx ()) + (b_y -list.get (i) .gety () * (b_y -list.get (i) .gety ()) {temp = b_x -List.get (i) .getx ()) * (b_x -list.get (i) .gety ()); }} return math.sqrt (temp); } / ** * Obtenez la longueur et trouvez la plus petite pour la classification * @param list1 * @param list2 * @param list3 * @param bb * / public void getContent (ArrayList <pointBean> list1, ArrayList <pointBean> list2, ArrayList <pointBean> list3, PointBean bb) {double a = getPointLingg (list1, bb); double b = getPointLength (list2, bb); double c = getPointLength (list3, bb); // fait une comparaison if (a> b) {if (b> c) {System.out.println ("ce point:" + bb.getx () + "," + bb.gety () + "" + "appartient à C"); } else {System.out.println ("Ce point:" + bb.getx () + "," + bb.gety () + "" + "appartient à b"); }} else {if (a> c) {System.out.println ("ce point:" + bb.getx () + "," + bb.gety () + "" + "appartient à C"); } else {if (a> c) {System.out.println ("ce point:" + bb.getx () + "," + bb.gety () + "" + "appartient à C"); } else {System.out.println ("Ce point:" + bb.getx () + "," + bb.gety () + "" + "appartient à un"); }}}}Fonction principale
package knn; import java.util.arraylist; / * * fonction principale knn * / classe publique testjava {static arrayList <pointBean> lista; statique ArrayList <PointBean> listB; statique ArrayList <pointBean> listC; statique ArrayList <pointBean> listD; public static void main (String [] args) {// chuangjia arrayList lista = new ArrayList <pointBean> (); listB = new ArrayList <pointBean> (); listc = new ArrayList <pointBean> (); listd = new ArrayList <pointBean> (); // Écriture de données setDate (); getTestResult (); } / ** * Obtenez le résultat * / private static void getTestResult () {// Créer un objet Knnmain km = new Knnmain (); pour (int i = 0; i <listd.size (); i ++) {km.getContent (lista, listB, listc, listd.get (i)); }} / ** * Données d'écriture * / private static void setDate () {// a de la coordonnée de A int a_x [] = {1,1,2,2,1}; int a_y [] = {0,1,1,0,2}; // Point de coordonnée de B int b_x [] = {2,3,3,3,4}; int b_y [] = {4,4,3,2,3}; // Point de coordonnée de C int c_x [] = {4,5,5,6,6}; int c_y [] = {1,2,0,2,1}; // Test Data // B's Point de coordonnée int d_x [] = {3,3,3,0,5}; int d_y [] = {0,1,5,0,1}; // PointBean BA; for (int i = 0; i <5; i ++) {ba = new PointBean (a_x [i], a_y [i]); lista.add (ba); } // PointBean BB; pour (int i = 0; i <5; i ++) {bb = new PointBean (b_x [i], b_y [i]); listB.Add (BB); } // PointBean BC; pour (int i = 0; i <5; i ++) {bc = new PointBean (c_x [i], c_y [i]); listc.Add (BC); } // PointBean bd; for (int i = 0; i <5; i ++) {bd = new PointBean (d_x [i], d_y [i]); listd.add (bd); }}}Résultats des tests:
Ce point: 3, 1 appartient à un
Ce point: 3, 5 appartient à b
Ce point: 0, 0 appartient à un
Ce point: 5, 1 appartient à C
À ce stade, l'algorithme KNN simple a mis en œuvre la division des points inconnus, ce qui aidera tout le monde à comprendre l'algorithme KNN. Certains algorithmes qui améliorent KNN seront affichés plus tard. Apprenez et progressez ensemble!
Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.