bsas.py

"""!

@brief Cluster analysis algorithm: BSAS (Basic Sequential Algorithmic Scheme).
@details Implementation based on paper @cite book::pattern_recognition::2009.

@authors Andrei Novikov (pyclustering@yandex.ru)
@date 2014-2018
@copyright GNU Public License

@cond GNU_PUBLIC_LICENSE
    PyClustering 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.

    PyClustering 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 General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
@endcond

"""


from pyclustering.core.wrapper import ccore_library;
from pyclustering.core.bsas_wrapper import bsas as bsas_wrapper;
from pyclustering.core.metric_wrapper import metric_wrapper;

from pyclustering.cluster import cluster_visualizer;
from pyclustering.cluster.encoder import type_encoding;

from pyclustering.utils.metric import type_metric, distance_metric;


class bsas_visualizer:
    """!
    @brief Visualizer of BSAS algorithm's results.
    @details BSAS visualizer provides visualization services that are specific for BSAS algorithm.

    """

    @staticmethod
    def show_clusters(sample, clusters, representatives, **kwargs):
        """!
        @brief Display BSAS clustering results.

        @param[in] sample (list): Dataset that was used for clustering.
        @param[in] clusters (array_like): Clusters that were allocated by the algorithm.
        @param[in] representatives (array_like): Allocated representatives correspond to clusters.
        @param[in] **kwargs: Arbitrary keyword arguments (available arguments: 'figure', 'display', 'offset').

        <b>Keyword Args:</b><br>
            - figure (figure): If 'None' then new is figure is created, otherwise specified figure is used for visualization.
            - display (bool): If 'True' then figure will be shown by the method, otherwise it should be shown manually using matplotlib function 'plt.show()'.
            - offset (uint): Specify axes index on the figure where results should be drawn (only if argument 'figure' is specified).

        @return (figure) Figure where clusters were drawn.

        """

        figure = kwargs.get('figure', None);
        display = kwargs.get('display', True);
        offset = kwargs.get('offset', 0);

        visualizer = cluster_visualizer();
        visualizer.append_clusters(clusters, sample, canvas=offset);

        for cluster_index in range(len(clusters)):
            visualizer.append_cluster_attribute(offset, cluster_index, [representatives[cluster_index]], '*', 10);

        return visualizer.show(figure=figure, display=display);


class bsas:
    """!
    @brief Class represents BSAS clustering algorithm - basic sequential algorithmic scheme.
    @details Algorithm has two mandatory parameters: maximum allowable number of clusters and threshold
              of dissimilarity or in other words maximum distance between points. Distance metric also can
              be specified using 'metric' parameters, by default 'Manhattan' distance is used.
              BSAS using following rule for updating cluster representative:

    \f[
    \vec{m}_{C_{k}}^{new}=\frac{ \left ( n_{C_{k}^{new}} - 1 \right )\vec{m}_{C_{k}}^{old} + \vec{x} }{n_{C_{k}^{new}}}
    \f]

    Clustering results of this algorithm depends on objects order in input data.

    Example:
    @code
        # Read data sample from 'Simple02.data'.
        sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE2);

        # Prepare algorithm's parameters.
        max_clusters = 2;
        threshold = 1.0;

        # Create instance of BSAS algorithm.
        bsas_instance = bsas(sample, max_clusters, threshold);
        bsas_instance.process();

        # Get clustering results.
        clusters = bsas_instance.get_clusters();
        representatives = bsas_instance.get_representatives();

        # Display results.
        bsas_visualizer.show_clusters(sample, clusters, representatives);
    @endcode

    @see pyclustering.cluster.mbsas, pyclustering.cluster.ttsas

    """

    def __init__(self, data, maximum_clusters, threshold, ccore=True, **kwargs):
        """!
        @brief Creates classical BSAS algorithm.

        @param[in] data (list): Input data that is presented as list of points (objects), each point should be represented by list or tuple.
        @param[in] maximum_clusters: Maximum allowable number of clusters that can be allocated during processing.
        @param[in] threshold: Threshold of dissimilarity (maximum distance) between points.
        @param[in] ccore (bool): If True than DLL CCORE (C++ solution) will be used for solving.
        @param[in] **kwargs: Arbitrary keyword arguments (available arguments: 'metric').

        <b>Keyword Args:</b><br>
            - metric (distance_metric): Metric that is used for distance calculation between two points.

        """

        self._data = data;
        self._amount = maximum_clusters;
        self._threshold = threshold;
        self._metric = kwargs.get('metric', distance_metric(type_metric.EUCLIDEAN));
        self._ccore = ccore and self._metric.get_type() != type_metric.USER_DEFINED;

        self._clusters = [];
        self._representatives = [];

        if self._ccore is True:
            self._ccore = ccore_library.workable();


    def process(self):
        """!
        @brief Performs cluster analysis in line with rules of BSAS algorithm.

        @remark Results of clustering can be obtained using corresponding get methods.

        @see get_clusters()
        @see get_representatives()

        """

        if self._ccore is True:
            self.__process_by_ccore();
        else:
            self.__prcess_by_python();


    def __process_by_ccore(self):
        ccore_metric = metric_wrapper.create_instance(self._metric);
        self._clusters, self._representatives = bsas_wrapper(self._data, self._amount, self._threshold, ccore_metric.get_pointer());


    def __prcess_by_python(self):
        self._clusters.append([0]);
        self._representatives.append(self._data[0]);

        for i in range(1, len(self._data)):
            point = self._data[i];
            index_cluster, distance = self._find_nearest_cluster(point);

            if (distance > self._threshold) and (len(self._clusters) < self._amount):
                self._representatives.append(point);
                self._clusters.append([i]);
            else:
                self._clusters[index_cluster].append(i);
                self._update_representative(index_cluster, point);


    def get_clusters(self):
        """!
        @brief Returns list of allocated clusters, each cluster contains indexes of objects in list of data.

        @see process()
        @see get_representatives()

        """
        return self._clusters;


    def get_representatives(self):
        """!
        @brief Returns list of representatives of allocated clusters.

        @see process()
        @see get_clusters()

        """
        return self._representatives;


    def get_cluster_encoding(self):
        """!
        @brief Returns clustering result representation type that indicate how clusters are encoded.

        @return (type_encoding) Clustering result representation.

        @see get_clusters()

        """

        return type_encoding.CLUSTER_INDEX_LIST_SEPARATION;


    def _find_nearest_cluster(self, point):
        """!
        @brief Find nearest cluster to the specified point.

        @param[in] point (list): Point from dataset.

        @return (uint, double) Index of nearest cluster and distance to it.

        """
        index_cluster = -1;
        nearest_distance = float('inf');

        for index in range(len(self._representatives)):
            distance = self._metric(point, self._representatives[index]);
            if distance < nearest_distance:
                index_cluster = index;
                nearest_distance = distance;

        return index_cluster, nearest_distance;


    def _update_representative(self, index_cluster, point):
        """!
        @brief Update cluster representative in line with new cluster size and added point to it.

        @param[in] index_cluster (uint): Index of cluster whose representative should be updated.
        @param[in] point (list): Point that was added to cluster.

        """
        length = len(self._clusters[index_cluster]);
        rep = self._representatives[index_cluster];

        for dimension in range(len(rep)):
            rep[dimension] = ( (length - 1) * rep[dimension] + point[dimension] ) / length;