In this section, a risk decision making approach based on the dynamic K-means clustering and logistic regression is proposed. The dynamic K-means clustering method is used to divide the samples iteratively into groups, in each of which the samples are approximately homogeneous, and logistic regression is applied to each group of samples to obtain the estimated smuggling probabilities. After the above steps, the risk decision making rule is applied to make the optimal targeting decision. To make the procedures of the proposed risk decision-making approach more clear, we first briefly introduce the conventional K-means clustering and present the validity function.

K-means clustering is a popular algorithm particularly suited for partitioning large amount of samples [26M.N. Vrahatis, B. Boutsinas, P. Alevizos, and G. Pavlides, "The new k-windows algorithm for improving the k-mean clustering algorithm", J. Complexity, vol. 18, no. 1, pp. 375-391, 2002.
[http://dx.doi.org/10.1006/jcom.2001.0633] ]. The main process of the K-means clustering includes the following four steps [15J. Han, and M. Kamber, Data mining: Concepts and Techniques., Morgan Kaufmann: New York, 2006.]: (1) selection of the initial K centroids. In this step, K samples are often randomly selected as the centroid of K clusters; (2) assignment. In this step, each sample is assigned to the nearest cluster in sequence (the distance is usually measured in Euclidean distance metric). Meanwhile, the centroid of newly changed cluster should be updated; (3) computation of the quality function of clustering; (4) evaluation. If the quality function does not change, stop and output the final clustering results, else go to step (2).

In K-means clustering, an important problem is to determine the number of clusters, which is usually called the cluster validity [27J.C. Bezdek, "Cluster validity with fuzzy sets", J. Cybern., vol. 3, pp. 58-73, 1974.
[http://dx.doi.org/10.1080/01969727308546047] ]. In the literature, many cluster validity indexes such as partition coefficient (PC) and partition entropy (PE) [27J.C. Bezdek, "Cluster validity with fuzzy sets", J. Cybern., vol. 3, pp. 58-73, 1974.
[http://dx.doi.org/10.1080/01969727308546047] ], XB index [28X.L. Xie, and G. Beni, "A validity measure for fuzzy clustering", IEEE T. Patt. Anal. Mach. Intell., vol. 13, no. 8, pp. 841-847, 1991.
[http://dx.doi.org/10.1109/34.85677] ], modified partition coefficient (MPC) [29R.N. Dave, "Validating fuzzy partition obtained through c-shell clustering", Pattern Recognit. Lett., vol. 17, no. 6, pp. 613-623, 1996.
[http://dx.doi.org/10.1016/0167-8655(96)00026-8] ], DB index and two of its generalized versions [30J.C. Bezdek, and N.R. Pal, "Some new indexes of cluster validity", IEEE T. Syst. Man Cybern. -Part B: Cybern., vol. 28, no. 3, pp. 301-315, 1998.
[http://dx.doi.org/10.1109/3477.678624] ], SC index [31N. Zahid, M. Limouri, and A. Essaid, "A new cluster-validity for fuzzy clustering", Patt. Recog., vol. 32, no. 7, pp. 1089-1097, 1999.
[http://dx.doi.org/10.1016/S0031-3203(98)00157-5] ], Dunn’s index [32S. Bandyopadhyay, and U. Maulik, "Nonparamatric genetic clustering: comparison of validity indices", IEEE T. Syst., Man Cybern. -Part C. Appl. Rev., vol. 31, no. 1, pp. 120-125, 2001.], and SV index for crisp clustering and SVF index for fuzzy clustering [33K.R. Zalik, and B. Zalik, "Validity index for clusters of different sizes and densities", Pattern Recognit. Lett., vol. 32, no. 2, pp. 221-234, 2011.
[http://dx.doi.org/10.1016/j.patrec.2010.08.007] ], have been proposed to determine the optimal number of clusters and evaluate the fitness of partitions produced by clustering algorithm. In this paper, a new validity function for hard K-means clustering is proposed based on the idea of Wu and Yang [34K.L. Wu, and M.S. Yang, "A cluster validity index for fuzzy clustering", Pattern Recognit. Lett., vol. 26, no. 9, pp. 1275-1291, 2005.
[http://dx.doi.org/10.1016/j.patrec.2004.11.022] ], in which two main aspects of clustering validity are considered, i.e., compactness of each cluster and separation between clusters. However, in their work, the validity function is for soft K-means clustering. In order to fit it to hard K-means clustering for supervised clustering, the validity function is modified as follows.

Assume the data set S consisting of N samples X₁, X₂,...,X_N (class labels are not considered in unsupervised clustering) is partitioned into K clusters C₁, C₂,...,C_K The centroids of these clusters are denoted by r₀¹, r₀²,...,r₀^K, in which r₀^K (k = 1, 2,...,K) is defined as

(1)

where m_k is the number of samples in cluster C_k, and X_i^k, (i = 1, 2,..., m_k ) denotes the ith sample that belongs to the cluster C_k. The index of compactness of clusters obtained is defined as

(2)

In formula (2), the term Intra(k ) represents the relative distance between each sample and the centroid, with respect to the maximal distance between all samples and the centroid, in the kth cluster. It is defined as

(3)

Intuitively, a compact cluster requires the term Intra defined in formula (2) to be small. Since 0 < Intra(k ) ≤ 1, it can be easily seen that 0 < Intra ≤ 1 . For clusters with only one sample, we define Intra(k ) = 1 .

For a good clustering result, not only each cluster obtained is compact, but also these clusters are well separated from each other. For this purpose, the index of separation between clusters is defined as follows

(4)

in which is the average distance between each pair of cluster centroids, and is the average distance of each cluster centroid r₀^k to the centroid of all samples. Apparently, 0 < Inter ≤ 1, and a smaller Inter indicates that clusters obtained are more separated from each other.

The objective of K-means clustering is to find out the optimal K clusters each of which is compact and separated from others. Therefore, the validity function considering both the compactness and separation of clusters is defined as follows

(5)

in which Intra and Inter are defined in formulas (2) and (4), respectively. Clearly, the smaller the VF (K ) is, the better the clustering results are.

Fig. (1) The main steps of the dynamic K-means clustering.

As described above, due to the outliers and diversity of samples, severe heterogeneity may exist in one or more groups obtained by conventional K-means clustering method. Moreover, this problem could not be solved by simply increasing the value of K. To improve the result of conventional K-means clustering, a dynamic K-means clustering method is developed.

The dynamic clustering is an iterative K-means clustering method. The main difference between dynamic clustering and conventional K-means clustering is that in dynamic clustering, the number of clusters is not constant. In each iteration of the dynamic clustering, the goodness of the kth cluster obtained is evaluated by the index Intra(k ) defined in formula (2). Since this index represents the compactness of a cluster, it is implied that a cluster with larger Intra(k ) may consist of samples with severe heterogeneity. Therefore, the cluster with ‘worst’ (largest) Intra(k ) is picked out and divided into sub-clusters iteratively. The main steps of the dynamic K-means clustering method are shown in Fig. (1).

There are two stages in Algorithm 1. In the first stage (step 1 to 4), samples are divided into K_opt clusters by conventional K-means clustering. The maximum K is set to be √N according to Wu and Yang [34K.L. Wu, and M.S. Yang, "A cluster validity index for fuzzy clustering", Pattern Recognit. Lett., vol. 26, no. 9, pp. 1275-1291, 2005.
[http://dx.doi.org/10.1016/j.patrec.2004.11.022] ]. The second stage (step 5 to 9) is a process of iterative partitioning in order to optimize the validity function. Since the total number of clusters increases in each iteration, the convergence of the algorithm is ensured.

Suppose there are N observations and each observation X_i, (i = 1, 2,..., N )can be described as X_i = [x_i,1 , x_i,2 ,..., x_i,D , y_i ], where x_i,d (d = 1, 2..., D) are observed values of attributes (independent variables), and y_i ϵ{0,1} is the occurrence of state of nature (target variable). The purpose of logistic regression is to investigate the relationship between the independent variables and target variable. Generally, the logistic regression model for D independent variables x₁ , x₂,..., x_D can be written as

(6)

where α₀, α₁, α₂,..., α_D are regression coefficients. In producing the logistic regression equation, the maximum-likelihood method is commonly used to estimate the coefficients and determine the statistical significance of the variables [35D.W. Hosmer, and S. Lemeshow, Applied Logistic Regression., John Wiley & Sons: New York, 2000.
[http://dx.doi.org/10.1002/0471722146] ].

After the establishment of the logistic regression model, it can be utilized to estimate the probability P( y_j^p = 1) for new-arrived samples X₁^p, X₂^p, ..., X_M^p whose values of independent variables x_i^p_,d (j = 1,2, ..., M and d = 1,2, ..., D) are observed but target variable y_i^p is unknown, using the following

(7)

where are the estimated coefficients of the logistic regression model.

After the samples are divided into clusters C₁ , C₂ ,..., C_K , relationship between independent variables and target variable in each cluster are modelled by logistic regression. Consequently, the smuggling probabilities of samples could be obtained. As described in Section 1, in China’s customs targeting problem, there are two states of nature, one state is legality and the other is smuggling, which means the set of states of nature is Ω = {θ₁ (legality), θ₂ (smuggling )}. For a newly encountered declaration of import/export goods, the customs officials have to make a decision, and the set of actions is A = {a₁ (no − inspection), a₂ (inspection)} . Since they do not know exactly whether a declaration of goods is of smuggling, they can make the inspection decision by a decision rule δ ( p, a) : [ p ≤ p₀ → a₁ , a₂ ] ([E → u, v] means that if E is true then take action a₁, otherwise take a₂ ), where p = Pr(θ₂) is the estimated smuggling probability of the declaration of goods and p₀ is a threshold smuggling probability.

This decision rule indicates that, if p ≤ p₀, the decision-maker predicts that the state of θ₁ would occur, and then he/she takes action a₁ ; on the contrary, if p > p₀ , the decision-maker predicts that the state of θ₂ would occur and then takes action a₂.

Two critical parameters of the above decision rule is the estimated smuggling probability p = Pr(θ₂) of the declaration of goods and the threshold smuggling probability p₀. Reasonably, the newly encountered declared goods should be assigned to a specific cluster first, and then the logistic regression model in the cluster is used to estimate the probability of smuggling. Assume that the newly encountered declaration of goods is assigned to cluster C_k , the empirical risk of inspection decision in cluster C_k is

(8)

where n_k is the number of historical observations in cluster C_k, p₀^k is the threshold probability in cluster C_k , and y_i is the occurrence of smuggling ( y_i = 1 means smuggling and y_i = 0 means not smuggling). To minimize the empirical risk of inspection decision, the threshold probability p₀^k, (k = 1, 2,..., K) is determined by

(9)

To sum up, the main procedure of the risk decision making rule (Decision Making Rule-I, DMR-I) is shown in Fig. (2).

Fig. (2) The main steps of DMR-I.

In the application to China’s customs targeting problem, the risk decision-making approach could be summarized as follows. Historical observations are divided into a number of clusters by using the dynamic K-means clustering method, and the relationship between the occurrence probabilities of smuggling and the attributes of observations is modelled by logistic regression in each cluster. After the estimated smuggling probabilities are obtained, a threshold probability is determined such that the empirical error is minimized. Given a newly encountered declaration of goods whose state of smuggling is unknown, it is first assigned to a cluster, and then the probability of smuggling is estimated by the logistic regression model. By comparing the estimated probability of smuggling with the threshold probability in this cluster, the state of smuggling is predicted and consequently, an action is suggested.

Due to the time and resource constraints on decision’s execution, declared goods with smuggling probabilities larger than the threshold probability in some clusters may not be totally inspected. As a matter of fact, most customs are only able to inspect a maximum of 5% of declared goods. To make the decision rule applicable in such situations, the DMR-I is modified and an alternative decision making rule (Decision Making Rule-II, DMR-II) is developed as follows. Denote by max_ per the maximum percentage of goods that the customs official could inspect within their execution time and ability. If in cluster C_k, , which means the number of goods suggested to be inspected is larger than the maximum capacity of inspection, the declared goods with highest smuggling probabilities are suggested to be inspected within the capacity of inspection.

The data set used in case study is collected from the database of one local customs in China during on year. The number of observations in the data set is 300,825. For each sample indicating a declaration of import/export goods in the data set, there are one label that indicates whether it is of smuggling and more than 30 attributes such as transportation mode of goods, delayed days of declaration, quantity, net weight, declared unit price of goods, et al.

For the performance evaluation, cross validation is often used to obtain robust and consistent predictions [36K. Coussement, and W. Buckinx, "A probability-mapping algorithm for calibrating the posterior probabilities: A direct marketing application", Eur. J. Oper. Res., vol. 214, no. 3, pp. 732-738, 2011.
[http://dx.doi.org/10.1016/j.ejor.2011.05.027] ]. In this procedure, a data set is randomly partitioned into two subsets: a training data set and a testing data set. The training data set is used to construct the prediction models, and the testing data set is used to evaluate their performance. In this study, the data set consists of 200,000 observations from the first eight months is used as the training data set, and the remaining 100,825 observations are used as the testing data set. In both training and testing data sets, the smuggling ratio (number of smuggling goods/total number of goods) is about 5%. Since the customs aim to inspect more smuggling goods out of a small proportion of declared goods, the hit ratio is used to evaluate the performance of risk decision-making approach, which is defined as

Clearly, a higher hit ratio, which means more smuggling declared goods are caught within a given number of inspected goods, indicates a better decision-making result.

In order to apply clustering method to the data set for preprocessing, variables (attributes) used for clustering should be first selected. Recall that the aim of clustering is to group the large amount of declared goods into a number of clusters so that samples in each cluster are approximately homogeneous. By discussing with the officials of China’s customs, eight variables that represent the similarity of declaration of import/export goods are selected for clustering. These variables are described in Table 1.

Table 1
Selected variables for clustering.

For logistic regression that estimates the empirical smuggling probabilities of goods, the target variable is the state of smuggling or not, which means that the variable is binary with the value 1 or 0, and the independent variables are a number of attributes of goods. Based on custom officials’ experience, we select thirteen independent variables indicative of the smuggling probability of goods. These variables are shown in Table 2.

Table 2
Selected variables used in logistic regression analysis.

Due to the variety and diversity of export/import trades in China, the values of variables selected for clustering have abnormally large ranges. For example, the values of variable VNW (ratio of value to net weight of goods) and QNW (Ratio of quantity to net weight of goods) range from less than one to more than a million. Tables 3 and 4 report the percentage of observations that lie in each interval of log₁₀ (VNW) and log₁₀ (QNW), respectively.

Table 3
The percentage of observations in each interval of log₁₀ (VNW).

Table 4
The percentage of observations in each interval of log₁₀ (QNW).

It can be observed from Table 3 and 4 that most values of the variables VNW and QNW lie in the interval (0,100), and a small number of values are more than a million. As pointed out by Xu et al. [37L. Xu, A. Krzyzak, and E. Oja, "Rival penalized competitive learning for clustering analysis, RBF net, and curve detection", IEEE Trans. Neural Netw., vol. 4, no. 4, pp. 636-649, 1993.
[http://dx.doi.org/10.1109/72.238318] [PMID: 18267764] ], there is dead-unit problem in the method of conventional K-mean clustering. That is, if some units are initialized far away from the input data set in comparison with other units, they then immediately become dead without learning chance any more in the whole learning process. Therefore, in K-means clustering, those samples with abnormally large variable values would make a large number of samples with relatively small or medium values clustered into one large group. Consequently, statistical analysis would be hindered due to the heterogeneity among the samples.

In order to investigate the impact of the abnormally large variable values on the clustering results, conventional K-means clustering method is used to divide the data set into clusters. To determine the optimal cluster number, we first calculate the validity function values for different K. As suggested in Wu and Yang [34K.L. Wu, and M.S. Yang, "A cluster validity index for fuzzy clustering", Pattern Recognit. Lett., vol. 26, no. 9, pp. 1275-1291, 2005.
[http://dx.doi.org/10.1016/j.patrec.2004.11.022] ], the range of K is set to vary from 2 to √N (N is the total number of samples). The values of VF (K ) corresponding to each K are shown in Fig. (3) (we omit the values of VF (K ) for K>20 because those values are all larger than 0.10).

It can be observed from Fig. (3) that K=4 is the optimal cluster number with the smallest function value 0.082. The result of K-means clustering with K=4 is shown in Table 5.

Fig. (3) VF(K) of conventional K-means clustering.

Table 5
The results of conventional K-means clustering on the data set.

Table 5 illustrates that more than 85 percent of the samples are clustered into one group, which means that there may be severe heterogeneity in this group. In the application of the K-means clustering method, it has been found that as the K turned larger, number of samples in the abnormally large group did not change significantly, while many clusters became very small with only a few samples, which would make statistical analysis insufficient because of the lack of samples. For example, parts of the clustering results of K=20 and K=50 are shown in Table 6.

Table 6
Abnormality in clustering results (K=20 and K=50).

It can be observed from Table 6 that increasing K is not an efficient way to improve the clustering result significantly. In order to get relatively equal-size groups in each of which the samples are approximately homogeneous, a more sophisticated clustering method for data preprocessing is needed in China’s customs targeting problem.

Table 7
The result of the dynamic K-means clustering method on the training dataset.

Alternatively, we apply the proposed dynamic K-means clustering method to the training data set. The values of validity function corresponding to different K are shown in Fig. (4).

Fig. (4) VF(K) of the dynamic K-means clustering method.

It can be observed from Fig. (4) that VF (K ) is minimized when K=13, which indicates the clustering result obtained in the iteration corresponding to K=13 is optimal. The clustering result is summarized in Table 7.

It can be observed from Table 7 that the data set could be divided into more clusters with approximately equal sizes by the proposed dynamic K-means clustering method. In order to investigate the validity of results obtained by the dynamic K-means clustering, we compare the values of validity function for K ϵ [8C.Y. Peng, B.D. Manz, and J. Keck, "Modeling categorical variables by logistic regression", Am. J. Health Behav., vol. 25, no. 3, pp. 278-284, 2001.
[http://dx.doi.org/10.5993/AJHB.25.3.15] [PMID: 11322627] , 20I. Benítez, A. Quijano, J.L. Díez, and I. Delgado, "Dynamic clustering segmentation applied to load profiles of energy consumption from Spanish customers", Electr. Power Ener. Syst., vol. 55, pp. 437-448, 2014.
[http://dx.doi.org/10.1016/j.ijepes.2013.09.022] ] in conventional K-means clustering and dynamic K-means clustering, as shown in Fig. (5).

Fig. (5) Comparison of VF(K) in different clustering methods.

By comparing VF (K) of conventional K-means clustering to that of the dynamic K-means clustering shown in Fig. (5), it can be concluded that for the same cluster number, the dynamic K-means clustering method delivers better clustering result with smaller value of validity function. Therefore, the clusters obtained are more compact and separated from each other. Consequently, the heterogeneity may be reduced in these clusters.

In order to evaluate the performance of the proposed risk decision-making approach for customs targeting, three different experiments are conducted for comparisons. In the first experiment, logistic regression is directly applied to the calibration data set and validation data set without any preprocessing. In the second experiment, DMR-I and DMR-II are applied, but the conventional K-means clustering instead of the dynamic K-means clustering is utilized for preprocessing. In the third experiment, DMR-I and DMR-II are applied.

By using SAS System for Windows 9.0 to execute the clustering methods and logistic regression, the computational results of the three experiments are shown in Table 8. It is noteworthy that the robustness of the k-means clustering algorithm is affected by the initial set of centroids as well as the number of iterations [38F. Lolli, A. Ishazaka, and R. Gamberini, "New AHP-based approaches for multi-criteria inventory classification", Int. J. Prod. Econ., vol. 156, pp. 62-74, 2014.
[http://dx.doi.org/10.1016/j.ijpe.2014.05.015] ]. However, since we focus on developing a dynamic clustering algorithm suitable for partitioning large amount of data and improving the accuracy of risk decision-making, we ignore the issues of initial set of centroids and the number of iterations, simply adopting the default setting in the SAS system.

Table 8
The results of three different experiments.

It can be observed from Table 8 that the accuracy of inspection decision in the 3^rd experiment is the best, which indicates that the dynamic K-means clustering method is effective in preprocessing data sets that contain a large variety of observations with severe heterogeneity. This is favourable for customs administration, whose purpose is to inspect as more smuggling goods as possible given a limited inspection capacity (about 5% of the total import/export goods).