Post-hoc cluster analysis of connection between the forming characteristics

Abstract

In this paper, one of the variants of so-called post-hoc cluster analysis problem is considered: the characteristics by which the clusters were constructed are ranked according to the degree of their influence on the final cluster partition. Wherein, using the pairwise coefficients proposed in the paper, we estimate the possibility of replacing a pair of characteristics by one of them (the degree of dominance of one characteristic over another), and the strength of the kind of mutual influence of the characteristics that is associated with the existing cluster structure. The latter influence we call a cluster connection. The most meaningful results were obtained, assuming that the addition or elimination of any forming characteristic leads to the grinding or consolidation of clusters, which is true for the algorithms of hierarchical classification.

Keywords

Cluster connection forming characteristics cluster dominance post-hoc problem in cluster analysis hierarchical cluster

1. Introduction

Algorithms for dividing observations into groups according to the degree of their proximity are in demand today in virtually any statistical study. If, in doing so, the objects of each of the obtained groups turn out to be closer in some sense than the objects taken from different groups, then the process is called clustering. In this case the family of groups being formed is referred to as a cluster partition, and the groups themselves are called clusters. A cluster method called discriminant analysis is one of the most practical, see Abdi (2007); Chance and Rossman (2013). It implies studying a certain training set. Then the rule constructed on the set is transferred to newly arrived objects. When solving such a problem we can talk about a process of classifying of new objects. So, the solution of the problem of discriminant analysis consists of two steps. First, we produce the clustering of the training set. Then, we construct a classifying rule based on it.

It often turns out that the number of those characteristics of the objects under study should be reduced. For example, it is done to obtain more comprehensive mathematical models and classification rules for practical usage. This leads to the need to estimate the relative information value of the characteristics. Such estimations can be derived from the results already obtained on the training set (post-hoc analysis of the characteristics, see, for example, Dronov & Dementjeva, 2012).

The post-hoc analysis of the characteristics can also be useful to solve some practical issue. Let’s assume that some of the characteristics of a newly arrived object to be unmeasurable (the absence of complicated equipment, lack of time, human factor). Such situations are frequent in medicine, if it is necessary to perform diagnostics with incomplete data. Investigating of such situation is a sphere of our major interest.

Let us consider the problem in a more accurate way. Let some finite set $U$ of objects, defined by a suit of their characteristics $X_{1},\ldots,X_{p}$ , be somehow divided into clusters. This clustering will be called proper partition. We believe that it takes into consideration the impact of all the characteristics. So $X_{1},\ldots,X_{p}$ will be further referred to as forming characteristics. We will study the relative information values of the forming characteristics for the formation of the proper cluster partition.

It should be noted that it is possible to abandon the using of any cluster algorithm for building the proper partition, and assume that it is constructed, say, by peer evaluation. Moreover, when considering medical applications in which, for example, various diagnoses are possible clusters, such proper partition can be considered completely error-free. Indeed, the necessary clarifications in the diagnoses are usually made after enough time has passed since the primary examination of the patients.

Our method for estimating information values is to compare the cluster partitions constructed only by one of the forming characteristics (individual partitions) with the proper partition. The smaller difference of these partitions will mean the greater importance of the characteristic under study.

We believe that the characteristics that received greater importance by the method selected will be more important when constructing a prognostic rule. Thus, the set $U$ , together with the proper partition, plays the role of a training sample for constructing rules for classifying objects.

One of the possible ways to implement the plan is a clustering algorithm, the high reliability of the results of which for the data class under study is not in doubt. We assume that if a complete set of forming characteristics is submitted to the entry of the algorithm, then it gives a proper partition U of the set $U$ . It also should be assumed that the algorithm continues to produce some results, if it does not enter the values of the missing characteristics, and not just refuses to produce clustering.

Undoubtedly, skipping the values of some characteristics can strongly change the result. But if the excluded characteristic is sufficiently closely related to the rest, its absence is compensated by the remaining data, and the cluster partition may not even change at all. Here, one must consider a special kind of connection between the characteristics, which differs, for example, from the correlation one, since, most often, the required type of connection is essentially nonlinear. Below, we call this type of relationship a cluster connection. It shows the ability to replace one of the characteristics with another when building clusters.

In addition, the influence of one of the characteristics can be absorbed by the influence of the second, against which the first one simply turns out unimportant. For example, the proximity of the values of the second characteristic means the closeness of the values of the first, but not vice versa. In this situation, we will say that the first characteristic is cluster dominated by the second, and the second is dominant. Cluster dominance means the possibility of replacing the aggregation of the two characteristics with the dominant one in the algorithm. This domination can certainly be considered as one of the forms of cluster connection.

One of the key issues that arise when trying to study cluster connection and the cluster dominance of characteristics is the problem of the location of the interaction of the two characteristics on the same scale with the individual contributions of each of them to clustering. The contribution of the interaction on this scale can be located almost arbitrarily (even to be zero if the characteristics in question act, in some sense, in opposite directions). Therefore, without additional assumptions, it is apparently impossible to achieve any significant progress in solving the problem. Due to this, it was decided to make an additional assumption on the method of operation of the main cluster algorithm.

We will call objects close in the aggregate of characteristics, which can consist of a single characteristic, if using this set of characteristics, the selected cluster algorithm assigns them to the same cluster. Thus, the concept of closeness of objects is determined by the algorithm used. So, by the assumptions made about it, the closeness is defined when using the arbitrary fixed set of their characteristics. If we use the only one characteristic for constructing clusters by the closeness in it, then the resulting cluster partition will be called an individual partition by this characteristic.

Basic Assumption. Objects are close in the aggregate of the characteristics if and only if they are close in each of them separately.

This assumption will be further used only when carrying out rigorous proofs. A qualitative interpretation of the coefficients introduced below is possible even if it is violated, which will be discussed each time.

Figure 1.

The proper and the joint cluster partitions.

The validity of the basic assumption leads to the fact that the introduction of a new characteristic into the main algorithm can lead only to a more detailed clustering. Namely, earlier clusters can only break into smaller ones if the objects contained in them have essentially different values of the new characteristic. Thus, we believe that as the characteristics are introduced into the algorithm, we will generally get smaller clusters, and hence a hierarchy of cluster partitions will arise. Of course, the class of admissible cluster algorithms is thereby greatly reduced, but many practical problems (for example, medical ones or the classification of animals for subspecies in zoology) use just such algorithms.

It is clear also, that if the basic assumption is fulfilled, then instead of the algorithm, which in general is a kind of black box, it can be assumed that all individual cluster partitions by each of the forming characteristics ( $p$ partitions totally) are given. Indeed, according to the basic assumption, the proper partition will be constructed from all possible nonempty intersections of clusters of these $p$ partitions, that is, the proper partition will be uniquely determined by them. Thus, we can replace the necessity of choosing the main cluster algorithm by specifying a set of $p$ individual partitions by each of the forming characteristics.

Of course, the proper partition in some sense can be sufficiently arbitrary, whereas in the performance of the basic assumption of the work, only parallelepiped-like sets with edges parallel to the axes determined by the forming characteristics can be obtained as clusters of the partitioning in all characteristics (joint partition). Figure 1 illustrates this situation for the case of two characteristics. In it, the areas $K_{i},i=1,2,3$ show the proper partition, and the rectangles numbered from 1 to 7 are clusters of joint partition formed according to the basic assumptions.

In most cases, the difference between a proper and a joint partition can be neglected, and assume that this is the same partition. Thus, in Fig. 1, clusters $K_{1}$ and $K_{2}$ were divided into smaller clusters 1, 2, 3 and 4, 5, and 7, respectively, which, for example, in medical interpretation would mean different treatment options for the resulting parts of $K_{1},K_{2}$ , but does not exclude some common procedures for each “large” cluster as a whole. Thus, we simply approach patients more differentially, which, in our opinion, can only improve the quality of treatment. Note that the situation depicted in Fig. 1 is typical for any of the practical interpretations of the problem.

Our main objective is to define the coefficients, using numerical values and properties of which, it is possible to estimate the degree of connection between the characteristics under the proper cluster partition and the possibility of their mutual replacement in the process of constructing the cluster partition. To do this, we introduce the concept of cluster connection and the related concept of cluster dominance of characteristics based on the study of individual cluster partitions.

Introducing the coefficients with the required properties, we will be able to propose a method for ranking the forming characteristics by the degree of their importance in the classification of objects and to estimate the losses when they cannot be used, and so to obtain new ways of solving the post-hoc analysis problem and a problem of reducing dimension of the data.

2. The degree of difference between two cluster partitions

In this section, we consider different separations of the main finite set $U$ into parts without any reference to the influence of the forming characteristics on this process. Therefore, here under the cluster partition of the main set we understand any separation of it into disjoint nonempty parts. More accurately, each cluster partition A is a collection $\{A_{1},\ldots,A_{k}\}$ of subsets of a set $U$ such that none of them is empty, and

$\displaystyle(i\neq j)\Rightarrow A_{i}\cap A_{j}=\emptyset,\bigcup\limits_{j=% 1}^{k}{A_{j}}=U.$

We are going to estimate the degree of the differences between the partitions of the main set. For this, we use the metric $d$ introduced in Dronov and Dementjeva (2012).

To determine the value of $d({\rm{\bf A}},{\rm{\bf B}})$ for a pair of cluster partitions ${\rm{\bf A}},{\rm{\bf B}}$ , note that any $x\in U$ enters only one of the sets in each of these cluster partitions. Denote these sets $A_{x},B_{x}$ respectively. Suppose $|A|$ means the number of elements of a finite set $A$ . Then, by definition,

$\displaystyle d({\rm{\bf A}},{\rm{\bf B}})=\sum\limits_{x\in U}|A_{x}\Delta B_% {x}|,$

where $A\Delta B=(A\cup B)\backslash(A\cap B)$ denotes the symmetric difference of sets $A, B$ .

In Dronov and Dementjeva (2012), another formula is also proposed to calculate this metric, which is often more convenient for applications. Let ${\rm{\bf A}}=\{A_{1},\ldots,A_{k}\}$ , ${\rm{\bf B}}=\{B_{1},\ldots,B_{m}\}$ . Then

$\displaystyle d({\rm{\bf A}},{\rm{\bf B}})=\sum\limits_{i=1}^{k}{\sum\limits_{% j=1}^{m}|}A_{i}\cap B_{j}|\cdot|A_{i}\Delta B_{j}|.$ (1)

We consider a special case, important for further considerations, when one of the two cluster partitions will be smaller than the other. Let ${\rm{\bf A}},{\rm{\bf C}}$ be two cluster partitions of $U$ . We write ${\rm{\bf C}}\subset{\rm{\bf A}}$ if any of the sets that make up C is a subset of some set in A.

Consider two cluster partitions ${\rm{\bf A}},{\rm{\bf B}}.$ We shall use AB as a notation for a cluster partition of the main set $U$ constructed from all nonempty intersections of the elements of ${\rm{\bf A}},{\rm{\bf B}}$ , and call it an intersection of the partitions. If C $=$ AB, then clearly ${\rm{\bf C}}\subset{\rm{\bf A}}$ and ${\rm{\bf C}}\subset{\rm{\bf B}}$ .

Theorem 1. Let A, B be two arbitral cluster partitions of the same set, C $=$ AB. Then

$\displaystyle d({\rm{\bf A}},{\rm{\bf B}})=d({\rm{\bf A}},{\rm{\bf C}})+d({\rm% {\bf C}},{\rm{\bf B}}).$

The assertion of the theorem can be interpreted, for example, as follows. We consider a metric space $\langle{\rm{\bf\Xi}},d\rangle$ whose points are the cluster partitions of the main set. Then the intersection of two cluster partitions is necessarily located on the segment of the straight line connecting the considered cluster partitions.

3. Coefficient of the cluster dominance

Consider two of the forming characteristics – $X$ and $Y$ . The geometric interpretation presented at the end of the previous section allows us to introduce a coefficient describing the degree of influence of one of them on the form of the cluster partition in relation to the other. Let X, Y be individual partitions of the main set by $X, Y$ , respectively, and XY be the intersection of these partitions. We set

$\displaystyle Q_{X,Y}(X)=\begin{cases}{{\displaystyle\frac{d({\rm{\bf Y}},{\rm% {\bf XY}})}{d({\rm{\bf Y}},{\rm{\bf X}})}},}&{d({\rm{\bf Y}},{\rm{\bf X}})\neq 0% .}\\ {1/2,}&{d({\rm{\bf Y}},{\rm{\bf X}})=0.}\\ \end{cases}$ (2)

This coefficient can we call the coefficient of the cluster dominance of the characteristic $X$ over $Y$ . The larger it is, the relatively closer the point XY in the metric space ${\rm{\bf\Xi}}$ will be to the point X, than to Y, on the segment between them. This fact can be interpreted as a greater opportunity for the characteristic $X$ to replace their collection $\{X,Y\}$ than for $Y$ . Obviously, the introduced coefficient can take values from 0 to 1. If $Q_{X,Y}(X)>1/2$ , then we will say that $X$ has greater cluster power than $Y$ .

Figure 2.

Cluster dominance.

If the basic assumption is violated, then the intersection of individual clustered partitions does not have to coincide with the result of the combined action of the two characteristics. In this case, we will mean XY as the cluster partition forming under their combined action. So, the values of the coefficient may cease to lie in $[0,1]$ , and the possibility of its simple interpretation is lost. To correct the situation, it is possible to replace the denominator of the fraction in Eq. (2) by the sum $d({\rm{\bf X}},{\rm{\bf XY}})+d({\rm{\bf XY}},{\rm{\bf Y}})$ . After this, it becomes clear that the introduced coefficient coincides, up to a linear transformation, with the so-called function of a rival similarity (FRiS-function) of individual cluster partitions by $X, Y$ , with respect to their collection $\{X,Y\}$ in ${\rm{\bf\Xi}}$ . This function was introduced in the works of Zagoruiko and his students (for example, Zagoruiko, 2008; Zagoruiko & Kutnenko, 2013) for use in the pattern recognition problem, but was later used in many other tasks, including the reduction of the data dimension.

Now for any cluster partition D let’s denote the sum of the squares of the number of elements of all sets that make up this partition by $sq_{{\rm{\bf D}}}$ . From the definition Eq. (2) it follows that (for details see Lemmas 5 and 6 in the Appendix).

$\displaystyle d({\rm{\bf X}},{\rm{\bf Y}})\neq 0\Rightarrow Q_{X,Y}(X)=\frac{1% }{2}\left({1+\frac{sq_{{\rm{\bf Y}}}-sq_{{\rm{\bf X}}}}{sq_{{\rm{\bf X}}}+sq_{% {\rm{\bf Y}}}-2sq_{{\rm{\bf XY}}}}}\right).$ (3)

Thus, the value of the coefficient of the cluster dominance turns out to be greater than 1/2 if and only if $sq_{{\rm{\bf Y}}}>sq_{{\rm{\bf X}}}$ . Most often it means that the clusters in the partition X have a smaller size than in the cluster partition Y. We note yet another consequence Eq. (3) – if you do not change the sizes (numbers of elements) of clusters in partitions, but only change their composition, then the location of $Q_{X,Y}(X)$ relative to 1/2 cannot be changed. But, for example, if this coefficient is greater than 1/2 ( $X$ has stronger cluster power than $Y$ ), it can be increased by increasing the value of $sq_{{\rm{\bf XY}}}$ , that is, making the clusters intersections larger (see Lemma 1 below).

The analogue of Eq. (2) for the case of rejecting the basic assumption is

$\displaystyle\hat{{Q}}_{X,Y}(X)=\frac{1}{2}\left({1+\frac{d({\rm{\bf X}},{\rm{% \bf XY}})-d({\rm{\bf Y}},{\rm{\bf YX}})}{d({\rm{\bf X}},{\rm{\bf XY}})+d({\rm{% \bf Y}},{\rm{\bf XY}})}}\right)=\frac{1}{2}(1+F),$

where $F$ is the FRiS-function of a similarity X with XY in a competition with Y. This relation precisely defines a linear transformation, which was mentioned earlier.

Note that while defining $Q_{X,Y}(X)$ instead of the individual characteristic $Y$ one can consider the characteristic that is the result of the joint action of all the remaining (except $X$ ) characteristics of the forming suite. We denote this collective characteristic $X^{*},X^{\ast}=\{X_{1},\ldots,X_{p}\}\setminus\{X\}$ . Then the coefficient $Q(X)=Q_{X,X^{\ast}}(X)$ can be called the coefficient of (absolute) cluster strength of $X$ or the coefficient of its cluster dominance. This coefficient shows how much $X$ alone can replace the entire set of forming characteristics.

If $Q(X)\geqslant 1/2$ , then such a characteristic $X$ we call dominant. Drawing the Eq. (3), we see that the necessary and sufficient condition for the dominance of the characteristic $X$ in the case of validity of the basic assumption is

$\displaystyle sq_{{\rm{\bf X}}}\leqslant sq_{{\rm{\bf X}}^{\ast}}.$ (4)

Here, of course, X ${}^{*}$ is a cluster partition constructed by the set of all characteristics except $X$ .

In going from an individual partition by $X$ to a joint by { $X, Y$ }, the value of $d$ will turn out to be less if larger are the clusters that are broken up by $Y$ , so the greater cluster strength $X$ has with respect to $Y$ . Figure 2 shows a joint cluster partition of a set of 9 elements (the rectangles lying to the right of the dotted line are temporarily ignored). $X$ here has a greater cluster strength, and therefore, as always for the case of two characteristics, is dominant ( $Q$ ( $X)=$ 11/20). It is so, because two individual clusters by $X$ (consisted of 5 and 4 elements) have relatively smaller losses in the transition to the joint partition, than individual clusters by $Y$ . When adding an additional cluster of 5 elements by $X$ (dotted line removed), this phenomenon is amplified ( $Q$ ( $X)=$ 7/10).

Suppose that the number of elements of the main set $U$ is equal to $n$ . Now it is clear that we are interested in studying the sum of squares of natural numbers whose sum is equal to a given number $n$ . Let $x, y$ be natural numbers. The elementary inequality $(x+y)^{2}>x^{2}+y^{2}$ immediately leads to the validity of the following assertion.

Lemma 1. Let $x_{1},\ldots,x_{f}$ be natural numbers, sq a sum of their squares. If any $x_{j}$ is divided into two or more natural terms, then the sum of the squares of the new set of numbers turns out to be strictly less than sq, and if two or more of them are replaced by their sum, then their sum of squares will increase strictly.

Lemma 2. Let the natural number $n$ be represented as the sum of a certain number of natural terms: $n=\sum\nolimits_{j=1}^{f}{x_{j}},sq=\sum\nolimits_{j=1}^{f}{x_{j}^{2}}.$ If number of terms in the sums is arbitrary, then the minimal possible value of $s q$ is $n$ , while maximum is $n^{2}$ . If number $f$ of terms is fixed, then

$\displaystyle\underline{sq}(f)=\min sq=n\cdot(2[n/f]+1)+f[n/f]\cdot([n/f]-1),$ $\displaystyle\overline{sq}(f)=\max sq=(n-f+1)^{2}+f-1,$

where [ $a$ ] denotes the integer part of the number $a$ .

Here is an easy consequence of Lemma 1.

Lemma 3. Suppose that the basic assumption holds. Then

$\displaystyle sq_{{\rm{\bf XY}}}\leqslant\min\{sq_{{\rm{\bf X}}},sq_{{\rm{\bf Y% }}}\},$

and the equality is achieved if and only if ${\rm{\bf X}}\subset{\rm{\bf Y}}$ or ${\rm{\bf Y}}\subset{\rm{\bf X}}$ .

Theorem 2. Let the basic assumption be fulfilled. Then

If $X$ is dominant, then for any forming characteristic $Ysq_{{\rm{\bf X}}}\leqslant sq_{{\rm{\bf Y}}}$ . The converse is not always true. For any two dominants $X$ and $Y$ $sq_{{\rm{\bf X}}}=sq_{{\rm{\bf Y}}}$ . This total value is the minimum among all $sq_{{\rm{\bf X}}_{j}},j=1,\ldots,p$ .

If for any characteristic $X$ $Q(X)>1/2$ holds, then $X$ is the only dominant.

The second and third assertions of the Theorem 2 imply

Corollary. If there are at least two dominant characteristics, then for each of them $Q(X)=1/2$ .

4. Cluster connection

Although the possibility for a characteristic $X$ to replace a collection $\{X,Y\}$ in building the partition, or its large relative cluster strength, is a kind of dependence of the characteristics on each other, but this is in some ways a degenerate form of such dependence. To study more subtle types of the connection, we recall that the cluster strength of the characteristic $X$ is determined by the magnitude of $sq_{{\rm{\bf X}}}$ . If you do not change $sq_{{\rm{\bf X}}},sq_{{\rm{\bf Y}}}$ , then the degree of dominance of the stronger of the characteristics $X, Y$ over the other changes along with the change $sq_{{\rm{\bf XY}}}$ – the larger this value, the stronger the dominance. The increase of the $sq_{{\rm{\bf XY}}}$ , considering the assertion of Lemma 1 and the basic assumption, corresponds to the enlargement of individual clusters at the intersection XY. Changes in the number of elements in each of the clusters of individual partitions do not occur. Consequently, a large value of $sq_{{\rm{\bf XY}}}$ corresponds to less changes in the cluster partition, for example, in the individual partition by $Y$ , with the additional influence of $X$ . Notice that $X$ and $Y$ enter in this reasoning equitably, in contrast to the study of the domination of one of them. Thus, it is possible to estimate the strength of the cluster connection between $X$ and $Y$ , using only the value of $sq_{{\rm{\bf XY}}}$ .

Let’s find the largest and smallest of its values. Of course, it is the sum of the squares of natural numbers in the sum giving the number of elements $n$ of the set $U$ , therefore the assertion of Lemma 2 can be used. But the upper bound $n^{2}$ that was found there, cannot be reached in any practically important case. Really, one, and usually both individual cluster partitions in view contain at least two clusters, and hence the intersection cannot consist of one element. The attainable upper bound is established by Lemma 3.

Now we can define a coefficient of the cluster connection between two forming characteristics $X, Y$ :

$\displaystyle L_{1}(X,Y)=\frac{sq_{{\rm{\bf XY}}}-n}{\min\{sq_{{\rm{\bf X}}},% sq_{{\rm{\bf Y}}}\}-n}.$ (5)

This coefficient takes values from 0 to 1, and, the larger it is, the stronger the cluster connection between the characteristics. It is interesting to note that the value $L_{1}(X,Y)=1$ (the strongest connection) corresponds to $Q_{X,Y}(X)=0$ or to $Q_{X,Y}(X)=1$ depending on which of the cluster partitions is smaller.

Figure 3.

Four clusters in the joint partition and the increasing cluster strength.

So, cluster connection between the characteristics we understand as the ability of one of them to replace the other in the process of constructing the proper cluster partition U, and the coefficient $L_{1}$ shows the strength of this connection.

Another specification of the degree of cluster connection between the characteristics is how much the number of clusters $f$ in XY increased with respect to $k, m$ –the numbers of clusters in correspondent individual partitions. The more significant this increase, the less strong one should consider the connection between them. This leads to another coefficient

$\displaystyle L_{2}(X,Y)=L_{2}(k,m,f)=\;\frac{\bar{{f}}(k,m)-f}{\bar{{f}}(k,m)% -{f}(k,m)},$ (6)

where, $\bar{{f}}(k,m),{f}(k,m)$ , respectively, the largest and smallest possible numbers of clusters in the intersection of the individual cluster partitions of $k$ and $m$ clusters. It is clear from Lemma 4 below that the denominator in this definition can turn to 0 only if at least one of the numbers $k, m$ is 1 or $n$ . This case obviously has no practical meaning, but it is possible to put by definition $L_{2}=1$ in this case, considering the dominance arising here.

Lemma 4. If the basic assumption holds, then

$\displaystyle{f}(k,m)=\max\{k,m\},\bar{{f}}(k,m)=\begin{cases}{mk,}&{mk% \leqslant n,}\\ {n,}&{mk>n.}\\ \end{cases}$

Since $\underline{sq}(f)$ defined in Lemma 2 is monotone with a respect to $f$ , then the smallest possible sum of squares $n$ in Eq. (5) can be replaced by $\underline{sq}(\bar{{f}}(k,m))$ . By doing this we will achieve the opportunity for $L_{1}$ to access 0 more often. But, comparing the difficulties of practical application of the new formula with the effect obtained, we believe that Eq. (5) is still preferable.

We note once more that the numerator of the fraction Eq. (5) estimates the closeness of the cluster partition by the interaction of $X, Y$ to the individual cluster partition that is the least distant from it, while in the denominator it is the largest possible such closeness. Using the same considerations, we can suggest estimating the degree of cluster connection in the case of violation of the basic assumption by the value of

$\displaystyle\widehat{L_{1}}(X,Y)\;=\;\frac{\min\{d({\rm{\bf X}},{\rm{\bf XY}}% );d({\rm{\bf Y}},{\rm{\bf XY}})\}}{n(n-1)}.$

In the denominator, here is the maximum possible value of the metric $d$ on the family of all cluster partitions of the set of $n$ elements (see Dronov & Dementjeva, 2012). The definition of the coefficient $L_{2}$ can, in our opinion, be left unchanged. In any case, $L_{2}$ gives a rougher, preliminary estimate of the strength of the cluster connection in comparison with $L_{1}$ , since it considers only the number of clusters, and not their sizes.

Table 1

An example illustrating differences in connection types

[dir=NW]CharacteristicsObjects	1	2	3	4	5	6	7
$X$	1	1	2	2	3	3	3
$Y$	1	1	8	8	2	2	2

Figure 4.

The strongest cluster connection.

Here is some illustration of the concept of the cluster connection. In Fig. 3, there are four clusters in the joint partition XY with numbers of elements $a_{i},\;i=1,\ldots,4$ respectively. Suppose that the numbers of elements $S_{1}^{X},S_{2}^{X},S_{1}^{Y},S_{2}^{Y}$ in the individual partitions not changed. Then cluster connection between $X$ and $Y$ will be all the stronger, the closer to 0 both numbers $a_{1},a_{4}$ (or both numbers $a_{2},a_{3}$ ). The strongest connection between characteristics, therefore, will correspond to such a cluster structure, when each of the characteristics completely determines the joint partitioning into clusters (Fig. 4). Note that, since here both individual partitions coincide with the joint one, then for the case in the Fig. 4 we get $Q$ ( $X$ ) and $Q$ ( $Y$ ) both equal to 1/2 (both characteristics dominate).

Cluster connection, the strength of which is determined by the value of the coefficient $L_{1}$ , is a special kind of statistical connection that does not coincide with the correlation one, since the relations between the values of the characteristics and the structure of the cluster partition are mostly nonlinear. Let, for example, consider a set of 7 objects with the values of the characteristics $X, Y$ given in Table 1. Clearly, here the individual partitions by each of the characteristics coincide, whence $L_{1}(X,Y)=L_{2}(X,Y)=1$ , and the cluster connection between them is extremely strong. But the Pearson’s correlation coefficient between $X$ and $Y$ is 0.03, which means a practical lack of correlation.

Table 2

Clusters in the individual cluster partitions

Patient	$L$	$P$	$F$	$X$	$K$	Patient	$L$	$P$	$F$	$X$	$K$
P01	2	1	2	2	2	P11	2	1	3	2	2
P02	2	1	2	2	2	P12	2	1	2	2	2
P03	2	1	2	1	2	P13	2	1	2	1	2
P04	2	1	2	2	2	P14	2	1	1	2	3
P05	2	1	3	2	2	P15	2	3	2	2	2
P06	2	1	1	2	3	P16	2	3	1	1	3
P07	2	2	1	2	2	P17	2	1	2	2	2
P08	2	2	2	1	1	P18	2	1	2	2	2
P09	2	1	2	2	2	P19	3	1	1	2	3
P10	2	1	2	2	2	P20	2	2	2	2	2

Table 3

Specifications of cluster partitions

Characteristics	$L$	$P$	$F$	$X$	$K$	LP	LF	LX	LK	PF
$f$	2	3	3	2	3	4	4	3	4	7
sq	362	238	222	272	222	210	190	242	214	119
Characteristics	PX	PK	FX	FK	XK	$L*$	$P*$	$F*$	$X*$	$K*$
$f$	6	6	5	6	5	9	9	8	10	10
sq	179	144	130	144	160	86	98	102	96	82

Table 4

Pairwise coefficients $L_{1}$ of the cluster connection

Characteristics	$L$	$P$	$F$	$X$	$K$
$L$	1.000	0.872	0.842	0.881	0.960
$P$		1.000	0.490	0.729	0.614
$F$			1.000	0.545	0.614
$X$				1.000	0.693

5. An example

Consider in this section one practical example. We use the results of examination of 20 patients of Altai medical center. For this example, we take 5 characteristics (the number of leukocytes $L$ , the levels of prolactin $P$ and FSH $F$ , as well as the percentage of T-helper $X$ and T-killers $K$ ). For each of these characteristics, the patients were divided into 3 groups (clusters), depending on whether the content was below the norm, within the normative limits or above the norm. In fact, L and X clusters turned out to be two. The results are shown in Table 2.

Considering the basic assumption fulfilled, we construct all necessary intersections of the partitions corresponding to the interactions, and the correct cluster partition, which considers all the characteristics. The specifications of these partitions are collected in Table 3. In it, $f$ denotes the number of clusters of the partition, sq is the sum of the squares of the number of elements of all clusters making up the partition. In the proper partition U, there appears to be 11 clusters, $sq_{{\rm{\bf U}}}=68$ .

On these data, we estimate the absolute cluster strength of the characteristics. Note that the values of the corresponding coefficients can be used for post-hoc ranking, and their relative magnitude determines the degree of importance of the relevant indicators for classification problems. We get

$\displaystyle Q(L)=0.06;\;Q(P)=0.15;\;Q(F)=0.18;\;Q(X)=0.12;\;Q(K)=0.08.$

Then, using the Eq. (5) we find the coefficients of the cluster connection strength between the forming characteristics. Their values are given in Table 4.

The presence of large coefficients shows a strong connection between the characteristics in the cluster sense, which explains the absence of cluster dominance and small values of the coefficients of absolute cluster strength. If we set the task of reducing the dimension to 2, then the coefficients $L_{1}$ show that $F$ and $P$ should be selected. At the same time, a full-scale post-hoc study using ANOVA reveals $P$ and $L$ as the most important $.$ This indicates the novelty of the proposed method.

It should be noted again that our purpose was to define not the most significant characteristics for clustering, but, on the contrary, to identify those whose absence would not affect too much influence. The characteristic here is $L$ (and the next in impotence is $K$ ).

Let’s finish the example by comparing the distances from U of the cluster partitions A, B, C, the first of which is constructed according to the set of {P, F, X, K} (our proposal), the second one by { $P, F$ } (the proposed reduction of dimension to 2), and the third by { $P, L$ } (classical dimension reduction). Calculations give

$\displaystyle d({\rm{\bf A}},{\rm{\bf U}})=18;\;d({\rm{\bf B}},{\rm{\bf U}})=5% 2;\;\;d({\rm{\bf C}},{\rm{\bf U}})=142.$

6. Discussion and conclusion

The concept of cluster connection introduced in the paper is oriented precisely to an estimation of the degree of interaction between forming characteristics (even not necessarily numerical ones) when constructing a cluster partition of the set of objects under study. Probably, it better corresponds to the very nature of cluster analysis problems than the common statistical types of connections. The concept of cluster dominance allows us to solve the post-hoc problem in a new way, by making the ranking of the forming characteristic by descending the proposed coefficients of their absolute cluster strength.

Excluding those characteristics, the cluster strength of which is not high, we come to one of the variants to reduce the dimensionality of the data. In this case, it is also possible to exclude one of the characteristics of an equal (and sufficiently large) cluster force. To do this, it is possible to use such data analysis procedures as isolating correlation pleiades or constructing a dependency tree of the characteristics (see, for example, Dronov, 2015, 167–169), where the values of the coefficients $L_{1}$ or $L_{2}$ are used as edge weights. Here, $L_{2}$ can be recommended for a quick, prescriptive analysis. The practical example given in the previous section demonstrated the advantage of the described method over the classical approach.

Nevertheless, it should be emphasized that the resulting option of reducing the dimension is rather a by-product of our work. The main task was precisely to decide on the degree of reliability of classification in incomplete information. So our main object was to find not the strongest, but the weakest characteristic in the cluster sense, the loss of which slightly affects the classification of objects.

When deriving formulas in the article, the assumption on the way of construction of the joint cluster partitions which was called the basic assumption, was usually assumed to be true. In fact, it unambiguously allows us to determine the cluster partition by any set of characteristics if individual partitions are known. We admit that dealing with the practical issues of cluster analysis this is not always the case. Nevertheless, for all defined coefficients we have proposed their variants, the possibility of using which does not depend on the validity of the basic assumption. Moreover, according to the authors’ conviction, the Eqs (2), (5) and (6) can be used with some degree of approximation even if the basic assumption is violated. After all, as a rule, the smaller clusters are obtained in clustering, the greater is the classifying force of the corresponding characteristic or the group of them.

The results of the work were partially announced in Dronov and Evdokimov (2017).

Footnotes

Appendix

References

Abdi

(2007). Discriminant correspondence analysis. In: Encyclopedia of measurement and statistics. Thousand Oaks. CA: Sage Publications, 270-275.

Chance

B. L.

, & Rossman

A. J.

(2013). Investigating statistical concepts, applications, and methods. Duxbury Press.

Dronov

S. V.

(2015). Methods and problems in multidimensional statistics. Barnaul: Altai State University Publishing House (in Russian).

Dronov

S. V.

, & Dementjeva

E. A.

(2012). A new approach to post-hoc problem in cluster analysis. Model Assisted Statistics and Applications, 7(1), 49-55.

Dronov

S. V.

, & Evdokimov

E. A.

(2017). On ranking of the characteristics forming the cluster partition, based on the relative similarity coefficients. Prikladnaya Diskretnaya Matematika (Applied Discrete Mathematics), Supplement 10, 160-162 (in Russian).

Keppel

, & Wickens

T. D.

(2004). Design and analysis: A researcher’s handbook, 4rd Edition. Upper Saddle River, NJ: Pearson.

Zagoruiko

N. G.

Borisova

I. A.

Dyubanov

V. V.

, & Kutnenko

O. A.

(2008). Methods of recognition based on the function of rival similarity. Pattern Recognition and Image Analysis, 18(1), 1-6.

Zagoruiko

N. G.

Kutnenko

O. A.

(2013). Censoring of the training sample. Tomsk State University Journal of Control and Computer Science, 1(22), 66-73 (in Russian).

Patient	$L$	$P$	$F$	$X$	$K$	Patient	$L$	$P$	$F$	$X$	$K$
P01	2	1	2	2	2	P11	2	1	3	2	2
P02	2	1	2	2	2	P12	2	1	2	2	2
P03	2	1	2	1	2	P13	2	1	2	1	2
P04	2	1	2	2	2	P14	2	1	1	2	3
P05	2	1	3	2	2	P15	2	3	2	2	2
P06	2	1	1	2	3	P16	2	3	1	1	3
P07	2	2	1	2	2	P17	2	1	2	2	2
P08	2	2	2	1	1	P18	2	1	2	2	2
P09	2	1	2	2	2	P19	3	1	1	2	3
P10	2	1	2	2	2	P20	2	2	2	2	2

Patient	$L$	$P$	$F$	$X$	$K$	Patient	$L$	$P$	$F$	$X$	$K$
P01	2	1	2	2	2	P11	2	1	3	2	2
P02	2	1	2	2	2	P12	2	1	2	2	2
P03	2	1	2	1	2	P13	2	1	2	1	2
P04	2	1	2	2	2	P14	2	1	1	2	3
P05	2	1	3	2	2	P15	2	3	2	2	2
P06	2	1	1	2	3	P16	2	3	1	1	3
P07	2	2	1	2	2	P17	2	1	2	2	2
P08	2	2	2	1	1	P18	2	1	2	2	2
P09	2	1	2	2	2	P19	3	1	1	2	3
P10	2	1	2	2	2	P20	2	2	2	2	2

Patient	$L$	$P$	$F$	$X$	$K$	Patient	$L$	$P$	$F$	$X$	$K$
P01	2	1	2	2	2	P11	2	1	3	2	2
P02	2	1	2	2	2	P12	2	1	2	2	2
P03	2	1	2	1	2	P13	2	1	2	1	2
P04	2	1	2	2	2	P14	2	1	1	2	3
P05	2	1	3	2	2	P15	2	3	2	2	2
P06	2	1	1	2	3	P16	2	3	1	1	3
P07	2	2	1	2	2	P17	2	1	2	2	2
P08	2	2	2	1	1	P18	2	1	2	2	2
P09	2	1	2	2	2	P19	3	1	1	2	3
P10	2	1	2	2	2	P20	2	2	2	2	2