Partage de technologie

Méthode d'analyse groupée (3)

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina


5. Évaluation de la qualité du clustering

L'analyse cluster consiste à décomposer un ensemble de données en sous-ensembles, chaque sous-ensemble est appelé un cluster et l'ensemble de tous les sous-ensembles est appelé un cluster de l'ensemble d'objets. Un bon algorithme de clustering doit produire des clusters de haute qualité et des clusters de haute qualité, c'est-à-dire que la similarité globale au sein des clusters est la plus élevée, tandis que la similarité globale entre les clusters est la plus faible.Étant donné que de nombreux algorithmes de clustering incluent kk-L'algorithme de moyenne, l'algorithme DBSCAN, etc. nécessitent tous que l'utilisateur spécifie à l'avance le nombre de clusters dans le cluster kk, par conséquent, la méthode d’estimation simple de k sera discutée ci-dessous.

(1) Estimation du nombre de clusters

De nombreux algorithmes de clustering tels que kk-Les algorithmes de moyenne, même les algorithmes DIANA, etc., doivent spécifier le nombre de clusters à l'avance kk,et kkLa valeur de affectera grandement la qualité du clustering. Cependant, le nombre de clusters doit être déterminé à l'avance. kk Ce n’est pas une tâche facile. Nous pouvons d’abord considérer deux cas extrêmes.
(1) Mettez l'ensemble des données SSSconsidéré comme un cluster, c'est-à-dire k = 1 k=1k=1, cela semble simple et pratique, mais les résultats de cette analyse groupée n'ont aucune valeur.
(2) Mettez l'ensemble de données SSSChaque objet de est traité comme un cluster, c'est-à-dire soit k = ∣ S ∣ = nk=|S|=nk=S=n , produisant ainsi le clustering le plus fin. Par conséquent, il n’y a pas de différence intra-cluster dans chaque cluster et la similarité intra-cluster atteint le niveau le plus élevé.Mais ce type de clustering ne peut pas être utilisé pour SSSfournir toute information sur SSSune description générale.
On voit que le nombre de clusters kkdevrait au moins satisfaire 2 ≤ k ≤ n − 1 2≤k≤n-12kn1, mais le nombre de clusters kkLa valeur exacte la plus appropriée reste ambiguë.
Généralement considéré, kkLa valeur de peut être estimée par la forme et l'échelle de la distribution de l'ensemble de données, ainsi que par la résolution de regroupement requise par l'utilisateur, et les chercheurs disposent de nombreuses méthodes d'estimation différentes, telles que la méthode du coude, la méthode de validation croisée et la théorie de l'information. méthodes basées, etc.
Un outil simple et couramment utilisé kkLa méthode d'estimation empirique de la valeur estime que pour ceux qui ont nnnUn ensemble de données d'objets, le nombre de clusters dans lesquels il est regroupé kkPrendre n 2n2 2n Il est approprié.À l'heure actuelle, selon les attentes moyennes, chaque cluster a environ 2 n carré{2n}2n objets.Sur cette base, certaines personnes ont proposé des restrictions supplémentaires supplémentaires, à savoir le nombre de clusters k &lt; nkk<n
Par exemple, supposons n = 8 n=8n=8, puis le nombre de clusters k = 2 k=2k=2 est approprié, et en moyenne il y a 4 points par cluster, et selon la formule empirique supplémentaire k &lt; 2,83 k&lt;2,83k<2.83 .En utilisant ces deux informations sur le nombre de clusters kkLa formule empirique semble être expliquée d'un côté, dans l'exemple 10-5 k = 2 k=2k=2 est le nombre de clusters le plus approprié.

(2) Évaluation externe de la qualité

Si nous avons une bonne estimation du nombre de clusters kk, vous pouvez utiliser une ou plusieurs méthodes de clustering, par exemple : kk -L'algorithme moyen, l'algorithme hiérarchique agglomératif ou l'algorithme DBSCAN effectue une analyse de cluster sur des ensembles de données connus et obtient une variété de résultats de clustering différents. La question est maintenant de savoir quelle méthode donne les meilleurs résultats de clustering, ou en d’autres termes, comment comparer les résultats de clustering produits par différentes méthodes. Il s’agit de l’évaluation de la qualité du clustering.
À l’heure actuelle, il existe de nombreuses méthodes parmi lesquelles choisir pour l’évaluation de la qualité du clustering, mais elles peuvent généralement être divisées en deux catégories, à savoir l’évaluation de la qualité externe (extrinsèque) et l’évaluation de la qualité interne (intrinsèque).
L'évaluation externe de la qualité suppose qu'un cluster idéal existe déjà dans l'ensemble de données (généralement construit par des experts) et le compare en tant que méthode de référence couramment utilisée avec les résultats de clustering d'un certain algorithme. Son évaluation comparative comprend principalement l'entropie de clustering et le clustering. sont deux méthodes courantes pour la précision des classes.

1. Méthode d'entropie de clustering

Ensemble de données hypothétiques S = { X 1 , X 2 , … , X n } S={X_1,X_2,…,X_n}S={X1,X2,,Xn},et T = { T 1 , T 2 , … , T m } T={T_1,T_2,…,T_m}T={T1,T2,,Tm} est le regroupement standard idéal donné par les experts, et C = { C 1 , C 2 , … , C k } C={C_1,C_2,…,C_k}C={C1,C2,,Ck} est déterminé par un algorithme sur SSSUn cluster de , puis pour le cluster C i C_iCjePar rapport au clustering de référence TTTL'entropie de clustering de est définie comme
E ( C i ∣ T ) = − ∑ j = 1 m ∣ C i ∩ T j ∣ ∣ C i ∣ log ⁡ 2 ∣ C i ∩ T j ∣ ∣ C i ∣ (10-20) E(C_i|T)=-sum_{j=1}^mfrac{|C_icap T_j|}{|C_i|}log_2frac{|C_icap T_j|}{|C_i|}tag{10-20}E(CjeT)=j=1mCjeCjeTjlog2CjeCjeTj(10-20) et CCCÀ propos des benchmarks TTTL'entropie de clustering globale de est définie comme tous les clusters C i C_iCjeÀ propos des benchmarks TTTLa moyenne pondérée de l'entropie de clustering, c'est-à-dire
E ( C ) = 1 ∑ i = 1 k ∣ C i ∣ ∑ i = 1 k ∣ C i ∣ × E ( C i ∣ T ) (10-21) E(C)=frac{1}{mathop{somme}limites_{i=1}^k|C_i|}somme_{i=1}^k|C_i|fois E(C_i|T)tag{10-21}E(C)=je=1kCje1je=1kCje×E(CjeT)(10-21) La méthode d'entropie de clustering estime que, E ( C ) E(C)E(C) Plus la valeur est petite, plus CCCPar rapport à la ligne de base TTTPlus la qualité du clustering est élevée.
Il est à noter que le dénominateur du premier terme à droite de la formule (10-21) ∑ i = 1 k ∣ C i ∣kje=1|Cje| je=1kCje est la somme du nombre d'éléments dans chaque cluster et ne peut pas être utilisé nnn remplacer.Parce que seulement quand CCCLorsqu'il s'agit d'un cluster de partitionnement, le dénominateur est nnn, et le dénominateur des méthodes de clustering générales, telles que le clustering DBSCAN, peut être inférieur à nnn

2. Précision du regroupement

L'idée de base de l'évaluation de l'exactitude (précision) du clustering est d'utiliser le plus grand nombre de catégories du cluster comme étiquette de catégorie du cluster, c'est-à-dire pour le cluster C i C_iCje, s'il existe T j T_jTjfaire ∣ C i ∩ T j ∣ = max ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } |C_icap T_j|=max{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}CjeTj=max{CjeT1,CjeT2,,CjeTm}, on considère que C i C_iCjeLa catégorie est T j T_jTj .Par conséquent, le cluster C i C_iCjeÀ propos des benchmarks TTTLa précision est définie comme
J ( C i ∣ T ) = max ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } ∣ C i ∣ (10-22) J(C_i|T)=frac{max{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}}{|C_i|}tag{10-22}J(CjeT)=Cjemax{CjeT1,CjeT2,,CjeTm}(10-22) et CCCÀ propos des benchmarks TTTLa précision globale de est définie pour tous les clusters C i C_iCjeÀ propos des benchmarks TTTLa moyenne pondérée de la précision du regroupement, c'est-à-dire
J ( C ) = 1 ∑ i = 1 k ∣ C i ∣ ∑ i = 1 k ∣ C i ∣ × J ( C i ∣ T ) (10-23) J(C)=frac{1}{mathop{somme}limites_{i=1}^k|C_i|}somme_{i=1}^k|C_i|fois J(C_i|T)tag{10-23}J(C)=je=1kCje1je=1kCje×J(CjeT)(10-23) La méthode de précision du clustering estime que, J ( C ) J(C)J(C) Plus la valeur est grande, plus le regroupement CCCPar rapport à la ligne de base TTTPlus la qualité du clustering est élevée.
De plus, généralement 1-J(C)1J(C) appelé CCCÀ propos des benchmarks TTT taux d’erreur global.Par conséquent, la précision du regroupement J ( C ) J(C)J(C) Taux d'erreur important ou global 1-J(C)1J(C) Petit, cela montre que l'algorithme de clustering peut mieux regrouper les objets de différentes catégories dans différents clusters, c'est-à-dire que la précision du clustering est élevée.

(3) Évaluation de la qualité interne

Il n'existe pas de références externes connues pour l'évaluation interne de la qualité, seuls des ensembles de données sont utilisés. SSSet regroupement CCCÉvaluer les caractéristiques et les ampleurs intrinsèques d’un cluster CCC la qualité de. Autrement dit, l'effet de regroupement est généralement évalué en calculant la similarité moyenne au sein des grappes, la similarité moyenne entre les grappes ou la similarité globale.
L'évaluation de la qualité interne est liée à l'algorithme de clustering. L'indice d'efficacité du clustering est principalement utilisé pour évaluer la qualité de l'effet de clustering ou pour juger du nombre optimal de clusters. L'effet de clustering idéal est d'avoir la plus petite distance intra-cluster et la plus petite. le plus grand cluster. Par conséquent, l’efficacité du clustering est généralement mesurée par une certaine forme de rapport entre la distance intra-cluster et la distance inter-clusters. Les indicateurs couramment utilisés de ce type comprennent l'indicateur CH, l'indicateur Dunn, l'indicateur I, l'indicateur Xie-eni, etc.

1. Indicateur CH

L'indice CH est l'abréviation de l'indice de Calinski-Harabasz. Il calcule d'abord la somme des carrés de la distance entre chaque point du cluster et son centre du cluster pour mesurer la proximité au sein de la classe, puis il calcule la somme des carrés de la distance ; entre chaque point central du cluster et le point central de l'ensemble de données à mesurer. La séparation de l'ensemble de données et le rapport séparation/proximité sont l'indice CH.
installation X ‾ i surligne{X}_iXjereprésente un cluster CCCpoint central (moyenne), X ‾ surligner{X}Xreprésente un ensemble de données SSSle point central de d ( X ‾ i , X ‾ ) d(surligner{X}_i,surligner{X})d(Xje,X) pour X ‾ i surligne{X}_iXjearriver X ‾ surligner{X}XUne certaine fonction de distance de , puis le regroupement CCCLa compacité d’un cluster intermédiaire est définie comme
Trace ( A ) = ∑ i = 1 k ∑ X j ∈ C id ( X j , X ‾ i ) 2 (10-24) texte{Trace}(A)=sum_{i=1}^ksum_{X_jin C_i}d(X_j,overline{X}_i)^2tag{10-24}Tracerrrr(UN)=je=1kXjCjed(Xj,Xje)2(10-24) Par conséquent, Trace(A) est le cluster CCC La somme des carrés des distances entre les centres du cluster.Et le regroupement CCCLe degré de séparation est défini comme
Trace ( B ) = ∑ i = 1 k ∣ C i ∣ d ( X ‾ i , X ‾ ) 2 (10-25) texte{Trace}(B)=sum_{i=1}^k|C_i|d(overline{X}_i,overline{X})^2tag{10-25}Tracerrrr(B)=je=1kCjed(Xje,X)2(10-25) Autrement dit, Trace(B) regroupe CCCChaque point central du cluster de SSSLa somme pondérée des distances carrées à partir du point central de .
De là, si N = ∑ i = 1 k ∣ C i ∣N=kje=1|Cje| N=je=1kCje L’indicateur CH peut alors être défini comme
V CH ( k ) = Trace ( B ) / ( k − 1 ) Trace ( A ) / ( N − k ) (10-26) V_{texte{CH}}(k)=frac{texte{Trace}(B)/(k-1)}{texte{Trace}(A)/(Nk)}balise{10-26}VCH(k)=Tracerrrr(UN)/(Nk)Tracerrrr(B)/(k1)(10-26) La formule (10-26) est généralement utilisée dans les deux situations suivantes :
(1) Évaluez quel clustering obtenu par les deux algorithmes est le meilleur.
Supposons que deux algorithmes soient utilisés pour analyser l'ensemble de données SSSUne analyse groupée a été réalisée et deux clusters différents (tous deux contenant kkclusters), le clustering correspondant à la valeur CH la plus grande est meilleur, car plus la valeur CH est grande, cela signifie que chaque cluster du cluster est plus proche de lui-même et que les clusters sont plus dispersés.
(2) Évaluez lequel des deux clusters avec un nombre différent de clusters obtenus par le même algorithme est le meilleur.
Supposons qu'un algorithme possède un ensemble de données SSSUne analyse de grappes a été effectuée et le nombre de grappes a été obtenu comme suit : k 1 k_1k1et b 2 b_2b2 Parmi les deux clusters, le résultat du clustering avec une valeur CH plus grande est meilleur, ce qui signifie également que le nombre de clusters correspondant à ce cluster est plus approprié.Par conséquent, en appliquant à plusieurs reprises la formule (10-26), nous pouvons également obtenir un ensemble de données SSSLe nombre optimal de clusters pour le clustering.

2. Indicateur Dunn

L'indicateur Dunn utilise des clusters C i C_iCjeavec grappe C j C_jCjdistance minimale entre ds ( C i , C j ) d_s(C_i,C_j)dm(Cje,Cj) pour calculer la séparation inter-clusters en utilisant le plus grand diamètre de cluster parmi tous les clusters max ⁡ { Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } max{varPhi(C_1), varPhi(C_2),...,varPhi(C_k)}max{Φ(C1),Φ(C2),...,Φ(Ck)} Pour caractériser l'étroitesse au sein d'un cluster, l'indice de Dunn est la valeur minimale du rapport entre le premier et le second, soit
VD ( k ) = min ⁡ i ≠ jds ( C i , C j ) max ⁡ { Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } (10-27) V_D(k)=min_{i≠j}frac{d_s(C_i,C_j)}{max{varPhi(C_1), varPhi(C_2),...,varPhi (C_k)}}balise{10-27}VD(k)=je=jminmax{Φ(C1),Φ(C2),...,Φ(Ck)}dm(Cje,Cj)(10-27) Plus la valeur de Dunn est grande, plus la distance entre les clusters est grande et meilleur est le clustering correspondant.Semblable à l'indice d'évaluation CH, l'indice Dunn peut être utilisé pour évaluer la qualité des clusters obtenus par différents algorithmes, et peut également être utilisé pour évaluer quels clusters obtenus par le même algorithme avec un nombre différent de clusters sont les meilleurs, c'est-à-dire qu'il peut être utilisé pour rechercher SSSle nombre optimal de clusters.

6. Exploitation minière aberrante

Les valeurs aberrantes sont des données spéciales dans l'ensemble de données qui s'écartent considérablement de la plupart des données. L'objectif des algorithmes d'exploration de données tels que la classification et le clustering introduits précédemment est de découvrir des modèles réguliers qui s'appliquent à la plupart des données. Par conséquent, de nombreux algorithmes d'exploration de données tentent de réduire ou d'éliminer l'impact des valeurs aberrantes et de réduire les valeurs aberrantes lors de la mise en œuvre de l'exploration. ou ignorés en tant que bruit, mais dans de nombreuses applications pratiques, les gens soupçonnent que la déviation des points aberrants n'est pas causée par des facteurs aléatoires, mais peut être causée par d'autres mécanismes complètement différents, qui doivent être découverts pour une analyse et une utilisation spéciales. Par exemple, dans des domaines d’application tels que la gestion de la sécurité et le contrôle des risques, le modèle d’identification des valeurs aberrantes est plus précieux que le modèle des données normales.

(1) Aperçu des questions connexes

Le mot Outlier est généralement traduit par valeur aberrante, mais aussi par anomalie. Cependant, il existe de nombreux alias dans différentes situations d'application, telles que des points isolés, des points anormaux, des points nouveaux, des points d'écart, des points d'exception, du bruit, des données anormales, etc. L'exploration de données aberrantes a des termes similaires tels que l'exploration de données d'anomalies, la détection de données d'anomalies, l'exploration de données aberrantes, l'exploration de données d'exception et l'exploration d'événements rares dans la littérature chinoise.

1. La génération des valeurs aberrantes

(1) Les données proviennent d'anomalies causées par des fraudes, des intrusions, des épidémies, des résultats expérimentaux inhabituels, etc. Par exemple, la facture de téléphone moyenne d'une personne est d'environ 200 yuans, mais augmente soudainement jusqu'à plusieurs milliers de yuans au cours d'un certain mois ; la carte de crédit d'une personne consomme généralement environ 5 000 yuans par mois, mais au cours d'un certain mois, la consommation dépasse 30 000 yuans, etc. De telles valeurs aberrantes sont généralement relativement intéressantes en data mining et constituent l’un des points clés d’application.
(2) Causé par des changements inhérents aux variables de données, reflétant les caractéristiques naturelles de la distribution des données, telles que le changement climatique, les nouvelles habitudes d'achat des clients, les mutations génétiques, etc. C’est également l’un des domaines d’intérêt intéressants.
(3) Les erreurs de mesure et de collecte des données sont principalement dues à une erreur humaine, à une défaillance des équipements de mesure ou à la présence de bruit. Par exemple, la note d'un étudiant de -100 dans un certain cours peut être due à la valeur par défaut fixée par le programme ; le salaire des cadres supérieurs d'une entreprise est nettement supérieur à celui des employés ordinaires. Cela peut sembler aberrant, mais c'est le cas. Données raisonnables.

2. Problème minier aberrant

Habituellement, le problème minier aberrant peut être décomposé en trois sous-problèmes à décrire.
(1) Définir les valeurs aberrantes
Étant donné que les valeurs aberrantes sont étroitement liées à des problèmes pratiques, définir clairement quels types de données sont des valeurs aberrantes ou anormales est la prémisse et la tâche principale de l'exploration des valeurs aberrantes. En général, il est nécessaire de combiner l'expérience et les connaissances des experts du domaine pour fournir une analyse précise des valeurs aberrantes. . Donnez une description ou une définition appropriée.
(2) Valeurs aberrantes du secteur minier
Une fois les points aberrants clairement définis, l'algorithme à utiliser pour identifier ou exploiter efficacement les points aberrants définis est la tâche clé de l'exploration des valeurs aberrantes. L'algorithme d'exploration des valeurs aberrantes fournit généralement aux utilisateurs des données aberrantes suspectes du point de vue des modèles qui peuvent se refléter dans les données, afin d'attirer l'attention de l'utilisateur.
(3) Comprendre les valeurs aberrantes
Une explication raisonnable, une compréhension et des conseils sur l'application pratique des résultats de l'exploitation minière sont les objectifs de l'exploitation minière aberrante. Étant donné que le mécanisme par lequel les valeurs aberrantes sont générées est incertain, la question de savoir si les « valeurs aberrantes » détectées par l'algorithme d'exploration des valeurs aberrantes correspondent réellement au comportement anormal réel ne peut pas être expliquée et expliquée par l'algorithme d'exploration des valeurs aberrantes, mais ne peut être expliquée que par l'algorithme d'exploration des valeurs aberrantes. . Des experts du secteur ou du domaine pour comprendre et expliquer les instructions.

3. Relativité des valeurs aberrantes

Les valeurs aberrantes sont des données spéciales dans l'ensemble de données qui s'écartent évidemment de la plupart des données, mais « évidemment » et « principalement » sont relatives, c'est-à-dire que même si les valeurs aberrantes sont différentes, elles sont relatives. Par conséquent, plusieurs problèmes doivent être pris en compte lors de la définition et de l’exploration des valeurs aberrantes.
(1) Valeurs aberrantes mondiales ou locales
Un objet de données peut être une valeur aberrante par rapport à ses voisins locaux, mais pas par rapport à l'ensemble de données dans son ensemble. Par exemple, un élève mesurant 1,9 mètre est une exception dans la classe 1 de la spécialisation en mathématiques de notre école, mais pas parmi les gens à travers le pays, y compris les joueurs professionnels tels que Yao Ming.
(2) Nombre de valeurs aberrantes
Bien que le nombre de points aberrants soit inconnu, le nombre de points normaux devrait largement dépasser le nombre de points aberrants. Autrement dit, le nombre de points aberrants devrait représenter une proportion plus faible dans le grand ensemble de données. des points aberrants Il devrait être inférieur à 5 %, voire inférieur à 1 %.
(3) Facteur aberrant du point
Vous ne pouvez pas utiliser « oui » ou « non » pour indiquer si un objet est une valeur aberrante. Vous devez plutôt utiliser le degré d'écart de l'objet, c'est-à-dire le facteur de valeur aberrante (Outlier Factor) ou le score de valeur aberrante (Outlier Score). pour caractériser l'écart d'une donnée par rapport au degré du groupe, puis filtrer les objets présentant des facteurs aberrants supérieurs à un certain seuil, les fournir aux décideurs ou aux experts du domaine pour compréhension et explication, et les appliquer dans des travaux pratiques.

(2) Méthode basée sur la distance

1. Notions de base

Définition 10-11 Il existe un entier positif kk, objet XXXde kk-La distance du voisin le plus proche est un entier positif qui satisfait aux conditions suivantes dk ( X ) d_k(X)dk(X)
(1) sauf XXXDe plus, il y a au moins kkobjets OuiYsatisfaire d ( X , Y ) ≤ dk ( X ) d(X,Y)≤d_k(X)d(X,Y)dk(X)
(2) sauf XXXDe plus, il y a au plus k − 1 k-1k1 objets OuiYsatisfaire d ( X , Y ) &lt; dk ( X ) d(X,Y)d(X,Y)<dk(X)
dans d(X,Y)d(X,Y) est un objet XXXet OuiYune certaine distance fonctionne entre eux.

d'un objet kk-Plus la distance du voisin le plus proche est grande, plus il est probable que l'objet soit éloigné de la plupart des données, donc l'objet peut être XXXde kk-distance du voisin le plus proche dk ( X ) d_k(X)dk(X) comme facteur aberrant.

Définition 10-12 faire D ( X , k ) = { Y ∣ d ( X , Y ) ≤ dk ( X ) ∧ Y ≠ X } D(X,k)={Y|d(X,Y)≤d_k(X)coin Y≠X}D(X,k)={Yd(X,Y)dk(X)Y=X}, alors on l'appelle D ( X , k ) D(X,k)D(X,k) Oui XXXde kk-Voisin le plus proche (domaine).

Il ressort des définitions 10 à 12 que D ( X , k ) D(X,k)D(X,k) Oui XXXcomme centre, distance XXXNe dépasse pas dk ( X ) d_k(X)dk(X) Objet OuiY La collection composée de. Cela mérite une attention particulière, XXXn'en fait pas partie kk-le voisin le plus proche, c'est-à-dire X ∉ D ( X , k ) Xnotin D(X,k)X/D(X,k) . En particulier, XXXde kk-voisin le plus proche D ( X , k ) D(X,k)D(X,k) Le nombre d'objets contenus peut dépasser de loin kk,Tout de suite ∣ D ( X , k ) ∣ ≥ k |D(X,k)|≥kD(X,k)k

Définition 10-13 Il existe un entier positif kk, objet XXXde kk-Le facteur aberrant du voisin le plus proche est défini comme
DE 1 ( X , k ) = ∑ Y ∈ D ( X , k ) d ( X , Y ) ∣ D ( X , k ) ∣ (10-28) texte{DE}_1(X,k)=frac{mathop{somme}limites_{Yin D(X,k)}d(X,Y)}{|D(X,k)|}balise{10-28}DE1(X,k)=D(X,k)YD(X,k)d(X,Y)(10-28)

2. Description de l'algorithme

Pour un ensemble de données donné et le nombre de distances des voisins les plus proches kk, nous pouvons utiliser la formule ci-dessus pour calculer le kk-Les facteurs aberrants des voisins les plus proches, et les afficher par ordre de grand à petit, parmi eux, plusieurs objets avec des facteurs aberrants plus importants sont les plus susceptibles d'être des valeurs aberrantes. Généralement, ils doivent être analysés et jugés par les décideurs ou les experts de l'industrie. , Quels points sont vraiment aberrants.

Algorithme 10-8 Algorithme de détection des valeurs aberrantes basé sur la distance
Entrée : ensemble de données SSS, le nombre de distances entre voisins les plus proches kk
Résultat : liste décroissante des points aberrants suspectés et des facteurs aberrants correspondants
(1)RÉPÉTER
(2) Prenez SSSun objet non traité dans XXX
(3) D'accord XXXde kk-voisin le plus proche D ( X , k ) D(X,k)D(X,k)
(4) Calcul XXXde kk-facteur aberrant du voisin le plus proche DE 1 ( X , k ) texte{DE}_1(X,k)DE1(X,k)
(5)JUSQU'À SSSChaque point a été traité
(6) Oui DE 1 ( X , k ) texte{DE}_1(X,k)DE1(X,k)Trier par ordre décroissant et sortie ( X , DE 1 ( X , k ) ) (X,texte{DE}_1(X,k))(X,DE1(X,k))

3. Exemples de calcul

Exemple 10-12 Un ensemble de données bidimensionnelles avec 11 points SSSIl est donné par le tableau 10-10, soit k = 2 k=2k=2, utilisez le calcul de la distance euclidienne au carré X 7 , X 10 , X 11 X_7, X_{10}, X_{11}X7,X10,X11 Facteur aberrant par rapport à tous les autres points.

Insérer la description de l'image ici
délier: Afin de comprendre intuitivement le principe de l’algorithme, nous allons SSSLes objets de données sont affichés sur le plan de la figure (10-27) ci-dessous.

Insérer la description de l'image ici
Ce qui suit calcule respectivement les facteurs aberrants du point spécifié et des autres points.

(1) Objet de calcul X 7 X_7X7facteur aberrant
Comme le montre la figure, la distance X7 = ( 6 , 8 ) X_7=(6,8)X7=(6,8) Le point le plus proche est X 10 = ( 5 , 7 ) X_{10}=(5,7)X10=(5,7),et d ( X 7 , X 10 ) = 1,41 d(X_7,X_{10}) =1,41d(X7,X10)=1.41, d'autres points les plus proches peuvent être X 11 = ( 5 , 2 ) X_{11}=(5,2)X11=(5,2) X 9 = ( 3 , 2 ) X_9=(3,2)X9=(3,2) X8 = ( 2 , 4 ) X_8=(2,4)X8=(2,4)
Calculé d ( X 7 , X 11 ) = 6,08 d(X_7,X_{11})=6,08d(X7,X11)=6.08 d ( X 7 , X 9 ) = 6,71 d(X_7,X_9)=6,71d(X7,X9)=6.71 d ( X 7 , X 8 ) = 5,66 d(X_7,X_8)=5,66d(X7,X8)=5.66
parce que k = 2 k=2k=2,donc d 2 ( X 7 ) = 5,66 d_2(X_7)=5,66d2(X7)=5.66, donc selon la définition 10-11 nous avons D ( X 7 , 2 ) = { X 10 , X 8 } D(X_7,2)={X_{10},X_8}D(X7,2)={X10,X8}
D'après la formule (10-28), X 7 X_7X7facteur aberrant
DE 1 ( X 7 , 2 ) = ∑ Y ∈ N ( X 7 , 2 ) d ( X 7 , Y ) ∣ N ( X 7 , k ) ∣ = d ( X 7 , X 10 ) + d ( X 7 , X 8 ) 2 = 1,41 + 5,66 2 = 3,54DE1(X7,2)=YN(X7,2)d(X7,Y)|N(X7,k)|=d(X7,X10)+d(X7,X8)2=1.41+5.662=3.54 DE1(X7,2)=N(X7,k)YN(X7,2)d(X7,Y)=2d(X7,X10)+d(X7,X8)=21.41+5.66=3.54(2) Objet de calcul X 10 X_{10}X10facteur aberrant DE 1 ( X 10 , 2 ) = 2,83 texte{DE}_1(X_{10},2)=2,83DE1(X10,2)=2.83

(3) Objet de calcul X 11 X_{11}X11facteur aberrant DE 1 ( X 11 , 2 ) = 2,5 texte{DE}_1(X_{11},2)=2,5DE1(X11,2)=2.5

(4) Objet de calcul X 5 X_{5}X5facteur aberrant DE 1 ( X 5 , 2 ) = 1 texte{DE}_1(X_{5},2)=1DE1(X5,2)=1

De même, les facteurs aberrants des objets restants peuvent être calculés, voir le tableau suivant (10-11).

Insérer la description de l'image ici
4. Seuil de facteur aberrant

selon kk -Dans la théorie du voisin le plus proche, plus le facteur de valeur aberrante est grand, plus il est probable qu'il s'agisse d'une valeur aberrante. Par conséquent, un seuil doit être spécifié pour distinguer les valeurs aberrantes des points normaux. La méthode la plus simple consiste à spécifier le nombre de points aberrants, mais cette méthode est trop simple et manque parfois de véritables points aberrants ou attribue trop de points normaux à d'éventuels points aberrants, ce qui rend difficile la tâche des experts du domaine ou des décideurs. dans la compréhension et l’interprétation des valeurs aberrantes.
(1) La méthode du seuil de segmentation des facteurs aberrants organise d'abord les facteurs aberrants par ordre décroissant, et en même temps renumérote les objets de données par ordre croissant en fonction des facteurs aberrants.
(2) Sur la base du facteur aberrant DE 1 ( X , k ) texte{DE}_1(X,k)DE1(X,k) est l'ordonnée et le numéro de série du facteur aberrant est l'abscisse, c'est-à-dire (numéro de série, DE 1 texte{DE}_1DE1valeur) sont marqués sur le plan et connectés pour former une polyligne non croissante, et le point où la polyligne se croise avec une forte diminution et une légère diminution correspond au facteur aberrant comme seuil. supérieur ou égal à ce seuil sont des objets normaux, les autres sont d'éventuelles valeurs aberrantes.

Exemple 10-13 Ensemble de données pour l'exemple 10-12 SSS , ses facteurs aberrants sont résumés par ordre décroissant et numéro de série dans le tableau 10-11. Essayez de trouver le seuil des points aberrants en fonction de la méthode du seuil de segmentation des facteurs aberrants.

délier: Tout d'abord, utilisez le (numéro de série, DE 1 texte{DE}_1DE1 valeur) sous forme de points sur le plan, marqués sur le plan et reliés par des polylignes. Comme le montre la figure 10-28 ci-dessous.

Insérer la description de l'image ici
En regardant ensuite la figure 10-28, nous pouvons constater que la polyligne à gauche du quatrième point (4, 1,27) chute très fortement, tandis que la polyligne à droite chute très doucement. Par conséquent, le facteur de valeur aberrante 1,27 est sélectionné comme facteur. seuil.parce que X 7, X 10 X_7, X_{10}X7X10 et X 11 X_{11}X11 Les facteurs aberrants sont respectivement de 3,54, 2,83 et 2,5, qui sont tous supérieurs à 1,27. Par conséquent, ces trois points sont très probablement des points aberrants, tandis que les points restants sont des points ordinaires.
En regardant à nouveau la figure 10-27, nous pouvons constater que X 7, X 10 X_7, X_{10}X7X10 et X 11 X_{11}X11 en effet loin de la majorité dense des objets sur la gauche, alors traitez-les comme un ensemble de données SSSLes valeurs aberrantes sont raisonnables.

5. Évaluation de l'algorithme

Le plus grand avantage de la méthode de détection des valeurs aberrantes basée sur la distance est qu'elle est simple dans son principe et facile à utiliser. Ses inconvénients se reflètent principalement dans les aspects suivants.
(1) Paramètres kkLa sélection ne dispose pas d'une méthode simple et efficace pour déterminer l'impact des résultats des tests sur les paramètres kkIl n’existe pas de résultat analytique universellement accepté sur le degré de sensibilité.
(2) La complexité temporelle est O ( ∣ S ∣ 2 ) O(|S|^2)O(S2), manque d’évolutivité pour des ensembles de données à grande échelle.
(3) En raison de l'utilisation d'un seuil global de facteur de valeur aberrante, il est difficile d'extraire les valeurs aberrantes dans des ensembles de données comportant des régions de densités différentes.

(3) Méthode basée sur la densité relative

La méthode de distance est une méthode globale de vérification des valeurs aberrantes, mais elle ne peut pas gérer des ensembles de données dans des zones de densité différentes, c'est-à-dire qu'elle ne peut pas détecter les valeurs aberrantes dans les zones de densité locales. Dans les applications pratiques, toutes les données ne sont pas distribuées avec une seule densité. Lorsque l'ensemble de données contient plusieurs distributions de densité ou est un mélange de différents sous-ensembles de densité, les méthodes globales de détection des valeurs aberrantes telles que la distance ne fonctionnent généralement pas bien, car le fait qu'un objet soit une valeur aberrante ne dépend pas seulement de sa relation avec les données environnantes. est lié à la densité du quartier.

1. Le concept de densité relative

Du point de vue du voisinage de densité, les valeurs aberrantes sont des objets situés dans des zones à faible densité. Par conséquent, il est nécessaire d'introduire les concepts de densité de quartier local et de densité relative des objets.

Définition 10-14 (1) un objet XXXde kk-La densité locale (densité) du voisin le plus proche est définie comme
dsty ( X , k ) = ∣ D ( X , k ) ∣ ∑ Y ∈ D ( X , k ) d ( X , Y ) (10-29) texte{dsty}(X,k)=frac{|D(X,k)|}{mathop{somme}limites_{Yin D(X,k)}d(X,Y)}balise{10-29}dsty(X,k)=YD(X,k)d(X,Y)D(X,k)(10-29) (2) un objet XXXde kk-Densité relative locale du voisin le plus proche (densité relative)
rdsty ( X , k ) = ∑ Y ∈ D ( X , k ) dsty ( X , k ) / ∣ D ( X , k ) ∣ dsty ( X , k ) (10-30) texte{rdsty}(X,k)=frac{mathop{somme}limites_{Yin D(X,k)}texte{dsty}(X,k)/|D(X,k)|}{texte{dsty}(X,k)}balise{10-30}rdsty(X,k)=dsty(X,k)YD(X,k)dsty(X,k)/∣D(X,k)(10-30) dans D ( X , k ) D(X,k)D(X,k) C'est l'objet XXXde kk- le voisin le plus proche (donné dans la Définition 10-12), ∣ D ( X , k ) ∣ |D(X,k)|D(X,k) est le nombre d'objets dans la collection.

2. Description de l'algorithme

par rdsty ( X , k ) texte{rdsty}(X,k)rdsty(X,k) comme une valeur aberrante DE 2 ( X , k ) texte{DE}_2(X,k)DE2(X,k), son calcul est divisé en deux étapes
(1) Selon le nombre de voisins kk, calcule chaque objet XXXde kk-Densité locale du voisin le plus proche dsty ( X , k ) texte{dsty}(X,k)dsty(X,k)
(2) Calcul XXXla densité moyenne des voisins les plus proches et kk-Densité relative locale du voisin le plus proche rdsty ( X , k ) texte{rdsty}(X,k)rdsty(X,k)
Un ensemble de données se compose de plusieurs clusters naturels. La densité relative des objets proches du point central au sein du cluster est proche de 1, tandis que la densité relative des objets au bord du cluster ou à l'extérieur du cluster est relativement grande. Par conséquent, plus la valeur de densité relative est élevée, plus il est probable qu’il s’agisse d’une valeur aberrante.

Algorithme 10-9 Algorithme de détection des valeurs aberrantes basé sur la densité relative
Entrée : ensemble de données SSS, le nombre de voisins les plus proches kk
Résultat : liste décroissante des points aberrants suspectés et des facteurs aberrants correspondants
(1)RÉPÉTER
(2) Prenez SSSun objet non traité dans XXX
(3) D'accord XXXde kk-voisin le plus proche D ( X , k ) D(X,k)D(X,k)
(4) Utilisation D ( X , k ) D(X,k)D(X,k)calculer XXXDensité dsty ( X , k ) texte{dsty}(X,k)dsty(X,k)
(5)JUSQU'À SSSChaque point a été traité
(6)RÉPÉTER
(7) Prenez SSSpremier objet dans XXX
(8) D'accord XXXdensité relative de rdsty ( X , k ) texte{rdsty}(X,k)rdsty(X,k), et attribuez-le à DE 2 ( X , k ) texte{DE}_2(X,k)DE2(X,k)
(9)JUSQU'À SSSTous les objets ont été traités
(10) Droite DE 2 ( X , k ) texte{DE}_2(X,k)DE2(X,k)Trier par ordre décroissant et sortie ( X , DE 2 ( X , k ) ) (X,texte{DE}_2(X,k))(X,DE2(X,k))

Exemple 10-14 Pour l'ensemble de données bidimensionnelles donné dans l'exemple 10-12 SSS (Voir le tableau 10-10 pour plus de détails), donc k = 2 k=2k=2, essayez de calculer la distance euclidienne X 7 , X 10 , X 11 X_7, X_{10}, X_{11}X7,X10,X11 Facteur aberrant basé sur la densité relative d’objets égaux.

Insérer la description de l'image ici
délier:parce que k = 2 k=2k=2, nous avons donc besoin de la densité locale des 2 voisins les plus proches de tous les objets.

(1) Trouvez les 2 voisins les plus proches de chaque objet de données dans le tableau 10-11. D ( X i , 2 ) D(X_i,2)D(Xje,2)
Selon la même méthode de calcul de l'exemple 10-12, on peut obtenir
D ( X 1 , 2 ) = { X 2 , X 3 , X 5 } , D ( X 2 , 2 ) = { X 1 , X 6 } , D ( X 3 , 2 ) = { X 1 , X 4 } , D ( X 4 , 2 ) = { X 3 , X 5 } , D ( X 5 , 2 ) = { X 1 , X 4 , X 6 , X 9 } , D ( X 6 , 2 ) = { X 2 , X 5 , X 8 } , D ( X 7 , 2 ) = { X 10 , X 8 } , D ( X 8 , 2 ) = { X 2 , X 6 } , D ( X 9 , 2 ) = { X 5 , X 4 , X 6 } , D ( X 10 , 2 ) = { X 7 , X 8 } , D ( X 11 , 2 ) = { X 9 , X 5 }D(X1,2)={X2,X3,X5}D(X2,2)={X1,X6}              D(X3,2)={X1,X4}D(X4,2)={X3,X5}       D(X5,2)={X1,X4,X6,X9}D(X6,2)={X2,X5,X8}D(X7,2)={X10,X8}     D(X8,2)={X2,X6}               D(X9,2)={X5,X4,X6}D(X10,2)={X7,X8}     D(X11,2)={X9,X5} D(X1,2)={X2,X3,X5}D(X2,2)={X1,X6}              D(X3,2)={X1,X4}D(X4,2)={X3,X5}       D(X5,2)={X1,X4,X6,X9}D(X6,2)={X2,X5,X8}D(X7,2)={X10,X8}     D(X8,2)={X2,X6}               D(X9,2)={X5,X4,X6}D(X10,2)={X7,X8}     D(X11,2)={X9,X5}

(2) Calculer la densité locale de chaque objet de données dsty ( X i , 2 ) texte{dsty}(X_i,2)dsty(Xje,2)

① Calculer X 1 X_1X1Densité
parce que D ( X 1 , 2 ) = { X 2 , X 3 , X 5 } D(X_1,2)={X_2,X_3,X_5}D(X1,2)={X2,X3,X5}, donc après calcul, on a d ( X 1 , X 2 ) = 1 d(X_1,X_2)=1d(X1,X2)=1 d ( X 1 , X 3 ) = 1 d(X_1,X_3)=1d(X1,X3)=1 d ( X 1 , X 5 ) = 1 d(X_1,X_5)=1d(X1,X5)=1
D'après la formule (10-29), on obtient :
dsty ( X 1 , 2 ) = ∣ D ( X 1 , 2 ) ∣ ∑ Y ∈ N ( X 1 , 2 ) d ( X 1 , Y ) = ∣ N ( X 1 , 2 ) ∣ d ( X 1 , X 2 ) + d ( X 1 , X 3 ) + d ( X 1 , X 5 ) = 3 1 + 1 + 1 = 1dsty(X1,2)=|D(X1,2)|YN(X1,2)d(X1,Y)=|N(X1,2)|d(X1,X2)+d(X1,X3)+d(X1,X5)=31+1+1=1 dsty(X1,2)=YN(X1,2)d(X1,Y)D(X1,2)=d(X1,X2)+d(X1,X3)+d(X1,X5)N(X1,2)=1+1+13=1

② Calcul X-2 X_2X2Densité
parce que D ( X 2 , 2 ) = { X 1 , X 6 } D(X_2,2)={X_1,X_6}D(X2,2)={X1,X6}, donc le calculé d ( X 2 , X 1 ) = 1 d(X_2,X_1) =1d(X2,X1)=1 d ( X 2 , X 6 ) = 1 d(X_2,X_6) =1d(X2,X6)=1
D'après la formule (10-29), on obtient :
dsty ( X 2 , 2 ) = ∣ D ( X 2 , 2 ) ∣ ∑ Y ∈ N ( X 2 , 2 ) d ( X 2 , Y ) = 2 1 + 1 = 1dsty(X2,2)=|D(X2,2)|YN(X2,2)d(X2,Y)=21+1=1 dsty(X2,2)=YN(X2,2)d(X2,Y)D(X2,2)=1+12=1

La densité locale d'autres objets de données peut être calculée de la même manière, voir le tableau 10-12 ci-dessous.

Insérer la description de l'image ici
(3) Calculer chaque objet X et X_iXjedensité relative de rdsty ( X i , 2 ) texte{rdsty}(X_i, 2)rdsty(Xje,2), et le considère comme un facteur aberrant Texte DE 2 {DE}_2DE2
① Calculer X 1 X_1X1densité relative de
En utilisant la valeur de densité de chaque objet dans le tableau 10-12, selon la formule de densité relative (10-30) :
rdsty ( X 1 , 2 ) = ∑ Y ∈ N ( X 1 , 2 ) dsty ( Y , 2 ) / ∣ N ( X 1 , 2 ) ∣ dsty ( X 1 , 2 ) = ( 1 + 1 + 1 ) / 3 1 = 1 = DE 2 ( X 1 , 2 )rdsty(X1,2)=YN(X1,2)dsty(Y,2)/|N(X1,2)|dsty(X1,2)=(1+1+1)/31=1=DE2(X1,2) rdsty(X1,2)=dsty(X1,2)YN(X1,2)dsty(Y,2)/∣N(X1,2)=1(1+1+1)/3=1=DE2(X1,2)

② Un calcul similaire peut être obtenu X 2, X 3, …, X 11 X_2, X_3,…, X_{11}X2X3X11 valeur de densité relative.
Par exemple X 5 X_5X5La densité relative de :
rdsty ( X 5 , 2 ) = ∑ Y ∈ N ( X 5 , 2 ) dsty ( Y , 2 ) / ∣ N ( X 5 , 2 ) ∣ dsty ( X 5 , 2 ) = ( 1 + 1 + 1 + 0,79 ) / 4 1 = 0,95 = DE 2 ( X 5 , 2 )rdsty(X5,2)=YN(X5,2)dsty(Y,2)/|N(X5,2)|dsty(X5,2)=(1+1+1+0.79)/41=0.95=DE2(X5,2) rdsty(X5,2)=dsty(X5,2)YN(X5,2)dsty(Y,2)/∣N(X5,2)=1(1+1+1+0.79)/4=0.95=DE2(X5,2) Les résultats sont résumés dans les tableaux 10 à 13 ci-dessous.

Insérer la description de l'image ici
Exemple 10-15 Compte tenu de l'ensemble de données présenté dans le tableau 10-14, veuillez utiliser la distance euclidienne pour k = 2 , 3 , 5 k=2,3,5k=2,3,5, calculez la valeur de chaque point kk-densité locale du voisin le plus proche, kk-Densité relative locale du voisin le plus proche (facteur aberrant Texte DE 2 {DE}_2DE2) et basé sur kk-Facteur aberrant pour la distance du voisin le plus proche DE 1 texte{DE}_1DE1

Insérer la description de l'image ici
délier: (1) Afin de faciliter la compréhension, il peut être SSSLes positions relatives des points sont marquées sur le plan bidimensionnel (Figure 10-30).

Insérer la description de l'image ici
(2) Utiliser les algorithmes basés sur la distance et la densité relative 10-8 et 10-9 respectivement.Calculer chaque objet séparément kk-Densité locale du voisin le plus proche texte dsty{dsty}dsty kk-Densité relative locale du voisin le plus proche (facteur aberrant Texte DE 2 {DE}_2DE2) et basé sur kk-Facteur aberrant pour la distance du voisin le plus proche DE 1 texte{DE}_1DE1, les résultats sont résumés dans le tableau 10-15.

Insérer la description de l'image ici
(3) Analyse simple
① Comme le montre la figure 10-30, X 15 X_{15}X15et X 16 X_{16}X16Oui SSSIl existe deux valeurs aberrantes évidentes, et les méthodes basées sur la distance et la densité relative peuvent mieux les identifier ;
② A partir de cet exemple, les deux algorithmes ont kkn'est pas aussi sensible que prévu, c'est peut-être une valeur aberrante. X 15 X_{15}X15et X 16 X_{16}X16La séparation des autres objets est très évidente.
③Comme le montre le tableau 10-15, peu importe kkPrenez-en 2, 3 ou 5, X 1 X_1X1de la région texte dsty{dsty}dsty les valeurs sont nettement inférieures à X 7 X_7X7de la région texte dsty{dsty}dsty valeur, qui est cohérente avec la densité de zone illustrée à la figure 10-30.Mais la valeur de densité relative des deux régions Texte DE 2 {DE}_2DE2 Mais il n’y a pratiquement aucune différence évidente. Ceci est déterminé par la nature de la densité relative, c'est-à-dire que pour des points de données uniformément répartis, la densité relative des points centraux est de 1, quelle que soit la distance entre les points.

7. Autres méthodes de regroupement

1. Algorithme de clustering amélioré

  (1) kk-mod ( kk-modes) l'algorithme est pour kk -L'algorithme de moyenne ne convient que pour la limitation des attributs numériques et est proposé pour réaliser un regroupement rapide de données discrètes.parce que kk-L'algorithme modulaire utilise une simple méthode de correspondance 0-1 pour calculer la distance entre deux valeurs d'attribut sous le même attribut discret, ce qui affaiblit la différence entre les valeurs d'attribut ordinales, c'est-à-dire qu'il ne peut pas refléter pleinement la différence entre deux valeurs d'attribut. Sous le même attribut ordinal, il y a encore place à l'amélioration et à l'amélioration.
  (2) kk-prototype ( kk-Prototype) algorithme combiné avec kk-Algorithme de moyenne avec kk -L'avantage de l'algorithme modulaire est qu'il peut regrouper des ensembles de données avec des attributs à la fois discrets et numériques (appelés attributs mixtes).Il faut des attributs discrets kk-Objet de calcul d'algorithme modulaire XXXet OuiYla distance entre d 1 ( X , Y ) d_1(X,Y)d1(X,Y), pour les attributs numériques, utilisez kk-Les méthodes de l'algorithme de moyenne calculent la distance entre les objets d_2(X,Y)d2(X,Y), et enfin utiliser la méthode de pondération, c'est-à-dire α d 1 ( X , Y ) + ( 1 − α ) d 2 ( X , Y ) alpha d_1(X,Y)+(1-alpha)d_2(X,Y)αd1(X,Y)+(1α)d2(X,Y) en tant qu'objet d'ensemble de données XXXet OuiYla distance entre d(X,Y)d(X,Y),dans α ∈ [ 0 , 1 ] alphain[0,1]α[0,1] est le coefficient de poids, il peut généralement être α = 0,5 alpha=0,5α=0.5
(3) L'algorithme BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) est une méthode de clustering hiérarchique complète.Il utilise les fonctionnalités de clustering (CF) et l'arbre de fonctionnalités de clustering (CF Tree, similaire à B-tree) pour résumer les clusters de clusters. C i C_iCje,dans CF i = ( ni , LS i , SS i ) texte{CF}_i=(ni, texte{LS}_i,texte{SS}_i)CFje=(ni,LSje,SSje) est un triplet, ni n_injeest le nombre d'objets dans le cluster, LS je texte{LS}_iLSjeOui ni n_injesomme linéaire des composants de l'objet, SS i texte{SS}_iSSjeOui ni n_injeLa somme des carrés des composants d'un objet.
(4) L'algorithme CURE (Clustering Using Representatives) est destiné kk -Une autre amélioration de l'algorithme de moyenne. De nombreux algorithmes de clustering ne sont efficaces que pour regrouper des clusters sphériques, tandis que certains algorithmes de clustering sont plus sensibles aux points isolés. Afin de résoudre les deux problèmes ci-dessus, l'algorithme CURE a changé kk-L'algorithme de moyenne utilise la somme centrale du cluster kk-L'algorithme du point central utilise un seul objet spécifique pour représenter un cluster, une méthode traditionnelle, mais utilise plusieurs objets représentatifs dans le cluster pour représenter un cluster, afin qu'il puisse s'adapter au clustering de clusters non sphériques et réduire l'impact de bruit sur le clustering.
(5) L'algorithme ROCK (RObust Clustering using linK) est un algorithme de clustering proposé pour les ensembles de données d'attributs binaires ou catégoriels.
(6) L'algorithme OPTICS (Ordering Points To Identity the Clustering Structure) est utilisé pour réduire la densité de l'algorithme DBSCAN. ( ε , MinPts ) (varepsilon,texte{MinPts})(ε,MinPts) sensibilité des paramètres. Il ne génère pas explicitement de clusters de résultats, mais génère un classement de cluster augmenté pour l'analyse de cluster (par exemple, un diagramme de coordonnées avec la distance accessible comme axe vertical et l'ordre de sortie des points d'échantillonnage comme axe horizontal). Ce classement représente la structure de regroupement basée sur la densité de chaque point d'échantillonnage.Nous pouvons obtenir de ce tri en fonction de n'importe quel paramètre de densité ( ε , MinPts ) (varepsilon,texte{MinPts})(ε,MinPts) Résultats de clustering de l'algorithme DBSCAN.

2. Autres nouvelles méthodes de clustering

Utilisez de nouvelles théories ou techniques pour concevoir de nouvelles méthodes de clustering.

(1) Méthode de clustering basée sur une grille
La méthode basée sur une grille quantifie l'espace objet en un nombre limité de cellules pour former une structure de grille, et les informations de position des points de division dans chaque dimension sont stockées dans le tableau. Les lignes de séparation traversent tout l'espace et tout le regroupement. les opérations sont effectuées dans Effectué sur cette structure de grille (c'est-à-dire l'espace de quantification). Le principal avantage de cette méthode est que sa vitesse de traitement est très rapide. Sa vitesse de traitement est indépendante du nombre d'objets de données et n'est liée qu'au nombre de cellules dans chaque dimension de l'espace de quantification. Cependant, son amélioration en termes d'efficacité est faible. au détriment du regroupement des résultats, au détriment de la précision. Étant donné que l'algorithme de regroupement de grille pose le problème de l'échelle de quantification, nous commençons généralement par rechercher des clusters à partir de petites unités, puis augmentons progressivement la taille des unités et répétons ce processus jusqu'à ce que des clusters satisfaisants soient trouvés.

(2) Méthode de clustering basée sur un modèle
Les méthodes basées sur un modèle supposent un modèle pour chaque cluster et trouvent le meilleur ajustement des données au modèle donné. Les méthodes basées sur des modèles tentent d'optimiser l'adaptabilité entre des données données et certains modèles de données en établissant des fonctions de densité qui reflètent la distribution spatiale des échantillons pour localiser les grappes.

(3) Méthode de clustering basée sur un ensemble flou
Dans la pratique, il n'existe pas de valeur d'attribution stricte à laquelle appartiennent la plupart des objets. Il existe une valeur intermédiaire ou une incertitude dans leur valeur et leur forme d'attribution, ce qui convient à un partitionnement doux. Parce que l'analyse de clustering floue a l'avantage de décrire l'interdépendance de l'attribution des échantillons et peut refléter objectivement le monde réel, elle est devenue l'un des points chauds de la recherche actuelle sur l'analyse de cluster.
L'algorithme de clustering flou est une méthode d'apprentissage non supervisée basée sur la théorie mathématique floue et une méthode de clustering incertaine. Une fois que le clustering flou a été proposé, il a reçu une grande attention de la part de la communauté universitaire. Le clustering flou est une grande « famille » de clustering, et la recherche sur le clustering flou est également très active.

(4) Méthode de clustering basée sur un ensemble approximatif
Le clustering approximatif est une méthode de clustering incertaine basée sur la théorie des ensembles approximatifs. Du point de vue du couplage entre les ensembles approximatifs et les algorithmes de clustering, les méthodes de clustering approximatif peuvent être divisées en deux catégories : le clustering approximatif à couplage fort et le clustering approximatif à couplage faible.
Bien entendu, les nouvelles orientations de recherche en matière d'analyse de cluster sont bien plus que celles-ci. Par exemple, les algorithmes d'exploration de flux de données et de clustering, les données incertaines et leurs algorithmes de clustering, l'informatique quantique et les algorithmes de clustering génétique quantique sont tous des technologies de clustering qui ont émergé ces dernières années. . des sujets de recherche de pointe.

3. Autres méthodes d'extraction aberrantes

Les méthodes d'extraction aberrantes présentées précédemment ne sont que deux représentants de l'exploitation minière aberrante. Il existe de nombreuses méthodes d'extraction aberrantes plus matures dans les applications pratiques. Elles peuvent être déterminées à partir du type de technologie utilisée dans la méthode d'extraction ou de l'utilisation de connaissances antérieures. angles : degrés.

(1) Type de technologie utilisée
Il existe principalement des méthodes statistiques, des méthodes basées sur la distance, des méthodes basées sur la densité, des méthodes basées sur le regroupement, des méthodes basées sur l'écart, des méthodes basées sur la profondeur, des méthodes basées sur la transformation en ondelettes, des méthodes basées sur des graphiques, des méthodes basées sur des modèles et des réseaux neuronaux. méthodes, etc

(2) Utilisation des connaissances antérieures
En fonction de la disponibilité des informations sur les classes normales ou aberrantes, il existe trois approches courantes :
① Méthode de détection des valeurs aberrantes non supervisée, c'est-à-dire qu'il n'y a aucune connaissance préalable telle que les étiquettes de catégorie dans l'ensemble de données ;
② Méthode de détection des valeurs aberrantes supervisée, c'est-à-dire extraire les caractéristiques des valeurs aberrantes grâce à l'existence d'un ensemble de formation contenant des valeurs aberrantes et des points normaux ;
③ Méthode de détection des valeurs aberrantes semi-supervisée, les données d'entraînement contiennent des données normales étiquetées, mais il n'y a aucune information sur les objets de données aberrantes.