To complete the on-board equipment of space systems with a highly reliable electronic component base (ECB), specialized test centers perform hundreds of tests to analyze each semiconductor device. One of the requirements is that the shipped lot of products must be made from a single batch of raw materials (wafers) which is not guaranteed if the devices are not manufactured for use in the space industry only. To solve the problem of detecting homogeneous production batches, various clustering algorithms are implemented on multidimensional data of test results. In practice, it is impossible to predict in advance which of the algorithms in each particular case will show the most adequate results and the use of the ensemble approach is promising. Most of the clustering algorithms for the problem of dividing the ECB mixed lot into two homogeneous production batches show rather high accuracy. With an increase in the number of homogeneous production batches in the mixed lot, the accuracy decreases. Authors propose an approach to constructing an ensemble of clustering algorithms based on co-occurrence matrices with weight coe cients. Results of computational experiments on specially mixed lots of the ECB show that for the such large-scale problems, the use of the ensemble approach allows to achieve a higher adequacy of the results. Individual algorithms can show results that exceed the ensemble's accuracy, but the accuracy of the ensemble is still higher than the averaged accuracy of individual algorithms.
Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
Intensive use of big data in various areas leads to increased interest of researchers
in methods and tools for processing and analysing datasets of huge volumes and
diversity. One of the promising directions of big data analysis is the cluster
analysis, which allows solving such problems as reducing the size of the initial data
set, identifying patterns, etc [
Clustering [
A criterion for the clustering quality is some functional which depends on the
scatter of objects within the group (cluster) and the distances between them [
The on-board units of spacecrafts must be equipped with a highly reliable
electronic component base (ECB). First of all, it is necessary to prevent
counterfeit products that do not meet the reliability requirements, ensure the purchase
of ECB from authorized suppliers and passing through the 100 % input
control, additional rejection tests and destructive physical analysis (DPA) of ECB.
Individual rejection tests of components are essential [
ECB clustering is important in terms of ensuring reliability and, even more, radiation resistance. Ionizing radiation as a physical factor of the space environment determines the period of active existence of space systems.
At present, there is a tendency to use collective methods in cluster analysis
[
Results of Various Standalone Clustering Algorithms As datasets for our experiments, we used the results of non-destructive tests of mixed production batches of the ECB performed in a specialized test center. The composition of the mixed production batches was known in advance. These mixed batches were completed from several obviously homogeneous batches of the ECB:
- 140UD25AVK: 2 production batches (ECB clusters) and comparatively small data volume (56 data vectors of dimensionality 18); - 3OT122A: 2 batches (767 data vectors of dimensionality 10); - 1526LE5: 6 batches (963 data vectors of dimensionality 41).
Our problem was to divide the mixed batch into homogeneous components and analyze the quality of this division.
We used 5 common clustering algorithms [
In addition to the actual form of the clustering algorithm, the result is significantly in uenced by the parameters of the algorithms which can be optimized by their values. By optimization, we mean the selection of such values of some optimized parameter at which the maximum clustering accuracy is ensured, that is, the best match of the result of clustering to the true partition of the mixed batch into homogeneous batches of ECB is achieved. As an optimized parameter in the k-Means, k-Means (fast) and k-Medoids algorithms, we used the type of distance measure. For the k-Means (kernel) algorithm, tried to use various types of the kernel (dot / radial kernel). For the EM algorithm, we tried to nd the optimal number of optimization steps in each iteration.
At the output of this process, we evaluate our results by the accuracy. By accuracy, we mean the proportion of data objects assigned to the "right" cluster. This "correctness" can be assessed by having a sample of marked data, for which it is known in advance that they are assigned to a particular cluster. In this case, our samples are combined from data from separate homogeneous batches of ECB. The results are summarized in Table 1.
As we can see from this table, the clustering algorithms with relatively small data volumes and small number of production batches (clusters) show rather high accuracy. With the increase in data volumes and the number of clusters, clustering accuracy decreases.
For clustering models, the most important parameter a ecting the result is
the distance measure used. The use of special measures sometimes allows us
to adapt simple models like k-means to rather complex clustering problems. In
case of using some complex and non-standard distance measures, a su cient
condition for the applicability of the measure of distance is the existence of
an algorithm for solving the corresponding Weber problem, i.e. the problem of
nding the center of the cluster [
For comparative analysis, in addition to the problems of ECB batches
clustering, we analyzed the features of clustering algorithms and their ensembles on
the most common data sets from the UCI Machine Learning Repository [
Results of standalone algorithms were summarized in Table 2.
Due to problems concerning the behavior of the EM algorithm with comparatively small datasets in the multidimensional space (all objects of a small cluster in a multidimensional space belong to the same hyperplane and the corresponding probability distribution represented by its covariation matrix collapses into the hyperplane), our realizatio of the EM algorithm did not allow to obtain results for some particular cases ("no result" in Table 2). In particular cases, analogous problem arose in the procedure which optimized parameters of the other algorithms. 3
The ensemble approach is one of the most promising directions in cluster analysis
[
1. Finding a consensus partition, i.e. consistent partitioning with several available solutions, optimal for some criterion;
2. Calculation of a consistent matrix of similarity/di erences (co-occurrence matrix).
When forming the nal solution, an ensemble uses the results obtained by various algorithms.
Let us consider an example of an ensemble of algorithms [
In the rst step, each algorithm splits the data into clusters using its objective function, based on the distance metric or on the likelihood function. Then, the accuracy and weight of the view of the algorithm in the ensemble are calculated by the following equation:
Wi =
Acci PL i=1 Acci (1) where Acci is the accuracy of the ith algorithm, i.e. the ratio of the number of correctly clustered objects to the volume of the entire sample, and L is the number of the algorithms in our ensemble.
For each partition obtained, our algorithm compiles a preliminary binary matrix of di erences of size n n (where n is the number of objects) to determine whether the objects of the partition are included in the same clusters. After that, our algorithm calculates a matched matrix of di erences, each element of which Algorith is a weighted sum (using the weight of equation (1)) of the elements of the preliminary matrices. The obtained matrix is used as input for the algorithm of hierarchical agglomerative clustering. Then, using common techniques, such as determining the jump in the agglomeration distance, we can choose the most suitable cluster solution.
As mentioned above, to obtain the best partitioning into clusters, a binary matrix of similarity/di erences for each partition in the ensemble is constructed:
Hi = hhi(i; j)i where h(i; j) = 0 if both ith and jth elements belong to the same cluster, and 1, otherwise.
The next step in composing an ensemble of clustering algorithms is to compile a matched matrix of binary partitions.
H = hh (i; j)i; h (i; j) =
L X wihi(i; j) i=1 where wi is the weight of the ith algorithm.
The most popular clustering algorithms often fail for certain datasets that do
not match well with the modeling assumptions [
For constructing an ensemble (Table 3), we take three or ve best algorithms showing the highest accuracy for each speci c dataset (Table 1).
For the 140UD25AVK dataset, we used k-Means, k-Means(kernel) and kMedoids to construct an ensemble of three best algorithms; for 3OT122A dataset, we used EM-Optim., k-Medoids-Optim. and EM; for 1526LE5, we used k-MeansOptim., k-Medoids-Optim. and k-Means(fast)-Optim.
Analogous results for various datasets from the UCI Repository are shown in Table 4 and Table 5.
A fragment of calculation of ensemble results for dataset 3OT122A is given in Table 6. In most rows, some of standalone algorithms demonstrate wrong result and the ensemble improves this situation. 4
Our computational experiments show that any clustering algorithms for the problem of dividing a batch of ECB batch into two homogeneous batches can be used with rather high accuracy. With increase in the number of homogeneous production batches in the mixed batch, the accuracy decreases. For di erent data sets, the best results are demonstrated by di erent algorithms.
Using ensemble approach allows achieving higher accuracy in comparison with standalone clustering algorithms. In this case, individual algorithms are able to show results that exceed the ensemble's accuracy, however, the accuracy of the ensemble is still higher than the averaged accuracy of the individual algorithms. It is also necessary for a particular problem to take into account the number of algorithms used in the ensemble, in connection with the fact that the accuracy of the ensemble of clustering algorithms for various data depends on the number of algorithms in the ensemble.
In practice, the accuracy of clustering cannot be determined due to the lack
of information on the actual classes in the sample and it is impossible to predict
a priori which of the algorithms in the particular case shows the most adequate
results. Thus, usage of an ensemble approach to our problem is a promising
research direction. In particular, the application of the ensemble approach in
combination with the clustering algorithms that provide the best result within
the framework of the given clustering model [
The last table shows that for three of ve data sets, the ensembles of algorithms show results that are worse than the averaged value of the individual algorithms from which they are composed. This is typical for ensembles of both three and ve best algorithms.
Though for our problem of mixed production batch separation, the ensemble approach does not show an advantage over individual algorithms in all cases, in general, the ensemble approach allows reducing the dependence of the obtained results on the features of using separate algorithms to a speci c data set. Taking into account that the best results for di erent data sets are achieved by di erent algorithms, selection of some set of the best algorithms that show good results for many problems of such class increases the reliability of the process of homogeneous ECB production batch separation.
Acknowledgement. Results were obtained in the framework of the state task No. 2.5527.2017/8.9 of the Ministry of Education and Science of the Russian Federation.