A Comparison of the Euclidean Distance Metric to a Similarity Metric based on Kolmogorov Complexity in Music Classi?cation
Eric Thul
December18,2006
Abstract
This work1studies music classi?cation using the1-Nearest Neighbor rule comparing the Eu-clidean distance metric to an information distance metric based on Kolmogorov Complexity.The
reason for this comparison is two-fold.First,to understand the music classi?cation task and how
similarity measures play a role.Secondly,to contribute to the knowledge regarding e?ective simi-
larity measures by validating previous work.Here we are testing the hypothesis that the Euclidean
distance metric will out-perform a similarity metric based on Kolmogorov Complexity.
1Note that all relevant materials of this project are available at http://www.cs.mcgill.ca/~ethul/pub/course/comp652/
1Introduction
Inherent to the?eld of machine learning and pattern recognition is the task of classi?cation.Objects that retain common properties and features have some degree of similarity and are typically in the same class.Music is one domain where classi?cation is becoming a prevelant research area.The motivation for music classi?cation can be seen in many ways.For example,consider the growing popularity of personalized online radio stations.Examples of these are Pandora[15]and LastFM[6].The main idea behind these online tools is to allow a user to input an artist,song,etc...and then retrieve a playlist of “similar”music.
This is precisely where classi?cation?ts in.In order to gather a collection of songs which are termed as similar,there must be some form of comparison or classi?cation of songs into de?ned categories(classes). By using techniques from machine learning and pattern recognition,we can work towards the goal of a classi?cation system which can automate the process of grouping similar peices of music.Currently,there is no unbeatable“best”approach.As there are many unexplored paths which may lead to successful music classi?cation.
1.1Problem
The topic2of this paper is an exploration of music classi?cation using the1-Nearest Neighbor rule, comparing two measures of similarity.The?rst measure is the Euclidean distance metric and the second measure is an information distance metric based on Kolmogorov Complexity.Original use of Kolmogorov Complexity for melodic similarity can be found in a papers by Rudi Cilibrasi et al[4]and also Ming Li and Ronan Sleep[8].The work by Cilibrasi et al uses the quartet method for hierarchical cluster whereas Li and Sleep use the nearest neighbor approach.The work here further investigates how Kolmogorov Complexity can be used in music classi?cation following more closely the approach by Li and Sleep. The question under investigation is:How does an information distance metric based on Kolmogorov Complexity perform against the Euclidean distance metric in the task of music classi?cation using the 1-Nearest Neighbor rule?We ask this question to understand how distance can be applied to music classi?cation so that we will further learn about the e?ectiveness of these metrics in music classi?cation. Moreover,the comparison of the Euclidean distance metric to an information distance metric based on Kolmogorov Complexity provides an extension and veri?cation to the work done in the previously men-tioned[4,8]papers.However,distinct in this work is the direct comparison of Kolmogorov Complexity to the Euclidean distance metric.
1.2Goals
This leads to the two main goals of this work.
1.To gain an understanding of music classi?cation using the1-Nearest neighbor rule.
2.To provide a comparison between the Euclidean distance metric and an information distance metric
based on Kolmogorov Complexity in the context of music classi?cation.
From the goals,the hypothesis being tested is:The Euclidean distance metric is a more e?ective similar-ity measure than an information distance based on Kolmogorov Complexity in music classi?cation using the1-Nearest Neighbor rule.
2I want to cite The Craft of Research[3]which is an excellent source for how to write a research paper.
2Background
The necessary background to test the hypothesis stated above involves the two distance metrics used. First we will consider the de?nition of a distance metric.Second we will see how a measure of distance can be formulated between two objects.We can then use these metrics to arrive at a measure of similarity between musical pieces.
2.1Metrics
Let us?rst consider the de?nition of a metric.A metric is a function that is characterized by certain properties,and act upon points in a metric space[1,19].The?rst property which must be satis?ed is translation invariance.This means that if two points are translated together,then the distance between them remains the same.The second property is symmetry,which is that the distance from point a to point b is the same as the distance from point b to point a.The third property is the triangle inequality: given three points a,b,and c,we have that the distance from a to c is less than or equal to the distance from a to b plus the distance from b to c.Finally,the last property is that any distance is zero if and only if point a is equal to point b,otherwise the distance is positive.[1,19].Below we de?ne two metrics which both satisfy these properties.
2.1.1The Euclidean Distance Metric
The Euclidean distance metric has been shown to satisfy the properties of a metric[1,Chapter6.1]. Recall the Euclidean distance metric to be the following for any two points p=(p1,p2)and q=(q1,q2) in the two-dimensional plane.
d(p,q)=[(p1?q1)2+(p2?q2)2]12(1) For our purposes however,we will use a d-dimensional version of this metric.Let our distance function d for any two points p and q in a d-dimensional space be the following[19,p.1].
d( p, q)= d
i=1
|p i?q i|2
12
(2)
2.1.2An Information Distance Metric Based on Kolmogorov Complexity
The information distance based on Kolmogorov Complexity requires a bit more explanation.We must ?rst introduce two de?nitions.First,the Kolmogorov Complexity,denoted K(x),is the smallest program which outputs x,where x is a?nite binary string[9,7].Second,the Conditional Kolmogorov Complexity, denoted K(x|y),is the smallest program which regenerates x from y where x,y are?nite binary strings [9,7,8,4].This means that if x and y share a lot of information,we can use the information from y to regenerate x.Hence we only need to store a little bit of x,which leads to a smaller program size. From these de?nitions,the following information distance is provided where an information distance is the smallest program to regenerate x from y and y from x,taking x and y to be binary strings[7].
E(x,y)=max{K(y|x),K(x|y)}(3) However,we want to use a normalized information distance.This is because if E(x,y)=E(z,w)and the binary strings x and y are longer than z and w,then we want to say that x and y share more information.
A normalized form of equation3is provided[7,8,4].
d(x,y)=max{K(x|y),K(y|x)}
max{K(x),K(y)}
(4)
The reason that we are using a normalized information distance also follows from the work of Cilibrasi et al[4]and also Li and Sleep[8].This allows us to make a comparison to the results of each work. Moreover,since here we are considering music classi?cation,the sequences used for x and y will not all be the same length.Thus,a normalized distance is appropriate for our input.
Now,in order to compute equation4we need to estimate values for K(x),K(x|y),and K(y|x).This is because Kolmolgorov Complexity is a theoretical lower bound which cannot be computed[9].Thus,we can approximate the values using compression[9,7,8,4].Here,we di?er in the compression algorithm used by Cilibrasi et al[4],and Li and Sleep[8].We use the freely available compression utility gzip [10],where Cilibrasi et al used the bzip2compression utility,and Li and Sleep used LZ77and LZ78 [8].However,this should not cause much of a di?erence compared to Li and Sleep,since gzip uses LZ77compression.Though,it should be noted that the compression of bzip2uses a di?erent scheme[4] compared to LZ77,which may cause di?erences in results when considering Cilibrasi et al.
We can now estimate K(x)by running gzip on a?le containing the binary string x and getting the compressed?le size.However,we still need to estimate the conditional Kolmolgorov Complexity.This can be written in terms of K(x)an K(y)as follows[7],where xy is the concatenation of x and y.
K(x|y)=K(xy)?K(y)(5)
K(y|x)=K(yx)?K(x)(6) Finally let us de?ne the normalized information distance metric[7,2]as the following,where the function N(·)is the compression estimate.
d(x,y)=max{N(xy)?N(y),N(yx)?N(x)}
max{N(x),N(y)}
(7)
3Methodology
The method chosen to employ the distance metrics of equation2and equation7was the1-Nearest Neighbor classi?cation rule[19,17].This is a non-parametric,instance-based learning technique which does not require training.Examples are stored and then tested against.Three classes were chosen in our approach.The?rst class was Classic Rock,the second class was Mixed Jazz,and the third class was Western Classical.
3.1Data Collection
The data collected for experimentation consisted of MIDI?les collected from the Internet.The main reason for choosing to use the MIDI format is two-fold.First,the work by Cilibrasi et al[4]and Li and Sleep[8]also used the MIDI format.Thus,for the comparison this work uses the same format.Secondly, there were several[11,5,20]freely available MIDI processing tools to choose from,making the feature extraction easier.
In total,1500MIDI samples were collected.Each of the classes contained roughly500samples each.The Classic Rock category contained various artists mainly from the1970s.However,there were instances of newer and older artists.The Mixed Jazz category contained artists ranging from the swing era of the early1940s to contemporary jazz music.This o?ers a wide range of styles that are present in jazz music. The Western Classical category contains music mostly from the more popular composers of western tradition.This includes Bach,Beethovan,Mozart,Tchaikovsky,Chopin,et al.
Upon gathering the MIDI?les,validity was taking into consideration.However,since an exhaustive check of all the MIDI?les was not practical,I randomly checked MIDI?les from each category.Even though the sampling proved valid,it should be noted that this does not guarentee high quality sequencing. For example,sequencing a MIDI?le by hand can yield di?erent notation than real-time sequencing
through a music keyboard.Thus,this should be taken as a note when considering the results of the experimentation.
3.2Pre-Processing
Following the work of Li and Sleep[8],the only pre-processesing necessary,consisted of extracting the melody contour from each of the MIDI?les.The following describes the procedure used.We will de?ne the melodic contour by this procedure.
A MIDI?le is composed of one or more tracks.In each track there is a sequence of events.Such events include note on,note o?,etc.The melodic contour was extracted by processing through each event in each track.If a note on event was encountered,then the pitch value was captured along with the time value of the event occurrence.If a di?erent track contained a note on event which had the same time value as a note already captured,then the higher note value was stored.This procedure follows Li and Sleep[8]and extracts the contour of the highest notes for each time value in the MIDI.
These contours are used in the experimentation with the Kolmogorov Complexity metric.The Euclidean distance metric did not require pre-processing of the midi?les;however,the following describes the process of extracting the feature vectors used in the experimentation.
3.3Feature Extraction
Among the choices of tools which can be used for feature extraction of MIDI?les,I chose the Bodhidharma software developed by Cory McKay at McGill University,Montreal,Quebec Canada[12,11].Note that this software can also be used for classi?cation;however,I strictly used it for feature extraction.
The input to the software is a MIDI formatted?le and the output is an XML document containing the list of features with their corresponding values.The software o?ers100one dimensional features and11 multi-dimensional features.I chose to extract all of the features.I gave all of my MIDI?les(separately for each class)as input and then extracted111features using Bodhidharma for each of the MIDI?les in each class.This gave me three XML?les(one for each class)of all of the features for each MIDI.
4Experimentation
There were two main experiments conducted in this work.Each of the experiments had the following common setup.The classi?cation technique used was the1-Nearest Neighbor rule.The data used was the1500songs divided into three categories:Classic Rock,Mixed Jazz,and Western Classical.There was no training except the storing of training examples.The testing phase done used k-fold cross validation [14]for values of k={2,3,4,5,6,7,8,9,10}.For each value of k in each experiment,the k-fold cross validation was repeated one-thousand times to?nd the variance.
The di?erences in the two experiments were the measure of distance in the1-Nearest Neighbor rule and the feature(s)used with that measure.In the?rst experiment,I used the Euclidean distance metric as seen from equation2.Also,I used a subset(described in§4.1and§4.2)of the111extracted features, where the features were then normalized.These normalized feature vectors were used for caculating the distance in the1-Nearest Neighbor rule for this experiment using the Euclidean distance metric.
In the second experiment,the information distance metric based on Kolmogorov Complexity as seen from equation7was used.Also,the only feature used to calculate the Kolmogorov Complexity was the melodic contour.Since we are using MIDIs,the pitch values extracted are in a range of[0,127].In each MIDI,the contour is composed of a sequence of pitch values.I converted each pitch value to a padded binary value of8-bits and then concatenated these values together to get a binary string representing
the contour of that MIDI.A distance lookup was stored and used in the 1-Nearest Neighbor rule for this experiment using the normalized information distance metric in equation 7and gzip .
4.1Feature Testing
For the ?rst experiment,we have a large feature space of over 111dimensions.This is because of the 111features,11are multi-dimensional.I wanted to reduce this feature space.Right away,I removed features which pertained to instrumentation.I chose not to use them because of possible consistency issues.The person sequencing a MIDI chooses the channel (instrument)to use for a track.For example,one could use a piano to play a guitar part.I found cases like this di?cult to track down,so I decided not to include information about instrumentation in the feature space.
This reduced the number of features to 91.With these remaining features,I decided to use a bottom-up approach to construct the feature vectors.I tested each feature individually using one run of 10-fold cross validation of the 1-Nearest Neighbor rule with the Euclidean distance metric.Consider the following graphs which show the overall success rate along with the success rates for each class.Note that a mapping of feature ID to the feature can be seen in table 1in appendix A.
0.3 0.35
0.4
0.45
0.5 0.55
0.6
10
20
30
40 50 60
70
80
90
S u c c e s s R a t e
Feature ID
Feature Performance Overall using the Euclidean Distance with 10-fold Cross Validation in 1-NN 0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 10 20 30
40 50 60 70 80 90
S u c c e s s R a t e
Feature ID
Feature Performance of Classic Rock using the Euclidean Distance with 10-fold Cross Validation in 1-NN Figure 1:The image on the left shows the overall success of each feature.The image on the right shows the success for each feature in the Classic Rock category.
0 0.1 0.2 0.3
0.4 0.5 0.6 0
10
20
30
40 50 60
70
80
90
S u c c e s s R a t e
Feature ID
Feature Performance of Mixed Jazz using the Euclidean Distance with 10-fold Cross Validation in 1-NN
0.1
0.2
0.3
0.4
0.5
0.6
0 10 20 30
40 50 60 70 80 90
S u c c e s s R a t e
Feature ID
Feature Performance of Western Classical using the Euclidean Distance with 10-fold Cross Validation in 1-NN
Figure 2:The image on the left shows the success of each feature in the Mixed Jazz category.The image on the right shows the success for each feature in the Western Classical category.
4.2Feature Set Testing
With information on how each feature performs,I then began with a bottom-up approach[16]to?nd a small set of features to use for the feature vectors.I chose sets where the features performed well and ones where the features gave moderate performance,in search of a synergistic e?ect.Out of all of the sets I tested,the following graphs depict the performance of the top15feature sets.Note that a mapping of feature set ID to the feature set can be seen in table2in appendix A.
shows the success for each feature set in the Classic Rock category.
image on the right shows the success for each feature set in the Western Classical category.
From the sets above,feature set4was chosen.The following features were in set4and used as the feature vectors for the experiment with the Euclidean distance metric.
1.Note Density:The average number of notes per second[12].Considering the three classes,this
feature performed well in distinguishing between songs in the Mixed Jazz category and also the Western Classical category.
https://www.doczj.com/doc/3d12627626.html,bined Strength of Two Strongest Rhythmic Pulses:The sum of the two rhythmic pulses which
occur most frequently[12].This can be thought of in the following way.Consider two people,each with a drum.Person A hits her drum every second for the whole song of5minutes.Person B hits
his drum three times per second,but only does this for1minute before he gets tired and stops to sing for4minutes.From this scenario,we can derive a beat histogram.If we do this,we will see that the bin for beat A will be much more frequent and beat B will be less frequent.This feature represents the sum of the two peaks in the beat histogram.In the system,an autocorrelation function is used to calculate the beat histogram values[12].
3.Strength of Strongest Rhythmic Pulse:Instead of adding the two peaks,just take the highest peak
in the beat histogram.The reason I chose this feature aside from the individual performance was because an overlap of features helped to balance the performance of the Mixed Jazz class among the other two classes.
4.Importance of High Register:The fraction of notes in a MIDI which have a pitch value between
73and127[12].Overall,this was the highest performing individual feature,so I included it in the ?nal feature vector.
5Results
The following shows the best result from the cross validations.Below we have the results for the success rate(with variance)using10-fold cross validation for both the Euclidean metric and the Kolmogorov metric.Note that the other graphs for k=2,3,4,5,6,7,8,9can be found in appendix B.
5.1Euclidean Metric
Performance of 1-NN using the Euclidean Distance with 10-fold Cross Validation
are shown for10-fold cross validation.Note that this is the graph after one-thousand runs.
In the?gure above,the overall performance is0.53409.And the variance is quite small.Also,note that the success rate in each class is fairly even.This indicates that the features selected average similar performance for each class when tested together.
5.2Kolmogorov Complexity Metric
S u c c e s s R a t e w i t h V a r i a n c e
Figure 6:are shown for 10-fold cross validation.Note that this is the graph after one-thousand runs.
In the ?gure above,the overall performance is 0.53499.And the variance is also quite small.One observation on the result is that the success rate of the Classic Rock class nearly reaches 0.8,whereas the the performance of the other two classes are almost half of that.
6Conclusions
Based on the results,let’s draw some conclusions.First,it may seem a bit surprising that the overall success of the information distance metric based on Kolmogorov Complexity outperformed the Euclidean distance metric.This disproved the hypothesis.However,the two success rates were very close.Di?ering by only 0.001or so.
Second,even though this comparison came out close,the success rates seem rather poor.However,when taking into consideration other results of music classi?cation of MIDI ?les,the results here are comparable.One summary of seven di?erent approaches using various techniques to classify MIDIs into genre is provided [18].Here,the average success rate is 0.69429,with the lowest being 0.49and the highest being 0.84[18].Moreover,from MIREX 2005[13],results of MIDI classi?cation are on average 0.64344for hierarchicical clustering with the higest being 0.771and lowest at 0.3776.And for overall raw classi?cation we have on average 0.51874success rate with the highest being 0.6528and lowest 0.2652[13].
With this said,music classi?cation is a di?cult task.However,the above cited results used a larger number of categories than what was used here,so the statistics were presented to give an idea of some of the current successes in the ?eld.By no means is this an exhaustive summary.
6.1Comparison to Related Work
Let us now consider the results achieved here with respect to the work by Li and Sleep[8]and also by Cilibrasi et al[4].The result shown by Li and Sleep which is comparable to the work here is a0.859 success rate using1-Nearest Neighbor.However,these results are not directly comparable since their data set was di?erent.Their dataset is not publically available.Still,some conclusions can be drawn. Since the work here followed the same procedure(according to how it was described[8])and obtained lower results,it seems that the method relies on the dataset.Li and Sleep note that since they had unbalanced classes,data-set evenness should be taken into account with their results[8].However,I am unsure if this unbalance can account for the0.32di?erence in success rate.However,here we used a dataset twice the size and also balanced among the classes.Furthermore,since MIDI data on the web varies drastically,there is a chance the speci?c samples played a role.
Let us now brie?y consider the work done by Cilibrasi et al[4].The reason this is considered brie?y is because they use a di?erent learning method than the work here,and also had a signi?cantly smaller data set(84samples).However,they retained a success rate in the range of[0.84,0.95]using subsets of their data[4].
6.2Future Work
In retrospect to these results and conclusions,one avenue of interest may be to investigate why the two similarity measures applied here perform at an overall success rate that is almost identical.However, the Euclidean distance seemed to show more of an even success rate among the classes.Whereas the Kolmogorov similarity metric very much favored the Classic Rock class.
Also,trying to improve the classi?cation when using the Euclidean distance metric would be bene?cial. Perhaps testing this approach on a smaller,hand-crafted data set would be a good baseline for compar-ison.Since the MIDI?les gathered from the Internet come with no guarentees.Furthermore,testing with a di?erent feature extraction tool would be an interesting route to take,since there is usually a chance for improvement in the features.
Overall,the current results obtained are fair on the average for music classi?cation of MIDI?les and the comparison of the Euclidean distance metric to a similarity metric based on Kolmogorov Complexity proved to be an interesting test as the goals of this work have been achieved.
A Tables
Table1:Table mapping feature ID to the feature
ID Feature
0Maximum Number of Independent Voices
1Average Number of Independent Voices
2Variability of Number of Independent Voices
3Voice Equality-Number of Notes
4Voice Equality-Note Duration
5Voice Equality-Dynamics
6Voice Equality-Melodic Leaps
7Voice Equality-Range
8Importance of Loudest Voice
9Relative Range of Loudest Voice
10Range of Highest Line
11Relative Note Density of Highest Line
12Melodic Intervals in Lowest Line
13Voice Separation
14Strongest Rhythmic Pulse
15Second Strongest Rhythmic Pulse
16Harmonicity of Two Strongest Rhythmic Pulses
17Strength of Strongest Rhythmic Pulse
18Strength of Second Strongest Rhythmic Pulse
19Strength Ratio of Two Strongest Rhythmic Pulses
20Combined Strength of Two Strongest Rhythmic Pulses
21Number of Strong Pulses
22Number of Moderate Pulses
23Number of Relatively Strong Pulses
24Rhythmic Looseness
25Polyrhythms
26Rhythmic Variability
27Beat Histogram
28Average Note Duration
29Variability of Note Duration
30Maximum Note Duration
31Minimum Note Duration
32Staccato Incidence
33Average Time Between Attacks
34Variability of Time Between Attacks
35Average Time Between Attacks For Each Voice
36Average Variability of Time Between Attacks For Each Voice
37Initial Tempo
38Initial Time Signature
39Compound Or Simple Meter
40Triple Meter
41Quintuple Meter
42Changes of Meter
43Overall Dynamic Range
44Variation of Dynamics
45Variation of Dynamics In Each Voice
46Average Note To Note Dynamics Change
47Most Common Pitch Prevalence
48Most Common Pitch Class Prevalence
49Relative Strength of Top Pitches
Table1:Table mapping feature ID to the feature
ID Feature
50Relative Strength of Top Pitch Classes
51Interval Between Strongest Pitches
52Interval Between Strongest Pitch Classes
53Number of Common Pitches
54Pitch Variety
55Pitch Class Variety
56Range
57Most Common Pitch
58Primary Register
59Importance of Bass Register
60Importance of Middle Register
61Importance of High Register
62Most Common Pitch Class
63Dominant Spread
64Strong Tonal Centres
65Basic Pitch Histogram
66Fifths Pitch Histogram
67Quality
68Glissando Prevalence
69Average Range of Glissandos
70Vibrato Prevalence
71Melodic Interval Histogram
72Most Common Melodic Interval
73Distance Between Most Common Melodic Intervals
74Most Common Melodic Interval Prevalence
75Relative Strength of Most Common Intervals
76Number of Common Melodic Intervals
77Amount of Arpeggiation
78Repeated Notes
79Chromatic Motion
80Stepwise Motion
81Melodic Thirds
82Melodic Fifths
83Melodic Tritones
84Melodic Octaves
85Direction of Motion
86Duration of Melodic Arcs
87Size of Melodic Arcs
88Average Melodic Interval
89Note Density
90Pitch Class Distribution
Table2:Table mapping feature set ID to the feature set
ID Feature Set
0Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Variability of Time Between Attacks,Average Note To Note Dynamics Change,Relative Note Density of Highest Line,Distance Between Most Common Melodic Intervals,Chromatic Mo-tion,Amount of Arpeggiation,Importance of High Register,Most Common Pitch Class Prevalence 1Variability of Number of Independent Voices,Note Density,Chromatic Motion,Amount of Arpeg-giation,Importance of High Register
Table2:Table mapping feature set ID to the feature set
ID Feature Set
2Note Density,Chromatic Motion,Amount of Arpeggiation,Combined Strength of Two Strongest Rhythmic Pulses
3Note Density,Combined Strength of Two Strongest Rhythmic Pulses
4Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Importance of High Register
5Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Importance of High Register,Variability of Number of Independent Voices,Average Number of Independent Voices,Voice Equality-Range,Variability of Time Between Attacks,Av-erage Note To Note Dynamics Change,Relative Note Density of Highest Line
6Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Importance of High Register,Variability of Number of Independent Voices,Average Num-ber of Independent Voices,Voice Equality-Range,Variability of Time Between Attacks,Average Note To Note Dynamics Change,Relative Note Density of Highest Line,Amount of Arpeggiation, Chromatic Motion
7Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Importance of High Register,Amount of Arpeggiation,Chromatic Motion
8Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Importance of High Register,Variability of Number of Independent Voices,Average Number of Independent Voices,Voice Equality-Range,Variability of Time Between Attacks,Aver-age Note To Note Dynamics Change,Relative Note Density of Highest Line,Distance Between Most Common Melodic Intervals,Number of Common Melodic Intervals,Number of Relatively Strong Pulses,Maximum Number of Independent Voices,Chromatic Motion,Amount of Arpeggiation, Importance of High Register
9Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Variability of Time Between Attacks,Average Note To Note Dynamics Change,Relative Note Density of Highest Line,Distance Between Most Common Melodic Intervals,Number of Com-mon Melodic Intervals,Number of Relatively Strong Pulses,Maximum Number of Independent Voices,Chromatic Motion,Amount of Arpeggiation,Importance of High Register
10Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Variability of Time Between Attacks,Average Note To Note Dynamics Change,Relative Note Density of Highest Line,Distance Between Most Common Melodic Intervals,Number of Com-mon Melodic Intervals,Number of Relatively Strong Pulses,Maximum Number of Independent Voices,Chromatic Motion,Amount of Arpeggiation,Importance of High Register,Most Common Pitch Class Prevalence
11Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Variability of Time Between Attacks,Average Note To Note Dynamics Change,Relative Note Density of Highest Line,Distance Between Most Common Melodic Intervals,Number of Rel-atively Strong Pulses,Maximum Number of Independent Voices,Chromatic Motion,Amount of Arpeggiation,Importance of High Register,Most Common Pitch Class Prevalence
12Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Variability of Time Between Attacks,Average Note To Note Dynamics Change,Rela-tive Note Density of Highest Line,Distance Between Most Common Melodic Intervals,Maximum Number of Independent Voices,Chromatic Motion,Amount of Arpeggiation,Importance of High Register,Most Common Pitch Class Prevalence
13Note Density,Combined Strength of Two Strongest Rhythmic Pulses,Strength of Strongest Rhyth-mic Pulse,Variability of Time Between Attacks,Average Note To Note Dynamics Change,Relative Note Density of Highest Line,Distance Between Most Common Melodic Intervals,Chromatic Mo-tion,Amount of Arpeggiation,Importance of High Register,Most Common Pitch Class Prevalence, Variation of Dynamics
14Fifths Pitch Histogram,Chromatic Motion,Note Density,Variation of Dynamics
B Figures
are shown for2-fold cross validation.Note that this is the graph after one-thousand runs.The left is the Euclidean metric and the right is the Kolmogorov Complexity metric
are shown for3-fold cross validation.Note that this is the graph after one-thousand runs.The left is the Euclidean metric and the right is the Kolmogorov Complexity metric
are shown for4-fold cross validation.Note that this is the graph after one-thousand runs.The left is the Euclidean metric and the right is the Kolmogorov Complexity metric
are shown for5-fold cross validation.Note that this is the graph after one-thousand runs.The left is the Euclidean metric and the right is the Kolmogorov Complexity metric
are shown for6-fold cross validation.Note that this is the graph after one-thousand runs.The left is the Euclidean metric and the right is the Kolmogorov Complexity metric
are shown for7-fold cross validation.Note that this is the graph after one-thousand runs.The left is the Euclidean metric and the right is the Kolmogorov Complexity metric
are shown for8-fold cross validation.Note that this is the graph after one-thousand runs.The left is the Euclidean metric and the right is the Kolmogorov Complexity metric
are shown for9-fold cross validation.Note that this is the graph after one-thousand runs.The left is the Euclidean metric and the right is the Kolmogorov Complexity metric
References
[1]Edwin F.Beckenbach and Richard Bellman.An Introduction to Inequalities.Mathematical Associ-
ation of America(MAA),1975.
[2]Charles H.Bennett,Peter Gacs,Ming Li,Paul M.B.Vitanyi,and Wojciech https://www.doczj.com/doc/3d12627626.html,rmation
distance.In IEEE Transactions on Information Theory,volume44NO.4,pages1407–1423,1998.
[3]Wayne C.Booth,Gregory G.Colomb,and Joseph M.Williams.The Craft of Research.The
University of Chicago Press,1995.
[4]Rudi Cilibrasi,Paul Vitanyi,and Ronald de Wolf.Algorithmic clustering of music based on string
compression.In Computer Music Journal,volume Vol.28No.4,pages49–67,Winter2004.
[5]Tuomas Eerola and Petri Toiviainen.Midi toolbox:Matlab tools for music research.Available at
http://www.jyu.fi/musica/miditoolbox/,2004.
[6]https://www.doczj.com/doc/3d12627626.html,stfm.https://www.doczj.com/doc/3d12627626.html,st.fm/.
[7]Ming Li,Xin Chen,Xin Li,Bin Ma,and Paul M.B.Vitanyi.The similarity metric.In14th
ACM-SIAM Symposium on Descrete Algorithms,2003.
[8]Ming Li and Ronan Sleep.Melody classi?cation using a similarity metric based on kolmogorov
complexity.In Conference on Sound and Music Computing SMC’04,pages126–129.IRCAM,2004.
[9]Ming Li and Paul Vitanyi.An Introduction to Kolmogorov Complexity and Its Applications Second
Edition.Spring-Verlag,Inc.,1997.
[10]Jean loup Gailly and Mark Adler.gzip.https://www.doczj.com/doc/3d12627626.html,/.
[11]C.McKay and I.Fujinaga.The bodhidharma system and the results of the mirex2005symbolic
genre classi?cation contest.In International Conference on Music Information Retrieval,2005. [12]Cory McKay.Automatic genre classi?cation of MIDI recordings.M.a.thesis,McGill University,
2004.
[13]MIREX.2005mirex contest results-symbolic genre classi?cation.https://www.doczj.com/doc/3d12627626.html,/
evaluation/mirex-results/sym-genre/index.html.
[14]Tom M.Mitchell.Machine Learning.WCB/McGraw-Hill,1997.
[15]Pandora.Pandora.https://www.doczj.com/doc/3d12627626.html,/.
[16]P.Pudil,J.Novovicova,and J.Kittler.Floating search methods in feature selection.In Pattern
Recognition Letters,volume15,pages1119–1125,1993.
[17]David G.Stork Richard O.Duda,Peter E.Hart.Pattern Classi?cation Second Edition.John Wiley
and Sons,Inc,2001.
[18]Adi Ruppin and Hezy Yeshurun.Midi music genre classi?cation by invariant features.In Interna-
tional Conference on Music Information Retrieval,2006.
[19]Gregory Shkhnarovich,Piotr Indyk,and Trevor Darrell.Nearest Neighbor Methods in Learning and
Vision.MIT Press,2005.
[20]Andrew Sorensen and Andrew Brown.jmusic.Available at https://www.doczj.com/doc/3d12627626.html,.au/,1998.