The theoretical distribution of the Goodman-Kruskal statistic (abstract only)

ABSTRACT

The Goodman-Kruskal &ggr; statistic is one of the internal criteria used in evaluating how good a hierarchical structure is, and it measures the global fit of the hierarchy imposed by the single link or complete link clustering method on the proximity matrix of ordinal data. This statistic ranks the correlation between proximity ranks and cophenetic (partition) ranks, and is defined as &ggr; = (Sc-sd)/(Sc+Sd), where Sc is the number of the concordant parts and Sd is the number of discordant parts between the proximity matrix and the cophenetic matrix entries. Hubert (1974), using Monte Carlo analysis with 1000 Monte Carlo runs, derived the approximate distributions of &ggr; for single and complete link with the number of features ranging from four to sixteen. The goal of this paper is to establish an appropriate null hypothesis Ho and find the theoretical distribution of &ggr; under Ho. The data are assumed to be on ordinal scale. Given a dissimilarity matrix break the ties by changing tied entries to entry+e,e small. Obtain the proximity matrix by rank order. If size of dissimilarity matrix is n by n then the derived proximity matrix is symmetric with no ties and consisting of the integers 1 to n(n-1)/2 above the diagonal. Given that the number features is n there are (n(n-1) /2) 1 such proximity matrices-as many as permutations of n(n-1) /2 integers. The null hypothesis adopted is that all proximity matrices are equally likely. The &ggr; distribution is discrete and the determination of the distribution of the &ggr; statistic depends on variables n and the hierarchical method used (in our case we use S.L). For n=8, we used Monte Carlo analysis and the resulting distribution was very close to the one derived by Hubert (see Figure 2 for the cumulative distributions and Fig. 1 for the &ggr; distribution). Based on our Monte Carlo analysis for n=8, we derive the threshold 0.6776 at the 0.05 level. I.e., if &ggr; > 0.6776 then we conclude that the fit imposed by the clustering is good. See Figure 2 for the cumulative distribution of &ggr; for n=8. By the central limit theorem we argue that as n approaches infinity the distribution gets closer and closer to normal. This observation agrees with Hubert's (1), where he empirically derived the formula E(&ggr;) = 1.1 log(n) /n and var(&ggr;) = I/n. Thus n&ggr; -1.1 log (n) is approximately N(0,1)n. For n=4,5 the exact theoretical distributions are derived, the means and variances evaluated and compared to Hubert's results. The means tend to agree but there is a big difference in the exact variance and the approximate one. For example, for n = 4 the exact variance is 0.045, while Hubert reports one of 0.13. We finally present a general algorithm for finding the exact distribution of gamma for any given n, and are currently in the process of implementing it.

REFERENCES

• 1: L. Hubert, Approximate evaluation techniques for the S.L and C.L hierarchial clustering, J.~..Statis.Ass. 69,698-704 (1974).
• 2: Baker, Stability of two hierarchial grouping techniques,. J.Am. Statist. Ass. 69, 440-~45 ( 197~_. ) .

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Design, Performance, Theory