From: "Joachim (München)" <wuttke1@...>
Date: 2008-04-24T00:15:07+09:00
Subject: Re: Grouping results by similar names

Max:

Your second approach is not only more flexible, it has also
the advantage of clearly structuring your problems into
two different steps.

Step 1, defining a similarity_rating: Given the complexity of
your input data, you should start with something as simple
as a count of matching words, and then gradually refine.

As result, step 1 gives you a quadratic, symmetric matrix
that can be treated as if containing covariances.

Step 2, cluster variables according to their covariance matrix:
While there is no unique solution, there are several well
established procdures. Scan books on multivariate data analysis
for "cluster analysis" or similar.

Below, I add some code which I wrote a while ago for my own use -
take it for what it's worth. A result of such a cluster analysis
is shown in http://www.messen-und-deuten.de/pisa/Wuttke2007b.pdf,
page 73.

Good luck, Joachim

# calculate ng*(ng-1)/2 correlation coefficients:
mg = gv.size-1
xcorr = (0..mg).collect{ (0..mg).collect { 0.0 } }
(0..mg).each do |jg|
    print "correlations for #{gv[jg]}:" if verbose
    (0..jg-1).each do |ig|
        xcorr[jg][ig] = calc_xcorr jg, ig, vv, nq
        printf " %4.2f", xcorr[jg][ig]
    end
    print "\n"
end

# determine closest correlation and confound the two owners:
while mg>0
    # determine closest correlation:
    xmin = 0
    imin = nil
    jmin = nil
    (0..mg).each do |jg|
        (0..jg-1).each do |ig|
            if xcorr[jg][ig]>xmin
                xmin = xcorr[jg][ig]; imin = ig; jmin = jg
            end
        end
    end
    printf "%6.4f join #{gv[imin]} and #{gv[jmin]}\n", xmin

    # confound into imin:
    (0..nq-1).each do |kq|
        y0 = vv[imin][kq]
        y1 = vv[jmin][kq]
        vv[imin][kq] =
            if y0<0
                y1
            elsif y1<0
                y0
            else
                (nv[imin]*y0+nv[jmin]*y1)/(nv[imin]+nv[jmin])
            end
    end
    nv[imin] = nv[imin]+nv[jmin]
    gv[imin] = gv[imin]+"&"+gv[jmin]

    # eliminate jmin:
    gv.delete_at jmin
    nv.delete_at jmin
    vv.delete_at jmin
    xcorr.delete_at jmin
    xcorr.each do |xv|
        xv.delete_at jmin
    end

    # recalculate correlations with imin:
    mg -= 1
    ( 0..imin-1).each{ |ig| xcorr[imin][ig] = calc_xcorr imin, ig, vv,
nq }
    (imin+1..mg).each{ |jg| xcorr[jg][imin] = calc_xcorr jg, imin, vv,
nq }
end