CRNkMeans.h

Go to the documentation of this file.

/* Copyright 2007-2016 Yann LEYDIER, CoReNum, INSA-Lyon, ENS-Lyon
 * 
 * This file is part of libcrn.
 * 
 * libcrn is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * libcrn is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with libcrn.  If not, see <http://www.gnu.org/licenses/>.
 * 
 * file: CRNkMeans.h
 * \author Yann LEYDIER
 */

#ifndef CRNKMEANS_HEADER
#define CRNKMEANS_HEADER

#include <CRNAI/CRNBasicClassify.h>
#include <vector>
#include <random>

namespace crn
{
    /****************************************************************************/
    template<
        typename T,
        typename std::enable_if<IsMetric<typename std::result_of<decltype(Dereference<T>)&(const T&)>::type>::value, int>::type = 0,
        typename std::enable_if<IsVectorOverR<typename std::result_of<decltype(Dereference<T>)&(const T&)>::type>::value, int>::type = 0
        > class kMeans
    {
        public:
            using value_type = typename std::result_of<decltype(Dereference<T>)&(const T&)>::type;
            kMeans(const kMeans&) = delete;
            kMeans(kMeans&&) = default;
            kMeans& operator=(const kMeans&) = delete;
            kMeans& operator=(kMeans&&) = default;

            void AddPrototype(const T &sam)
            {
                proto.push_back(Dereference(sam));
            }
            void AddRandomPrototype()
            {
                const auto nb = GetNbSamples();
                if (!nb)
                    throw ExceptionNotFound("No sample available.");
                auto generator = std::default_random_engine{};
                auto distribution = std::uniform_int_distribution<size_t>{0, nb - 1};
                AddPrototype(data[distribution(generator)]);
            }
            size_t GetNbClasses() const noexcept { return proto.size(); }
            const std::vector<value_type>& GetPrototypes() const noexcept { return proto; }
            void ClearPrototypes() noexcept { proto.clear(); }

            void AddSample(const T &sam)
            {
                data.push_back(sam);
            }
            void AddSample(T &&sam)
            {
                data.push_back(std::move(sam));
            }
            size_t GetNbSamples() const noexcept { return data.size(); }
            const std::vector<const T>& GetSamples() const noexcept { return data; }
            void ClearSamples() noexcept { data.clear(); }

            size_t Run(size_t maxcnt = 100)
            {
                auto cnt = size_t(0);
                const auto k = proto.size();
                classes.clear();
                classes.resize(k);
                auto popclasses = std::vector<size_t>(k, 0);
                auto finished = false;
                while (!finished)
                {
                    for (auto &c : classes)
                        c.clear();
                    // for each sample
                    for (auto elnum = size_t(0); elnum < data.size(); ++elnum)
                    {
                        // classify
                        classes[Classify(*data[elnum])].push_back(elnum);
                    }
                    finished = true;
                    // for each class
                    for (auto p = size_t(0); p < k; p++)
                    {
                        // compute mean
                        auto sum = SumType<value_type>(Zero(*data.front()));
                        for (const auto &num : classes[p])
                            sum += *data[num];
                        proto[p] = value_type(sum * (1.0 / double(classes[p].size())));
                        // check if finished
                        if (popclasses[p] != classes[p].size())
                        {
                            popclasses[p] = classes[p].size();
                            finished = false;
                        }
                    }
                    cnt += 1;
                    if (cnt > maxcnt)
                        break;
                }
                return cnt;
            }

            size_t Classify(const value_type &obj, double *distance = nullptr)
            {
                if (proto.empty())
                    throw ExceptionDimension();
                auto res = BasicClassify::NearestNeighbor(obj, proto.begin(), proto.end());
                if (distance)
                    *distance = res.distance;
                return res.class_id;
            }

            const std::vector<size_t>& GetClass(size_t k) const
            {
                if (k >= classes.size())
                    throw ExceptionDimension("kMeans::GetClass(): Wrong class number.");
                return classes[k];
            }

        private:
            std::vector<const T> data; 
            std::vector<value_type> proto; 
            std::vector<std::vector<size_t>> classes; 
    };
}
#endif