I've been trying to implement Affinity Propagation in Java for the past week. I did exactly as the original paper by frey and dueck describes yet I do not get good exemplars.
The research paper can be found here: http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf
Here is the code I wrote for the similarity function (clustering sentences from the research paper.)
public static void calculateSimilarity(){
try{
for(int i=0; i<tweets.size(); i++){//For each tweet
for(int j=0; j<tweets.size(); j++){//and the one next to it, split both into tokens
String[]firstTokens=tweets.get(i).toLowerCase().split(" ");
String[]secondTokens=tweets.get(j).toLowerCase().split(" ");//tokenize it
//store summed cost in respective matrix.
if(i==j){//calculate self similarity{
similarity[i][j]=firstTokens.length*NEGATIVE_LOG_OF_DICTIONARY+ADJUSTMENT_FACTOR;
System.out.println(similarity[i][j]);
}
else{
//The costC per word. These will be summed
double Cost=compare(firstTokens, secondTokens);//compare
similarity[i][j]=Cost;//assign the similarity
}
}//end inner for
}//end outer for
}//end try
catch(Exception e){
System.out.println(temp);
e.printStackTrace();
}//end catch
}//end method
public static double compare(String[]firstString,String[]secondString){
double Cost=0;
for(int k=0; k<firstString.length; k++){//for first tweet tokens
for(int l=0; l<secondString.length;l++){//compare to second tweet tokens
//Look at words that are greater than 2 characters
if(firstString[k].length()>=5 &&secondString[l].length()>=5){
if(firstString[k].contains(secondString[l])){
//increment the cost
Cost+=-Math.log10(secondString.length);
}
else//Cost of the word if no word is similar
{
Cost+=NEGATIVE_LOG_OF_DICTIONARY;
}
}//end big if
}//end l for loop
}//end inner inner for
return Cost;
}
And here is how they say they calculated similarity between two data points (sentences): The similarity of sentence i to sentence k was set to the negative sum of the information-theoretic costs (S5) of encoding every word in sentence i using the words in sentence k and a dictionary of all words in the manuscript. For each word in sentence i, if the word matched a word in sentence k, the coding cost for the word was set to the neg- ative logarithm of the number of words in sentence k (the cost of coding the index of the 5 matched word), and otherwise it was set to the negative logarithm of the number of words in the manuscript dictionary (the cost of coding the index of the word in the manuscript dictionary). A word was considered to match another word if either word was a substring of the other.
I also wrote the availability and responsibility function.
AVAILABILITY: public static double updateAvalibility(int datapoint, int candidate,double[][] a, double[][] r,double aOld){ double availibity; //ArrayListtemp=new ArrayList(); double total=0;
//*For self availibility
if(datapoint==candidate){
for(int j=0; j<tweets.size(); j++){
if(j==datapoint)
continue;
else if(r[j][candidate]<0)//skip negative terms
continue;
else
total+=(r[j][candidate]);//sum up r of rows
}//end for
availibity=total;//The total becjomes the A
System.out.println("Availibility :"+availibity);
}//end if
else{//else
for(int j=0; j<tweets.size(); j++){
if(j==candidate||j==datapoint)
continue;
else if(r[j][candidate]<0)//skip negative terms
continue;
else
total+=r[j][candidate];//else sum all R of all rows
}//end for
availibity=(r[candidate][candidate]+total);//A is set to self R + the sum
if(availibity<0)//if not positive ignore
availibity=0;
}//end else
return (1-LAM)*availibity+(LAM*aOld);//Return with Adjustment factor
}
RESPONSIBILITY:
//updates responsibility. Takes the two competeing datapoints, s, r, and a
//returns the responsibility of i to k
public static double updateResponsibility(int datapoint, int candidate, double[][] s, double[][] a,double rOld){
double responsibility;
//A temporary array
ArrayList<Double>temp=new ArrayList<Double>();
double max;//The max of the a(i,k')+r(i,k')
//################################
//SETTING THE SELF RESPONSIBILITY
if(datapoint==candidate){
for(int k=0;k<tweets.size(); k++){
if(k==candidate)
continue;
else
temp.add(s[datapoint][k]);//store all the similarites b/w this point
//others
}
max=Collections.max(temp);//The max of the similarity
responsibility=(similarity[datapoint][candidate])-max;
System.out.println("s:"+similarity[datapoint][candidate]+"- m:"+max+"= responsibility: "+responsibility);
}
else{
for(int j=0; j<tweets.size();j++){
//store the A + S
if(j==candidate)
continue;
else
temp.add(a[datapoint][j]+s[datapoint][j]);// a(i,k')+r(i,k') Max will be calculated later
}//end inner for
//Max of the a+r of other k's.
max=Collections.max(temp);//Then get the max
responsibility=s[datapoint][candidate]-max;//then the similarity - the max
}//end else
return ((1-LAM)*responsibility)-(LAM*rOld);//Dampen responsibility and return
}//end method
Why do I get crappy exemplars even when I use the adjutment factors listed in the paper? What am I doing wrong?
Any help would be greatly appreciated.
