Changeset 8070:c48e8260b4b1 in orange


Ignore:
Timestamp:
07/05/11 10:58:45 (3 years ago)
Author:
ales_erjavec <ales.erjavec@…>
Branch:
default
Convert:
cfa38da5227c196c9cdb7a7573d4ea8bc59c1005
Message:

Undo the previous commit (will commit again when it works)

Location:
source/orange
Files:
1 added
8 deleted
5 edited

Legend:

Unmodified
Added
Removed
  • source/orange/Makefile

    r8069 r8070  
    1111    python ../pyxtract/jitlink_build.py R.so r_imports.hpp 
    1212 
     13obj/daxpy.o : blas/daxpy.c  
     14    $(CCOMPILER) $(COMPILEOPTIONS) -c blas/daxpy.c  -o obj/daxpy.o 
     15     
     16obj/ddot.o : blas/ddot.c  
     17    $(CCOMPILER) $(COMPILEOPTIONS) -c blas/ddot.c  -o obj/ddot.o 
    1318 
    14 # TODO: Dont compile BLAS if we can link with system (or user 
    15 # supplied) blas 
     19obj/dnrm2.o : blas/dnrm2.c  
     20    $(CCOMPILER) $(COMPILEOPTIONS) -c blas/dnrm2.c  -o obj/dnrm2.o 
    1621 
    17 BLAS_OBJECTS = obj/daxpy.o obj/ddot.o obj/dnrm2.o obj/dscal.o obj/dcopy.o 
    18      
    19 obj/%.o : blas/%.c blas/blas.h blas/blasp.h 
    20     $(CCOMPILER) $(COMPILEOPTIONS) -c $< -o $@ 
     22obj/dscal.o : blas/dscal.c  
     23    $(CCOMPILER) $(COMPILEOPTIONS) -c blas/dscal.c  -o obj/dscal.o 
    2124 
    22 LINPACK_OBJECTS = obj/dqrsl.o obj/dqrdc2.o obj/dtrsl.o obj/linpack.o 
     25BLAS_OBJECTS = obj/daxpy.o obj/ddot.o obj/dnrm2.o obj/dscal.o 
    2326 
    24 obj/%.o : linpack/%.c linpack/linpack.h 
    25     $(CCOMPILER) $(COMPILEOPTIONS) -c $< -o $@ 
    26  
    27 $(OLD)/orange.so:   ppp/stamp px/stamp $(ORANGE_OBJECTS) $(BLAS_OBJECTS) $(LINPACK_OBJECTS) 
    28     $(LINKER) $(ORANGE_OBJECTS) $(BLAS_OBJECTS) $(LINPACK_OBJECTS) $(LINKOPTIONS) -o $(OLD)/orange.so 
     27$(OLD)/orange.so:   ppp/stamp px/stamp $(ORANGE_OBJECTS) $(BLAS_OBJECTS) 
     28    $(LINKER) $(ORANGE_OBJECTS) $(BLAS_OBJECTS) $(LINKOPTIONS) -o $(OLD)/orange.so 
    2929ifeq ($(OS), Darwin) 
    3030    install_name_tool -id $(DESTDIR)/orange.so $(OLD)/orange.so 
  • source/orange/hclust.cpp

    r6531 r8070  
    554554  return restructure(root); 
    555555} 
     556 
     557 
     558/* 
     559 *  Optimal leaf ordering. 
     560 */ 
     561 
     562m_element::m_element(THierarchicalCluster * _cluster, int _left, int _right): 
     563    cluster(_cluster), left(_left), right(_right) 
     564{} 
     565 
     566m_element::m_element(const m_element & other): 
     567    cluster(other.cluster), left(other.left), right(other.right) 
     568{} 
     569 
     570bool m_element::operator< (const m_element & other) 
     571{ 
     572    if (cluster < other.cluster) 
     573        return true; 
     574    else 
     575        if (cluster == other.cluster) 
     576            if (left < other.left) 
     577                return true; 
     578            else 
     579                if (left == other.left) 
     580                    return right < other.right; 
     581                else 
     582                    return false; 
     583        else 
     584            return false; 
     585} 
     586 
     587ordering_element::ordering_element(): 
     588    left(NULL), u(-1), m(-1), 
     589    right(NULL), w(-1), k(-1) 
     590{} 
     591 
     592ordering_element::ordering_element(THierarchicalCluster * _left, 
     593        unsigned int _u, 
     594        unsigned _m, 
     595        THierarchicalCluster * _right, 
     596        unsigned int _w, 
     597        unsigned int _k 
     598    ): left(_left), u(_u), m(_m), 
     599       right(_right), w(_w), k(_k) 
     600{} 
     601 
     602ordering_element::ordering_element(const ordering_element & other): 
     603       left(other.left), u(other.u), m(other.m), 
     604       right(other.right), w(other.w), k(other.k) 
     605{} 
     606 
     607// Return the minimum distance between elements in matrix 
     608// 
     609float min_distance( 
     610        TIntList::iterator indices1_begin, 
     611        TIntList::iterator indices1_end, 
     612        TIntList::iterator indices2_begin, 
     613        TIntList::iterator indices2_end, 
     614        TSymMatrix & matrix) 
     615{ 
     616//  TIntList::iterator iter1 = indices1.begin(), iter2 = indices2.begin(); 
     617    float mininum = std::numeric_limits<float>::infinity(); 
     618    for (; indices1_begin != indices1_end; indices1_begin++) 
     619        for (; indices2_begin != indices2_end; indices2_begin++) 
     620            mininum = std::min(matrix.getitem(*indices1_begin, *indices2_begin), mininum); 
     621    return mininum; 
     622} 
     623 
     624 
     625struct CompareByScores 
     626{ 
     627    const join_scores & scores; 
     628    const THierarchicalCluster & cluster; 
     629    const int & fixed; 
     630 
     631    CompareByScores(const join_scores & _scores, const THierarchicalCluster & _cluster, const int & _fixed): 
     632        scores(_scores), cluster(_cluster), fixed(_fixed) 
     633    {} 
     634    bool operator() (int lhs, int rhs) 
     635    { 
     636        return scores[m_element(&cluster, fixed, lhs)] < scores[m_element(&cluster, fixed, rhs)]; 
     637    } 
     638}; 
     639 
     640// This needs to be called with all left, right pairs to 
     641// update all scores for cluster. 
     642#include <iostream> 
     643#include <cassert> 
     644 
     645void partial_opt_ordering( 
     646        THierarchicalCluster & cluster, 
     647        THierarchicalCluster & left, 
     648        THierarchicalCluster & right, 
     649        THierarchicalCluster & left_left, 
     650        THierarchicalCluster & left_right, 
     651        THierarchicalCluster & right_left, 
     652        THierarchicalCluster & right_right, 
     653        TSymMatrix &matrix, 
     654        join_scores & M, 
     655        cluster_ordering & ordering) 
     656{ 
     657    int u = 0, w = 0; 
     658    TIntList & mapping = cluster.mapping.getReference(); 
     659    for (TIntList::iterator u_iter = mapping.begin() + left_left.first; 
     660            u_iter != mapping.begin() + left_left.last; 
     661            u_iter++) 
     662        for (TIntList::iterator w_iter = mapping.begin() + right_right.first; 
     663                w_iter != mapping.begin() + right_right.last; 
     664                w_iter++) 
     665        { 
     666            u = *u_iter; w = *w_iter; 
     667            float curr_min = std::numeric_limits<float>::infinity(); 
     668            int curr_k = 0, curr_m = 0; 
     669            float C = min_distance(mapping.begin() + left_right.first, 
     670                    mapping.begin() + left_right.last, 
     671                    mapping.begin() + right_left.first, 
     672                    mapping.begin() + right_left.last, 
     673                    matrix); 
     674 
     675            vector<int> m_ordered(mapping.begin() + left_right.first, 
     676                    mapping.begin() + left_right.last); 
     677            vector<int> k_ordered(mapping.begin() + right_left.first, 
     678                    mapping.begin() + right_left.last); 
     679 
     680            std::sort(m_ordered.begin(), m_ordered.end(), CompareByScores(M, left, u)); 
     681            std::sort(k_ordered.begin(), k_ordered.end(), CompareByScores(M, right, w)); 
     682 
     683 
     684            int k0 = k_ordered.front(); 
     685            m_element m_right_k0(&right, w, k0); 
     686            int m = 0, k = 0; 
     687            for (vector<int>::iterator iter_m=m_ordered.begin(); iter_m != m_ordered.end(); iter_m++) 
     688            { 
     689                m = *iter_m; 
     690 
     691                m_element m_left(&left, u, m); 
     692 
     693                if (M[m_left] + M[m_right_k0] + C >= curr_min){ 
     694//                  M[m_element(&cluster, u, w)] = curr_min; 
     695                    break; 
     696                } 
     697                for (vector<int>::iterator iter_k = k_ordered.begin(); iter_k != k_ordered.end(); iter_k++) 
     698                { 
     699                    k = *iter_k; 
     700                    m_element m_right(&right, w, k); 
     701                    if (M[m_left] + M[m_right] + C >= curr_min) 
     702                    { 
     703                        break; 
     704                    } 
     705                    float test_val = M[m_left] + M[m_right] + matrix.getitem(m, k); 
     706                    if (curr_min > test_val) 
     707                    { 
     708                        curr_min = test_val; 
     709                        curr_k = k; 
     710                        curr_m = m; 
     711                    } 
     712                } 
     713 
     714            } 
     715 
     716            M[m_element(&cluster, u, w)] = curr_min; 
     717            M[m_element(&cluster, w, u)] = curr_min; 
     718 
     719            assert(M[m_element(&cluster, u, w)] == M[m_element(&cluster, u, w)]); 
     720            assert(M[m_element(&cluster, u, w)] == curr_min); 
     721 
     722//          assert(ordering.find(m_element(&cluster, u, w)) == ordering.end()); 
     723//          assert(ordering.find(m_element(&cluster, w, u)) == ordering.end()); 
     724 
     725            ordering[m_element(&cluster, u, w)] = ordering_element(&left, u, curr_m, &right, w, curr_k); 
     726            ordering[m_element(&cluster, w, u)] = ordering_element(&right, w, curr_k, &left, u, curr_m); 
     727        } 
     728} 
     729 
     730void THierarchicalClusterOrdering::order_clusters( 
     731        THierarchicalCluster & cluster, 
     732        TSymMatrix &matrix, 
     733        join_scores & M, 
     734        cluster_ordering & ordering) 
     735{ 
     736    if (cluster.size() == 1) 
     737    { 
     738        M[m_element(&cluster, cluster.mapping->at(cluster.first), cluster.mapping->at(cluster.first))] = 0.0; 
     739        return; 
     740    } 
     741 
     742    else if (cluster.branches->size() == 2) 
     743    { 
     744        PHierarchicalCluster left = cluster.branches->at(0); 
     745        PHierarchicalCluster right = cluster.branches->at(1); 
     746 
     747        order_clusters(left.getReference(), matrix, M, ordering); 
     748        order_clusters(right.getReference(), matrix, M, ordering); 
     749 
     750        PHierarchicalCluster  left_left = (!left->branches) ? left : left->branches->at(0); 
     751        PHierarchicalCluster  left_right = (!left->branches) ? left : left->branches->at(1); 
     752        PHierarchicalCluster  right_left = (!right->branches) ? right : right->branches->at(0); 
     753        PHierarchicalCluster  right_right = (!right->branches) ? right : right->branches->at(1); 
     754 
     755        partial_opt_ordering(cluster, 
     756                left.getReference(), right.getReference(), 
     757                left_left.getReference(), left_right.getReference(), 
     758                right_left.getReference(), right_right.getReference(), 
     759                matrix, M, ordering); 
     760 
     761        partial_opt_ordering(cluster, 
     762                left.getReference(), right.getReference(), 
     763                left_left.getReference(), left_right.getReference(), 
     764                right_right.getReference(), right_left.getReference(), 
     765                matrix, M, ordering); 
     766 
     767        partial_opt_ordering(cluster, 
     768                left.getReference(), right.getReference(), 
     769                left_right.getReference(), left_left.getReference(), 
     770                right_left.getReference(), right_right.getReference(), 
     771                matrix, M, ordering); 
     772 
     773        partial_opt_ordering(cluster, 
     774                left.getReference(), right.getReference(), 
     775                left_right.getReference(), left_left.getReference(), 
     776                right_right.getReference(), right_left.getReference(), 
     777                matrix, M, ordering); 
     778    } 
     779} 
     780 
     781/* Check if TIntList contains element. 
     782 */ 
     783bool contains(TIntList::iterator iter_begin, TIntList::iterator iter_end, int element) 
     784{ 
     785    return std::find(iter_begin, iter_end, element) != iter_end; 
     786} 
     787 
     788void THierarchicalClusterOrdering::optimal_swap(THierarchicalCluster * cluster, int u, int w, cluster_ordering & ordering) 
     789{ 
     790    if (cluster->branches) 
     791    { 
     792        assert(ordering.find(m_element(cluster, u, w)) != ordering.end()); 
     793        ordering_element ord = ordering[m_element(cluster, u, w)]; 
     794 
     795        PHierarchicalCluster left_right = (ord.left->branches)? ord.left->branches->at(1) : PHierarchicalCluster(NULL); 
     796        PHierarchicalCluster right_left = (ord.right->branches)? ord.right->branches->at(0) : PHierarchicalCluster(NULL); 
     797 
     798        TIntList & mapping = cluster->mapping.getReference(); 
     799        if (left_right && !contains(mapping.begin() + left_right->first, 
     800                mapping.begin() + left_right->last, ord.m)) 
     801        { 
     802            assert(!contains(mapping.begin() + left_right->first, 
     803                             mapping.begin() + left_right->last, ord.m)); 
     804            std::cout << "Swapping left " << ord.m << endl; 
     805            ord.left->swap(); 
     806            left_right = ord.left->branches->at(1); 
     807            assert(contains(mapping.begin() + left_right->first, 
     808                            mapping.begin() + left_right->last, ord.m)); 
     809        } 
     810        optimal_swap(ord.left, ord.u, ord.m, ordering); 
     811 
     812        assert(mapping.at(ord.left->first) == ord.u); 
     813        assert(mapping.at(ord.left->last - 1) == ord.m); 
     814 
     815        if (right_left && !contains(mapping.begin() + right_left->first, 
     816                mapping.begin() + right_left->last, ord.k)) 
     817        { 
     818            assert(!contains(mapping.begin() + right_left->first, 
     819                             mapping.begin() + right_left->last, ord.k)); 
     820            std::cout << "Swapping right " << ord.k << endl; 
     821            ord.right->swap(); 
     822            right_left = ord.right->branches->at(0); 
     823            assert(contains(mapping.begin() + right_left->first, 
     824                            mapping.begin() + right_left->last, ord.k)); 
     825        } 
     826        optimal_swap(ord.right, ord.k, ord.w, ordering); 
     827 
     828        assert(mapping.at(ord.right->first) == ord.k); 
     829        assert(mapping.at(ord.right->last - 1) == ord.w); 
     830 
     831        assert(mapping.at(cluster->first) == ord.u); 
     832        assert(mapping.at(cluster->last - 1) == ord.w); 
     833    } 
     834} 
     835 
     836PHierarchicalCluster THierarchicalClusterOrdering::operator() ( 
     837        PHierarchicalCluster root, 
     838        PSymMatrix matrix) 
     839{ 
     840    join_scores M; // scores 
     841    cluster_ordering ordering; 
     842    order_clusters(root.getReference(), matrix.getReference(), M, ordering); 
     843 
     844    int u = 0, w = 0; 
     845    int min_u = 0, min_w = 0; 
     846    float min_score = std::numeric_limits<float>::infinity(); 
     847    TIntList & mapping = root->mapping.getReference(); 
     848 
     849    for (TIntList::iterator u_iter = mapping.begin() + root->branches->at(0)->first; 
     850            u_iter != mapping.begin() + root->branches->at(0)->last; 
     851            u_iter++) 
     852        for (TIntList::iterator w_iter = mapping.begin() + root->branches->at(1)->first; 
     853                    w_iter != mapping.begin() + root->branches->at(1)->last; 
     854                    w_iter++) 
     855        { 
     856            u = *u_iter; w = *w_iter; 
     857            m_element el(root.getUnwrappedPtr(), u, w); 
     858            if (M[el] < min_score) 
     859            { 
     860                min_score = M[el]; 
     861                min_u = u; 
     862                min_w = w; 
     863            } 
     864        } 
     865//  std::cout << "Min score "<< min_score << endl; 
     866 
     867    optimal_swap(root.getUnwrappedPtr(), min_u, min_w, ordering); 
     868    return root; 
     869} 
  • source/orange/hclust.hpp

    r6531 r8070  
    5353    void permute(const TIntList &newOrder); 
    5454 
     55    unsigned int size(){ return last - first; } 
     56 
    5557protected: 
    5658    void recursiveMove(const int &offset); 
     
    8284    TClusterW *THierarchicalClustering::merge_AverageLinkage(TClusterW **clusters, float *callbackMilestones); 
    8385    // Average linkage also computes Ward's linkage 
     86 
     87private: 
     88    PHierarchicalCluster order_leaves(PHierarchicalCluster root, PSymMatrix matrix, PProgressCallback progress_callback); 
     89}; 
     90 
     91 
     92/* 
     93 * Optimal leaf ordering. 
     94 */ 
     95 
     96struct m_element { 
     97    THierarchicalCluster * cluster; 
     98    int left; 
     99    int right; 
     100 
     101    m_element(THierarchicalCluster * cluster, int left, int right); 
     102    m_element(const m_element & other); 
     103 
     104    bool operator< (const m_element & other); 
     105}; // cluster joined at left and right index 
     106 
     107struct ordering_element { 
     108    THierarchicalCluster * left; 
     109    unsigned int u; // the left most (outer) index of left luster 
     110    unsigned m; // the rightmost (inner) index of left cluster 
     111    THierarchicalCluster * right; 
     112    unsigned int w; // the right most (outer) index of the right cluster 
     113    unsigned int k; // the left most (inner) index of the right cluster 
     114 
     115    ordering_element(); 
     116    ordering_element(THierarchicalCluster * left, unsigned int u, unsigned m, 
     117            THierarchicalCluster * right, unsigned int w, unsigned int k); 
     118    ordering_element(const ordering_element & other); 
     119}; 
     120 
     121typedef std::map<m_element, double> join_scores; 
     122typedef std::map<m_element, ordering_element> cluster_ordering; 
     123 
     124class ORANGE_API THierarchicalClusterOrdering: public TOrange { 
     125public: 
     126    __REGISTER_CLASS 
     127 
     128    PProgressCallback progressCallback; //P progress callback function 
     129 
     130    PHierarchicalCluster operator() (PHierarchicalCluster root, PSymMatrix matrix); 
     131 
     132private: 
     133    void order_clusters(THierarchicalCluster & cluster, TSymMatrix &matrix, join_scores & M, cluster_ordering & ordering); 
     134    void optimal_swap(THierarchicalCluster * cluster, int u, int w, cluster_ordering & ordering); 
    84135}; 
    85136 
  • source/orange/lib_components.cpp

    r7715 r8070  
    35423542C_CALL3(HierarchicalClustering - Orange.clustering.hierarchical.HierarchicalClustering, HierarchicalClustering, Orange, "(linkage=)") 
    35433543 
     3544C_CALL3(HierarchicalClusterOrdering - Orange.clustering.hierarchical.HierarchicalClusterOrdering, HierarchicalClusterOrdering, Orange, "(progressCallback=)") 
     3545 
    35443546PyObject *HierarchicalClustering_call(PyObject *self, PyObject *args, PyObject *keywords) PYDOC("(distance matrix) -> HierarchicalCluster") 
    35453547{ 
     
    35673569} 
    35683570 
     3571PyObject * HierarchicalClusterOrdering_call(PyObject *self, PyObject *args, PyObject *keywords) PYDOC("(hierarchical cluster, distance_matrix) -> None") 
     3572{ 
     3573    PyTRY 
     3574        NO_KEYWORDS 
     3575        PHierarchicalCluster root; 
     3576        PSymMatrix matrix; 
     3577        if (!PyArg_ParseTuple(args, "O&O&:HierarchicalClustering", cc_HierarchicalCluster, &root, cc_SymMatrix, &matrix)) 
     3578            return NULL; 
     3579        SELF_AS(THierarchicalClusterOrdering).operator ()(root, matrix); 
     3580        RETURN_NONE 
     3581    PyCATCH 
     3582} 
    35693583 
    35703584Py_ssize_t HierarchicalCluster_len_sq(PyObject *self) 
  • source/orange/lib_learner.cpp

    r8069 r8070  
    15031503} 
    15041504 
    1505  
    1506 /************ EARTH (MARS) ******/ 
    1507 #include "earth.hpp" 
    1508  
    1509 C_CALL(EarthLearner - Orange.core.EarthLearner, Learner, "([examples], [weight=] -/-> Classifier)") 
    1510 C_NAMED(EarthClassifier - Orange.core.EarthClassifier, ClassifierFD, " ") 
    1511  
    1512 PyObject *EarthClassifier_formatEarth(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "() -> None") 
    1513 { 
    1514     PyTRY 
    1515     CAST_TO(TEarthClassifier, classifier); 
    1516     classifier->format_earth(); 
    1517     RETURN_NONE; 
    1518     PyCATCH 
    1519 } 
    1520  
     1505     
    15211506     
    15221507/************* BAYES ************/ 
Note: See TracChangeset for help on using the changeset viewer.