KNN.h

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Written (W) 2006 Christian Gehl
 * Written (W) 1999-2009 Soeren Sonnenburg
 * Written (W) 2011 Sergey Lisitsyn
 * Written (W) 2012 Fernando José Iglesias García, cover tree support
 * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
 */

#ifndef _KNN_H__
#define _KNN_H__

#include <shogun/lib/config.h>

#include <shogun/lib/common.h>
#include <shogun/io/SGIO.h>
#include <shogun/features/Features.h>
#include <shogun/distance/Distance.h>
#include <shogun/machine/DistanceMachine.h>

namespace shogun
{
    enum KNN_SOLVER
    {
        KNN_BRUTE,
        KNN_KDTREE,
        KNN_COVER_TREE,
#ifdef HAVE_CXX11
        KNN_LSH
#endif
    };

class CDistanceMachine;

class CKNN : public CDistanceMachine
{
    public:
        MACHINE_PROBLEM_TYPE(PT_MULTICLASS)

        
        CKNN();

        CKNN(int32_t k, CDistance* d, CLabels* trainlab, KNN_SOLVER knn_solver=KNN_BRUTE);

        virtual ~CKNN();

        virtual EMachineType get_classifier_type() { return CT_KNN; }

        SGMatrix<index_t> nearest_neighbors();

        virtual CMulticlassLabels* apply_multiclass(CFeatures* data=NULL);

        virtual float64_t apply_one(int32_t vec_idx)
        {
            SG_ERROR("for performance reasons use apply() instead of apply(int32_t vec_idx)\n")
            return 0;
        }

        SGMatrix<int32_t> classify_for_multiple_k();

        virtual bool load(FILE* srcfile);

        virtual bool save(FILE* dstfile);

        inline void set_k(int32_t k)
        {
            ASSERT(k>0)
            m_k=k;
        }

        inline int32_t get_k()
        {
            return m_k;
        }

        inline void set_q(float64_t q)
        {
            ASSERT(q<=1.0 && q>0.0)
            m_q = q;
        }

        inline float64_t get_q() { return m_q; }

        inline int32_t get_leaf_size() const {return m_leaf_size; }

        inline void set_leaf_size(int32_t leaf_size)
        {
            m_leaf_size = leaf_size;
        }

        virtual const char* get_name() const { return "KNN"; }

        inline KNN_SOLVER get_knn_solver_type()
        {
            return m_knn_solver;
        }

        inline void set_knn_solver_type(KNN_SOLVER knn_solver)
        {
            m_knn_solver = knn_solver;
        }

#ifdef HAVE_CXX11

        inline void set_lsh_parameters(int32_t l, int32_t t)
        {
            m_lsh_l = l;
            m_lsh_t = t;
        }
#endif

    protected:
        virtual void store_model_features();

        virtual CMulticlassLabels* classify_NN();

        void init_distance(CFeatures* data);

        virtual bool train_machine(CFeatures* data=NULL);

    private:
        void init();

        int32_t choose_class(float64_t* classes, int32_t* train_lab);

        void choose_class_for_multiple_k(int32_t* output, int32_t* classes, int32_t* train_lab, int32_t step);

    protected:
        int32_t m_k;

        float64_t m_q;

        int32_t m_num_classes;

        int32_t m_min_label;

        SGVector<int32_t> m_train_labels;

        KNN_SOLVER m_knn_solver;

        int32_t m_leaf_size;

#ifdef HAVE_CXX11
        /* Number of hash tables for LSH */
        int32_t m_lsh_l;

        /* Number of probes per query for LSH */
        int32_t m_lsh_t;
#endif
};

}
#endif