# An Improved Semisupervised Outlier Detection Algorithm Based on Adaptive Feature Weighted Clustering

Authors: Tingquan Deng; Jinhong Yang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

There exist already various approaches to outlier detection, in which semisupervised methods achieve encouraging superiority due to the introduction of prior knowledge. In this paper, an adaptive feature weighted clustering-based semisupervised outlier detection strategy is proposed. This method maximizes the membership degree of a labeled normal object to the cluster it belongs to and minimizes the membership degrees of a labeled outlier to all clusters. In consideration of distinct significance of features or components in a dataset in determining an object being an inlier or outlier, each feature is adaptively assigned different weights according to the deviation degrees between this feature of all objects and that of a certain cluster prototype. A series of experiments on a synthetic dataset and several real-world datasets are implemented to verify the effectiveness and efficiency of the proposal.


---

## Body

## 1. Introduction

Outlier detection is an important topic in data mining community, which aims at finding patterns that occur infrequently as opposed to other data mining techniques [1]. An outlier is an observation that deviates significantly from, or inconsistent with the main body of a dataset, as if it was generated by a different mechanism [2]. The importance of outlier detection is in the view of the fact that outliers can provide raw patterns and valuable knowledge about a dataset. Current application areas of outlier detection include crime detection, credit card fraud detection, network intrusion detection, medical diagnosis, faulty detection in critical safety systems, or detecting abnormal regions in image processing [3–9].Recently the studies on outlier detection are very active and many approaches have been proposed. In general, existing work on outlier detection can be broadly classified into three modes depending on whether label information is available or can be used to build outlier detection models: unsupervised, supervised, and semisupervised methods.Supervised outlier detection concerns the situation where the training dataset contains prior information about the class of each instance that is normal or abnormal. One-class support vector machine (OCSVM) [10] or support vector data description (SVDD) [11, 12], which considers the case that training data are all normal instances, conducts a hypersphere around the normal data and utilizes the constructed hypersphere to detect an unknown sample as an inlier or outlier. The supervised outlier detection problem is a difficult case in many real-world applications, since the acquisition of label information of the whole training dataset is often expensive, time consuming, and subjective.Unsupervised outlier detection, without prior information about the class distribution, is generally classified into distribution-based [3], distance-based [13, 14], density-based [15, 16], and clustering-based [17–20] approaches. Distribution-based approach assumes that all data points are generated by a certain statistical model, while outliers do not obey the model. However, the assumption of an underlying distribution of data points is not always available in many real-life applications. Distance-based approach was firstly investigated by Knox and Ng [14]. An object o in a dataset X is an outlier if at least p% of objects in X are further than the distance D from o. The global parameters p and D are not suitable when the local information of the dataset varies greatly. Representatives of this type of approaches include K-nearest neighbor (KNN) algorithm [13] and its variants [21, 22]. Density-based approach was originally proposed by Breunig et al. [15]. A local outlier factor (LOF) is assigned to each data point based on their local neighborhood density. Then a data point with a high LOF value is determined as an outlier. However, this method is very sensitive to the choice of neighborhood parameter.Clustering-based approaches [17–20] partition the dataset into several clusters depending on similarity of objects and detect outliers by examining the relationship between objects and clusters. In general, clusters containing significantly less data points than other clusters or being remote from other clusters are considered as outliers. The cluster structure of data can facilitate the task of outlier detection and a small amount of related literatures has been proposed. A classical clustering method is used to find anomaly in the intrusion detection domain [18]. In the work of [19], the clustering techniques iteratively detect outliers for multidimensional data analysis in subspace. Zhao et al. [20] propose an adaptive fuzzy c-means (AFCM) algorithm by introducing sample weight coefficients to the objective function and apply it to anomaly data detection in energy system of steel industry. Since clustering-based approaches are unsupervised without requiring any labeled training data, their performance in outlier detection is limited. In addition, most of the existing clustering-based methods only involve the optimal clustering but do not incorporate optimal outlier detection into clustering process.In many real-world applications, one may encounter cases where a small set of objects are labeled as outliers or belonging to a certain class, but most of the data are unlabeled. Studies indicate that the introduction of a small amount of prior knowledge can significantly improve the effectiveness of outlier detection [23–25]. Therefore, semisupervised approaches to outlier detection have been developed to tackle such scenarios and have been thought of a popular direction of outlier detection recently. In order to take advantage of the label information of a target dataset, entropy-based outlier detection based on semisupervised learning from few positive examples (EODSP) is proposed in [23]. That method extracts reliable normal instances from unlabeled objects and regards them as labeled normal samples. Entropy-based outlier detection method is used to detect top M outliers. However, when a dataset initially provides labeled normal and abnormal samples, the algorithm in [23] cannot make full use of the given label information. Literature [24] develops a semisupervised outlier detection method based on the assessment of deviation from known labeled objects by punishing poor clustering results and restricting the number of outliers. Xue et al. [25] present a semisupervised outlier detection proposal based on fuzzy rough c-means clustering, which detects outliers by minimizing the sum of squared errors of clustering results and the deviation from known labeled examples as well as the number of outliers. Unfortunately, some labeled normal objects are finally misidentified as outliers due to improper parameter selection in [24, 25].Most of the previous research equally treats different features of objects in outlier detecting process, which does not conform to the intrinsic characteristic of a dataset. Actually, it is more reasonable that different features have different importance in each cluster, especially for high-dimension sparse datasets where the structure of each cluster is often limited to a subset of features rather than the entire feature set. Some works concerning feature weighted clustering have been studied. Huang et al. [26] propose a W-c-means type clustering algorithm that can automatically calculate feature weights. W-c-means adds a new step into the basic c-means algorithm to update the variable weights based on the current partition of data. Literature [27] develops an approach called simultaneous clustering and attribute discrimination (SCAD). SCAD learns the feature relevance representation of each cluster independently in an unsupervised manner. Zhou et al. [28] publish a maximum-entropy-regularized weighted fuzzy c-means (EWFCM) clustering algorithm for “nonspherical” shaped data. A new objective function is developed in the EWFCM algorithm to achieve the optimal clustering result by minimizing the dispersion within clusters and maximizing the entropy of attribute weights simultaneously. These existing methods about feature weighted clustering encourage scholars to study outlier detection based on feature weighted clustering.To make full use of prior knowledge to facilitate clustering-based outlier detection, we develop a semisupervised outlier detection algorithm based on adaptive feature weighted clustering (SSOD-AFW) in this paper, in which the feature weights are iteratively obtained. The proposed algorithm emphasizes the diversity of different features in each cluster and assigns lower weights to irrelevant features to reduce their negative influence on outlier decision. Furthermore, based on the convention that outliers usually have a lower membership to every cluster, we relax the constraint of fuzzy c-means (FCM) clustering where the membership degrees of a sample to all clusters must sum up to one and propose an adaptive feature weighted semisupervised possibilistic clustering-based outlier detection algorithm. The interaction problem between optimal clustering and outlier detection is addressed in the proposed method. The label information is introduced into the possibilistic clustering method according to the following principles: (1) maximizing the membership degree of a labeled normal object to the cluster it belongs to; (2) minimizing the membership degrees of a labeled normal object to the clusters it does not belong to; and (3) minimizing the membership degrees of a labeled outlier to all clusters. In addition to the above principles, we simultaneously minimize the dispersion within clusters in the new objective function of clustering to achieve a proper cluster structure. Finally the yielded optimal membership degrees are used to indicate the outlying degree of each sample in the dataset. The proposed algorithm is found promising in improving the performance of outlier detection in comparison with typical outlier detection methods in accuracy, running time as well as other evaluation metrics.The remainder of this paper is organized as follows. Section2 gives a short review on possibilistic clustering algorithms. Section 3 presents the detailed description of feature weighted semisupervised clustering-based outlier detection algorithm. In Section 4, the experimental results of the proposed method against typical outlier detection algorithms are discussed on synthetic and real-world datasets. Finally, Section 5 follows our conclusions.


## 2. Possibilistic Clustering Algorithms

LetX=x1,x2,…,xn be a given dataset of n objects, where xi=xi1,xi2,…,xiN∈RN is the ith object characterized by N features. Suppose that the dataset is divided into c clusters and ok denotes the kth cluster prototype.FCM is a well-known clustering algorithm [29], whose objective function is(1)JFCM=∑i=1n∑k=1cuikmxi-ok2,(2)s.t.∑k=1cuik=1,uik∈0,1,where uik is the membership degree of the ith (1≤i≤n) object to the kth (1≤k≤c) cluster. · represents the l2-norm of a vector and m>0 is the fuzzification coefficient. Note that the constraint condition in (2) indicates that the membership sum of each object to all clusters equals one. Therefore, FCM is sensitive to outliers due to the intuition that outliers or noises commonly locate far away from all cluster prototypes. For this reason, Krishnapuram and Keller [30] proposed a possibilistic c-means (PCM) clustering algorithm, which relaxes the constraint on the sum of memberships and minimizes the following objective function:(3)JPCM=∑i=1n∑k=1cuikmxi-ok2+∑k=1cηk∑i=1n1-uikm,(4)s.t.uik∈0,1,where ηk is a suitable positive number. In PCM, the constraint (4) allows an outlier holding a low membership to all clusters, so an outlier has a low impact on the objective function (3). The membership information of each sample can be naturally used to interpret the outlying characteristic of a sample. For a certain sample, if it has a low membership to all clusters, it is likely to be an outlier.Afterward, another unsupervised possibilistic clustering algorithm (PCA) is proposed by Yang and Wu [31] and the objective function of PCA is described as(5)JPCA=∑i=1n∑k=1cuikmxi-ok2+βm2c∑i=1n∑k=1cuikmlog⁡uikm-uikm,s.t.uik∈0,1,where the parameter β can be calculated by the sample covariance:(6)β=∑i=1n∑j=1Nxij-∑l=1nxlj/n2n.


## 3. Semisupervised Outlier Detection Framework Based on Feature Weighted Clustering

### 3.1. Model Formulation

In this section, we introduce prior knowledge into possibilistic c-means clustering method to improve the performance of outlier detection. First, a small subset of samples in a given datasetX=x1,x2,…,xn is labeled as normal or outlier objects. Each labeled normal object carries the label of class it belongs to. A semisupervised indicator matrix A=aikn×c is constructed to describe the semisupervised information and its entries are defined by the following:(i)
If an objectxi is labeled as a normal point and it belongs to the kth cluster, then aik=-1, and for all s=1,2,…,c,s≠k, we let ais=1.(ii)
Ifxi is labeled as an outlier, then for all s=1,2,…,c, we set ais=1.(iii)
Ifxi is unlabeled, then for all s=1,2,…,c, it has ais=0.Usually data often contain a number of redundant features. The cluster structure in a given dataset is often confined to a subset of features rather than the entire feature set. Irrelevant features can only obscure the discovery of the cluster structure by a clustering algorithm. An intrinsic outlier is easy to be neglected due to the vagueness of cluster structure. Figure1 presents an example of a three-dimensional dataset. The dataset has two clusters (c1 and c2) and 3 features (f1, f2, and f3). In the feature space (f1, f2, f3), neither of the clusters is discovered (see Figure 1(a)). In the subspace (f1, f2), cluster c1 can be found, but c2 cannot (see Figure 1(b)). Nevertheless, only cluster c2 can be clearly shown in (f2, f3) (see Figure 1(c)). Therefore, if we assign weights 0.47, 0.45, and 0.08 to features f1, f2, and f3, respectively, cluster c1 will be recovered by a clustering algorithm. If the weights of features f1, f2, and f3 are assigned as 0.13, 0.46, and 0.41, respectively, cluster c2 will be recovered. In this consideration, each cluster is relevant to different subsets of features, and the same feature may have different importance in different clusters.Figure 1
Three-dimensional synthetic example.
(a)
Plot of the space (f1, f2, f3) (b)
Plot of the subspace (f1, f2) (c)
Plot of the subspace (f2, f3)In our research, letvjk be the weight of the jth (1≤j≤N) dimensional feature with respect to the kth (1≤k≤c) cluster, which satisfies ∑j=1Nvjk=1; then the feature weighted distance dik between the ith object and the kth cluster prototype is defined as(7)dik=∑j=1Nvjkqxij-okj2,where the parameter q>1 is the feature weight index.The points within clusters usually behave strongly correlated, while weak correlation is shown between outliers. That is, normal points belong to one of thec clusters and outliers do not belong to any cluster. Therefore, a normal point should have a high membership to the cluster it belongs to, and an outlier has a low membership to all clusters. Based on this idea, we define a new objective function and minimize it as follows:(8)JSSOD-AFWU,O,V=∑i=1n∑k=1cuikmdik2+βm2c∑i=1n∑k=1cuikmlog⁡uikm-uikm+∑i=1n∑k=1cαikaikuikm,(9)s.t.∑j=1Nvjk=1,uik∈0,1,vjk∈0,1,where n, N, and c are the number of objects, features, and clusters, respectively. U=(uik)n×c, uik is the membership degree of the ith object belonging to the kth cluster. V=(vjk)N×c, vjk denotes the feature weight of the jth dimensional feature with respect to the kth cluster. O=(okj)c×N, okj indicates the jth dimensional feature value of the kth cluster prototype. dik denotes the feature weighted distance between object xi and the kth cluster prototype. aik∈{1,-1,0} is the element in semisupervised indicator matrix A. m>0 is the fuzzification coefficient and the parameter β can be fixed as the sample covariance according to (6). The positive coefficient αik adjusts the significance of the label information of the ith object with respect to the kth cluster in objective function (8). The larger αik is, the larger the influence of label knowledge is.The first term in (8) is equivalent to the FCM objective function which requires the distances of objects from the cluster prototypes to be as small as possible. The second term is constructed to force uik to be as large as possible. The third term αikaikuikm focuses on minimizing the membership degrees of a labeled outlier to all the clusters and maximizing the membership degree of a labeled normal object to the cluster it belongs to. With a proper choice of αik, we can balance the label information weight of every object and achieve the optimal fuzzy partition.The virtue of semisupervised indicator matrixA in objective function (8) can be elaborated as follows. Recalling the construction of semisupervised indicator matrix A and objective function (8), note that if we know that xi belongs to the kth cluster, then aik=-1 and all the other entries in the ith row equal 1. Thus, minimizing αikaikuikm in (8) means maximizing the membership of xi to the kth cluster and simultaneously minimizing the memberships of xi to the other clusters. If xi is labeled as an outlier, namely, where all the elements in the ith row of A equal 1, then minimizing αikaikuikm in (8) means minimizing the memberships of xi to all clusters, for an outlier does not belong to any cluster. If xi is unlabeled, namely, where aik=0 for all k=1,2,…,c, then the term αikaikuikm has no impact on objective function (8).


### 3.2. Solutions to the Objective Function

In this subsection, an iterative algorithm for minimizingJSSOD-AFW with respect to uik, vjk, and okj is derived similar to classical FCM.First, in order to minimizeJSSOD-AFW with respect to V, U and O are fixed and the parameters αik (i=1,2,…,n; k=1,2,…,c) are constants. The Lagrange function is constructed as follows:(10)L1=∑i=1n∑k=1cuikmdik2+βm2c∑i=1n∑k=1cuikmlog⁡uikm-uikm+∑i=1n∑k=1cαikaikuikm-∑k=1cγk∑j=1Nvjk-1,where γk (k=1,2,…,c) are the Lagrange multipliers.By taking the gradient ofL1 with respect to vjk and setting it to zero, we obtain(11)∂L1∂vjk=qvjkq-1∑i=1nuikmxij-okj2-γk=0.Then(12)vjk=γkq∑i=1nuikmxij-okj21/q-1.Substituting (12) into (9), we have(13)∑j=1Nvjk=γkq1/q-1∑j=1N1∑i=1nuikmxij-okj21/q-1=1.It follows that(14)γkq1/q-1=1∑j=1N1/∑i=1nuikmxij-okj21/q-1.The updating criteria of feature weightvjk (1≤j≤N, 1≤k≤c) are obtained:(15)vjk=1/∑i=1nuikmxij-okj21/q-1∑l=1N1/∑i=1nuikmxil-okl21/q-1.The updating way ofvjk implies that the larger the deviation degrees from all samples to the kth cluster prototype regarding the jth feature are, the smaller the weight of the jth feature is. That is, if the distribution of all data is compact around the kth cluster prototype in the jth feature space, the jth feature plays a significant role in formulating the kth cluster. Meanwhile, irrelevant features thus are assigned a smaller weight to reduce the negative impact of them on the clustering process.To find the optimal cluster prototypeO, we assume U and V are fixed and the parameters αik (i=1,2,…,n; k=1,2,…,c) are also constants. We take the gradient of JSSOD-AFW with respect to okj and set it to zero: (16)∂JSSOD-AFW∂okj=∑i=1n-2uikmvjkxij-okj=0.The updating formula of cluster prototypeokj is obtained as follows:(17)okj=∑i=1nuikmxij∑i=1nuikm.To solve the optimal fuzzy partition matrixU, we assume O and V are fixed and the parameters αik (i=1,2,…,n; k=1,2,…,c) are also constants. We set the gradient of JSSOD-AFW with respect to uik to zero:(18)∂JSSOD-AFW∂uik=muikm-1dik2+βmcuikm-1log⁡uikm+αikaikmuikm-1=0.The updating formula ofuik is derived as follows:(19)uik=exp⁡-mcβdik2+αikaik.Formula (19) indicates that a large value of weighted distance dik leads to a smaller value of uik, for all 1≤i≤n, 1≤k≤c. It should be noted that the membership degree uik is also dependent on the coefficient αik. The choice of αik is important to the performance of the SSOD-AFW algorithm because it serves in distinguishing the importance of the third term relative to the other terms in objective function (8). If αik is too small, the third term will be neglected and the labels of objects will not work to promote the cluster structure. If αik is too large, the other terms will be neglected, and the negative influence of possible mislabels of objects will be enlarged. The value of αik should be chosen such that it has the same order of magnitude with the first term in (8). To determine the parameter αik in an adaptive way, in all experiments described in this paper, we choose αik proportional to dik2 as follows:(20)αik=Kdik2,where K∈(0,1) is a constant. Since the weighted distance dik is dynamically updated, the value of parameter αik is adaptively updated in each iteration.


### 3.3. Criteria for Outlier Identification

Based on the above analysis, outliers should hold low membership degrees to all clusters. Therefore, the sum of memberships of an object to all clusters can be used to evaluate its outlying degree. For a certain objectxi, its outlying degree is defined as(21)ODxi=∑k=1cuik.Thus, a small value ofOD(xi) indicates a high outlying possibility of object xi. The outlying degree of each sample in a dataset is calculated, respectively, and sorted incrementally. The suspicious outliers can be found just by extracting the top M objects in the sorted outlying degree sequence, where M is a given number of outliers contained in the dataset or a given number of outliers one needs.In summary, the description of the SSOD-AFW algorithm is shown in Algorithm1.Algorithm 1 (semisupervised outlier detection based on adaptive feature weighted clustering (SSOD-AFW)).
Input. Dataset X, the label information of some objects, the number of clusters c, parameters m>1, K∈(0,1), q>1, ε>0, and the number of outliers M.
Output. M suspicious outliers.(1)
Calculate the parameterβ according to (6), randomly initialize matrix U(0)=(uik(0))n×c, and initialize all elements in V(0)=(vjk(0))N×c as 1/N. Set iteration counter t=0.(2)
Compute the matrix of cluster prototypeO(t+1)=(okj(t+1))c×N according to (17).(3)
Update the feature weight matrixV(t+1)=(vjk(t+1))N×c by (15).(4)
Update the feature weighted distanceD(t+1)=(dik(t+1))n×c by (7).(5)
Update parameterαik(t+1) by (20).(6)
Update the membership degree matrixU(t+1)=(uik(t+1))n×c according to (19).(7)
IfU(t+1)-U(t)<ε, go to step (8); else, t=t+1, repeat step (2) to step (7).(8)
The outlying degree of each object is computed, and the OD values are sorted in an ascending manner. Finally output topM outliers with the smallest outlying degrees.Computational complexity analysis: Step (2) needsO(cNn) operations to compute c cluster prototype. The computational complexity of computing the weights of N features is O(cNn) in Step (3). Step (4) requires O(cNn) to compute the weighted distances of n objects to c cluster prototypes. Step (5) needs O(cn) to compute parameter αik of n objects with respect to c cluster prototypes. Moreover, Step (6) needs O(cn) operations to calculate the memberships of n objects to c clusters. Therefore, the whole computational complexity is O(cNn), the same as that of the classical FCM algorithm.


### 3.4. Proof of Convergence

In this section, we discuss the convergence of the proposed SSOD-AFW algorithm. To prove the convergence of objective functionJSSOD-AFW in (8) by iterating V, O, and U with formulas (15), (17), and (19), it only needs to prove that JSSOD-AFW is monotonically decreasing and bounded after a finite number of iterations. Next Lemmas 2, 3, and 4 verify the monotonically decreasing property of JSSOD-AFW with respect to V, O, and U, respectively. Lemma 5 presents the boundedness of JSSOD-AFW.Lemma 2.
Objective functionJSSOD-AFW in (8) is nonincreasing by updating U=(uik)n×c with formula (19).Proof.
Due to the fact thatV and O are fixed when updating U by (19), here the objective function JSSOD-AFW can be regarded as a function only associated with U, denoted as JSSOD-AFW(U). According to Lagrangian multiplier technique, U∗ computed via (19) is a stagnation point of JSSOD-AFW(U). On the other hand, if Hessian matrix ∇2JSSOD-AFW(U) is proved to be positive definite at U∗, it can be proved that JSSOD-AFW(U) attains its local minimum at U∗. The Hessian matrix ∇2JSSOD-AFW(U∗) is expressed as(22)∇2JSSOD-AFWU∗=∂2JSSOD-AFWU∗∂u11∂u11⋯∂2JSSOD-AFWU∗∂u11∂unc⋮⋱⋮∂2JSSOD-AFWU∗∂unc∂u11⋯∂2JSSOD-AFWU∗∂unc∂unc.∇2JSSOD-AFW(U∗) is a diagonal matrix and its diagonal element is(23)∂2JSSOD-AFWU∗∂uik∂uik=βcuikm-2.
Sinceuik>0, Hessian matrix ∇2JSSOD-AFW(U∗) is positive definite. Having proved that U∗ is a stagnation point of JSSOD-AFW(U) and ∇2JSSOD-AFW(U∗) is positive definite, we conclude U∗ is the local minimum of JSSOD-AFW(U). Then we have JSSOD-AFW(U(t))≥JSSOD-AFW(U∗)=JSSOD-AFW(U(t+1)), where U(t) is the membership matrix after the tth iteration in (19) and U∗=U(t+1) is the one after the (t+1)th iteration. Therefore, objective function JSSOD-AFW in (8) is nonincreasing by updating U=(uik)n×c using formula (19).Lemma 3.
Objective functionJSSOD-AFW in (8) is nonincreasing by updating V=(vjk)N×c using (15).Proof.
Similar to Lemma2, when U and O are fixed, we just need to prove that the Hessian matrix of Lagrangian of JSSOD-AFW(V) at V∗ is positive definite, where V∗ is computed by (15). The Hessian matrix is denoted as H(V)=(hjk,lm(V)), whose element is expressed as follows:(24)hjk,lmV=∂2L1V∂vjk∂vlm=qq-1vjkq-2∑i=1nuikmxij-okj2,ifj=l,k=m,0,otherwise.
Sinceq>1 and vjk>0, the diagonal entries of the diagonal matrix are apparently positive. Therefore, Hessian matrix H(V) is positive definite. JSSOD-AFW(V) attains its local minimum at V∗ computed by (15). This completes the proof.Lemma 4.
Objective functionJSSOD-AFW in (8) is nonincreasing when O=(okj)c×N is updated using (17).The proof of Lemma4 is similar to Lemma 2.Lemma 5.
Objective functionJSSOD-AFW in (8) is bounded, there exists a constant B, and it satisfies JSSOD-AFW<B.Proof.
∀ i ∈ { 1 , … , n } and ∀k∈{1,…,c}, we have 0<uik≤1. Thus, uikmlog⁡uikm-uikm is monotonically decreasing with respect to uik and hence -1≤uikmlog⁡uikm-uikm<0. Apparently, the first term and the second term of the objective function JSSOD-AFW are also bounded. In consequence, objective function JSSOD-AFW in (8) is bounded.Theorem 6.
The objective functionJSSOD-AFW converges to a local minimum by updating V, O, and U using formulas (15), (17), and (19), which subjects to the constraints in (9).Proof.
Lemmas2, 3, and 4 verify that objective function in (8) is nonincreasing under iterations according to (15), (17), and (19). Lemma 5 shows that JSSOD-AFW has a finite bound. Though the parameter αik needs to be updated in the iteration process, it is a constant in the problem solving using Lagrangian multiplier technique. So αik does not affect the convergence of the SSOD-AFW algorithm. Combining the above conclusions, JSSOD-AFW is sure to converge to a local minimum through iterations of V, O, and U by (15), (17), and (19).


## 3.1. Model Formulation

In this section, we introduce prior knowledge into possibilistic c-means clustering method to improve the performance of outlier detection. First, a small subset of samples in a given datasetX=x1,x2,…,xn is labeled as normal or outlier objects. Each labeled normal object carries the label of class it belongs to. A semisupervised indicator matrix A=aikn×c is constructed to describe the semisupervised information and its entries are defined by the following:(i)
If an objectxi is labeled as a normal point and it belongs to the kth cluster, then aik=-1, and for all s=1,2,…,c,s≠k, we let ais=1.(ii)
Ifxi is labeled as an outlier, then for all s=1,2,…,c, we set ais=1.(iii)
Ifxi is unlabeled, then for all s=1,2,…,c, it has ais=0.Usually data often contain a number of redundant features. The cluster structure in a given dataset is often confined to a subset of features rather than the entire feature set. Irrelevant features can only obscure the discovery of the cluster structure by a clustering algorithm. An intrinsic outlier is easy to be neglected due to the vagueness of cluster structure. Figure1 presents an example of a three-dimensional dataset. The dataset has two clusters (c1 and c2) and 3 features (f1, f2, and f3). In the feature space (f1, f2, f3), neither of the clusters is discovered (see Figure 1(a)). In the subspace (f1, f2), cluster c1 can be found, but c2 cannot (see Figure 1(b)). Nevertheless, only cluster c2 can be clearly shown in (f2, f3) (see Figure 1(c)). Therefore, if we assign weights 0.47, 0.45, and 0.08 to features f1, f2, and f3, respectively, cluster c1 will be recovered by a clustering algorithm. If the weights of features f1, f2, and f3 are assigned as 0.13, 0.46, and 0.41, respectively, cluster c2 will be recovered. In this consideration, each cluster is relevant to different subsets of features, and the same feature may have different importance in different clusters.Figure 1
Three-dimensional synthetic example.
(a)
Plot of the space (f1, f2, f3) (b)
Plot of the subspace (f1, f2) (c)
Plot of the subspace (f2, f3)In our research, letvjk be the weight of the jth (1≤j≤N) dimensional feature with respect to the kth (1≤k≤c) cluster, which satisfies ∑j=1Nvjk=1; then the feature weighted distance dik between the ith object and the kth cluster prototype is defined as(7)dik=∑j=1Nvjkqxij-okj2,where the parameter q>1 is the feature weight index.The points within clusters usually behave strongly correlated, while weak correlation is shown between outliers. That is, normal points belong to one of thec clusters and outliers do not belong to any cluster. Therefore, a normal point should have a high membership to the cluster it belongs to, and an outlier has a low membership to all clusters. Based on this idea, we define a new objective function and minimize it as follows:(8)JSSOD-AFWU,O,V=∑i=1n∑k=1cuikmdik2+βm2c∑i=1n∑k=1cuikmlog⁡uikm-uikm+∑i=1n∑k=1cαikaikuikm,(9)s.t.∑j=1Nvjk=1,uik∈0,1,vjk∈0,1,where n, N, and c are the number of objects, features, and clusters, respectively. U=(uik)n×c, uik is the membership degree of the ith object belonging to the kth cluster. V=(vjk)N×c, vjk denotes the feature weight of the jth dimensional feature with respect to the kth cluster. O=(okj)c×N, okj indicates the jth dimensional feature value of the kth cluster prototype. dik denotes the feature weighted distance between object xi and the kth cluster prototype. aik∈{1,-1,0} is the element in semisupervised indicator matrix A. m>0 is the fuzzification coefficient and the parameter β can be fixed as the sample covariance according to (6). The positive coefficient αik adjusts the significance of the label information of the ith object with respect to the kth cluster in objective function (8). The larger αik is, the larger the influence of label knowledge is.The first term in (8) is equivalent to the FCM objective function which requires the distances of objects from the cluster prototypes to be as small as possible. The second term is constructed to force uik to be as large as possible. The third term αikaikuikm focuses on minimizing the membership degrees of a labeled outlier to all the clusters and maximizing the membership degree of a labeled normal object to the cluster it belongs to. With a proper choice of αik, we can balance the label information weight of every object and achieve the optimal fuzzy partition.The virtue of semisupervised indicator matrixA in objective function (8) can be elaborated as follows. Recalling the construction of semisupervised indicator matrix A and objective function (8), note that if we know that xi belongs to the kth cluster, then aik=-1 and all the other entries in the ith row equal 1. Thus, minimizing αikaikuikm in (8) means maximizing the membership of xi to the kth cluster and simultaneously minimizing the memberships of xi to the other clusters. If xi is labeled as an outlier, namely, where all the elements in the ith row of A equal 1, then minimizing αikaikuikm in (8) means minimizing the memberships of xi to all clusters, for an outlier does not belong to any cluster. If xi is unlabeled, namely, where aik=0 for all k=1,2,…,c, then the term αikaikuikm has no impact on objective function (8).


## 3.2. Solutions to the Objective Function

In this subsection, an iterative algorithm for minimizingJSSOD-AFW with respect to uik, vjk, and okj is derived similar to classical FCM.First, in order to minimizeJSSOD-AFW with respect to V, U and O are fixed and the parameters αik (i=1,2,…,n; k=1,2,…,c) are constants. The Lagrange function is constructed as follows:(10)L1=∑i=1n∑k=1cuikmdik2+βm2c∑i=1n∑k=1cuikmlog⁡uikm-uikm+∑i=1n∑k=1cαikaikuikm-∑k=1cγk∑j=1Nvjk-1,where γk (k=1,2,…,c) are the Lagrange multipliers.By taking the gradient ofL1 with respect to vjk and setting it to zero, we obtain(11)∂L1∂vjk=qvjkq-1∑i=1nuikmxij-okj2-γk=0.Then(12)vjk=γkq∑i=1nuikmxij-okj21/q-1.Substituting (12) into (9), we have(13)∑j=1Nvjk=γkq1/q-1∑j=1N1∑i=1nuikmxij-okj21/q-1=1.It follows that(14)γkq1/q-1=1∑j=1N1/∑i=1nuikmxij-okj21/q-1.The updating criteria of feature weightvjk (1≤j≤N, 1≤k≤c) are obtained:(15)vjk=1/∑i=1nuikmxij-okj21/q-1∑l=1N1/∑i=1nuikmxil-okl21/q-1.The updating way ofvjk implies that the larger the deviation degrees from all samples to the kth cluster prototype regarding the jth feature are, the smaller the weight of the jth feature is. That is, if the distribution of all data is compact around the kth cluster prototype in the jth feature space, the jth feature plays a significant role in formulating the kth cluster. Meanwhile, irrelevant features thus are assigned a smaller weight to reduce the negative impact of them on the clustering process.To find the optimal cluster prototypeO, we assume U and V are fixed and the parameters αik (i=1,2,…,n; k=1,2,…,c) are also constants. We take the gradient of JSSOD-AFW with respect to okj and set it to zero: (16)∂JSSOD-AFW∂okj=∑i=1n-2uikmvjkxij-okj=0.The updating formula of cluster prototypeokj is obtained as follows:(17)okj=∑i=1nuikmxij∑i=1nuikm.To solve the optimal fuzzy partition matrixU, we assume O and V are fixed and the parameters αik (i=1,2,…,n; k=1,2,…,c) are also constants. We set the gradient of JSSOD-AFW with respect to uik to zero:(18)∂JSSOD-AFW∂uik=muikm-1dik2+βmcuikm-1log⁡uikm+αikaikmuikm-1=0.The updating formula ofuik is derived as follows:(19)uik=exp⁡-mcβdik2+αikaik.Formula (19) indicates that a large value of weighted distance dik leads to a smaller value of uik, for all 1≤i≤n, 1≤k≤c. It should be noted that the membership degree uik is also dependent on the coefficient αik. The choice of αik is important to the performance of the SSOD-AFW algorithm because it serves in distinguishing the importance of the third term relative to the other terms in objective function (8). If αik is too small, the third term will be neglected and the labels of objects will not work to promote the cluster structure. If αik is too large, the other terms will be neglected, and the negative influence of possible mislabels of objects will be enlarged. The value of αik should be chosen such that it has the same order of magnitude with the first term in (8). To determine the parameter αik in an adaptive way, in all experiments described in this paper, we choose αik proportional to dik2 as follows:(20)αik=Kdik2,where K∈(0,1) is a constant. Since the weighted distance dik is dynamically updated, the value of parameter αik is adaptively updated in each iteration.


## 3.3. Criteria for Outlier Identification

Based on the above analysis, outliers should hold low membership degrees to all clusters. Therefore, the sum of memberships of an object to all clusters can be used to evaluate its outlying degree. For a certain objectxi, its outlying degree is defined as(21)ODxi=∑k=1cuik.Thus, a small value ofOD(xi) indicates a high outlying possibility of object xi. The outlying degree of each sample in a dataset is calculated, respectively, and sorted incrementally. The suspicious outliers can be found just by extracting the top M objects in the sorted outlying degree sequence, where M is a given number of outliers contained in the dataset or a given number of outliers one needs.In summary, the description of the SSOD-AFW algorithm is shown in Algorithm1.Algorithm 1 (semisupervised outlier detection based on adaptive feature weighted clustering (SSOD-AFW)).
Input. Dataset X, the label information of some objects, the number of clusters c, parameters m>1, K∈(0,1), q>1, ε>0, and the number of outliers M.
Output. M suspicious outliers.(1)
Calculate the parameterβ according to (6), randomly initialize matrix U(0)=(uik(0))n×c, and initialize all elements in V(0)=(vjk(0))N×c as 1/N. Set iteration counter t=0.(2)
Compute the matrix of cluster prototypeO(t+1)=(okj(t+1))c×N according to (17).(3)
Update the feature weight matrixV(t+1)=(vjk(t+1))N×c by (15).(4)
Update the feature weighted distanceD(t+1)=(dik(t+1))n×c by (7).(5)
Update parameterαik(t+1) by (20).(6)
Update the membership degree matrixU(t+1)=(uik(t+1))n×c according to (19).(7)
IfU(t+1)-U(t)<ε, go to step (8); else, t=t+1, repeat step (2) to step (7).(8)
The outlying degree of each object is computed, and the OD values are sorted in an ascending manner. Finally output topM outliers with the smallest outlying degrees.Computational complexity analysis: Step (2) needsO(cNn) operations to compute c cluster prototype. The computational complexity of computing the weights of N features is O(cNn) in Step (3). Step (4) requires O(cNn) to compute the weighted distances of n objects to c cluster prototypes. Step (5) needs O(cn) to compute parameter αik of n objects with respect to c cluster prototypes. Moreover, Step (6) needs O(cn) operations to calculate the memberships of n objects to c clusters. Therefore, the whole computational complexity is O(cNn), the same as that of the classical FCM algorithm.


## 3.4. Proof of Convergence

In this section, we discuss the convergence of the proposed SSOD-AFW algorithm. To prove the convergence of objective functionJSSOD-AFW in (8) by iterating V, O, and U with formulas (15), (17), and (19), it only needs to prove that JSSOD-AFW is monotonically decreasing and bounded after a finite number of iterations. Next Lemmas 2, 3, and 4 verify the monotonically decreasing property of JSSOD-AFW with respect to V, O, and U, respectively. Lemma 5 presents the boundedness of JSSOD-AFW.Lemma 2.
Objective functionJSSOD-AFW in (8) is nonincreasing by updating U=(uik)n×c with formula (19).Proof.
Due to the fact thatV and O are fixed when updating U by (19), here the objective function JSSOD-AFW can be regarded as a function only associated with U, denoted as JSSOD-AFW(U). According to Lagrangian multiplier technique, U∗ computed via (19) is a stagnation point of JSSOD-AFW(U). On the other hand, if Hessian matrix ∇2JSSOD-AFW(U) is proved to be positive definite at U∗, it can be proved that JSSOD-AFW(U) attains its local minimum at U∗. The Hessian matrix ∇2JSSOD-AFW(U∗) is expressed as(22)∇2JSSOD-AFWU∗=∂2JSSOD-AFWU∗∂u11∂u11⋯∂2JSSOD-AFWU∗∂u11∂unc⋮⋱⋮∂2JSSOD-AFWU∗∂unc∂u11⋯∂2JSSOD-AFWU∗∂unc∂unc.∇2JSSOD-AFW(U∗) is a diagonal matrix and its diagonal element is(23)∂2JSSOD-AFWU∗∂uik∂uik=βcuikm-2.
Sinceuik>0, Hessian matrix ∇2JSSOD-AFW(U∗) is positive definite. Having proved that U∗ is a stagnation point of JSSOD-AFW(U) and ∇2JSSOD-AFW(U∗) is positive definite, we conclude U∗ is the local minimum of JSSOD-AFW(U). Then we have JSSOD-AFW(U(t))≥JSSOD-AFW(U∗)=JSSOD-AFW(U(t+1)), where U(t) is the membership matrix after the tth iteration in (19) and U∗=U(t+1) is the one after the (t+1)th iteration. Therefore, objective function JSSOD-AFW in (8) is nonincreasing by updating U=(uik)n×c using formula (19).Lemma 3.
Objective functionJSSOD-AFW in (8) is nonincreasing by updating V=(vjk)N×c using (15).Proof.
Similar to Lemma2, when U and O are fixed, we just need to prove that the Hessian matrix of Lagrangian of JSSOD-AFW(V) at V∗ is positive definite, where V∗ is computed by (15). The Hessian matrix is denoted as H(V)=(hjk,lm(V)), whose element is expressed as follows:(24)hjk,lmV=∂2L1V∂vjk∂vlm=qq-1vjkq-2∑i=1nuikmxij-okj2,ifj=l,k=m,0,otherwise.
Sinceq>1 and vjk>0, the diagonal entries of the diagonal matrix are apparently positive. Therefore, Hessian matrix H(V) is positive definite. JSSOD-AFW(V) attains its local minimum at V∗ computed by (15). This completes the proof.Lemma 4.
Objective functionJSSOD-AFW in (8) is nonincreasing when O=(okj)c×N is updated using (17).The proof of Lemma4 is similar to Lemma 2.Lemma 5.
Objective functionJSSOD-AFW in (8) is bounded, there exists a constant B, and it satisfies JSSOD-AFW<B.Proof.
∀ i ∈ { 1 , … , n } and ∀k∈{1,…,c}, we have 0<uik≤1. Thus, uikmlog⁡uikm-uikm is monotonically decreasing with respect to uik and hence -1≤uikmlog⁡uikm-uikm<0. Apparently, the first term and the second term of the objective function JSSOD-AFW are also bounded. In consequence, objective function JSSOD-AFW in (8) is bounded.Theorem 6.
The objective functionJSSOD-AFW converges to a local minimum by updating V, O, and U using formulas (15), (17), and (19), which subjects to the constraints in (9).Proof.
Lemmas2, 3, and 4 verify that objective function in (8) is nonincreasing under iterations according to (15), (17), and (19). Lemma 5 shows that JSSOD-AFW has a finite bound. Though the parameter αik needs to be updated in the iteration process, it is a constant in the problem solving using Lagrangian multiplier technique. So αik does not affect the convergence of the SSOD-AFW algorithm. Combining the above conclusions, JSSOD-AFW is sure to converge to a local minimum through iterations of V, O, and U by (15), (17), and (19).


## 4. Experiments and Analysis

Comprehensive experiments and analysis on a synthetic dataset and several real-world datasets are conducted to show the effectiveness and superiority of the proposed SSOD-AFW. We compared the proposed algorithm with two the-state-of-the-art unsupervised outlier algorithms, LOF [15] and KNN [13], one supervised method SVDD [32], and one semisupervised method EODSP [23].


### 4.1. Evaluation Metrics

For numerically performance evaluation of outlier detection algorithms, three metrics, namely, accuracy [7], AUC [33], and rank-power [16], are used in this paper.LetM be the number of true outliers that a dataset X contains and S denotes the number of true outliers detected by an algorithm. In experiments, top M most suspicious instances are detected out. Then the accuracy is given by(25)Accuracy=SM.The receiver operating characteristic (ROC) curve represents the trade-off relationship between the detection rate and the false alarm rate. In general, the area under the ROC curve (AUC) is used to measure the performance of outlier detection method, and the value of AUC for ideal detection performance is close to one.For a given outlier detection algorithm, true outliers occupy top positions with respect to the nonoutliers amongM suspicious instances; then the rank-power (RP) of the algorithm is said to be high. If S is the number of true outliers found within top M instances and Ri denotes the rank of the ith true outlier, then the metric rank-power (RP) is given by(26)RP=SS+12∑i=1SRi.RP reaches the maximum value 1 when allS true outliers are in the top S positions. Larger value of RP implies better performance of an algorithm.


### 4.2. Experiments on Synthetic Dataset

A two-dimensional synthetic dataset with two cluster patterns is generated from Gaussian distribution to intuitively compare the outlier detection results of the proposed method against the other four algorithms mentioned above. The mean vectors of the two clusters areμ1=(7.5,9)T and μ2=(1,3)T, respectively, and the covariance matrixes of them are Σ1=1002 and Σ2=1002. As Figure 2(a) shows, a total of 199 samples are contained in the synthetic dataset, in which there are 183 normal samples (within two clusters) and 16 outliers (cluttered between two clusters). 13 normal objects are labeled and marked as symbol “×” and 5 outliers are labeled and marked with symbol “∗”, while the rest samples are unlabeled marked with “·.” Figures 2(b)–2(f), respectively, illustrate the outlier detection results on the synthetic dataset by using LOF, KNN, SVDD, EODSP, and SSOD-AFW, where the red colored symbols “∘” denote the detected suspicious outliers. Here, the value of parameter k (size of neighborhood) in LOF and KNN is assigned to 3. Gauss kernel function is chosen in SVDD and we set the bandwidth σ=0.3 and the trade-off coefficient C=0.45. Besides, the Euclidean distance threshold T in EODSP is set as 0.1 and the percentage of negative set is set to l=10%. The parameter settings of the proposed algorithm are m=2.3, K=0.85, and q=2.23. In addition to SVDD, the top 16 objects with the highest outlying scores are considered as the results in the other four algorithms.Figure 2
Outlier detection results of different algorithms on the two-dimensional synthetic dataset.
(a)
Original synthetic dataset (b)
LOF (c)
KNN (d)
SVDD (e)
EODSP (f)
SSOD-AFWIn Figure2, it is noticeable that the unsupervised methods LOF and KNN as well as the supervised SVDD fail to completely detect all of the 5 labeled outliers. Nevertheless, some normal points in clusters are badly misjudged as outliers. In contrast, the semisupervised EODSP algorithm and the proposed SSOD-AFW algorithm successfully detect all of the 5 labeled outliers. However, EODSP does not completely detect all the unlabeled true outliers, and several true normal samples are improperly identified as outliers. It is concluded from Figure 2 that the proposed algorithm finds all the true outliers in the synthetic dataset and excludes the normal samples, while the other methods do not.Figure3 numerically presents the performance evaluation of outlier detection using LOF, KNN, SVDD, EODSP, and SSOD-AFW for the synthetic dataset. From Figure 3 we see that the values of accuracy, AUC, and RP of the proposed algorithm all reach 1, outperforming the other methods.Figure 3
Performance comparison of different algorithms on the synthetic dataset.
(a)
Accuracy (b)
AUC (c)
RPFurthermore, during the experimental process shown in Figure3, the feature weights of the synthetic dataset learned by formula (15) in our method are v11=0.6727, v12=0.5985, v21=0.3273, and v22=0.4015. To strengthen the effectiveness of feature weights in the proposed SSOD-AFW algorithm, a comparative analysis of the weighted and the nonweighted versions is implemented on the synthetic dataset, respectively. Considering the nonweighted scenario of the proposed algorithm, the outlier detection result on the synthetic dataset is presented in Figure 4. As can be observed from Figure 4, the nonweighted SSOD-AFW ends up tagging 15 true outlying and 1 normal samples as outliers, with one unlabeled true outlier missed.Figure 4
Outlier detection result of the nonweighted SSOD-AFW on the synthetic dataset.


### 4.3. Experiments on Real-World Datasets

#### 4.3.1. Introduction of Datasets

For further verification of the effectiveness of the proposed algorithm, five real-world datasets from UCI Machine Learning Repository [34] (i.e., Iris, Abalone, Wine, Ecoli, and Breast Cancer Wisconsin (WDBC)) are employed to test the performance of the proposed algorithm against LOF, KNN, SVDD, and EODSP. As mentioned in Aggarwal and Yu [35], one way to test the performance of an outlier detection algorithm is to run it on the dataset and calculate the percentage of points belonging to the rare classes. So a small amount of samples from the same class are randomly selected as outlying objects or as target objects, for the five datasets. For instance, the original Iris dataset incorporates 150 objects with 50 objects in each of three classes. We randomly selected 26 objects from class “Iris-virginica” as target outliers and all objects in the other two classes are considered as normal objects. The other four datasets are similarly preprocessed and more detailed description about the five real-world datasets is given in Table 1.Table 1
Description of real-world datasets.
Dataset Instances Features Outlying classes Outliers (percent) Clusters Prior information Iris 126 4 “Virginica” 26 (20.63%) 2 10 labeled normal samples, 4 labeled outliers Abalone 4177 8 “1”–“4,” “16”–“27,” “29” 335 (8.02%) 11 11 labeled normal samples, 18 labeled outliers Wine 130 13 “3” 11 (8.46%) 2 9 labeled normal samples, 4 labeled outliers Ecoli 336 9 “omL,” “imL,” “imS” 9 (2.68%) 5 11 labeled normal samples, 3 labeled outliers WDBC 387 30 “Malignant” 30 (7.75%) 1 10 labeled normal samples, 8 labeled outliers


#### 4.3.2. Experimental Result Analysis

We compare the outlier detection performance of the proposed algorithm with LOF,KNN, SVDD, and EODSP on real-world datasets. Each method has its own parameters, and the detailed parameter settings of each algorithm are as follows. The parameters of the proposed algorithm are m=2.1, K=0.65, and q=1.53 for all the five datasets. The strategy of parameter selection for SSOD-AFW will be discussed in the later subsection called parameter analysis. For the other algorithms, those parameters are set exactly as mentioned in their references. It is well known that LOF and KNN have high dependency on the neighborhood parameter k. In this paper we set k=5 for datasets Iris and WDBC, k=3 for dataset Abalone, k=10 for dataset Wine, and k=10 for dataset Ecoli. For SVDD method, Gaussian kernel function is employed and the bandwidths σ=0.45 and C=0.5 on all of the five real-world datasets. In EODSP, the Euclidean distance threshold T is set as 0.1 and the percentage of negative set l is set as 30% for Iris and Abalone datasets, and T=0.5,  l=30% for datasets Ecoli, Wine, and WDBC. Since we randomly select outliers from target classes for each dataset, each experiment is repeated 10 times with the same number of different outliers. The average accuracy, AUC, and RP are calculated as the criteria of performance of various detection methods.Figure5 illustrates the outlier detection results of SSOD-AFW algorithm against LOF, KNN, SVDD, and EODSP, respectively, on the five real-world datasets. As can be seen from Figure 5, the proposed algorithm can accurately identify outliers according to the cluster structure of a dataset, with the guidance of the label knowledge. It shows distinct superiority over the other unsupervised (LOF, KNN), semisupervised (EODSP), and supervised (SVDD) methods. In particular, the outlier detection accuracy of SSOD-AFW in Figure 5(a) is significantly higher than the others, especially for datasets Iris and Wine. One can know from Figure 5(b) that the AUC values of our method are always higher than the others for all datasets except for WDBC. In terms of RP, SSOD-AFW performs better than the other four algorithms on datasets Iris and Wine, whereas slightly poorer than SVDD on Abalone, poorer than LOF on Ecoli, and poorer than KNN on WDBC, seen as in Figure 5(c).Figure 5
Performance comparison of various algorithms on the real-world datasets.
(a)
Accuracy (b)
AUC (c)
RPIt is worth mentioning that the experiment of the proposed algorithm on WDBC involves one-class clustering problem. Although one-class clustering task is generally meaningless, one-class clustering-based outlier detection is especially meaningful and feasible in our proposal because our approach does not require that the membership degrees must sum up to 1. This is one of the powerful and important characteristics of the proposed algorithm.


#### 4.3.3. The Influence of the Proportion of Labeled Data on Outlier Detection

In this subsection, we will investigate the influence of the proportion of labeled samples on the accuracies of our methodology. Two typical situations are considered and tested. The first one is that the proportion of labeled outliers increases when the number of labeled normal objects is fixed at a certain constant. The other one is that the percent of labeled normal samples varies while the quantity of labeled outliers is fixed. So two groups of experiments are designed to compare the accuracies of the proposed algorithm against the EODSP, in the situations of different percent of labeled outliers and normal samples, respectively, on the datasets Iris, Abalone, Wine, Ecoli, and WDBC. In the two experiments, the percent of labeled outliers or labeled normal samples ranges from 0% to 40%, respectively, when the number of another kind of labeled objects is fixed. We randomly select a certain number of labeled outliers or normal samples from each dataset, each experiment is repeated 10 times, and the average accuracies of SSOD-AFW and EODSP are computed.Figure6 shows results of the first group of experiments where the percent of labeled outliers varies from 0% to 40%. One can see from Figure 6 that the accuracies of the two semisupervised algorithms are roughly increased with the proportion of labeled outliers becoming larger. This powerfully supports the idea that semisupervised outlier detection algorithms can improve the accuracy of outlier detection by using prior information. Furthermore, the SSOD-AFW achieves a better accuracy than EODSP algorithm for the same proportion of labeled outliers on the five datasets. Especially for Wine, the accuracy of SSOD-AFW is 40% higher than that of EODSP. EODSP addresses the problem of detecting outliers with only few labeled outliers as training data. The labeled normal instances are extracted according to the maximum entropy principle, where the entropy is computed only using the distance between each testing sample and all the labeled outliers. That makes EODSP not flexible as our proposed method due to information deficiencies.Figure 6
Accuracy analysis of algorithms EODSP and SSOD-AFW with different percent of labeled outliers on the real-world datasets.
(a)
Iris (b)
Abalone (c)
Wine (d)
Ecoli (e)
WDBCFigure7 illustrates the accuracy comparison of the proposed algorithm and EODSP, when the proportion of labeled normal samples increases from 0% to 40% and the percent of labeled outliers is fixed. Note that our method obtains a better accuracy than EODSP on all of the five real-world datasets. The accuracy of the proposed algorithm gets larger when the percent of labeled normal samples increases. As mentioned, EODSP emphasizes the semisupervised outlier detection only with few labeled outliers in the initial dataset, but without considering any labeled normal objects. Therefore, the accuracy of EODSP algorithm keeps harper with various proportions of labeled normal objects and always equals the accuracy value of 0% labeled normal samples as well.Figure 7
Accuracy analysis of algorithms EODSP and SSOD-AFW with different percent of labeled normal samples on the real-world datasets.
(a)
Iris (b)
Abalone (c)
Wine (d)
Ecoli (e)
WDBC


#### 4.3.4. Parameter Analysis

The parametersm, K, and q are important in our proposed algorithm, which affect the performance of SSOD-AFW. In this section, the influence of each parameter on outlier detection accuracy is studied.The parameterm is the fuzzification coefficient. Figure 8(a) analyzes the relationship between the outlier detection accuracy of our proposed algorithm and parameter m, with m varying from 1.5 to 5.0. The results imply that the highest accuracy is achieved when m ranges in [2,4]. So it is reasonable that m value in the experiments shown in Figure 5 has been set as 2.1. The parameter K∈(0,1) controls the importance of the label information in the result of outlier detection. Outlier detection accuracies are testified by varying K from 0.1 to 0.9, which are shown in Figure 8(b). The overall tendency is that the accuracies become larger as K increases. The best results of the proposed algorithm occur and keep stable when K≥0.7. Finally, from Figure 8(c), we conclude that the feature weight index q has small influence on the accuracy of SSOD-AFW in the situation that the other parameters maintain the same settings. So the proposed algorithm is not sensitive to the parameter q. In general, the parameter q is suggested to select a constant from (1,4].Figure 8
Outlier detection accuracy of the proposed algorithm under various parameters on the real-world datasets.
(a)
Parameterm (b)
ParameterK (c)
Parameterq


#### 4.3.5. Execution Time Analysis

Figure9 analyzes the average running time of the proposed algorithm against the other algorithms on five real-world datasets. The experimental environment is Windows XP systems, MATLAB 7.1 platform, 3 GHz CPU, 2 GB RAM. Because the volume of Abalone dataset is far greater than the other four datasets, the running times of various datasets are distinctly different. In order to facilitate the display, in Figure 9 the horizontal coordinate axis is translated downward a short distance. The result indicates that the proposed algorithm is more time-saving than the other four typical outlier detection algorithms, except for KNN on dataset Wine. In whole, the execution time of the SSOD-AFW is comparable to that of KNN and less than those of other algorithms on most of the datasets.Figure 9
Execution time comparison of different algorithms on the real-world datasets.


## 4.1. Evaluation Metrics

For numerically performance evaluation of outlier detection algorithms, three metrics, namely, accuracy [7], AUC [33], and rank-power [16], are used in this paper.LetM be the number of true outliers that a dataset X contains and S denotes the number of true outliers detected by an algorithm. In experiments, top M most suspicious instances are detected out. Then the accuracy is given by(25)Accuracy=SM.The receiver operating characteristic (ROC) curve represents the trade-off relationship between the detection rate and the false alarm rate. In general, the area under the ROC curve (AUC) is used to measure the performance of outlier detection method, and the value of AUC for ideal detection performance is close to one.For a given outlier detection algorithm, true outliers occupy top positions with respect to the nonoutliers amongM suspicious instances; then the rank-power (RP) of the algorithm is said to be high. If S is the number of true outliers found within top M instances and Ri denotes the rank of the ith true outlier, then the metric rank-power (RP) is given by(26)RP=SS+12∑i=1SRi.RP reaches the maximum value 1 when allS true outliers are in the top S positions. Larger value of RP implies better performance of an algorithm.


## 4.2. Experiments on Synthetic Dataset

A two-dimensional synthetic dataset with two cluster patterns is generated from Gaussian distribution to intuitively compare the outlier detection results of the proposed method against the other four algorithms mentioned above. The mean vectors of the two clusters areμ1=(7.5,9)T and μ2=(1,3)T, respectively, and the covariance matrixes of them are Σ1=1002 and Σ2=1002. As Figure 2(a) shows, a total of 199 samples are contained in the synthetic dataset, in which there are 183 normal samples (within two clusters) and 16 outliers (cluttered between two clusters). 13 normal objects are labeled and marked as symbol “×” and 5 outliers are labeled and marked with symbol “∗”, while the rest samples are unlabeled marked with “·.” Figures 2(b)–2(f), respectively, illustrate the outlier detection results on the synthetic dataset by using LOF, KNN, SVDD, EODSP, and SSOD-AFW, where the red colored symbols “∘” denote the detected suspicious outliers. Here, the value of parameter k (size of neighborhood) in LOF and KNN is assigned to 3. Gauss kernel function is chosen in SVDD and we set the bandwidth σ=0.3 and the trade-off coefficient C=0.45. Besides, the Euclidean distance threshold T in EODSP is set as 0.1 and the percentage of negative set is set to l=10%. The parameter settings of the proposed algorithm are m=2.3, K=0.85, and q=2.23. In addition to SVDD, the top 16 objects with the highest outlying scores are considered as the results in the other four algorithms.Figure 2
Outlier detection results of different algorithms on the two-dimensional synthetic dataset.
(a)
Original synthetic dataset (b)
LOF (c)
KNN (d)
SVDD (e)
EODSP (f)
SSOD-AFWIn Figure2, it is noticeable that the unsupervised methods LOF and KNN as well as the supervised SVDD fail to completely detect all of the 5 labeled outliers. Nevertheless, some normal points in clusters are badly misjudged as outliers. In contrast, the semisupervised EODSP algorithm and the proposed SSOD-AFW algorithm successfully detect all of the 5 labeled outliers. However, EODSP does not completely detect all the unlabeled true outliers, and several true normal samples are improperly identified as outliers. It is concluded from Figure 2 that the proposed algorithm finds all the true outliers in the synthetic dataset and excludes the normal samples, while the other methods do not.Figure3 numerically presents the performance evaluation of outlier detection using LOF, KNN, SVDD, EODSP, and SSOD-AFW for the synthetic dataset. From Figure 3 we see that the values of accuracy, AUC, and RP of the proposed algorithm all reach 1, outperforming the other methods.Figure 3
Performance comparison of different algorithms on the synthetic dataset.
(a)
Accuracy (b)
AUC (c)
RPFurthermore, during the experimental process shown in Figure3, the feature weights of the synthetic dataset learned by formula (15) in our method are v11=0.6727, v12=0.5985, v21=0.3273, and v22=0.4015. To strengthen the effectiveness of feature weights in the proposed SSOD-AFW algorithm, a comparative analysis of the weighted and the nonweighted versions is implemented on the synthetic dataset, respectively. Considering the nonweighted scenario of the proposed algorithm, the outlier detection result on the synthetic dataset is presented in Figure 4. As can be observed from Figure 4, the nonweighted SSOD-AFW ends up tagging 15 true outlying and 1 normal samples as outliers, with one unlabeled true outlier missed.Figure 4
Outlier detection result of the nonweighted SSOD-AFW on the synthetic dataset.


## 4.3. Experiments on Real-World Datasets

### 4.3.1. Introduction of Datasets

For further verification of the effectiveness of the proposed algorithm, five real-world datasets from UCI Machine Learning Repository [34] (i.e., Iris, Abalone, Wine, Ecoli, and Breast Cancer Wisconsin (WDBC)) are employed to test the performance of the proposed algorithm against LOF, KNN, SVDD, and EODSP. As mentioned in Aggarwal and Yu [35], one way to test the performance of an outlier detection algorithm is to run it on the dataset and calculate the percentage of points belonging to the rare classes. So a small amount of samples from the same class are randomly selected as outlying objects or as target objects, for the five datasets. For instance, the original Iris dataset incorporates 150 objects with 50 objects in each of three classes. We randomly selected 26 objects from class “Iris-virginica” as target outliers and all objects in the other two classes are considered as normal objects. The other four datasets are similarly preprocessed and more detailed description about the five real-world datasets is given in Table 1.Table 1
Description of real-world datasets.
Dataset Instances Features Outlying classes Outliers (percent) Clusters Prior information Iris 126 4 “Virginica” 26 (20.63%) 2 10 labeled normal samples, 4 labeled outliers Abalone 4177 8 “1”–“4,” “16”–“27,” “29” 335 (8.02%) 11 11 labeled normal samples, 18 labeled outliers Wine 130 13 “3” 11 (8.46%) 2 9 labeled normal samples, 4 labeled outliers Ecoli 336 9 “omL,” “imL,” “imS” 9 (2.68%) 5 11 labeled normal samples, 3 labeled outliers WDBC 387 30 “Malignant” 30 (7.75%) 1 10 labeled normal samples, 8 labeled outliers


### 4.3.2. Experimental Result Analysis

We compare the outlier detection performance of the proposed algorithm with LOF,KNN, SVDD, and EODSP on real-world datasets. Each method has its own parameters, and the detailed parameter settings of each algorithm are as follows. The parameters of the proposed algorithm are m=2.1, K=0.65, and q=1.53 for all the five datasets. The strategy of parameter selection for SSOD-AFW will be discussed in the later subsection called parameter analysis. For the other algorithms, those parameters are set exactly as mentioned in their references. It is well known that LOF and KNN have high dependency on the neighborhood parameter k. In this paper we set k=5 for datasets Iris and WDBC, k=3 for dataset Abalone, k=10 for dataset Wine, and k=10 for dataset Ecoli. For SVDD method, Gaussian kernel function is employed and the bandwidths σ=0.45 and C=0.5 on all of the five real-world datasets. In EODSP, the Euclidean distance threshold T is set as 0.1 and the percentage of negative set l is set as 30% for Iris and Abalone datasets, and T=0.5,  l=30% for datasets Ecoli, Wine, and WDBC. Since we randomly select outliers from target classes for each dataset, each experiment is repeated 10 times with the same number of different outliers. The average accuracy, AUC, and RP are calculated as the criteria of performance of various detection methods.Figure5 illustrates the outlier detection results of SSOD-AFW algorithm against LOF, KNN, SVDD, and EODSP, respectively, on the five real-world datasets. As can be seen from Figure 5, the proposed algorithm can accurately identify outliers according to the cluster structure of a dataset, with the guidance of the label knowledge. It shows distinct superiority over the other unsupervised (LOF, KNN), semisupervised (EODSP), and supervised (SVDD) methods. In particular, the outlier detection accuracy of SSOD-AFW in Figure 5(a) is significantly higher than the others, especially for datasets Iris and Wine. One can know from Figure 5(b) that the AUC values of our method are always higher than the others for all datasets except for WDBC. In terms of RP, SSOD-AFW performs better than the other four algorithms on datasets Iris and Wine, whereas slightly poorer than SVDD on Abalone, poorer than LOF on Ecoli, and poorer than KNN on WDBC, seen as in Figure 5(c).Figure 5
Performance comparison of various algorithms on the real-world datasets.
(a)
Accuracy (b)
AUC (c)
RPIt is worth mentioning that the experiment of the proposed algorithm on WDBC involves one-class clustering problem. Although one-class clustering task is generally meaningless, one-class clustering-based outlier detection is especially meaningful and feasible in our proposal because our approach does not require that the membership degrees must sum up to 1. This is one of the powerful and important characteristics of the proposed algorithm.


### 4.3.3. The Influence of the Proportion of Labeled Data on Outlier Detection

In this subsection, we will investigate the influence of the proportion of labeled samples on the accuracies of our methodology. Two typical situations are considered and tested. The first one is that the proportion of labeled outliers increases when the number of labeled normal objects is fixed at a certain constant. The other one is that the percent of labeled normal samples varies while the quantity of labeled outliers is fixed. So two groups of experiments are designed to compare the accuracies of the proposed algorithm against the EODSP, in the situations of different percent of labeled outliers and normal samples, respectively, on the datasets Iris, Abalone, Wine, Ecoli, and WDBC. In the two experiments, the percent of labeled outliers or labeled normal samples ranges from 0% to 40%, respectively, when the number of another kind of labeled objects is fixed. We randomly select a certain number of labeled outliers or normal samples from each dataset, each experiment is repeated 10 times, and the average accuracies of SSOD-AFW and EODSP are computed.Figure6 shows results of the first group of experiments where the percent of labeled outliers varies from 0% to 40%. One can see from Figure 6 that the accuracies of the two semisupervised algorithms are roughly increased with the proportion of labeled outliers becoming larger. This powerfully supports the idea that semisupervised outlier detection algorithms can improve the accuracy of outlier detection by using prior information. Furthermore, the SSOD-AFW achieves a better accuracy than EODSP algorithm for the same proportion of labeled outliers on the five datasets. Especially for Wine, the accuracy of SSOD-AFW is 40% higher than that of EODSP. EODSP addresses the problem of detecting outliers with only few labeled outliers as training data. The labeled normal instances are extracted according to the maximum entropy principle, where the entropy is computed only using the distance between each testing sample and all the labeled outliers. That makes EODSP not flexible as our proposed method due to information deficiencies.Figure 6
Accuracy analysis of algorithms EODSP and SSOD-AFW with different percent of labeled outliers on the real-world datasets.
(a)
Iris (b)
Abalone (c)
Wine (d)
Ecoli (e)
WDBCFigure7 illustrates the accuracy comparison of the proposed algorithm and EODSP, when the proportion of labeled normal samples increases from 0% to 40% and the percent of labeled outliers is fixed. Note that our method obtains a better accuracy than EODSP on all of the five real-world datasets. The accuracy of the proposed algorithm gets larger when the percent of labeled normal samples increases. As mentioned, EODSP emphasizes the semisupervised outlier detection only with few labeled outliers in the initial dataset, but without considering any labeled normal objects. Therefore, the accuracy of EODSP algorithm keeps harper with various proportions of labeled normal objects and always equals the accuracy value of 0% labeled normal samples as well.Figure 7
Accuracy analysis of algorithms EODSP and SSOD-AFW with different percent of labeled normal samples on the real-world datasets.
(a)
Iris (b)
Abalone (c)
Wine (d)
Ecoli (e)
WDBC


### 4.3.4. Parameter Analysis

The parametersm, K, and q are important in our proposed algorithm, which affect the performance of SSOD-AFW. In this section, the influence of each parameter on outlier detection accuracy is studied.The parameterm is the fuzzification coefficient. Figure 8(a) analyzes the relationship between the outlier detection accuracy of our proposed algorithm and parameter m, with m varying from 1.5 to 5.0. The results imply that the highest accuracy is achieved when m ranges in [2,4]. So it is reasonable that m value in the experiments shown in Figure 5 has been set as 2.1. The parameter K∈(0,1) controls the importance of the label information in the result of outlier detection. Outlier detection accuracies are testified by varying K from 0.1 to 0.9, which are shown in Figure 8(b). The overall tendency is that the accuracies become larger as K increases. The best results of the proposed algorithm occur and keep stable when K≥0.7. Finally, from Figure 8(c), we conclude that the feature weight index q has small influence on the accuracy of SSOD-AFW in the situation that the other parameters maintain the same settings. So the proposed algorithm is not sensitive to the parameter q. In general, the parameter q is suggested to select a constant from (1,4].Figure 8
Outlier detection accuracy of the proposed algorithm under various parameters on the real-world datasets.
(a)
Parameterm (b)
ParameterK (c)
Parameterq


### 4.3.5. Execution Time Analysis

Figure9 analyzes the average running time of the proposed algorithm against the other algorithms on five real-world datasets. The experimental environment is Windows XP systems, MATLAB 7.1 platform, 3 GHz CPU, 2 GB RAM. Because the volume of Abalone dataset is far greater than the other four datasets, the running times of various datasets are distinctly different. In order to facilitate the display, in Figure 9 the horizontal coordinate axis is translated downward a short distance. The result indicates that the proposed algorithm is more time-saving than the other four typical outlier detection algorithms, except for KNN on dataset Wine. In whole, the execution time of the SSOD-AFW is comparable to that of KNN and less than those of other algorithms on most of the datasets.Figure 9
Execution time comparison of different algorithms on the real-world datasets.


## 4.3.1. Introduction of Datasets

For further verification of the effectiveness of the proposed algorithm, five real-world datasets from UCI Machine Learning Repository [34] (i.e., Iris, Abalone, Wine, Ecoli, and Breast Cancer Wisconsin (WDBC)) are employed to test the performance of the proposed algorithm against LOF, KNN, SVDD, and EODSP. As mentioned in Aggarwal and Yu [35], one way to test the performance of an outlier detection algorithm is to run it on the dataset and calculate the percentage of points belonging to the rare classes. So a small amount of samples from the same class are randomly selected as outlying objects or as target objects, for the five datasets. For instance, the original Iris dataset incorporates 150 objects with 50 objects in each of three classes. We randomly selected 26 objects from class “Iris-virginica” as target outliers and all objects in the other two classes are considered as normal objects. The other four datasets are similarly preprocessed and more detailed description about the five real-world datasets is given in Table 1.Table 1
Description of real-world datasets.
Dataset Instances Features Outlying classes Outliers (percent) Clusters Prior information Iris 126 4 “Virginica” 26 (20.63%) 2 10 labeled normal samples, 4 labeled outliers Abalone 4177 8 “1”–“4,” “16”–“27,” “29” 335 (8.02%) 11 11 labeled normal samples, 18 labeled outliers Wine 130 13 “3” 11 (8.46%) 2 9 labeled normal samples, 4 labeled outliers Ecoli 336 9 “omL,” “imL,” “imS” 9 (2.68%) 5 11 labeled normal samples, 3 labeled outliers WDBC 387 30 “Malignant” 30 (7.75%) 1 10 labeled normal samples, 8 labeled outliers


## 4.3.2. Experimental Result Analysis

We compare the outlier detection performance of the proposed algorithm with LOF,KNN, SVDD, and EODSP on real-world datasets. Each method has its own parameters, and the detailed parameter settings of each algorithm are as follows. The parameters of the proposed algorithm are m=2.1, K=0.65, and q=1.53 for all the five datasets. The strategy of parameter selection for SSOD-AFW will be discussed in the later subsection called parameter analysis. For the other algorithms, those parameters are set exactly as mentioned in their references. It is well known that LOF and KNN have high dependency on the neighborhood parameter k. In this paper we set k=5 for datasets Iris and WDBC, k=3 for dataset Abalone, k=10 for dataset Wine, and k=10 for dataset Ecoli. For SVDD method, Gaussian kernel function is employed and the bandwidths σ=0.45 and C=0.5 on all of the five real-world datasets. In EODSP, the Euclidean distance threshold T is set as 0.1 and the percentage of negative set l is set as 30% for Iris and Abalone datasets, and T=0.5,  l=30% for datasets Ecoli, Wine, and WDBC. Since we randomly select outliers from target classes for each dataset, each experiment is repeated 10 times with the same number of different outliers. The average accuracy, AUC, and RP are calculated as the criteria of performance of various detection methods.Figure5 illustrates the outlier detection results of SSOD-AFW algorithm against LOF, KNN, SVDD, and EODSP, respectively, on the five real-world datasets. As can be seen from Figure 5, the proposed algorithm can accurately identify outliers according to the cluster structure of a dataset, with the guidance of the label knowledge. It shows distinct superiority over the other unsupervised (LOF, KNN), semisupervised (EODSP), and supervised (SVDD) methods. In particular, the outlier detection accuracy of SSOD-AFW in Figure 5(a) is significantly higher than the others, especially for datasets Iris and Wine. One can know from Figure 5(b) that the AUC values of our method are always higher than the others for all datasets except for WDBC. In terms of RP, SSOD-AFW performs better than the other four algorithms on datasets Iris and Wine, whereas slightly poorer than SVDD on Abalone, poorer than LOF on Ecoli, and poorer than KNN on WDBC, seen as in Figure 5(c).Figure 5
Performance comparison of various algorithms on the real-world datasets.
(a)
Accuracy (b)
AUC (c)
RPIt is worth mentioning that the experiment of the proposed algorithm on WDBC involves one-class clustering problem. Although one-class clustering task is generally meaningless, one-class clustering-based outlier detection is especially meaningful and feasible in our proposal because our approach does not require that the membership degrees must sum up to 1. This is one of the powerful and important characteristics of the proposed algorithm.


## 4.3.3. The Influence of the Proportion of Labeled Data on Outlier Detection

In this subsection, we will investigate the influence of the proportion of labeled samples on the accuracies of our methodology. Two typical situations are considered and tested. The first one is that the proportion of labeled outliers increases when the number of labeled normal objects is fixed at a certain constant. The other one is that the percent of labeled normal samples varies while the quantity of labeled outliers is fixed. So two groups of experiments are designed to compare the accuracies of the proposed algorithm against the EODSP, in the situations of different percent of labeled outliers and normal samples, respectively, on the datasets Iris, Abalone, Wine, Ecoli, and WDBC. In the two experiments, the percent of labeled outliers or labeled normal samples ranges from 0% to 40%, respectively, when the number of another kind of labeled objects is fixed. We randomly select a certain number of labeled outliers or normal samples from each dataset, each experiment is repeated 10 times, and the average accuracies of SSOD-AFW and EODSP are computed.Figure6 shows results of the first group of experiments where the percent of labeled outliers varies from 0% to 40%. One can see from Figure 6 that the accuracies of the two semisupervised algorithms are roughly increased with the proportion of labeled outliers becoming larger. This powerfully supports the idea that semisupervised outlier detection algorithms can improve the accuracy of outlier detection by using prior information. Furthermore, the SSOD-AFW achieves a better accuracy than EODSP algorithm for the same proportion of labeled outliers on the five datasets. Especially for Wine, the accuracy of SSOD-AFW is 40% higher than that of EODSP. EODSP addresses the problem of detecting outliers with only few labeled outliers as training data. The labeled normal instances are extracted according to the maximum entropy principle, where the entropy is computed only using the distance between each testing sample and all the labeled outliers. That makes EODSP not flexible as our proposed method due to information deficiencies.Figure 6
Accuracy analysis of algorithms EODSP and SSOD-AFW with different percent of labeled outliers on the real-world datasets.
(a)
Iris (b)
Abalone (c)
Wine (d)
Ecoli (e)
WDBCFigure7 illustrates the accuracy comparison of the proposed algorithm and EODSP, when the proportion of labeled normal samples increases from 0% to 40% and the percent of labeled outliers is fixed. Note that our method obtains a better accuracy than EODSP on all of the five real-world datasets. The accuracy of the proposed algorithm gets larger when the percent of labeled normal samples increases. As mentioned, EODSP emphasizes the semisupervised outlier detection only with few labeled outliers in the initial dataset, but without considering any labeled normal objects. Therefore, the accuracy of EODSP algorithm keeps harper with various proportions of labeled normal objects and always equals the accuracy value of 0% labeled normal samples as well.Figure 7
Accuracy analysis of algorithms EODSP and SSOD-AFW with different percent of labeled normal samples on the real-world datasets.
(a)
Iris (b)
Abalone (c)
Wine (d)
Ecoli (e)
WDBC


## 4.3.4. Parameter Analysis

The parametersm, K, and q are important in our proposed algorithm, which affect the performance of SSOD-AFW. In this section, the influence of each parameter on outlier detection accuracy is studied.The parameterm is the fuzzification coefficient. Figure 8(a) analyzes the relationship between the outlier detection accuracy of our proposed algorithm and parameter m, with m varying from 1.5 to 5.0. The results imply that the highest accuracy is achieved when m ranges in [2,4]. So it is reasonable that m value in the experiments shown in Figure 5 has been set as 2.1. The parameter K∈(0,1) controls the importance of the label information in the result of outlier detection. Outlier detection accuracies are testified by varying K from 0.1 to 0.9, which are shown in Figure 8(b). The overall tendency is that the accuracies become larger as K increases. The best results of the proposed algorithm occur and keep stable when K≥0.7. Finally, from Figure 8(c), we conclude that the feature weight index q has small influence on the accuracy of SSOD-AFW in the situation that the other parameters maintain the same settings. So the proposed algorithm is not sensitive to the parameter q. In general, the parameter q is suggested to select a constant from (1,4].Figure 8
Outlier detection accuracy of the proposed algorithm under various parameters on the real-world datasets.
(a)
Parameterm (b)
ParameterK (c)
Parameterq


## 4.3.5. Execution Time Analysis

Figure9 analyzes the average running time of the proposed algorithm against the other algorithms on five real-world datasets. The experimental environment is Windows XP systems, MATLAB 7.1 platform, 3 GHz CPU, 2 GB RAM. Because the volume of Abalone dataset is far greater than the other four datasets, the running times of various datasets are distinctly different. In order to facilitate the display, in Figure 9 the horizontal coordinate axis is translated downward a short distance. The result indicates that the proposed algorithm is more time-saving than the other four typical outlier detection algorithms, except for KNN on dataset Wine. In whole, the execution time of the SSOD-AFW is comparable to that of KNN and less than those of other algorithms on most of the datasets.Figure 9
Execution time comparison of different algorithms on the real-world datasets.


## 5. Conclusions

In order to detect outliers more precisely, a semisupervised outlier detection algorithm based on adaptive feature weighted clustering, called SSOD-AFW, is proposed in this paper. Distinct weights of each feature with respect to different clusters are considered and obtained by adaptive iteration, so that the negative effects of irrelevant features on outlier detection are weakened. Moreover, the proposed method makes full use of the prior knowledge contained in datasets and detects outliers in virtue of the cluster structure. It is verified by a series of experiments that the proposed SSOD-AFW algorithm is superior to other typical unsupervised, semisupervised, and supervised algorithms in both outlier detection precision and running speed.In this paper, we present a new semisupervised outlier detection method which utilizes labels of a small amount of objects. However, our method assumes that the labels of objects are reliable and does not consider mislabel punishment in the new objective function. Therefore, a robust version of the proposed method dealing with noisy or imperfect labels of objects deserves further studies. Moreover, since only one typical dissimilarity measure named Euclidean distance is discussed in our method, the SSOD-AFW algorithm is limited to outlier detection for numerical data. The future research aims at extending our method to mixed-attribute data in more real-life applications such as fault diagnosis in industrial process or network anomaly detection.



---

*Source: 6394253-2016-12-28.xml*