/**
*
* Affinity propagation for symmetric matrix data
*
*/
package medusa.georgios.ClusteringAlgorithms;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Vector;
public class Affinity_Propagation
{
double RAND_MAX = 0x7fffffff;
private float lamda=0.5f;
private int number_iterations = 50;
public int number_of_exemplars=0;
private float infinite=1000000000;
private Hashtable GiveNameGetIndex = new Hashtable();
private Hashtable GiveIndexGetName = new Hashtable();
private ArrayList IndexesOfExamplars = new ArrayList();
public ArrayList NamesOfExamplars = new ArrayList();
public ArrayList ClusterList = new ArrayList();
public Hashtable GiveNodeIndex_getClusterThatThis_node_belongs_to = new Hashtable();
public Hashtable GiveNodeName_getClusterThatThis_node_belongs_to = new Hashtable();
//public static ArrayList ColorList_For_Clustering=new ArrayList();
private List2Graph g;
public int getNumberOfClusters()
{
return number_of_exemplars;
}
public ArrayList getIndexesOfExamplars()
{
return IndexesOfExamplars;
}
public ArrayList getNamesOfExamplars()
{
return NamesOfExamplars;
}
public ArrayList getClusterList()
{
return ClusterList;
}
// public Affinity_Propagation_Cluster GiveNodeIndex_getClusterThatThis_node_belongs_to(int index)
// {
// return ClusterList.get(GiveNodeIndex_getClusterThatThis_node_belongs_to.get(index));
// }
public Affinity_Propagation(String filename)
{
StringBuffer input = new StringBuffer();
String thisLine;
try{
FileInputStream fin = new FileInputStream(filename);
BufferedReader myInput = new BufferedReader(new InputStreamReader(fin));
while ((thisLine = myInput.readLine()) != null) {
input.append(thisLine+"\n");
}
} catch (Exception e) {
e.printStackTrace();
}
g = new List2Graph(filename);
g.print_matrix_f();
run_Affinity_Propagation(input);
}
public Affinity_Propagation(ArrayList list)
{
StringBuffer input = new StringBuffer();
String thisLine;
for (int i = 0; i < list.size(); i++)
input.append(list.get(i)+"\n");
g = new List2Graph(list);
//g.print_matrix_f();
run_Affinity_Propagation(input);
}
public Affinity_Propagation(StringBuffer input) {
run_Affinity_Propagation(input);
}
public void run_Affinity_Propagation(StringBuffer input) {
int flag, dn, it, conv, decit, maxits, convits;
double RAND_MAX = 0x7fffffff;
////////////////////////////////////////////////////////////////////
String input_string=input.toString();
String str[] = input_string.split("\n");
int counter=0;
int number_of_nodes;
ArrayList unique_nodes = new ArrayList();
for (int i = 0; i < str.length; i++)
{
String str1[] = str[i].split("\t");
if(unique_nodes.contains(str1[0])==false)
{
unique_nodes.add(str1[0]);
GiveNameGetIndex.put(str1[0],counter);
GiveIndexGetName.put(counter,str1[0]);
counter++;
}
if(unique_nodes.contains(str1[1])==false)
{
unique_nodes.add(str1[1]);
GiveNameGetIndex.put(str1[1],counter);
GiveIndexGetName.put(counter,str1[1]);
counter++;
}
}
number_of_nodes=unique_nodes.size();
//System.out.println("number_of_nodes = " + number_of_nodes);
double[][] S=new double[number_of_nodes][number_of_nodes];
double[][] A=new double[number_of_nodes][number_of_nodes];
double[][] R=new double[number_of_nodes][number_of_nodes];
for (int i = 0; i < A.length; i++)
{
for (int j = 0; j < A.length; j++)
{
A[i][j]=0;
R[i][j]=0;
S[i][j]=0;
}
}
for (int i = 0; i < str.length; i++)
{
String str1[] = str[i].split("\t");
int x=GiveNameGetIndex.get(str1[0]);
int y=GiveNameGetIndex.get(str1[1]);
// System.out.println("x,y="+x+","+y);
S[x][y]=S[y][x]=Double.parseDouble(str1[2]);
}
for (int i = 0; i < S.length; i++)
for (int j = 0; j < S.length; j++) {
S[i][j]=S[i][j]+(float)(((1e-16)*S[i][j]+Float.MIN_VALUE*100)*(Math.random()/(RAND_MAX+1)));
}
My_Matrix Availabilities = new My_Matrix(A);
My_Matrix Similarities = new My_Matrix(S);
My_Matrix Responsibilities = new My_Matrix(R);
// System.out.println(" Similarities My_Matrix =");
// Similarities.show();
// Availabilities.show();
// Responsibilities.show();
/**************************ITERATION*******************************/
for(int iteration = 1 ; iteration < number_iterations ; iteration++)
{
// Compute responsibilities
if(iteration%100==0)
System.out.println("iteration:"+iteration+"/"+number_iterations);
My_Matrix AS = Similarities.plus(Availabilities);
My_Matrix ROld= My_Matrix.copyMatrix(Responsibilities);
double[] max_values = new double[number_of_nodes];
int[] index_of_max_values = new int[number_of_nodes];
for (int i = 0; i < number_of_nodes; i++)
{max_values[i]=index_of_max_values[i]=0;}
for (int i = 0; i < number_of_nodes; i++)
{
double maximum=-1000000;
int position=-1;
for (int j = 0; j < number_of_nodes; j++)
{
if(AS.get_element(i,j)>maximum)
{
maximum=AS.get_element(i,j);
position=j;
}
}
max_values[i]=maximum;
index_of_max_values[i]=position;
}
//for (int i = 0; i < number_of_nodes; i++)
// System.out.println(max_values[i]+"\t\t"+index_of_max_values[i]);
//printf("%f\t\t5f\n",max_values[i],index_of_max_values[i]);
for (int i = 0; i < number_of_nodes; i++)
AS.set_element(-1*infinite,i,index_of_max_values[i]);
double[] max_values2 = new double[number_of_nodes];
int[] index_of_max_values2 = new int[number_of_nodes];
for (int i = 0; i < number_of_nodes; i++)
{max_values2[i]=index_of_max_values2[i]=0;}
for (int i = 0; i < number_of_nodes; i++)
{
double maximum=-1000000;
int position=-1;
for (int j = 0; j < number_of_nodes; j++)
{
if(AS.get_element(i,j)>maximum)
{
maximum=AS.get_element(i,j);
position=j;
}
}
max_values2[i]=maximum;
index_of_max_values2[i]=position;
}
for (int i = 0; i < number_of_nodes; i++)
{
for (int j = 0; j < number_of_nodes; j++)
{
double value=Similarities.get_element(i,j)-max_values[i];
Responsibilities.set_element(value,i,j);
}
}
for (int i = 0; i < number_of_nodes; i++)
{
double val=Similarities.get_element(i,index_of_max_values[i])-max_values2[i];
Responsibilities.set_element(val,i,index_of_max_values[i]);
}
for (int i = 0; i < number_of_nodes; i++)
{
for (int j = 0; j < number_of_nodes; j++)
{
double val=(1-lamda)*Responsibilities.get_element(i,j)+lamda*ROld.get_element(i,j);
Responsibilities.set_element(val,i,j);
}
}
// Compute availabilities
My_Matrix AOld= My_Matrix.copyMatrix(Availabilities);
double[][] R_positive_values = new double[number_of_nodes][number_of_nodes];
for (int i = 0; i < number_of_nodes; i++)
{
for (int j = 0; j < number_of_nodes; j++)
{
if(Responsibilities.get_element(i,j)>=0)
R_positive_values[i][j]=Responsibilities.get_element(i,j);
else
R_positive_values[i][j]=0;
}
}
for (int i = 0; i < number_of_nodes; i++)
R_positive_values[i][i]=Responsibilities.get_element(i,i);
double[] sum_matrix = new double[number_of_nodes];
for (int i = 0; i < number_of_nodes; i++)
{
double sum=0;
for (int j = 0; j < number_of_nodes; j++)
{
sum+=R_positive_values[j][i];
}
sum_matrix[i]=sum;
}
for (int i = 0; i < number_of_nodes; i++)
{
for (int j = 0; j < number_of_nodes; j++)
{
double value=sum_matrix[i]-R_positive_values[j][i];
Availabilities.set_element(value,j,i);
}
}
double[] diag_matrix = new double[number_of_nodes];
for (int i = 0; i < number_of_nodes; i++)
diag_matrix[i]=Availabilities.get_element(i,i);
for (int i = 0; i < number_of_nodes; i++)
for (int j = 0; j < number_of_nodes; j++)
if(Availabilities.get_element(i,j)>=0)
Availabilities.set_element(0,i,j);
for (int i = 0; i < number_of_nodes; i++)
Availabilities.set_element(diag_matrix[i],i,i);
for (int i = 0; i < number_of_nodes; i++)
{
for (int j = 0; j < number_of_nodes; j++)
{
double val=(1-lamda)*Availabilities.get_element(i,j)+lamda*AOld.get_element(i,j);
Availabilities.set_element(val,i,j);
}
}
// System.out.println(" Availabilities My_Matrix =");
/**********************ITERATIONS***************************/
}
// Calculate Pseudomarginals
My_Matrix E = new My_Matrix(number_of_nodes,number_of_nodes);
for (int i = 0; i < number_of_nodes; i++)
for (int j = 0; j < number_of_nodes; j++)
E.set_element(Responsibilities.get_element(i,j) + Availabilities.get_element(i,j),i,j);
// System.out.println(" * * * Results: --------------");
// System.out.println(" E My_Matrix =");
//E.show();
// save the indices of the lines whose diagonal element > 0
// Table pos_diag_idx[i] has 0 if the corresponding diag element <= 0
// else pos_diag_idx[i] = i
Vector pos_diag_idx = new Vector();
for (int i = 0; i < number_of_nodes; i++)
if(E.get_element(i,i) > 0)
pos_diag_idx.add(Integer.valueOf(i));
number_of_exemplars = pos_diag_idx.size();
if(number_of_exemplars==0){
number_of_exemplars=1;
pos_diag_idx.add(Integer.valueOf(0));
}
// System.out.println(" --> Number of Exemplars = " + number_of_exemplars);
// System.out.println(" --> List of Exemplars : ");
int cluster_counter=0;
for (int i = 0; i < number_of_exemplars; i++)
{
IndexesOfExamplars.add(pos_diag_idx.get(i));
NamesOfExamplars.add(GiveIndexGetName.get(pos_diag_idx.get(i)));
Affinity_Propagation_Cluster cluster = new Affinity_Propagation_Cluster();
cluster.index_of_the_exemplar_of_this_cluster=pos_diag_idx.get(i);
cluster.name_of_the_exemplar_of_this_cluster=GiveIndexGetName.get(pos_diag_idx.get(i));
ClusterList.add(cluster);
// System.out.println(" -" + i + "- Node { " + pos_diag_idx.get(i) + " }");
cluster_counter++;
}
My_Matrix exemplar_cols = new My_Matrix(number_of_nodes,number_of_exemplars);
for (int i = 0; i < number_of_nodes; i++)
for (int j = 0; j < number_of_exemplars; j++)
exemplar_cols.set_element(Similarities.get_element(i,pos_diag_idx.get(j)), i,j);
// exemplar_cols.show();
double[] tmp = new double[number_of_nodes];
int[] c = new int[number_of_nodes];
for (int i = 0; i < number_of_nodes; i++)
{
double maximum=-1000000;
int position=-1;
for (int j = 0; j < number_of_exemplars; j++)
{
if(exemplar_cols.get_element(i,j)>maximum)
{
maximum=exemplar_cols.get_element(i,j);
position=j;
}
}
tmp[i]=maximum;
c[i]=position;
}
// for (int i = 0; i < number_of_nodes; i++)
// System.out.println("tmp = " + tmp[i] + " c = " + c[i]);
for (int i = 0; i < pos_diag_idx.size(); i++)
c[pos_diag_idx.get(i)] = i;
int[] idx = new int[number_of_nodes];
for (int i = 0; i < number_of_nodes; i++)
{
idx[i] = pos_diag_idx.get(c[i]);
// System.out.println(idx[i] );
}
// System.out.println(" --- CLUSTERING ---");
ArrayList unique = new ArrayList();
for (int i = 0; i < number_of_nodes; i++) {
if (unique.contains(idx[i])==false)
unique.add(idx[i]);
}
Hashtable indices = new Hashtable();
for (int i = 0; i< unique.size(); i++) {
indices.put(unique.get(i),i);
}
for (int i = 0; i < number_of_nodes; i++) {
int cluster_id=indices.get(idx[i]);
ClusterList.get(cluster_id).cluster_id=cluster_id;
ClusterList.get(cluster_id).Indexes_Of_Nodes_In_the_cluster.add(i);
ClusterList.get(cluster_id).Names_Of_Nodes_In_the_cluster.add(GiveIndexGetName.get(i));
GiveNodeIndex_getClusterThatThis_node_belongs_to.put(i,ClusterList.get(cluster_id));
GiveNodeName_getClusterThatThis_node_belongs_to.put(GiveIndexGetName.get(i),ClusterList.get(cluster_id));
}
for (int i = 0; i < this.getNumberOfClusters(); i++)
this.ClusterList.get(i).number_of_elements=this.ClusterList.get(i).Indexes_Of_Nodes_In_the_cluster.size();
}
public static void main(String[] args)
{ Affinity_Propagation clustering = new Affinity_Propagation("C:\\Documents and Settings\\Georgios\\Desktop\\test5.txt");
System.out.println("Number of clusters="+clustering.getNumberOfClusters());
clustering.Save_To_File("Affinity_Propagation.txt");
}
public String getReport()
{
StringBuffer str = new StringBuffer();
for (int i = 0; i < this.getNumberOfClusters(); i++) {
str.append("\n"+this.ClusterList.get(i).showInformation_about_cluster());
//System.out.println("\n"+this.ClusterList.get(i).showInformation_about_cluster());
}
return str.toString();
}
public String Save_To_File(String filename)
{
try {
StringBuffer str = new StringBuffer();
System.out.println("General Information");
for (int i = 0; i < this.getNumberOfClusters(); i++) {
str.append("\n"+this.ClusterList.get(i).showInformation_about_cluster());
//System.out.println("\n"+this.ClusterList.get(i).showInformation_about_cluster());
}
BufferedWriter outp = new BufferedWriter(new FileWriter(filename));
outp.append(str.toString());
outp.close();
return str.toString();
} catch (IOException e) {}
return null;
}
}
Ads help maintain this website.