LibOPF/0000775000175000017500000000000012351344261011672 5ustar afalcaoafalcaoLibOPF/include/0000775000175000017500000000000012345417450013321 5ustar afalcaoafalcaoLibOPF/include/util/0000775000175000017500000000000014624105561014275 5ustar afalcaoafalcaoLibOPF/include/util/common.h0000664000175000017500000000271214624105561015740 0ustar afalcaoafalcao#ifndef _COMMON_H_ #define _COMMON_H_ #include #include #include #include #include #include /* Error messages */ #define MSG1 "Cannot allocate memory space" #define MSG2 "Cannot open file" #define MSG3 "Invalid option" /* Common data types */ typedef struct timeval timer; /* Common definitions */ #define PI 3.1415926536 #define INTERIOR 0 #define EXTERIOR 1 #define BOTH 2 #define WHITE 0 #define GRAY 1 #define BLACK 2 #define NIL -1 #define INCREASING 1 #define DECREASING 0 #define Epsilon 1E-05 /* Common operations */ #ifndef MAX #define MAX(x,y) (((x) > (y))?(x):(y)) #endif #ifndef MIN #define MIN(x,y) (((x) < (y))?(x):(y)) #endif int *AllocIntArray(int n); /* It allocates 1D array of n integers */ float *AllocFloatArray(int n); /* It allocates 1D array of n floats */ void Error(char *msg,char *func); /* It prints error message and exits the program. */ void Warning(char *msg,char *func); /* It prints warning message and leaves the routine. */ inline void Change(int *a, int *b); /* It changes content between a and b */ int RandomInteger (int low, int high);/* Generates a random number within [low,high]. http://www.ime.usp.br/~pf/algoritmos/aulas/random.html */ #endif LibOPF/include/util/subgraph.h0000664000175000017500000000435512345206420016262 0ustar afalcaoafalcao#ifndef _SUBGRAPH_H_ #define _SUBGRAPH_H_ #include "common.h" #include "set.h" /*--------- Data types ----------------------------- */ typedef struct _snode { float pathval; //path value float dens; //node density float radius; // maximum distance among the k-nearest neighbors in // the training set. It is used to propagate // clustering labels to testing nodes) int label; //node label int root; //root node int pred; //predecessor node int truelabel; //true label if it is known int position; //index in the feature space float *feat; //feature vector char status; //0 - nothing, 1 - prototype char relevant; //0 - irrelevant, 1 - relevant int nplatadj; //holds the amount of adjacent nodes on plateaus //It is used to optimize opf_BestkMinCut //because a knn graph need only be built //for kmax, but the opf_PDF and opf_NormalizedCut computation //need only be done for the current k, //or until k+nplatadj is reached. Set *adj; //adjacency list for knn graphs } SNode; typedef struct _subgraph { SNode *node; //nodes of the image/scene subgraph int nnodes; //number of nodes int nfeats; //number of features int bestk; //number of adjacent nodes int nlabels; //number of clusters float df; //radius in the feature space for density computation float mindens; //minimum density value float maxdens; //maximum density value float K; //Constant for opf_PDF computation int *ordered_list_of_nodes; // Store the list of nodes in the increasing order of cost for speeding up supervised classification. } Subgraph; /*----------- Constructor and destructor ------------------------*/ Subgraph *CreateSubgraph(int nnodes); //Allocates nodes without features void DestroySubgraph(Subgraph **sg); //Deallocates memory for subgraph void WriteSubgraph(Subgraph *g, char *file); //write subgraph to disk Subgraph *ReadSubgraph(char *file);//read subgraph from opf format file Subgraph *CopySubgraph(Subgraph *g);//Copy subgraph (does not copy Arcs) void CopySNode(SNode *dest, SNode *src, int nfeats); //Copy nodes void SwapSNode(SNode *a, SNode *b); //Swap nodes #endif // _SUBGRAPH_H_ LibOPF/include/util/sgctree.h0000664000175000017500000000220512345206420016073 0ustar afalcaoafalcao#ifndef _SGCTREE_H_ #define _SGCTREE_H_ #include "gqueue.h" #include "set.h" #include "subgraph.h" // ---- Component tree for built from Subgraph ------------ typedef struct _sgctnode { int level; /* gray level */ int comp; /* representative pixel of this node */ int dad; /* dad node in the maxtree */ int *son; /* son nodes in the maxtree */ int numsons; /* number of sons in the maxtree */ int size; /* number of pixels of the node */ } SgCTNode; typedef struct _sgctree { SgCTNode *node; /* nodes of the mtree */ int *cmap; /* component map */ int root; /* root node of the mtree */ int numnodes; /* number of nodes of the maxtree */ } SgCTree; SgCTree *CreateSgMaxTree(Subgraph *g); void DestroySgCTree(SgCTree **ctree); int SgAncestor(int *dad, int *cmap, int rq); int SgRepresentative(int *cmap, int p); void SgCumSize(SgCTree *ctree, int i); int *SgAreaOpen(Subgraph *g, int thres); int SgAreaLevel(SgCTree *ctree, int *level, int i, int thres); int *SgVolumeOpen(Subgraph *g, int thres); int SgVolumeLevel(SgCTree *ctree, int *level, int i, int thres, int cumvol); #endif LibOPF/include/util/common.h~0000664000175000017500000000270314623124361016134 0ustar afalcaoafalcao#ifndef _COMMON_H_ #define _COMMON_H_ #include #include #include #include #include #include /* Error messages */ #define MSG1 "Cannot allocate memory space" #define MSG2 "Cannot open file" #define MSG3 "Invalid option" /* Common data types */ typedef struct timeval timer; /* Common definitions */ #define PI 3.1415926536 #define INTERIOR 0 #define EXTERIOR 1 #define BOTH 2 #define WHITE 0 #define GRAY 1 #define BLACK 2 #define NIL -1 #define INCREASING 1 #define DECREASING 0 #define Epsilon 1E-05 /* Common operations */ #ifndef MAX #define MAX(x,y) (((x) > (y))?(x):(y)) #endif #ifndef MIN #define MIN(x,y) (((x) < (y))?(x):(y)) #endif int *AllocIntArray(int n); /* It allocates 1D array of n integers */ float *AllocFloatArray(int n); /* It allocates 1D array of n floats */ void Error(char *msg,char *func); /* It prints error message and exits the program. */ void Warning(char *msg,char *func); /* It prints warning message and leaves the routine. */ void Change(int *a, int *b); /* It changes content between a and b */ int RandomInteger (int low, int high);/* Generates a random number within [low,high]. http://www.ime.usp.br/~pf/algoritmos/aulas/random.html */ #endif LibOPF/include/util/.svn/0000775000175000017500000000000012345417447015170 5ustar afalcaoafalcaoLibOPF/include/util/.svn/prop-base/0000775000175000017500000000000012345206420017043 5ustar afalcaoafalcaoLibOPF/include/util/.svn/text-base/0000775000175000017500000000000012345417447017064 5ustar afalcaoafalcaoLibOPF/include/util/.svn/text-base/gqueue.h.svn-base0000664000175000017500000000357512345206420022242 0ustar afalcaoafalcao#ifndef _GQUEUE_H_ #define _GQUEUE_H_ #include "common.h" #define MINVALUE 0 /* define queue to remove node with minimum value */ #define MAXVALUE 1 /* define queue to remove node with maximum value */ #define FIFOBREAK 0 /* define queue to solve ambiguity by FIFO */ #define LIFOBREAK 1 /* define queue to solve ambiguity by LIFO */ #define QSIZE 32768 #define SetTieBreak(a,b) a->C.tiebreak=b #define SetRemovalPolicy(a,b) a->C.removal_policy=b typedef struct _gqnode { int next; /* next node */ int prev; /* prev node */ char color; /* WHITE=0, GRAY=1, BLACK=2 */ } GQNode; typedef struct _gdoublylinkedlists { GQNode *elem; /* all possible doubly-linked lists of the circular queue */ int nelems; /* total number of elements */ int *value; /* the value of the nodes in the graph */ } GDoublyLinkedLists; typedef struct _gcircularqueue { int *first; /* list of the first elements of each doubly-linked list */ int *last; /* list of the last elements of each doubly-linked list */ int nbuckets; /* number of buckets in the circular queue */ int minvalue; /* minimum value of a node in queue */ int maxvalue; /* maximum value of a node in queue */ char tiebreak; /* 1 is LIFO, 0 is FIFO (default) */ char removal_policy; /* 0 is MINVALUE and 1 is MAXVALUE */ } GCircularQueue; typedef struct _gqueue { /* Priority queue by Dial implemented as proposed by A. Falcao */ GCircularQueue C; GDoublyLinkedLists L; } GQueue; GQueue *CreateGQueue(int nbuckets, int nelems, int *value); void DestroyGQueue(GQueue **Q); void ResetGQueue(GQueue *Q); int EmptyGQueue(GQueue *Q); void InsertGQueue(GQueue **Q, int elem); int RemoveGQueue(GQueue *Q); void RemoveGQueueElem(GQueue *Q, int elem); void UpdateGQueue(GQueue **Q, int elem, int newvalue); GQueue *GrowGQueue(GQueue **Q, int nbuckets); #endif LibOPF/include/util/.svn/text-base/common.h.svn-base0000664000175000017500000000271212345206420022227 0ustar afalcaoafalcao#ifndef _COMMON_H_ #define _COMMON_H_ #include #include #include #include #include #include /* Error messages */ #define MSG1 "Cannot allocate memory space" #define MSG2 "Cannot open file" #define MSG3 "Invalid option" /* Common data types */ typedef struct timeval timer; /* Common definitions */ #define PI 3.1415926536 #define INTERIOR 0 #define EXTERIOR 1 #define BOTH 2 #define WHITE 0 #define GRAY 1 #define BLACK 2 #define NIL -1 #define INCREASING 1 #define DECREASING 0 #define Epsilon 1E-05 /* Common operations */ #ifndef MAX #define MAX(x,y) (((x) > (y))?(x):(y)) #endif #ifndef MIN #define MIN(x,y) (((x) < (y))?(x):(y)) #endif int *AllocIntArray(int n); /* It allocates 1D array of n integers */ float *AllocFloatArray(int n); /* It allocates 1D array of n floats */ void Error(char *msg,char *func); /* It prints error message and exits the program. */ void Warning(char *msg,char *func); /* It prints warning message and leaves the routine. */ inline void Change(int *a, int *b); /* It changes content between a and b */ int RandomInteger (int low, int high);/* Generates a random number within [low,high]. http://www.ime.usp.br/~pf/algoritmos/aulas/random.html */ #endif LibOPF/include/util/.svn/text-base/subgraph.h.svn-base0000664000175000017500000000435512345206420022557 0ustar afalcaoafalcao#ifndef _SUBGRAPH_H_ #define _SUBGRAPH_H_ #include "common.h" #include "set.h" /*--------- Data types ----------------------------- */ typedef struct _snode { float pathval; //path value float dens; //node density float radius; // maximum distance among the k-nearest neighbors in // the training set. It is used to propagate // clustering labels to testing nodes) int label; //node label int root; //root node int pred; //predecessor node int truelabel; //true label if it is known int position; //index in the feature space float *feat; //feature vector char status; //0 - nothing, 1 - prototype char relevant; //0 - irrelevant, 1 - relevant int nplatadj; //holds the amount of adjacent nodes on plateaus //It is used to optimize opf_BestkMinCut //because a knn graph need only be built //for kmax, but the opf_PDF and opf_NormalizedCut computation //need only be done for the current k, //or until k+nplatadj is reached. Set *adj; //adjacency list for knn graphs } SNode; typedef struct _subgraph { SNode *node; //nodes of the image/scene subgraph int nnodes; //number of nodes int nfeats; //number of features int bestk; //number of adjacent nodes int nlabels; //number of clusters float df; //radius in the feature space for density computation float mindens; //minimum density value float maxdens; //maximum density value float K; //Constant for opf_PDF computation int *ordered_list_of_nodes; // Store the list of nodes in the increasing order of cost for speeding up supervised classification. } Subgraph; /*----------- Constructor and destructor ------------------------*/ Subgraph *CreateSubgraph(int nnodes); //Allocates nodes without features void DestroySubgraph(Subgraph **sg); //Deallocates memory for subgraph void WriteSubgraph(Subgraph *g, char *file); //write subgraph to disk Subgraph *ReadSubgraph(char *file);//read subgraph from opf format file Subgraph *CopySubgraph(Subgraph *g);//Copy subgraph (does not copy Arcs) void CopySNode(SNode *dest, SNode *src, int nfeats); //Copy nodes void SwapSNode(SNode *a, SNode *b); //Swap nodes #endif // _SUBGRAPH_H_ LibOPF/include/util/.svn/text-base/sgctree.h.svn-base0000664000175000017500000000220512345206420022370 0ustar afalcaoafalcao#ifndef _SGCTREE_H_ #define _SGCTREE_H_ #include "gqueue.h" #include "set.h" #include "subgraph.h" // ---- Component tree for built from Subgraph ------------ typedef struct _sgctnode { int level; /* gray level */ int comp; /* representative pixel of this node */ int dad; /* dad node in the maxtree */ int *son; /* son nodes in the maxtree */ int numsons; /* number of sons in the maxtree */ int size; /* number of pixels of the node */ } SgCTNode; typedef struct _sgctree { SgCTNode *node; /* nodes of the mtree */ int *cmap; /* component map */ int root; /* root node of the mtree */ int numnodes; /* number of nodes of the maxtree */ } SgCTree; SgCTree *CreateSgMaxTree(Subgraph *g); void DestroySgCTree(SgCTree **ctree); int SgAncestor(int *dad, int *cmap, int rq); int SgRepresentative(int *cmap, int p); void SgCumSize(SgCTree *ctree, int i); int *SgAreaOpen(Subgraph *g, int thres); int SgAreaLevel(SgCTree *ctree, int *level, int i, int thres); int *SgVolumeOpen(Subgraph *g, int thres); int SgVolumeLevel(SgCTree *ctree, int *level, int i, int thres, int cumvol); #endif LibOPF/include/util/.svn/text-base/realheap.h.svn-base0000664000175000017500000000155612345206420022525 0ustar afalcaoafalcao#ifndef _REALHEAP_H_ #define _REALHEAP_H_ #include "common.h" #include "gqueue.h" /* Auxiliary for RealHeap */ #define HEAP_DAD(i) ((i - 1) / 2) #define HEAP_LEFTSON(i) (2 * i + 1) #define HEAP_RIGHTSON(i) (2 * i + 2) typedef struct _realheap { float *cost; char *color; int *pixel; int *pos; int last; int n; char removal_policy; /* 0 is MINVALUE and 1 is MAXVALUE */ } RealHeap; void SetRemovalPolicyRealHeap(RealHeap *H, char policy); char IsFullRealHeap(RealHeap *H); char IsEmptyRealHeap(RealHeap *H); RealHeap *CreateRealHeap(int n, float *cost); void DestroyRealHeap(RealHeap **H); char InsertRealHeap(RealHeap *H, int pixel); char RemoveRealHeap(RealHeap *H, int *pixel); void UpdateRealHeap(RealHeap *H, int p, float value); void GoUpRealHeap(RealHeap *H, int i); void GoDownRealHeap(RealHeap *H, int i); void ResetRealHeap(RealHeap *H); #endif LibOPF/include/util/.svn/text-base/set.h.svn-base0000664000175000017500000000040312345206420021525 0ustar afalcaoafalcao#ifndef _SET_H_ #define _SET_H_ #include "common.h" typedef struct _set { int elem; struct _set *next; } Set; void InsertSet(Set **S, int elem); int RemoveSet(Set **S); int GetSetSize(Set *S); Set *CloneSet(Set *S); void DestroySet(Set **S); #endif LibOPF/include/util/.svn/props/0000775000175000017500000000000012345206420016316 5ustar afalcaoafalcaoLibOPF/include/util/.svn/tmp/0000775000175000017500000000000012345417443015764 5ustar afalcaoafalcaoLibOPF/include/util/.svn/tmp/prop-base/0000775000175000017500000000000012345206420017643 5ustar afalcaoafalcaoLibOPF/include/util/.svn/tmp/text-base/0000775000175000017500000000000012345206420017647 5ustar afalcaoafalcaoLibOPF/include/util/.svn/tmp/props/0000775000175000017500000000000012345206420017116 5ustar afalcaoafalcaoLibOPF/include/util/.svn/entries0000664000175000017500000000227112345206420016551 0ustar afalcaoafalcao10 dir 1797 svn+ssh://afalcao@lutz.ic.unicamp.br/home/svnroot/trunk/LibOPF/include/util svn+ssh://afalcao@lutz.ic.unicamp.br/home/svnroot 2013-06-09T03:58:20.135503Z 1574 afalcao 5c13e56e-d2c1-492d-b9d2-8850a87b4d6a common.h file 2013-06-02T14:23:59.000000Z 5607535833a169f05566ba05205300c2 2013-06-09T03:58:20.135503Z 1574 afalcao 1482 gqueue.h file 2010-08-31T15:02:15.000000Z 1c7192b64dc0c3148298f7ec1475d76f 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 1917 set.h file 2010-08-31T15:02:15.000000Z 457050db4f0206d7d57b04018727c1f9 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 259 subgraph.h file 2010-08-31T15:02:15.000000Z 049f51cfa523ca31b6dd33b15fca5520 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 2285 sgctree.h file 2010-08-31T15:02:15.000000Z b1c6998e8fe4d32ecd6f7c5f7af45bc8 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 1157 realheap.h file 2010-08-31T15:02:15.000000Z e2f60537b975f0da04ce9bff7cca800a 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 878 LibOPF/include/util/set.h0000664000175000017500000000040312345206420015230 0ustar afalcaoafalcao#ifndef _SET_H_ #define _SET_H_ #include "common.h" typedef struct _set { int elem; struct _set *next; } Set; void InsertSet(Set **S, int elem); int RemoveSet(Set **S); int GetSetSize(Set *S); Set *CloneSet(Set *S); void DestroySet(Set **S); #endif LibOPF/include/util/realheap.h0000664000175000017500000000155612345206420016230 0ustar afalcaoafalcao#ifndef _REALHEAP_H_ #define _REALHEAP_H_ #include "common.h" #include "gqueue.h" /* Auxiliary for RealHeap */ #define HEAP_DAD(i) ((i - 1) / 2) #define HEAP_LEFTSON(i) (2 * i + 1) #define HEAP_RIGHTSON(i) (2 * i + 2) typedef struct _realheap { float *cost; char *color; int *pixel; int *pos; int last; int n; char removal_policy; /* 0 is MINVALUE and 1 is MAXVALUE */ } RealHeap; void SetRemovalPolicyRealHeap(RealHeap *H, char policy); char IsFullRealHeap(RealHeap *H); char IsEmptyRealHeap(RealHeap *H); RealHeap *CreateRealHeap(int n, float *cost); void DestroyRealHeap(RealHeap **H); char InsertRealHeap(RealHeap *H, int pixel); char RemoveRealHeap(RealHeap *H, int *pixel); void UpdateRealHeap(RealHeap *H, int p, float value); void GoUpRealHeap(RealHeap *H, int i); void GoDownRealHeap(RealHeap *H, int i); void ResetRealHeap(RealHeap *H); #endif LibOPF/include/util/gqueue.h0000664000175000017500000000357512345206420015745 0ustar afalcaoafalcao#ifndef _GQUEUE_H_ #define _GQUEUE_H_ #include "common.h" #define MINVALUE 0 /* define queue to remove node with minimum value */ #define MAXVALUE 1 /* define queue to remove node with maximum value */ #define FIFOBREAK 0 /* define queue to solve ambiguity by FIFO */ #define LIFOBREAK 1 /* define queue to solve ambiguity by LIFO */ #define QSIZE 32768 #define SetTieBreak(a,b) a->C.tiebreak=b #define SetRemovalPolicy(a,b) a->C.removal_policy=b typedef struct _gqnode { int next; /* next node */ int prev; /* prev node */ char color; /* WHITE=0, GRAY=1, BLACK=2 */ } GQNode; typedef struct _gdoublylinkedlists { GQNode *elem; /* all possible doubly-linked lists of the circular queue */ int nelems; /* total number of elements */ int *value; /* the value of the nodes in the graph */ } GDoublyLinkedLists; typedef struct _gcircularqueue { int *first; /* list of the first elements of each doubly-linked list */ int *last; /* list of the last elements of each doubly-linked list */ int nbuckets; /* number of buckets in the circular queue */ int minvalue; /* minimum value of a node in queue */ int maxvalue; /* maximum value of a node in queue */ char tiebreak; /* 1 is LIFO, 0 is FIFO (default) */ char removal_policy; /* 0 is MINVALUE and 1 is MAXVALUE */ } GCircularQueue; typedef struct _gqueue { /* Priority queue by Dial implemented as proposed by A. Falcao */ GCircularQueue C; GDoublyLinkedLists L; } GQueue; GQueue *CreateGQueue(int nbuckets, int nelems, int *value); void DestroyGQueue(GQueue **Q); void ResetGQueue(GQueue *Q); int EmptyGQueue(GQueue *Q); void InsertGQueue(GQueue **Q, int elem); int RemoveGQueue(GQueue *Q); void RemoveGQueueElem(GQueue *Q, int elem); void UpdateGQueue(GQueue **Q, int elem, int newvalue); GQueue *GrowGQueue(GQueue **Q, int nbuckets); #endif LibOPF/include/.svn/0000775000175000017500000000000012345417446014212 5ustar afalcaoafalcaoLibOPF/include/.svn/prop-base/0000775000175000017500000000000012345206420016066 5ustar afalcaoafalcaoLibOPF/include/.svn/text-base/0000775000175000017500000000000012345417450016101 5ustar afalcaoafalcaoLibOPF/include/.svn/text-base/OPF.h.svn-base0000664000175000017500000001252312345206420020407 0ustar afalcaoafalcao#ifndef _OPF_H_ #define _OPF_H_ #include #include #include #include #include #include #include #include #include #include #include "common.h" #include "set.h" #include "gqueue.h" #include "subgraph.h" #include "sgctree.h" #include "realheap.h" /*--------- Common definitions --------- */ #define opf_MAXARCW 100000.0 #define opf_MAXDENS 1000.0 #define opf_PROTOTYPE 1 typedef float (*opf_ArcWeightFun)(float *f1, float *f2, int n); extern opf_ArcWeightFun opf_ArcWeight; extern char opf_PrecomputedDistance; extern float **opf_DistanceValue; /*--------- Supervised OPF with complete graph -----------------------*/ void opf_OPFTraining(Subgraph *sg); //Training function void opf_OPFClassifying(Subgraph *sgtrain, Subgraph *sg); //Classification function: it simply classifies samples from sg void opf_OPFLearning(Subgraph **sgtrain, Subgraph **sgeval); //Learning function void opf_OPFAgglomerativeLearning(Subgraph **sgtrain, Subgraph **sgeval); //Agglomerative learning function /*--------- Unsupervised OPF -------------------------------------*/ void opf_OPFClustering(Subgraph *sg); //Training function: it computes unsupervised training for the pre-computed best k. void opf_OPFKNNClassify(Subgraph *sgtrain, Subgraph *sg); // Classification function: it classifies nodes of sg by using the labels created by program opf_cluster in sgtrain /*------------ Auxiliary functions ------------------------------ */ void opf_ResetSubgraph(Subgraph *sg); //Resets subgraph fields (pred and arcs) void opf_SwapErrorsbyNonPrototypes(Subgraph **sgtrain, Subgraph **sgeval); //Replace errors from evaluating set by non prototypes from training set void opf_MoveIrrelevantNodes(Subgraph **sgtrain, Subgraph **sgeval); //Move irrelevant nodes from source graph (src) to destiny graph (dst) void opf_MoveMisclassifiedNodes(Subgraph **sgtrain, Subgraph **sgeval, int *p); //Move misclassified nodes from source graph (src) to destiny graph (dst) void opf_RemoveIrrelevantNodes(Subgraph **sg); //Remove irrelevant nodes void opf_MarkNodes(Subgraph *g, int i); //mark nodes and the whole path as relevants void opf_WriteModelFile(Subgraph *g, char *file); //write model file to disk Subgraph *opf_ReadModelFile(char *file); //read subgraph from opf model file void opf_NormalizeFeatures(Subgraph *sg); //normalize features void opf_MSTPrototypes(Subgraph *sg); //Find prototypes by the MST approach Subgraph **opf_kFoldSubgraph(Subgraph *sg, int k); //It creates k folds for cross validation void opf_SplitSubgraph(Subgraph *sg, Subgraph **sg1, Subgraph **sg2, float perc1); //Split subgraph into two parts such that the size of the first part is given by a percentual of samples. Subgraph *opf_MergeSubgraph(Subgraph *sg1, Subgraph *sg2); //Merge two subgraphs float opf_Accuracy(Subgraph *g); //Compute accuracy int **opf_ConfusionMatrix(Subgraph *sg); //Compute the confusion matrix float **opf_ReadDistances(char *fileName, int *n); //read distances from precomputed distances file float opf_NormalizedCut( Subgraph *sg ); void opf_BestkMinCut(Subgraph *sg, int kmin, int kmax); void opf_CreateArcs(Subgraph *sg, int knn); //it creates arcs for each node (adjacency relation) void opf_DestroyArcs(Subgraph *sg); //it destroys the adjacency relation void opf_PDF(Subgraph *sg); //it computes the PDf for each node void opf_ElimMaxBelowVolume(Subgraph *sg, int V); // Eliminate maxima in the graph with volume below V void opf_ElimMaxBelowArea(Subgraph *sg, int A); //Eliminate maxima in the graph with area below A void opf_ElimMaxBelowH(Subgraph *sg, float H);// Eliminate maxima in the graph with pdf below H /*------------ Distance functions ------------------------------ */ float opf_EuclDist(float *f1, float *f2, int n); //Computes Euclidean distance between feature vectors float opf_EuclDistLog(float *f1, float *f2, int n); //Computes Euclidean distance between feature vectors and applies //logarithmic function float opf_GaussDist(float *f1, float *f2, int n, float gamma); //Computes Gaussian distance between feature vectors float opf_ChiSquaredDist(float *f1, float *f2, int n); //Compute chi-squared distance between feature vectors float opf_ManhattanDist(float *f1, float *f2, int n); //Compute Manhattan distance between feature vectors float opf_CanberraDist(float *f1, float *f2, int n); //Compute Camberra distance between feature vectors float opf_SquaredChordDist(float *f1, float *f2, int n); //Compute Squared Chord distance between feature vectors float opf_SquaredChiSquaredDist(float *f1, float *f2, int n); //Compute Squared Chi-squared distance between feature vectors float opf_BrayCurtisDist(float *f1, float *f2, int n); //Compute Bray Curtis distance between feature vectors /* -------- Auxiliary functions used to optimize BestkMinCut -------- */ float* opf_CreateArcs2(Subgraph *sg, int kmax); //Creates arcs for each node (adjacency relation) and returns //the maximum distances for each k=1,2,...,kmax void opf_OPFClusteringToKmax(Subgraph *sg); //OPFClustering computation only for sg->bestk neighbors void opf_PDFtoKmax(Subgraph *sg); //PDF computation only for sg->bestk neighbors float opf_NormalizedCutToKmax( Subgraph *sg ); //Normalized cut computed only for sg->bestk neighbors #endif LibOPF/include/.svn/props/0000775000175000017500000000000012345206420015341 5ustar afalcaoafalcaoLibOPF/include/.svn/tmp/0000775000175000017500000000000012345417443015007 5ustar afalcaoafalcaoLibOPF/include/.svn/tmp/prop-base/0000775000175000017500000000000012345206420016666 5ustar afalcaoafalcaoLibOPF/include/.svn/tmp/text-base/0000775000175000017500000000000012345206420016672 5ustar afalcaoafalcaoLibOPF/include/.svn/tmp/props/0000775000175000017500000000000012345206420016141 5ustar afalcaoafalcaoLibOPF/include/.svn/entries0000664000175000017500000000060312345206420015571 0ustar afalcaoafalcao10 dir 1797 svn+ssh://afalcao@lutz.ic.unicamp.br/home/svnroot/trunk/LibOPF/include svn+ssh://afalcao@lutz.ic.unicamp.br/home/svnroot 2013-06-09T03:58:20.135503Z 1574 afalcao 5c13e56e-d2c1-492d-b9d2-8850a87b4d6a OPF.h file 2013-06-02T21:50:32.000000Z e8687f0ad5fd7cd7a1dec263eaad2706 2013-06-09T03:58:20.135503Z 1574 afalcao 5459 util dir LibOPF/include/OPF.h0000664000175000017500000001311212345206420014105 0ustar afalcaoafalcao#ifndef _OPF_H_ #define _OPF_H_ #include #include #include #include #include #include #include #include #include #include #include "common.h" #include "set.h" #include "gqueue.h" #include "subgraph.h" #include "sgctree.h" #include "realheap.h" /*--------- Common definitions --------- */ #define opf_MAXARCW 100000.0 #define opf_MAXDENS 1000.0 #define opf_PROTOTYPE 1 #define opf_version "\nLibOPF version 3.0 (2013)\n" typedef float (*opf_ArcWeightFun)(float *f1, float *f2, int n); extern opf_ArcWeightFun opf_ArcWeight; extern char opf_PrecomputedDistance; extern float **opf_DistanceValue; /*--------- Supervised OPF with complete graph -----------------------*/ void opf_OPFTraining(Subgraph *sg); //Training function void opf_OPFClassifying(Subgraph *sgtrain, Subgraph *sg); //Classification function: it simply classifies samples from sg void opf_OPFLearning(Subgraph **sgtrain, Subgraph **sgeval); //Learning function void opf_OPFAgglomerativeLearning(Subgraph **sgtrain, Subgraph **sgeval); //Agglomerative learning function /*--------- Unsupervised OPF -------------------------------------*/ void opf_OPFClustering(Subgraph *sg); //Training function: it computes unsupervised training for the pre-computed best k. void opf_OPFKNNClassify(Subgraph *sgtrain, Subgraph *sg); // Classification function: it classifies nodes of sg by using the labels created by program opf_cluster in sgtrain /*--------- Semi Supervised OPF with complete graph -----------------------*/ Subgraph *opf_OPFSemiLearning(Subgraph *sg, Subgraph *nonsg, Subgraph *sgeval);// Semi-supervised learning function /*------------ Auxiliary functions ------------------------------ */ void opf_ResetSubgraph(Subgraph *sg); //Resets subgraph fields (pred and arcs) void opf_SwapErrorsbyNonPrototypes(Subgraph **sgtrain, Subgraph **sgeval); //Replace errors from evaluating set by non prototypes from training set void opf_MoveIrrelevantNodes(Subgraph **sgtrain, Subgraph **sgeval); //Move irrelevant nodes from source graph (src) to destiny graph (dst) void opf_MoveMisclassifiedNodes(Subgraph **sgtrain, Subgraph **sgeval, int *p); //Move misclassified nodes from source graph (src) to destiny graph (dst) void opf_RemoveIrrelevantNodes(Subgraph **sg); //Remove irrelevant nodes void opf_MarkNodes(Subgraph *g, int i); //mark nodes and the whole path as relevants void opf_WriteModelFile(Subgraph *g, char *file); //write model file to disk Subgraph *opf_ReadModelFile(char *file); //read subgraph from opf model file void opf_NormalizeFeatures(Subgraph *sg); //normalize features void opf_MSTPrototypes(Subgraph *sg); //Find prototypes by the MST approach Subgraph **opf_kFoldSubgraph(Subgraph *sg, int k); //It creates k folds for cross validation void opf_SplitSubgraph(Subgraph *sg, Subgraph **sg1, Subgraph **sg2, float perc1); //Split subgraph into two parts such that the size of the first part is given by a percentual of samples. Subgraph *opf_MergeSubgraph(Subgraph *sg1, Subgraph *sg2); //Merge two subgraphs float opf_Accuracy(Subgraph *g); //Compute accuracy int **opf_ConfusionMatrix(Subgraph *sg); //Compute the confusion matrix float **opf_ReadDistances(char *fileName, int *n); //read distances from precomputed distances file float opf_NormalizedCut( Subgraph *sg ); void opf_BestkMinCut(Subgraph *sg, int kmin, int kmax); void opf_CreateArcs(Subgraph *sg, int knn); //it creates arcs for each node (adjacency relation) void opf_DestroyArcs(Subgraph *sg); //it destroys the adjacency relation void opf_PDF(Subgraph *sg); //it computes the PDf for each node void opf_ElimMaxBelowVolume(Subgraph *sg, int V); // Eliminate maxima in the graph with volume below V void opf_ElimMaxBelowArea(Subgraph *sg, int A); //Eliminate maxima in the graph with area below A void opf_ElimMaxBelowH(Subgraph *sg, float H);// Eliminate maxima in the graph with pdf below H /*------------ Distance functions ------------------------------ */ float opf_EuclDist(float *f1, float *f2, int n); //Computes Euclidean distance between feature vectors float opf_EuclDistLog(float *f1, float *f2, int n); //Computes Euclidean distance between feature vectors and applies //logarithmic function float opf_GaussDist(float *f1, float *f2, int n, float gamma); //Computes Gaussian distance between feature vectors float opf_ChiSquaredDist(float *f1, float *f2, int n); //Compute chi-squared distance between feature vectors float opf_ManhattanDist(float *f1, float *f2, int n); //Compute Manhattan distance between feature vectors float opf_CanberraDist(float *f1, float *f2, int n); //Compute Camberra distance between feature vectors float opf_SquaredChordDist(float *f1, float *f2, int n); //Compute Squared Chord distance between feature vectors float opf_SquaredChiSquaredDist(float *f1, float *f2, int n); //Compute Squared Chi-squared distance between feature vectors float opf_BrayCurtisDist(float *f1, float *f2, int n); //Compute Bray Curtis distance between feature vectors /* -------- Auxiliary functions used to optimize BestkMinCut -------- */ float* opf_CreateArcs2(Subgraph *sg, int kmax); //Creates arcs for each node (adjacency relation) and returns //the maximum distances for each k=1,2,...,kmax void opf_OPFClusteringToKmax(Subgraph *sg); //OPFClustering computation only for sg->bestk neighbors void opf_PDFtoKmax(Subgraph *sg); //PDF computation only for sg->bestk neighbors float opf_NormalizedCutToKmax( Subgraph *sg ); //Normalized cut computed only for sg->bestk neighbors #endif LibOPF/examples/0000775000175000017500000000000012345417450013514 5ustar afalcaoafalcaoLibOPF/examples/example2.sh0000664000175000017500000000100312345206420015550 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the OPF classifier with learning procedure." #splitting dataset into training, evaluating and test sets with, respectively, 30%, 20% and 50% of the samples each one without features normalization ../bin/opf_split ../data/boat.dat 0.3 0.2 0.5 0 #executing the OPF learning procedure ../bin/opf_learn training.dat evaluating.dat #classifying the test set ../bin/opf_classify testing.dat # computing the accuracy over the test set ../bin/opf_accuracy testing.dat LibOPF/examples/example6.sh0000644000175000017500000000337612345206420015571 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the OPF classifier with semi supervised learning procedure." #splitting dataset into training, evaluating and test sets with, respectively, 30%, 20% and 50% of the samples each one without features normalization ../bin/opf_split ../data/saturn.dat 0.6 0.2 0.2 0 cp training.dat Z1.dat cp testing.dat Z3.dat rm training.dat rm testing.dat ../bin/opf_split Z1.dat 0.4 0.0 0.6 0 cp training.dat Z1LINE.dat #labeled samples cp testing.dat Z1DOUBLELINE.dat #unlabeled samples rm training.dat rm testing.dat #executing the classifier with semi supervised training procedure without evaluating #----------------------------------------------------------------------------------- ../bin/opf_semi Z1LINE.dat Z1DOUBLELINE.dat #classifying the test set ../bin/opf_classify Z3.dat # computing the accuracy over the test set echo --------------------------------- echo Semi Supervised OPF mean accuracy echo --------------------------------- ../bin/opf_accuracy Z3.dat rm *.acc *.time *.out *.opf #----------------------------------------------------------------------------------- #executing the classifier with semi supervised training procedure with evaluating #----------------------------------------------------------------------------------- ../bin/opf_semi Z1LINE.dat Z1DOUBLELINE.dat evaluating.dat #classifying the test set ../bin/opf_classify Z3.dat # computing the accuracy over the test set echo --------------------------------- echo Semi Supervised OPF mean accuracy with Evaluating echo --------------------------------- ../bin/opf_accuracy Z3.dat #----------------------------------------------------------------------------------- rm Z1.dat Z3.dat Z1LINE.dat Z1DOUBLELINE.dat evaluating.dat classifier.opf *.acc *.time *.out LibOPF/examples/example4.sh0000664000175000017500000000144612345206420015565 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the OPF classifier with learning procedure and with precomputed distances." # Generating the precomputed distances for cone-torus dataset, with Manhattan distance (ID 3) and without # distance normalization (parameter 0 at the final of the command line) ../bin/opf_distance ../data/cone-torus.dat 3 0 #splitting dataset into training, evaluating and test sets with, respectively, 30%, 20% and 50% of the samples each one without features normalization ../bin/opf_split ../data/cone-torus.dat 0.3 0.2 0.5 0 #executing the OPF learning procedure ../bin/opf_learn training.dat evaluating.dat distances.dat #classifying the test set ../bin/opf_classify testing.dat distances.dat # computing the accuracy over the test set ../bin/opf_accuracy testing.dat LibOPF/examples/.svn/0000775000175000017500000000000012345417446014405 5ustar afalcaoafalcaoLibOPF/examples/.svn/prop-base/0000775000175000017500000000000012345206420016261 5ustar afalcaoafalcaoLibOPF/examples/.svn/text-base/0000775000175000017500000000000012345417450016274 5ustar afalcaoafalcaoLibOPF/examples/.svn/text-base/example2.sh.svn-base0000664000175000017500000000100312345206420022045 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the OPF classifier with learning procedure." #splitting dataset into training, evaluating and test sets with, respectively, 30%, 20% and 50% of the samples each one without features normalization ../bin/opf_split ../data/boat.dat 0.3 0.2 0.5 0 #executing the OPF learning procedure ../bin/opf_learn training.dat evaluating.dat #classifying the test set ../bin/opf_classify testing.dat # computing the accuracy over the test set ../bin/opf_accuracy testing.dat LibOPF/examples/.svn/text-base/example3.sh.svn-base0000664000175000017500000000143012345206420022052 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the OPF classifier without learning procedure and with precomputed distances." # Generating the precomputed distances for cone-torus dataset, with Manhattan distance (ID 3) and without # distance normalization (parameter 0 at the final of the command line) ../bin/opf_distance ../data/cone-torus.dat 3 0 #splitting dataset into training, evaluating and test sets with, respectively, 30%, 20% and 50% of the samples each one without features normalization ../bin/opf_split ../data/cone-torus.dat 0.5 0 0.5 0 #executing the OPF learning procedure ../bin/opf_train training.dat distances.dat #classifying the test set ../bin/opf_classify testing.dat distances.dat # computing the accuracy over the test set ../bin/opf_accuracy testing.dat LibOPF/examples/.svn/text-base/example5.sh.svn-base0000664000175000017500000000613312345206420022061 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the unsupervised OPF classifier." # executing and evaluating the unsupervised OPF #splitting dataset into training and test sets with, respectively, 80% #and 20% of the samples each one without features normalization. Then #computing example for k=100, removing maxima whose dome area (P2=1) is #below 20% of the total number of nodes. It also creates a classifier #by assigning the true label of the root node to the remaining nodes #of its optimum-path tree (cluster), then evaluates the accuracy of #this classification on the test set. ../bin/opf_split ../data/data1.dat 0.8 0.0 0.2 0 ../bin/opf_cluster training.dat 100 1 0.2 ../bin/opf_knn_classify testing.dat ../bin/opf_accuracy testing.dat #splitting dataset into training and test sets with, respectively, 80% #and 20% of the samples each one without features normalization. Then #computing example using k=100, removing maxima whose dome volume (P2=2) is #below 1% of the pdf volume. It also creates a classifier by assigning #the true label of the root node to the remaining nodes of its #optimum-path tree (cluster), then evaluates the accuracy of this #classification. ../bin/opf_split ../data/data2.dat 0.8 0.0 0.2 0 ../bin/opf_cluster training.dat 100 2 0.01 ../bin/opf_knn_classify testing.dat ../bin/opf_accuracy testing.dat #splitting dataset into training and test sets with, respectively, 80% #and 20% of the samples each one without features normalization. Then #computing example using k=20, removing maxima whose dome volume (P2=2) is #below 0.1% of the pdf volume. It also creates a classifier by #assigning the true label of the root node to the remaining nodes of #its optimum-path tree (cluster), then evaluates the accuracy of this #classification. ../bin/opf_split ../data/data3.dat 0.8 0.0 0.2 0 ../bin/opf_cluster training.dat 20 2 0.001 ../bin/opf_knn_classify testing.dat ../bin/opf_accuracy testing.dat #splitting dataset into training and test sets with, respectively, 80% #and 20% of the samples each one without features normalization. Then #computing example using k=100, removing maxima whose dome volume (P2=2) is #below 2% of the pdf volume. It also creates a classifier by assigning #the true label of the root node to the remaining nodes of its #optimum-path tree (cluster), then evaluates the accuracy of this #classification. ../bin/opf_split ../data/data4.dat 0.8 0.0 0.2 0 ../bin/opf_cluster training.dat 100 2 0.02 ../bin/opf_knn_classify testing.dat ../bin/opf_accuracy testing.dat #splitting dataset into training and test sets with, respectively, 80% #and 20% of the samples each one without features normalization. Then #computing example using k=50, removing maxima whose dome area (P2=1) #is below 20% of the total number of nodes. It also creates a #classifier by assigning the true label of the root node to the #remaining nodes of its optimum-path tree (cluster), then evaluates #the accuracy of this classification. ../bin/opf_split ../data/data5.dat 0.8 0.0 0.2 0 ../bin/opf_cluster training.dat 50 1 0.2 ../bin/opf_knn_classify testing.dat ../bin/opf_accuracy testing.dat LibOPF/examples/.svn/text-base/example4.sh.svn-base0000664000175000017500000000144612345206420022062 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the OPF classifier with learning procedure and with precomputed distances." # Generating the precomputed distances for cone-torus dataset, with Manhattan distance (ID 3) and without # distance normalization (parameter 0 at the final of the command line) ../bin/opf_distance ../data/cone-torus.dat 3 0 #splitting dataset into training, evaluating and test sets with, respectively, 30%, 20% and 50% of the samples each one without features normalization ../bin/opf_split ../data/cone-torus.dat 0.3 0.2 0.5 0 #executing the OPF learning procedure ../bin/opf_learn training.dat evaluating.dat distances.dat #classifying the test set ../bin/opf_classify testing.dat distances.dat # computing the accuracy over the test set ../bin/opf_accuracy testing.dat LibOPF/examples/.svn/text-base/example1.sh.svn-base0000664000175000017500000000070012345206420022047 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the OPF classifier without learning procedure." #splitting dataset into training and test sets with 50% of the samples each one without features normalization ../bin/opf_split ../data/boat.dat 0.5 0 0.5 0 #training OPF classifier ../bin/opf_train training.dat #classifying the test set ../bin/opf_classify testing.dat # computing the accuracy over the test set ../bin/opf_accuracy testing.dat LibOPF/examples/.svn/props/0000775000175000017500000000000012345206420015534 5ustar afalcaoafalcaoLibOPF/examples/.svn/tmp/0000775000175000017500000000000012345417443015202 5ustar afalcaoafalcaoLibOPF/examples/.svn/tmp/prop-base/0000775000175000017500000000000012345206420017061 5ustar afalcaoafalcaoLibOPF/examples/.svn/tmp/text-base/0000775000175000017500000000000012345206420017065 5ustar afalcaoafalcaoLibOPF/examples/.svn/tmp/props/0000775000175000017500000000000012345206420016334 5ustar afalcaoafalcaoLibOPF/examples/.svn/entries0000664000175000017500000000207512345206420015771 0ustar afalcaoafalcao10 dir 1797 svn+ssh://afalcao@lutz.ic.unicamp.br/home/svnroot/trunk/LibOPF/examples svn+ssh://afalcao@lutz.ic.unicamp.br/home/svnroot 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 5c13e56e-d2c1-492d-b9d2-8850a87b4d6a example1.sh file 2010-08-31T15:02:14.000000Z e2dc66dea29f43cc5b9dc55413b4b164 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 448 example2.sh file 2010-08-31T15:02:14.000000Z 1fb9bbbfee07e3c0a45382c5fe2e67f8 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 515 example3.sh file 2010-08-31T15:02:14.000000Z d0f079412cf34250a54c4d993d44ff2b 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 792 example4.sh file 2010-08-31T15:02:14.000000Z 7599daaa98fcb35e3c449cc3217d2607 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 806 example5.sh file 2010-08-31T15:02:14.000000Z 22dc4f122317e05d42b8beae1dd1655a 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 3163 LibOPF/examples/example1.sh0000664000175000017500000000070012345206420015552 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the OPF classifier without learning procedure." #splitting dataset into training and test sets with 50% of the samples each one without features normalization ../bin/opf_split ../data/boat.dat 0.5 0 0.5 0 #training OPF classifier ../bin/opf_train training.dat #classifying the test set ../bin/opf_classify testing.dat # computing the accuracy over the test set ../bin/opf_accuracy testing.dat LibOPF/examples/example5.sh0000664000175000017500000000613312345206420015564 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the unsupervised OPF classifier." # executing and evaluating the unsupervised OPF #splitting dataset into training and test sets with, respectively, 80% #and 20% of the samples each one without features normalization. Then #computing example for k=100, removing maxima whose dome area (P2=1) is #below 20% of the total number of nodes. It also creates a classifier #by assigning the true label of the root node to the remaining nodes #of its optimum-path tree (cluster), then evaluates the accuracy of #this classification on the test set. ../bin/opf_split ../data/data1.dat 0.8 0.0 0.2 0 ../bin/opf_cluster training.dat 100 1 0.2 ../bin/opf_knn_classify testing.dat ../bin/opf_accuracy testing.dat #splitting dataset into training and test sets with, respectively, 80% #and 20% of the samples each one without features normalization. Then #computing example using k=100, removing maxima whose dome volume (P2=2) is #below 1% of the pdf volume. It also creates a classifier by assigning #the true label of the root node to the remaining nodes of its #optimum-path tree (cluster), then evaluates the accuracy of this #classification. ../bin/opf_split ../data/data2.dat 0.8 0.0 0.2 0 ../bin/opf_cluster training.dat 100 2 0.01 ../bin/opf_knn_classify testing.dat ../bin/opf_accuracy testing.dat #splitting dataset into training and test sets with, respectively, 80% #and 20% of the samples each one without features normalization. Then #computing example using k=20, removing maxima whose dome volume (P2=2) is #below 0.1% of the pdf volume. It also creates a classifier by #assigning the true label of the root node to the remaining nodes of #its optimum-path tree (cluster), then evaluates the accuracy of this #classification. ../bin/opf_split ../data/data3.dat 0.8 0.0 0.2 0 ../bin/opf_cluster training.dat 20 2 0.001 ../bin/opf_knn_classify testing.dat ../bin/opf_accuracy testing.dat #splitting dataset into training and test sets with, respectively, 80% #and 20% of the samples each one without features normalization. Then #computing example using k=100, removing maxima whose dome volume (P2=2) is #below 2% of the pdf volume. It also creates a classifier by assigning #the true label of the root node to the remaining nodes of its #optimum-path tree (cluster), then evaluates the accuracy of this #classification. ../bin/opf_split ../data/data4.dat 0.8 0.0 0.2 0 ../bin/opf_cluster training.dat 100 2 0.02 ../bin/opf_knn_classify testing.dat ../bin/opf_accuracy testing.dat #splitting dataset into training and test sets with, respectively, 80% #and 20% of the samples each one without features normalization. Then #computing example using k=50, removing maxima whose dome area (P2=1) #is below 20% of the total number of nodes. It also creates a #classifier by assigning the true label of the root node to the #remaining nodes of its optimum-path tree (cluster), then evaluates #the accuracy of this classification. ../bin/opf_split ../data/data5.dat 0.8 0.0 0.2 0 ../bin/opf_cluster training.dat 50 1 0.2 ../bin/opf_knn_classify testing.dat ../bin/opf_accuracy testing.dat LibOPF/examples/example3.sh0000664000175000017500000000143012345206420015555 0ustar afalcaoafalcao#!/bin/sh echo "This is an example of how to use the OPF classifier without learning procedure and with precomputed distances." # Generating the precomputed distances for cone-torus dataset, with Manhattan distance (ID 3) and without # distance normalization (parameter 0 at the final of the command line) ../bin/opf_distance ../data/cone-torus.dat 3 0 #splitting dataset into training, evaluating and test sets with, respectively, 30%, 20% and 50% of the samples each one without features normalization ../bin/opf_split ../data/cone-torus.dat 0.5 0 0.5 0 #executing the OPF learning procedure ../bin/opf_train training.dat distances.dat #classifying the test set ../bin/opf_classify testing.dat distances.dat # computing the accuracy over the test set ../bin/opf_accuracy testing.dat LibOPF/COPYRIGHT0000664000175000017500000000300112345206420013154 0ustar afalcaoafalcaoCopyright (c) 2008-2009 João Paulo Papa, Alexandre Xavier Falcão and Celso Tetsuo Nagase Suzuki All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. 3. Neither name of copyright holders nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. LibOPF/Makefile0000664000175000017500000000732412351125507013340 0ustar afalcaoafalcaoLIB=./lib INCLUDE=./include SRC=./src OBJ=./obj UTIL=util CC=gcc FLAGS= -O3 -Wall INCFLAGS = -I$(INCLUDE) -I$(INCLUDE)/$(UTIL) all: libOPF opf_split opf_accuracy opf_train opf_classify opf_learn opf_distance opf_info opf_fold opf_merge opf_cluster opf_knn_classify statistics txt2opf opf2txt opf_check opf_normalize libOPF: libOPF-build echo "libOPF.a built..." libOPF-build: \ util \ $(OBJ)/OPF.o \ ar csr $(LIB)/libOPF.a \ $(OBJ)/common.o \ $(OBJ)/set.o \ $(OBJ)/gqueue.o \ $(OBJ)/realheap.o \ $(OBJ)/sgctree.o \ $(OBJ)/subgraph.o \ $(OBJ)/OPF.o \ $(OBJ)/OPF.o: $(SRC)/OPF.c $(CC) $(FLAGS) -c $(SRC)/OPF.c $(INCFLAGS) \ -o $(OBJ)/OPF.o opf_split: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_split.c -L./lib -o bin/opf_split -lOPF -lm opf_accuracy: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_accuracy.c -L./lib -o bin/opf_accuracy -lOPF -lm opf_train: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_train.c -L./lib -o bin/opf_train -lOPF -lm opf_classify: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_classify.c -L./lib -o bin/opf_classify -lOPF -lm opf_learn: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_learn.c -L./lib -o bin/opf_learn -lOPF -lm opf_distance: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_distance.c -L./lib -o bin/opf_distance -lOPF -lm opf_info: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_info.c -L./lib -o bin/opf_info -lOPF -lm opf_fold: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_fold.c -L./lib -o bin/opf_fold -lOPF -lm opf_merge: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_merge.c -L./lib -o bin/opf_merge -lOPF -lm opf_cluster: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_cluster.c -L./lib -o bin/opf_cluster -lOPF -lm opf_knn_classify: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_knn_classify.c -L./lib -o bin/opf_knn_classify -lOPF -lm statistics: $(CC) $(FLAGS) tools/src/statistics.c -o tools/statistics -lm txt2opf: libOPF $(CC) $(FLAGS) $(INCFLAGS) tools/src/txt2opf.c -L./lib -o tools/txt2opf -lOPF -lm opf_check: libOPF $(CC) $(FLAGS) $(INCFLAGS) tools/src/opf_check.c -L./lib -o tools/opf_check -lOPF -lm opf2txt: libOPF $(CC) $(FLAGS) $(INCFLAGS) tools/src/opf2txt.c -L./lib -o tools/opf2txt -lOPF -lm opf_normalize: libOPF $(CC) $(FLAGS) $(INCFLAGS) src/opf_normalize.c -L./lib -o bin/opf_normalize -lOPF -lm util: $(SRC)/$(UTIL)/common.c $(SRC)/$(UTIL)/set.c $(SRC)/$(UTIL)/gqueue.c $(SRC)/$(UTIL)/realheap.c $(SRC)/$(UTIL)/sgctree.c $(SRC)/$(UTIL)/subgraph.c $(CC) $(FLAGS) $(INCFLAGS) -c $(SRC)/$(UTIL)/common.c -o $(OBJ)/common.o $(CC) $(FLAGS) $(INCFLAGS) -c $(SRC)/$(UTIL)/set.c -o $(OBJ)/set.o $(CC) $(FLAGS) $(INCFLAGS) -c $(SRC)/$(UTIL)/gqueue.c -o $(OBJ)/gqueue.o $(CC) $(FLAGS) $(INCFLAGS) -c $(SRC)/$(UTIL)/realheap.c -o $(OBJ)/realheap.o $(CC) $(FLAGS) $(INCFLAGS) -c $(SRC)/$(UTIL)/sgctree.c -o $(OBJ)/sgctree.o $(CC) $(FLAGS) $(INCFLAGS) -c $(SRC)/$(UTIL)/subgraph.c -o $(OBJ)/subgraph.o ## Compiling LibOPF with LibIFT opf-ift: libOPF-ift libOPF-ift: libOPF-ift-build echo "libOPF.a built with IFT..." libOPF-ift-build: \ OPF-ift.o \ ar csr $(LIB)/libOPF.a \ $(OBJ)/OPF.o \ OPF-ift.o: $(SRC)/OPF.c $(CC) $(FLAGS) -c $(SRC)/OPF.c -I$(INCLUDE) -I$(IFT_DIR)/include \ -o $(OBJ)/OPF.o ## Cleaning-up clean: rm -f $(LIB)/lib*.a; rm -f $(OBJ)/*.o bin/opf_split bin/opf_accuracy bin/opf_train bin/opf_classify bin/opf_learn bin/opf_distance bin/opf_info bin/opf_cluster bin/opf_fold bin/opf_merge tools/opf_check bin/opf_knn_classify tools/statistics tools/txt2opf tools/opf2txt tools/opf_check bin/opf_normalize clean_results: rm -f *.out *.opf *.acc *.time *.opf training.dat evaluating.dat testing.dat clean_results_in_examples: rm -f examples/*.out examples/*.opf examples/*.acc examples/*.time examples/*.opf examples/training.dat examples/evaluating.dat examples/testing.dat LibOPF/obj/0000775000175000017500000000000014624105635012451 5ustar afalcaoafalcaoLibOPF/obj/.svn/0000775000175000017500000000000012345417446013341 5ustar afalcaoafalcaoLibOPF/obj/.svn/prop-base/0000775000175000017500000000000012345206420015215 5ustar afalcaoafalcaoLibOPF/obj/.svn/text-base/0000775000175000017500000000000012345206420015221 5ustar afalcaoafalcaoLibOPF/obj/.svn/props/0000775000175000017500000000000012345206420014470 5ustar afalcaoafalcaoLibOPF/obj/.svn/tmp/0000775000175000017500000000000012345417443014136 5ustar afalcaoafalcaoLibOPF/obj/.svn/tmp/prop-base/0000775000175000017500000000000012345206420016015 5ustar afalcaoafalcaoLibOPF/obj/.svn/tmp/text-base/0000775000175000017500000000000012345206420016021 5ustar afalcaoafalcaoLibOPF/obj/.svn/tmp/props/0000775000175000017500000000000012345206420015270 5ustar afalcaoafalcaoLibOPF/obj/.svn/entries0000664000175000017500000000036412345206420014724 0ustar afalcaoafalcao10 dir 1797 svn+ssh://afalcao@lutz.ic.unicamp.br/home/svnroot/trunk/LibOPF/obj svn+ssh://afalcao@lutz.ic.unicamp.br/home/svnroot 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 5c13e56e-d2c1-492d-b9d2-8850a87b4d6a LibOPF/lib/0000775000175000017500000000000014624105635012445 5ustar afalcaoafalcaoLibOPF/lib/.svn/0000775000175000017500000000000012345417446013335 5ustar afalcaoafalcaoLibOPF/lib/.svn/prop-base/0000775000175000017500000000000012345206420015211 5ustar afalcaoafalcaoLibOPF/lib/.svn/text-base/0000775000175000017500000000000012345206420015215 5ustar afalcaoafalcaoLibOPF/lib/.svn/props/0000775000175000017500000000000012345206420014464 5ustar afalcaoafalcaoLibOPF/lib/.svn/tmp/0000775000175000017500000000000012345417443014132 5ustar afalcaoafalcaoLibOPF/lib/.svn/tmp/prop-base/0000775000175000017500000000000012345206420016011 5ustar afalcaoafalcaoLibOPF/lib/.svn/tmp/text-base/0000775000175000017500000000000012345206420016015 5ustar afalcaoafalcaoLibOPF/lib/.svn/tmp/props/0000775000175000017500000000000012345206420015264 5ustar afalcaoafalcaoLibOPF/lib/.svn/entries0000664000175000017500000000036412345206420014720 0ustar afalcaoafalcao10 dir 1797 svn+ssh://afalcao@lutz.ic.unicamp.br/home/svnroot/trunk/LibOPF/lib svn+ssh://afalcao@lutz.ic.unicamp.br/home/svnroot 2010-05-13T18:54:49.579159Z 44 guilhermeruppert@gmail.com 5c13e56e-d2c1-492d-b9d2-8850a87b4d6a LibOPF/README0000664000175000017500000005055312351344244012563 0ustar afalcaoafalcaoLibOPF is a library of functions and programs for free usage in the design of optimum-path forest classifiers. This second version contains some additional resources related to the supervised OPF classifier reported in reference [PapaIJIST09,PapaPR12], and also contains the unsupervised version of OPF reported in reference [RochaIJIST09]. A short explanation about the method can be found in http://www.ic.unicamp.br/~afalcao/LibOPF. Please read the COPYRIGHT file before using LibOPF. For large datasets (thousands/millions of samples), it is usually desirable to keep some maximum size for the training set. However, an evaluation set can improve the training samples during pseudo tests (learning procedure). Therefore, LibOPF provides a program to randomly split the dataset into training, evaluation and test sets (opf_split). One can project an OPF classifier by using the program 'opf_train' and test it by using the program 'opf_classify'. However, for large datasets, the program 'opf_learn' substitutes the 'opf_train' by learning from classification errors in the evaluation set without increasing the training set size. Afterwards, the classifier is tested by using 'opf_classify'. In the case of time-consuming distance functions, one can generate a precomputed distance file in the format specified in section 'opf_distance' Usage. LibOPF also provides a program (opf_distance) with some options of distance functions, which generates a precomputed distance file. Table of Contents ================= - Installation - OPF file format for datasets - Programs included SUPERVISED OPF - 'opf_split' Usage - 'opf_train' Usage - 'opf_learn' Usage - 'opf_classify' Usage - 'opf_accuracy' Usage UNSUPERVISED OPF - 'opf_cluster' Usage - 'opf_knn_classify' Usage COMMON (Auxiliary functions) - 'opf_distance' Usage - 'opf_normalize' Usage - 'opf_info' Usage - 'opf_fold' Usage - 'opf_merge' Usage - Datasets - Examples of scripts - Tools - Accuracy computation - Fixed bugs - Additional Information Installation ============ On Unix systems, decompress the LibOPF.tar.bz2 file (use tar -xvjf LibOPF.tar.bz2) into a directory. The system will create a directory named 'LibOPF'. Type 'cd LibOPF', and then type `make' to build the programs 'opf_split', 'opf_accuracy', 'opf_train', 'opf_learn', 'opf_distance', and 'opf_classify' into the /bin directory. Run them without arguments to show their usage. OPF file format for datasets ============================ The original dataset and its parts training, evaluation and test sets must be in the following BINARY file format: <# of samples> <# of labels> <# of features> <0>