Changeset 15052

Timestamp:

07/02/08 20:15:15 (6 months ago)

Author:

ayu

Message:

• added 'furthest neighbor method'
  

Location:

lang/cplusplus/misc/clustercpp

Files:

• include/maxdistupdator.h (added)
• include/ward.h (modified) (2 diffs)
• include/wardupdator.h (modified) (1 diff)
• src/Makefile (modified) (2 diffs)
• src/maxdistupdator.cpp (added)
• src/ward.cpp (modified) (3 diffs)
• src/wardupdator.cpp (modified) (4 diffs)

lang/cplusplus/misc/clustercpp/include/ward.h

@@ -6 +6 @@
 #include <boost/shared_ptr.hpp>
 #include <iostream>
+#include <ctime>
+#include <cstdlib>
+
 
 #include "wardtypes.h"
 #include "wardupdator.h"
+#include "maxdistupdator.h"
 
 
@@ -19 +23 @@
     ~Ward();
 
-    template < class VECTORSTYPE >
+    template < class UPDATOR, class VECTORSTYPE >
     HISTORIES* cluster(VECTORSTYPE* vectors){
-      WardUpdator updator;
+      std::clock_t t1,t2;
+      t1 = std::clock();
+      //WardUpdator updator;
+      //MaxDistUpdator updator;
+      UPDATOR updator;
       History h = updator.create_matrix(vectors);
+      t2 = std::clock();
+      double T1 = static_cast<double>(t2-t1) / CLOCKS_PER_SEC;
+      std::cout << "Time: building_matrix=" << T1 << std::endl;
+
       INDEX size = updator.size();
 

lang/cplusplus/misc/clustercpp/include/wardupdator.h

@@ -17 +17 @@
     History create_matrix(SPARSEVECTORS* vectors);
     inline INDEX size(){  return mat->size()+1; }
+  protected:
+    MATRIX* mat;
+
+    virtual double calc_distance(MATRIXROW* objp, INDEX j, INDEX p, INDEX q, INDEX sqp, INDEX sp, INDEX sq, VALUE mqp);
+    inline VALUE elm(INDEX i, INDEX j){ return (*((*mat)[i]))[j]; }
 
   private:
-    MATRIX* mat;
     std::vector<INDEX> sizes;
     std::set<INDEX> kieta;
+    CACHES* caches;
 
     void initcache();
-
-    virtual double calc_distance(MATRIXROW* objp, INDEX j, INDEX p, INDEX q, INDEX sqp, INDEX sp, INDEX sq, VALUE mqp);
-
-    inline VALUE elm(INDEX i, INDEX j){ 
-      return (*((*mat)[i]))[j];}
-    CACHES* caches;
     inline void savecache(INDEX i, VALUE d, INDEX i1){
       CacheP p = CacheP(new Cache);

lang/cplusplus/misc/clustercpp/src/Makefile

@@ -1 +1 @@
 CXXFLAGS=-O3 -ffast-math -funroll-loops -Wall -fno-common -march=nocona -DBUILDMAIN
-ward: ward.o wardupdator.o
-        g++ $(CXXFLAGS) -o ward -I../include ward.o wardupdator.o
+
+ward: ward.o wardupdator.o maxdistupdator.o
+        g++ $(CXXFLAGS) -o ward -I../include ward.o wardupdator.o maxdistupdator.o
 
 wardupdator.o: wardupdator.cpp
@@ -9 +10 @@
         g++ $(CXXFLAGS) -c -I../include ward.cpp
 
+maxdistupdator.o: maxdistupdator.cpp
+        g++ $(CXXFLAGS) -c -I../include maxdistupdator.cpp
 
 

lang/cplusplus/misc/clustercpp/src/ward.cpp

@@ -11 +11 @@
 #include "ward.h"
 #include "wardupdator.h"
+#include "maxdistupdator.h"
 
 namespace clustercpp{
@@ -37 +38 @@
     ans.push_back(std::string(line, p));
     return ans.size();
+  }
+
+  void printmat(MATRIX* mat){
+    for(MATRIX::iterator i=mat->begin(); i != mat->end(); i++){
+      for(MATRIXROW::iterator j=i->second->begin(); j != i->second->end(); j++){
+        std::cout << "(" << i->first << "," << j->first << ")=" << j->second << ",";
+      }
+      std::cout << std::endl;
+    }
+    std::cout << "--------------------" << std::endl;
   }
 
@@ -108 +119 @@
 
   clustercpp::Ward ward;
-  std::clock_t t1,t2,t3;
-  t1 = std::clock();
+  std::clock_t t2,t3;
   t2 = std::clock();
   //clustercpp::printmat(mat);
-  HISTORIES* hist = ward.cluster(vectors.get());
+  HISTORIES* hist = ward.cluster<clustercpp::MaxDistUpdator>(vectors.get());
   t3 = std::clock();
+  int t = 0;
   for(HISTORIES::iterator it=hist->begin(); it!=hist->end(); it++){
     idlabel.push_back("("+idlabel[it->index1]+"+"+idlabel[it->index2]+")");
-    std::cout << "dist "<< it->index1 << "+" << it->index2 << " / " << it->distance << std::endl; // ")  " << idlabel[idlabel.size()-1] << std::endl;
+    std::cout << t << "  dist "<< it->index1 << "+" << it->index2 << " / " << it->distance << std::endl; // ")  " << idlabel[idlabel.size()-1] << std::endl;
+    t++;
   }
-  double T1 = static_cast<double>(t2-t1) / CLOCKS_PER_SEC;
   double T2 = static_cast<double>(t3-t2) / CLOCKS_PER_SEC;
-  std::cout << "Time: building_matrix=" << T1 << "  clustering=" << T2 << std::endl;
+  std::cout << "Time: clustering=" << T2 << std::endl;
 
   return 0;

lang/cplusplus/misc/clustercpp/src/wardupdator.cpp

@@ -6 +6 @@
 
 namespace clustercpp{
-  void printmat(MATRIX* mat){
-    for(MATRIX::iterator i=mat->begin(); i != mat->end(); i++){
-      for(MATRIXROW::iterator j=i->second->begin(); j != i->second->end(); j++){
-        std::cout << "(" << i->first << "," << j->first << ")=" << j->second << ",";
-      }
-      std::cout << std::endl;
-    }
-    std::cout << "--------------------" << std::endl;
-  }
-
   WardUpdator::WardUpdator(): sizes(), kieta(){
     caches = new CACHES;
@@ -81 +71 @@
       mat->insert(MATRIX::value_type(i, p));
       SPARSEVECTOR::iterator e2 = v.end();
+      double vsum = 0.0;
+      for(SPARSEVECTOR::iterator it0=v.begin();it0!=v.end();it0++){
+        vsum += (it0->second) * (it0->second);
+      }
+
       for(INDEX j=0; j<i; j++){
         SPARSEVECTOR& u = (*sparsevectors)[j];  
         //ベクトル間のユークリッド距離を計算
-        double pp = 0.0;
+        double pp = vsum;
         SPARSEVECTOR::iterator e = u.end();
         for(SPARSEVECTOR::iterator it=u.begin();it!=e;it++){
           SPARSEVECTOR::iterator it2 = v.find(it->first);
+          double x = it->second;
+          pp += x*x;
           if(it2!=e2){
-            VALUE x = (it2->second)-(it->second);
-            pp += x*x;
+            pp += -2*x*(it2->second);
           }
         }
@@ -136 +132 @@
 
       double tmpdist = calc_distance(objp, j, p, q, sqp, sp, sq, mqp);
-      /*
-      double tmpdist;
-      if(j < p){ //TODO ここをobjpの参照先を書き換えるのでなく、リストにして返す or ローカルに保存しっぱなしでどうか。。。
-        tmpdist = (*objp)[j] = ((sp+sizes[j])*elm(p,j)+(sq+sizes[j])*elm(q,j)-sizes[j]*mqp)/(sqp+sizes[j]);
-      }else if(p<j && j<q){
-        tmpdist = (*objp)[j] = ((sp+sizes[j])*elm(j,p)+(sq+sizes[j])*elm(q,j)-sizes[j]*mqp)/(sqp+sizes[j]);
-        (*mat)[j]->erase(p);  //今後使わなくなる成分の消去
-      }else{
-        tmpdist = (*objp)[j] =((sp+sizes[j])*elm(j,p)+(sq+sizes[j])*elm(j,q)-sizes[j]*mqp)/(sqp+sizes[j]);        
-        (*mat)[j]->erase(p); //今後使わなくなる成分の消去
-        (*mat)[j]->erase(q); //今後使わなくなる成分の消去
-      } 
-      */        
       
       //今の所最小距離のものを一時記憶
@@ -191 +174 @@
   double WardUpdator::calc_distance(MATRIXROW* objp, INDEX j, INDEX p, INDEX q, INDEX sqp, INDEX sp, INDEX sq, VALUE mqp){
       double tmpdist;
+      INDEX sizes_j = sizes[j];
       if(j < p){ //TODO ここをobjpの参照先を書き換えるのでなく、リストにして返す or ローカルに保存しっぱなしでどうか。。。
-        tmpdist = (*objp)[j] = ((sp+sizes[j])*elm(p,j)+(sq+sizes[j])*elm(q,j)-sizes[j]*mqp)/(sqp+sizes[j]);
+        return (*objp)[j] = ((sp+sizes_j)*elm(p,j)+(sq+sizes_j)*elm(q,j)-sizes_j*mqp)/(sqp+sizes_j);
       }else if(p<j && j<q){
-        tmpdist = (*objp)[j] = ((sp+sizes[j])*elm(j,p)+(sq+sizes[j])*elm(q,j)-sizes[j]*mqp)/(sqp+sizes[j]);
+        tmpdist = ((sp+sizes_j)*elm(j,p)+(sq+sizes_j)*elm(q,j)-sizes_j*mqp)/(sqp+sizes_j);
         (*mat)[j]->erase(p);  //今後使わなくなる成分の消去
       }else{
-        tmpdist = (*objp)[j] =((sp+sizes[j])*elm(j,p)+(sq+sizes[j])*elm(j,q)-sizes[j]*mqp)/(sqp+sizes[j]);        
+        tmpdist = ((sp+sizes_j)*elm(j,p)+(sq+sizes_j)*elm(j,q)-sizes_j*mqp)/(sqp+sizes_j);        
         (*mat)[j]->erase(p); //今後使わなくなる成分の消去
         (*mat)[j]->erase(q); //今後使わなくなる成分の消去
       }         
-      return tmpdist;
+      return (*objp)[j] = tmpdist;
   }
 }