From: Mikael Brockman <mikael@...>
Date: 2004-10-10T04:36:06+09:00
Subject: Re: Unofficial quiz: Here's an algorithmic question for you

Hal Fulton <hal9000@hypermetrics.com> writes:

> This is actually related to an interesting problem given to me in college
> by one of my professors.
> 
> I'm thinking of digging out that disk and resurrecting the problem as a
> quiz. So I won't go into detail on it here.
> 
> The original problem:
>    - 100 text fragments come from four different sources.
>    - There are 25 from each source.
>    - They're now scrambled.
>    - The sources are not labeled or named as such (their order
>      does not matter).
>    - Do whatever textual or statistical analysis you deem appropriate,
>      and separate them into four buckets, approximating their original
>      buckets as well as you can.
> 
> The question I'm asking here is related only to the evalution of the
> quality of a given result:
> 
> Given four bins e,f,g,h (the results of our guesswork) and given
> the four original bins a,b,c,d -- evaluate how well we did.
> 
> For simplicity, assume these bins are just arrays of integers.
> 
> Note that:
>    - each bin has exactly 25 items
>    - the union of a,b,c,d is 0..99
>    - the union of e,f,g,h is also 0..99
>    - there is no special correspondence between a and e,
>      b and f, etc.
> 
> So my real questions are:
> 
> 1. How would you solve the problem of evaluating the correctness
>     of the partitioning? This would have to be "fuzzy" in some
>     sense, of course -- maybe a Float answer between 0 and 1.
> 2. And the meta-question: Is the "correctness" ambiguous? I think
>     not, but I haven't examined it thoroughly.
> 
> 
> Cheers,
> Hal

You may find http://arxiv.org/abs/cs.SD/0303025 interesting:

>> We present a fully automatic method for music classification, based
>> only on compression of strings that represent the music pieces. The
>> method uses no background knowledge about music whatsoever: it is
>> completely general and can, without change, be used in different
>> areas like linguistic classification and genomics. It is based on an
>> ideal theory of the information content in individual objects
>> (Kolmogorov complexity), information distance, and a universal
>> similarity metric. Experiments show that the method distinguishes
>> reasonably well between various musical genres and can even cluster
>> pieces by composer.