Technology Sharing

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

---

V. Quality Evaluation of Clustering

Cluster analysis is to decompose a data set into several subsets, each subset is called a cluster, and the set formed by all subsets is called a cluster of the object set. A good clustering algorithm should produce high-quality clusters and high-quality clusters, that is, the overall similarity within the cluster is the highest, and the overall similarity between clusters is the lowest. Given that many clustering algorithms, including $k$-Average algorithm, DBSCAN algorithm, etc. require the user to specify the number of clusters in the clustering in advance$k$, therefore, we first discuss a simple estimation method for k.

1. Estimation of the number of clusters

Many clustering algorithms, such as $k$-Average algorithm, even DIANA algorithm, etc., require the number of clusters to be specified in advance$k$,and$k$The value of will greatly affect the quality of clustering, but the number of clusters is determined in advance.$k$This is not an easy task. We can first consider two extreme cases.
(1) Take the entire data set$S$As a cluster, $k=1$, which seems simple and convenient, but the cluster analysis results are of no value.
(2) Dataset$S$Each object of is considered as a cluster, that is, $k=|S|=n$, which produces the most fine-grained clustering. Therefore, there is no intra-cluster difference in each cluster, and the intra-cluster similarity reaches the highest. However, this clustering cannot be used for$S$Provide any information about$S$A general description of .
It can be seen that the number of clusters$k$At least it should satisfy $2\le k\le n-1$, but the number of clusters$k$It is still unclear what value is most appropriate.
Generally considered,$k$The value of can be estimated by the shape and scale of the data set distribution and the clustering resolution required by the user, and scholars have proposed many different estimation methods, such as the elbow method, cross-validation method, and information theory-based methods.
A simple and commonly used$k$The empirical estimation method of the value believes that for$n$The number of clusters in a dataset of objects$k$Pick $\begin{array}{r}\sqrt{\frac{n}{2}}\end{array}$ In this case, under the average expectation, each cluster has approximately$\sqrt{2n}$ On this basis, some people have proposed further additional restrictions, namely the number of clusters$k<\sqrt{n}$。
For example, suppose$n=8$, then the number of clusters $k=2$ is appropriate, and on average each cluster has 4 points, and according to the additional empirical formula$k<2.83$Using these two cluster numbers$k$The empirical formula seems to also illustrate from one side that in Example 10-5 $k=2$ is the most appropriate number of clusters.

2. External quality evaluation

If we have estimated the number of clusters well,$k$, one or more clustering methods can be used, for example,$k$-average algorithm, agglomerative hierarchical algorithm or DBSCAN algorithm etc. perform cluster analysis on known data sets and obtain a variety of different clustering results. The question now is which method has better clustering results, or how to compare the clustering results generated by different methods, which is the quality evaluation of clustering.
Currently, there are many methods available for clustering quality evaluation, but they can generally be divided into two categories, namely extrinsic quality evaluation and intrinsic quality evaluation.
External quality evaluation assumes that an ideal clustering already exists for the data set (usually constructed by experts), and uses it as a common benchmark method to compare with the clustering results of a certain algorithm. Its comparative evaluation mainly includes two common methods: clustering entropy and clustering accuracy.

1. Clustering entropy method

Assume data set S = { X 1 , X 2 , … , X n } S={X_1,X_2,…,X_n} S={X1​,X2​,…,Xn​},and T = { T 1 , T 2 , … , T m } T={T_1,T_2,…,T_m} T={T1​,T2​,…,Tm​} is the ideal standard clustering given by experts, and C = { C 1 , C 2 , … , C k } C={C_1,C_2,…,C_k} C={C1​,C2​,…,Ck​} is determined by an algorithm$S$A cluster of, then for cluster$C_i$Relative to the benchmark clustering$T$The clustering entropy is defined as
$$E(C_i|T)=-\sum _{j=1}^m\frac{|C_i\cap T_j|}{|C_i|}{\log }_2\frac{|C_i\cap T_j|}{|C_i|}\text{\hspace{1em}(10-20)}$$ and$C$About Benchmarks$T$The overall clustering entropy of is defined as$C_i$About Benchmarks$T$The weighted average of the clustering entropy is
$$E(C)=\frac{1}{\sum _{i=1}^k|C_i|}\sum _{i=1}^k|C_i|\times E(C_i|T)\text{\hspace{1em}(10-21)}$$ The clustering entropy method believes that$E(C)$ The smaller the value, the$C$Relative to the benchmark$T$The higher the clustering quality.
It is worth noting that the denominator of the first term on the right side of formula (10-21)$\begin{array}{r}\sum _{i=1}^k|C_i|\end{array}$ is the sum of the number of elements in each cluster and cannot be used$n$To replace. Because, only when$C$is a partition cluster, the denominator is$n$, while the denominator of general clustering methods, such as DBSCAN clustering, may be smaller than$n$。

2. Clustering accuracy

The basic idea of ​​clustering accuracy evaluation is to use the category with the largest number in the cluster as the category label of the cluster, that is,$C_i$,if it exists$T_j$make ∣ 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|} ∣Ci​∩Tj​∣=max{∣Ci​∩T1​∣,∣Ci​∩T2​∣,⋯,∣Ci​∩Tm​∣}, then it is believed that$C_i$The category is$T_j$Therefore, the cluster$C_i$About Benchmarks$T$The accuracy is defined as
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(Ci​∣T)=∣Ci​∣max{∣Ci​∩T1​∣,∣Ci​∩T2​∣,⋯,∣Ci​∩Tm​∣}​(10-22) and$C$About Benchmarks$T$The overall accuracy is defined as the total accuracy of all clusters$C_i$About Benchmarks$T$The weighted average of the clustering accuracy is
$$J(C)=\frac{1}{\sum _{i=1}^k|C_i|}\sum _{i=1}^k|C_i|\times J(C_i|T)\text{\hspace{1em}(10-23)}$$ The clustering accuracy method believes that$J(C)$ The larger the value, the more clustered$C$Relative to the benchmark$T$The higher the clustering quality.
In addition, generally$1-J(C)$ called$C$About Benchmarks$T$Therefore, the clustering accuracy $J(C)$ Large or overall error rate$1-J(C)$ Small, which means that the clustering algorithm can better cluster objects of different categories into different clusters, that is, the clustering accuracy is high.

(III) Internal quality evaluation

Internal quality assessment has no known external benchmark and only uses datasets$S$and clustering$C$The inherent characteristics and values ​​of a cluster$C$That is, the clustering effect is generally evaluated by calculating the average similarity within the cluster, the average similarity between clusters, or the overall similarity.
Internal quality evaluation is related to clustering algorithms. Clustering effectiveness indicators are mainly used to evaluate the quality of clustering effects or determine the optimal number of clusters. The ideal clustering effect is to have the smallest intra-cluster distance and the largest inter-cluster distance. Therefore, clustering effectiveness is generally measured by a certain ratio of intra-cluster distance to inter-cluster distance. Common indicators of this type include CH indicator, Dunn indicator, I indicator, Xie-eni indicator, etc.

1. CH index

The CH index is the abbreviation of the Calinski-Harabasz index. It first calculates the sum of the squares of the distances between each point in each cluster and its cluster center to measure the compactness within the class; then it calculates the sum of the squares of the distances between each cluster center and the center of the data set to measure the separation of the data set. The ratio of separation to compactness is the CH index.
set up${\overline{X}}_i$Representation Cluster$C$The center point (mean),$\overline{X}$Representation dataset$S$The center point of$d({\overline{X}}_i,\overline{X})$ for${\overline{X}}_i$arrive$\overline{X}$If a distance function of$C$The compactness of the cluster is defined as
$$\text{Trace}(A)=\sum _{i=1}^k\sum _{X_j\in C_i}d(X_j,{\overline{X}}_i{)}^2\text{\hspace{1em}(10-24)}$$ Therefore, Trace(A) is a cluster$C$The sum of the squares of the center distances within the cluster.$C$The separation is defined as
$$\text{Trace}(B)=\sum _{i=1}^k|C_i|d({\overline{X}}_i,\overline{X}{)}^2\text{\hspace{1em}(10-25)}$$ That is, Trace(B) is a cluster$C$Each cluster center point to$S$The weighted sum of the squared distances to the center points of .
Therefore, if$\begin{array}{r}N=\sum _{i=1}^k|C_i|\end{array}$ Then the CH index can be defined as
$$V_{\text{CH}}(k)=\frac{\text{Trace}(B)/(k-1)}{\text{Trace}(A)/(N-k)}\text{\hspace{1em}(10-26)}$$ Formula (10-26) is generally used in the following two situations:
(1) Evaluate which of the two algorithms produces a better clustering.
Suppose two algorithms are used to analyze the data set$S$Perform cluster analysis and obtain two different clusters (both containing$k$clusters), the clustering corresponding to the larger CH value is better, because the larger the CH value means that each cluster in the cluster is more compact and the clusters are more dispersed.
(2) Evaluate which of the two clusterings with different numbers of clusters obtained by the same algorithm is better.
Suppose an algorithm has a dataset$S$Cluster analysis was performed and the number of clusters was obtained as$k_1$and$b_2$If there are two clusters, the cluster with a larger CH value has a better result, which also indicates that the number of clusters corresponding to this cluster is more appropriate. Therefore, by repeatedly applying formula (10-26), we can also obtain a data set:$S$The optimal number of clusters for clustering.

2. Dunn indicator

Dunn indicator using clusters$C_i$With cluster$C_j$Minimum distance between $d_s(C_i,C_j)$ To calculate the separation between clusters, use the largest cluster diameter among all clusters max ⁡ { Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } max{varPhi(C_1), varPhi(C_2),...,varPhi(C_k)} max{Φ(C1​),Φ(C2​),...,Φ(Ck​)} To characterize the compactness within the cluster, the Dunn index is the minimum value of the ratio of the former to the latter, that is,
V D ( k ) = min ⁡ i ≠ j d s ( 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)}}tag{10-27} VD​(k)=i=jmin​max{Φ(C1​),Φ(C2​),...,Φ(Ck​)}ds​(Ci​,Cj​)​(10-27) The larger the Dunn value, the farther the distance between clusters, and the better the corresponding clustering. Similar to the CH evaluation index, the Dunn index can be used to evaluate the pros and cons of clustering obtained by different algorithms, and can also be used to evaluate which clustering with different numbers of clusters obtained by the same algorithm is better, that is, it can be used to find$S$The optimal number of clusters.

6. Outlier Mining

Outliers are special data that deviate significantly from the majority of data in a data set. The data mining algorithms introduced above, such as classification and clustering, focus on discovering common patterns that apply to most data. Therefore, many data mining algorithms attempt to reduce or eliminate the impact of outliers and remove or ignore outliers as noise when implementing mining. However, in many practical applications, people suspect that the deviation of outliers is not caused by random factors, but may be caused by other completely different mechanisms, and they need to be mined for special analysis and utilization. For example, in application fields such as safety management and risk control, the pattern of identifying outliers is more valuable than the pattern of normal data.

1. Overview of related issues

The word Outlier is usually translated as outlier or abnormal. But it has many aliases in different applications, such as isolated point, abnormal point, novel point, deviation point, exceptional point, noise, abnormal data, etc. In Chinese literature, outlier mining has similar terms such as abnormal data mining, abnormal data detection, outlier data mining, exceptional data mining and rare event mining.

1. Generation of outliers

(1) Data comes from anomalies caused by fraud, intrusion, disease outbreaks, unusual experimental results, etc. For example, someone's average phone bill is about 200 yuan, but it suddenly increases to thousands of yuan in a certain month; someone's credit card usually spends about 5,000 yuan per month, but in a certain month the spending exceeds 30,000 yuan, etc. This type of outlier is usually relatively interesting in data mining and is one of the key points of application.
(2) Caused by inherent changes in data variables, reflecting the natural characteristics of data distribution, such as climate change, new customer purchasing patterns, gene mutations, etc. This is also one of the interesting focus areas.
(3) Data measurement and collection errors are mainly due to human error, measurement equipment failure or noise. For example, a student's grade of -100 in a course may be caused by the default value of the program setting; the salary of a company's senior management is significantly higher than that of ordinary employees, which may seem like an outlier, but it is reasonable data.

2. Outlier mining problem

Generally, the outlier mining problem can be decomposed into three sub-problems.
(1) Defining outliers
Since outliers are closely related to practical problems, clearly defining what kind of data is an outlier or abnormal data is the premise and primary task of outlier mining. Generally, it is necessary to combine the experience and knowledge of domain experts to give an appropriate description or definition of outliers.
(2) Mining outliers
After the outliers are clearly defined, the key task of outlier mining is to use an algorithm to effectively identify or mine the defined outliers. Outlier mining algorithms usually provide users with suspicious outlier data from the perspective of the laws that the data can reflect in order to attract the user's attention.
(3) Understanding outliers
The goal of outlier mining is to reasonably explain, understand and guide practical applications of mining results. Since the mechanism of outlier generation is uncertain, whether the "outliers" detected by the outlier mining algorithm actually correspond to actual abnormal behaviors cannot be explained and explained by the outlier mining algorithm, but can only be understood and explained by industry or field experts.

3. Relativity of outliers

Outliers are special data in a data set that are obviously different from most of the data, but "obvious" and "most of the data" are relative, that is, outliers are different, but they are relative. Therefore, several issues need to be considered when defining and mining outliers.
(1) Global or local outliers
A data object may be an outlier relative to its local neighbors, but not relative to the entire data set. For example, a student with a height of 1.9 meters is an outlier in the first class of the mathematics major in our school, but not among the people of the whole country, including professional players such as Yao Ming.
(2) Number of outliers
Although the number of outliers is unknown, the number of normal points should far exceed the number of outliers, that is, the proportion of outliers in a large data set should be low. It is generally believed that the number of outliers should be less than 5% or even less than 1%.
(3) Outlier factor of a point
You cannot use "yes" or "no" to report whether an object is an outlier. Instead, the degree of deviation of the object, that is, the outlier factor (Outlier Factor) or the outlier score (Outlier Score), should be used to characterize the degree to which a data deviates from the group. Then, objects with outlier factors higher than a certain threshold are filtered out and provided to decision makers or domain experts for understanding and explanation, and applied in actual work.

2. Distance-based methods

1. Basic concepts

Definition 10-11 There is a positive integer$k$, object$X$of $k$-The nearest neighbor distance is a positive integer that satisfies the following conditions $d_k(X)$：
(1) Except$X$In addition, at least$k$Objects$Y$satisfy $d(X,Y)\le d_k(X)$。
(2) Except$X$In addition, at most $k-1$ Objects$Y$satisfy $d(X,Y)<d_k(X)$。
in$d(X,Y)$ Is an object$X$and$Y$Some distance function between .

of an object $k$-The larger the distance of the nearest neighbor, the more likely it is to be far away from most data objects, so the object can be$X$of $k$-Nearest neighbor distance $d_k(X)$ as its outlier factor.

Definition 10-12 make D ( X , k ) = { Y ∣ d ( X , Y ) ≤ d k ( X ) ∧ Y ≠ X } D(X,k)={Y|d(X,Y)≤d_k(X)wedge Y≠X} D(X,k)={Y∣d(X,Y)≤dk​(X)∧Y=X}, then it is called $D(X,k)$ yes$X$of $k$-Nearest neighbor (Domain).

From definitions 10-12, we can see that$D(X,k)$ So$X$Center, distance$X$Does not exceed $d_k(X)$ Object$Y$It is worth noting that$X$It does not belong to $k$-Nearest neighbor, i.e. $X\notin D(X,k)$.In particular,$X$of $k$-Nearest Neighbor $D(X,k)$ The number of objects contained may far exceed$k$,Right now $|D(X,k)|\ge k$。

Definitions 10-13 There is a positive integer$k$, object$X$of $k$-The nearest neighbor outlier factor is defined as
$${\text{OF}}_1(X,k)=\frac{\sum _{Y\in D(X,k)}d(X,Y)}{|D(X,k)|}\text{\hspace{1em}(10-28)}$$

2. Algorithm Description

For a given data set and the number of nearest neighbor distances$k$, we can use the above formula to calculate the$k$-Nearest neighbor outlier factor, and sort them from large to small and output them. Among them, several objects with larger outlier factors are most likely to be outliers. Generally, decision makers or industry experts need to analyze and judge which of them are really outliers.

Algorithm 10-8 Distance-based outlier detection algorithm
Input: Dataset$S$, the number of nearest neighbor distances$k$
Output: A table of suspected outliers and their corresponding outlier factors in descending order
（1）REPEAT
(2) Take$S$An unprocessed object in$X$
(3) Determination$X$of$k$-Nearest Neighbor$D(X,k)$
(4) Calculation$X$of$k$-Nearest neighbor outlier factor${\text{OF}}_1(X,k)$
（5）UNTIL $S$Each point has been processed
(6) Yes${\text{OF}}_1(X,k)$Arrange in descending order and output$(X,{\text{OF}}_1(X,k))$

3. Calculation Example

Example 10-12 Suppose there are 11 points in the two-dimensional data set.$S$Given in Table 10-10, let$k=2$, try to calculate the Euclidean distance squared $X_7,X_{10},X_{11}$ The outlier factor to all other points.

untie：In order to intuitively understand the principle of the algorithm,$S$The data objects in are displayed on the plane shown in the following figure (10-27).

The outlier factors of the specified point and other points are calculated below.

(1) Calculation object$X_7$Outlier factor
As can be seen from the figure, the distance$X_7=(6,8)$ The nearest point is$X_{10}=(5,7)$,and $d(X_7,X_{10})=1.41$, the other closest points may be $X_{11}=(5,2)$，$X_9=(3,2)$，$X_8=(2,4)$；
Calculated$d(X_7,X_{11})=6.08$，$d(X_7,X_9)=6.71$，$d(X_7,X_8)=5.66$
because$k=2$,so $d_2(X_7)=5.66$, so according to definition 10-11 we have D ( X 7 , 2 ) = { X 10 , X 8 } D(X_7,2)={X_{10},X_8} D(X7​,2)={X10​,X8​}
According to formula (10-28),$X_7$Outlier factor
$$\begin{array}{rl}{\text{OF}}_1(X_7,2)& =\frac{\sum _{Y\in N(X_7,2)}d(X_7,Y)}{|N(X_7,k)|}=\frac{d(X_7,X_{10})+d(X_7,X_8)}{2}\\ & =\frac{1.41+5.66}{2}=3.54\end{array}$$(2) Calculation object$X_{10}$Outlier factor ${\text{OF}}_1(X_{10},2)=2.83$

(3) Calculation object$X_{11}$Outlier factor ${\text{OF}}_1(X_{11},2)=2.5$

(4) Calculation object$X_5$Outlier factor ${\text{OF}}_1(X_5,2)=1$

Similarly, the outlier factors of the remaining objects can be calculated, see the following table (10-11).

4. Outlier Factor Threshold

according to$k$- According to the nearest neighbor theory, the larger the outlier factor, the more likely it is an outlier. Therefore, a threshold must be specified to distinguish outliers from normal points. The simplest method is to specify the number of outliers, but this method is too simple and sometimes misses some real outliers or attributes too many normal points to possible outliers, making it difficult for domain experts or decision makers to understand and interpret outliers.
(1) The outlier factor segmentation threshold method first arranges the outlier factors in descending order, and then renumbers the data objects in ascending order according to the outlier factors.
(2) Outlier Factor${\text{OF}}_1(X,k)$ As the ordinate, the outlier factor sequence number is the abscissa, that is, (sequence number,${\text{OF}}_1$Value) are marked on the plane and connected to form a non-increasing broken line. The point where the broken line drops sharply and drops gently is found to correspond to the outlier factor as the threshold. Objects with outlier factors less than or equal to this threshold are normal objects, and the others are possible outliers.

Example 10-13 For the data set in Example 10-12$S$, and their outlier factors are arranged in descending order and summarized in Table 10-11. Try to find the threshold of outliers based on the outlier factor segmentation threshold method.

untie：First, take Table 10-11 (serial number, ${\text{OF}}_1$Values) are used as points on the plane, marked on the plane and connected with broken lines, as shown in Figure 10-28.

Then, we can observe Figure 10-28 and find that the line on the left of the fourth point (4, 1.27) drops very steeply, while the line on the right drops very gently. Therefore, we choose the outlier factor 1.27 as the threshold.$X_7、X_{10}$ and$X_{11}$ The outlier factors of are 3.54, 2.83 and 2.5, which are all greater than 1.27. Therefore, these three points are most likely outliers, and the rest are ordinary points.
Looking at Figure 10-27 again, we can see that$X_7、X_{10}$ and$X_{11}$ Indeed, they are far away from the dense majority of objects on the left, so we treat them as a dataset$S$The outliers are reasonable.

5. Algorithm Evaluation

The biggest advantage of the distance-based outlier detection method is its simple principle and ease of use. Its shortcomings are mainly reflected in the following aspects.
(1) Parameters$k$There is no simple and effective method to determine the selection of$k$There is no unanimously accepted analytical result on the sensitivity level.
(2) The time complexity is$O(|S{|}^2)$, lack of scalability for large-scale data sets.
(3) Due to the use of a global outlier factor threshold, it is difficult to mine outliers in a dataset with regions of different densities.

3. Method based on relative density

The distance method is a global outlier detection method, but it cannot handle data sets with different density areas, that is, it cannot detect outliers in local density areas. In actual applications, data is not always distributed in a single density. When the data set contains multiple density distributions or is a mixture of different density subsets, global outlier detection methods such as distance usually do not work well, because whether an object is an outlier depends not only on the distance between it and the surrounding data, but also on the density conditions in the neighborhood.

1. The concept of relative density

From the perspective of density neighborhood, outliers are objects in low-density areas. Therefore, it is necessary to introduce the concepts of local neighborhood density and relative density of objects.

Definitions 10-14 (1) An object$X$of$k$-Nearest neighbor local density is defined as
$$\text{dsty}(X,k)=\frac{|D(X,k)|}{\sum _{Y\in D(X,k)}d(X,Y)}\text{\hspace{1em}(10-29)}$$ (2) An object$X$of$k$-Nearest neighbor local relative density (relative density)
$$\text{rdsty}(X,k)=\frac{\sum _{Y\in D(X,k)}\text{dsty}(X,k)/|D(X,k)|}{\text{dsty}(X,k)}\text{\hspace{1em}(10-30)}$$ in$D(X,k)$ It's the object$X$of$k$- nearest neighbor (given in Definitions 10-12),$|D(X,k)|$ is the number of objects in the collection.

2. Algorithm Description

by $\text{rdsty}(X,k)$ As an outlier${\text{OF}}_2(X,k)$, which is calculated in two steps
(1) According to the number of neighbors$k$, calculate each object$X$of$k$-Nearest neighbor local density $\text{dsty}(X,k)$
(2) Calculation$X$The average density of neighbors and$k$-Nearest neighbor local relative density $\text{rdsty}(X,k)$
A data set consists of multiple natural clusters. The relative density of objects close to the core point in the cluster is close to 1, while the relative density of objects at the edge of the cluster or outside the cluster is relatively large. Therefore, the larger the relative density value, the more likely it is an outlier.

Algorithm 10-9 Outlier Detection Algorithm Based on Relative Density
Input: Dataset$S$, the number of nearest neighbors$k$
Output: A table of suspected outliers and their corresponding outlier factors in descending order
（1）REPEAT
(2) Take$S$An unprocessed object in$X$
(3) Determination$X$of$k$-Nearest Neighbor$D(X,k)$
(4) Utilization$D(X,k)$calculate$X$Density$\text{dsty}(X,k)$
（5）UNTIL $S$Each point has been processed
（6）REPEAT
(7) Take$S$The first object in$X$
(8) Determine$X$Relative density$\text{rdsty}(X,k)$, and assign it to${\text{OF}}_2(X,k)$
（9）UNTIL $S$All objects in have been processed
(10) Yes${\text{OF}}_2(X,k)$Arrange in descending order and output$(X,{\text{OF}}_2(X,k))$

Example 10-14 For the two-dimensional data set given in Example 10-12$S$ (See Table 10-10 for details),$k=2$, try Euclidean distance calculation $X_7,X_{10},X_{11}$ The outlier factor of objects such as is based on the relative density.

untie:because$k=2$, so we need the 2-nearest neighbor local density of all objects.

(1) Find the 2-nearest neighbors of each data object in Table 10-11 $D(X_i,2)$。
According to the same calculation method as in Example 10-12, we can get
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 } $$begin{aligned} &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} end{aligned}$$ ​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) Calculate the local density of each data object $\text{dsty}(X_i,2)$：

① Calculation$X_1$Density
because 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​}, so it is calculated that $d(X_1,X_2)=1$，$d(X_1,X_3)=1$，$d(X_1,X_5)=1$；
According to formula (10-29), we get:
$$\begin{array}{rl}\text{dsty}(X_1,2)& =\frac{|D(X_1,2)|}{\sum _{Y\in N(X_1,2)}d(X_1,Y)}\\ & =\frac{|N(X_1,2)|}{d(X_1,X_2)+d(X_1,X_3)+d(X_1,X_5)}\\ & =\frac{3}{1+1+1}=1\end{array}$$

② Calculation$X_2$Density
because D ( X 2 , 2 ) = { X 1 , X 6 } D(X_2,2)={X_1,X_6} D(X2​,2)={X1​,X6​}, so the calculated $d(X_2,X_1)=1$，$d(X_2,X_6)=1$；
According to formula (10-29), we get:
$$\begin{array}{rl}\text{dsty}(X_2,2)& =\frac{|D(X_2,2)|}{\sum _{Y\in N(X_2,2)}d(X_2,Y)}=\frac{2}{1+1}=1\end{array}$$

The local density of other data objects can be calculated similarly, see Table 10-12 below.

(3) Calculate each object$X_i$Relative density $\text{rdsty}(X_i,2)$, and use it as an outlier factor ${\text{OF}}_2$。
① Calculation$X_1$Relative density
Using the density value of each object in Table 10-12, according to the relative density formula (10-30), we have:
$$\begin{array}{rl}\text{rdsty}(X_1,2)& =\frac{\sum _{Y\in N(X_1,2)}\text{dsty}(Y,2)/|N(X_1,2)|}{\text{dsty}(X_1,2)}\\ & =\frac{(1+1+1)/3}{1}=1={\text{OF}}_2(X_1,2)\end{array}$$

② Similar calculations can be obtained $X_2、X_3、\dots 、X_{11}$ The relative density value.
for example$X_5$Relative density:
$$\begin{array}{rl}\text{rdsty}(X_5,2)& =\frac{\sum _{Y\in N(X_5,2)}\text{dsty}(Y,2)/|N(X_5,2)|}{\text{dsty}(X_5,2)}\\ & =\frac{(1+1+1+0.79)/4}{1}=0.95={\text{OF}}_2(X_5,2)\end{array}$$ The results are summarized in Tables 10-13 below.

Example 10-15 Given the data set shown in Table 10-14, please use the Euclidean distance$k=2,3,5$, calculate each point$k$- nearest neighbor local density,$k$-Nearest neighbor local relative density (outlier factor${\text{OF}}_2$) and based on$k$-Outlier factor of the nearest neighbor distance${\text{OF}}_1$。

untie：（1）For ease of understanding,$S$The relative positions of the points are marked on the two-dimensional plane (Figure 10-30).

(2) Use the distance-based and relative density-based algorithms 10-8 and 10-9 respectively. Calculate the$k$-Nearest neighbor local density$\text{dsty}$、$k$-Nearest neighbor local relative density (outlier factor${\text{OF}}_2$) and based on$k$-Outlier factor of the nearest neighbor distance${\text{OF}}_1$, and the results are summarized in Tables 10-15.

(3) Simple analysis
① As can be seen from Figure 10-30,$X_{15}$and$X_{16}$yes$S$There are two obvious outliers in the figure, and the distance-based and relative density-based methods can mine them well.
② From this example, we can see that the two algorithms$k$Not as sensitive as expected, maybe it's an outlier$X_{15}$and$X_{16}$Because it is clearly separated from other objects.
③ From Table 10-15, we can see that regardless of$k$Take 2, 3 or 5,$X_1$The area $\text{dsty}$ The values ​​are significantly lower than$X_7$The area $\text{dsty}$ This is consistent with the regional density shown in Figure 10-30. However, the relative density values ​​of the two regions${\text{OF}}_2$ There is almost no noticeable difference. This is determined by the nature of relative density, that is, for uniformly distributed data points, the relative density of the core points is 1, regardless of the distance between the points.

7. Other Clustering Methods

1. Improved clustering algorithm

  （1）$k$-Module ($k$-modes) algorithm is for$k$-The average algorithm is only suitable for numerical attributes and is proposed to achieve fast clustering of discrete data.$k$The -modulo algorithm uses a simple 0-1 matching method to calculate the distance between two attribute values ​​under the same discrete attribute, which weakens the difference between the ordinal attribute values. That is, it cannot fully reflect the true distance between two attribute values ​​under the same ordinal attribute, and there is still room for improvement and perfection.
  （2）$k$-prototype ($k$-Prototype) algorithm combines$k$-Averaging algorithm and$k$The advantage of the -modular algorithm is that it can cluster data sets with both discrete and numerical attributes (called mixed attributes).$k$-Modular arithmetic calculation object$X$and$Y$the distance between $d_1(X,Y)$, for numerical attributes,$k$-Methods in the average algorithm calculate the distance between objects $d_2(X,Y)$, and finally use the weighted method, that is $\alpha d_1(X,Y)+(1-\alpha )d_2(X,Y)$ As a data set object$X$and$Y$the distance between $d(X,Y)$,in $\alpha \in [0,1]$ is the weight coefficient, which is usually taken as$\alpha =0.5$。
(3) The BIRCH algorithm (Balanced Iterative Reducing and Clustering Using Hierarchies) is a comprehensive hierarchical clustering method. It uses clustering features (CF) and clustering feature trees (CF Tree, similar to B-tree) to summarize and describe clusters.$C_i$,in ${\text{CF}}_i=(ni,{\text{LS}}_i,{\text{SS}}_i)$ is a triple,$n_i$is the number of objects in the cluster,${\text{LS}}_i$yes$n_i$The linear sum of the object components,${\text{SS}}_i$yes$n_i$The sum of the squares of the components of the objects.
(4) CURE (Clustering Using Representatives) algorithm is a$k$-Another improvement of the average algorithm. Many clustering algorithms are only good at clustering spherical clusters, while some clustering algorithms are more sensitive to isolated points. In order to solve the above two problems, the CURE algorithm changes$k$-Average algorithm uses cluster centers and$k$-The center point algorithm uses a single specific object to represent a cluster in the traditional method. Instead, it selects multiple representative objects in the cluster to represent a cluster, so that it can adapt to the clustering of non-spherical clusters and reduce the impact of noise on clustering.
(5) ROCK (RObust Clustering using linK) algorithm is a clustering algorithm proposed for binary or categorical attribute data sets.
(6) OPTICS (Ordering Points To Identify the Clustering Structure) algorithm is used to reduce the density of the DBSCAN algorithm.$(\epsilon ,\text{MinPts})$ It is proposed to test the sensitivity of the parameters. It does not produce the resulting clusters explicitly, but generates an augmented cluster ranking for cluster analysis (for example, a coordinate graph with reachable distance as the vertical axis and the output order of the sample points as the horizontal axis). This ranking represents the density-based clustering structure of each sample point. We can get the clustering structure based on any density parameter from this ranking.$(\epsilon ,\text{MinPts})$ Clustering results of the DBSCAN algorithm.

2. Other new clustering methods

Use some new theories or techniques to design new clustering methods.

(1) Grid-based clustering method
The grid-based method quantizes the object space into a finite number of cells to form a grid structure, and the position information of the segmentation points in each dimension is stored in an array. The segmentation line runs through the entire space, and all clustering operations are performed on this grid structure (i.e., quantized space). The main advantage of this method is that it has a fast processing speed, which is independent of the number of data objects and only related to the number of cells in each dimension in the quantized space. However, its efficiency improvement comes at the cost of reducing the accuracy of the clustering results. Since the grid clustering algorithm has the problem of quantization scale, it is usually started from small cells to find clusters, and then the volume of the cells is gradually increased, and this process is repeated until a satisfactory cluster is found.

(2) Model-based clustering method
Model-based methods assume a model for each cluster and find the best fit of the data to the given model. Model-based methods locate clusters by establishing a density function that reflects the spatial distribution of samples, attempting to optimize the adaptability between given data and certain data models.

(3) Clustering method based on fuzzy sets
In practice, most objects do not have a strict belonging value to which cluster, and their belonging values ​​and forms are intermediate or uncertain, which is suitable for soft segmentation. Fuzzy cluster analysis has the advantage of describing the intermediate nature of sample belonging and can objectively reflect the real world, becoming one of the hot spots in cluster analysis research today.
The fuzzy clustering algorithm is an unsupervised learning method based on fuzzy mathematics theory and an uncertain clustering method. Once fuzzy clustering was proposed, it received great attention from the academic community. Fuzzy clustering is a large clustering "family" and research on fuzzy clustering is also very active.

(4) Clustering method based on rough sets
Rough clustering is an uncertain clustering method based on rough set theory. From the coupling of rough sets and clustering algorithms, rough clustering methods can be divided into two categories: strong coupling rough clustering and weak coupling rough clustering.
Of course, there are far more new research directions in cluster analysis than these. For example, data stream mining and clustering algorithms, uncertain data and their clustering algorithms, quantum computing and quantum genetic clustering algorithms, etc., are all cutting-edge topics in clustering research that have emerged in recent years.

3. Other outlier mining methods

The outlier mining methods introduced above are only two representatives of outlier mining. There are many more mature outlier mining methods in practical applications. They can be classified from two perspectives: the type of technology used by the mining method or the degree of utilization of prior knowledge.

(1) Type of technology used
The main ones include statistics-based methods, distance-based methods, density-based methods, clustering-based methods, deviation-based methods, depth-based methods, wavelet transform-based methods, graph-based methods, pattern-based methods, neural network-based methods, etc.

(2) Utilization of prior knowledge
There are three common approaches, depending on the degree of information available about the normal or outlier classes:
① Unsupervised outlier detection method, that is, there is no prior knowledge such as category labels in the data set;
② Supervised outlier detection method, that is, extracting the features of outliers from the training set containing outliers and normal points;
③ Semi-supervised outlier detection method, the training data contains labeled normal data, but no information about outlier data objects.