#NEWLINE# def linkage( y , method = 'single' , metric = 'euclidean' ) : #NEWLINE# #INDENT# '\n    Performs hierarchical/agglomerative clustering on the condensed\n    distance matrix y.\n\n    y must be a :math:`{n \\choose 2}` sized\n    vector where n is the number of original observations paired\n    in the distance matrix. The behavior of this function is very\n    similar to the MATLAB linkage function.\n\n    An :math:`(n-1)` by 4  matrix ``Z`` is returned. At the\n    :math:`i`-th iteration, clusters with indices ``Z[i, 0]`` and\n    ``Z[i, 1]`` are combined to form cluster :math:`n + i`. A\n    cluster with an index less than :math:`n` corresponds to one of\n    the :math:`n` original observations. The distance between\n    clusters ``Z[i, 0]`` and ``Z[i, 1]`` is given by ``Z[i, 2]``. The\n    fourth value ``Z[i, 3]`` represents the number of original\n    observations in the newly formed cluster.\n\n    The following linkage methods are used to compute the distance\n    :math:`d(s, t)` between two clusters :math:`s` and\n    :math:`t`. The algorithm begins with a forest of clusters that\n    have yet to be used in the hierarchy being formed. When two\n    clusters :math:`s` and :math:`t` from this forest are combined\n    into a single cluster :math:`u`, :math:`s` and :math:`t` are\n    removed from the forest, and :math:`u` is added to the\n    forest. When only one cluster remains in the forest, the algorithm\n    stops, and this cluster becomes the root.\n\n    A distance matrix is maintained at each iteration. The ``d[i,j]``\n    entry corresponds to the distance between cluster :math:`i` and\n    :math:`j` in the original forest.\n\n    At each iteration, the algorithm must update the distance matrix\n    to reflect the distance of the newly formed cluster u with the\n    remaining clusters in the forest.\n\n    Suppose there are :math:`|u|` original observations\n    :math:`u[0], \\ldots, u[|u|-1]` in cluster :math:`u` and\n    :math:`|v|` original objects :math:`v[0], \\ldots, v[|v|-1]` in\n    cluster :math:`v`. Recall :math:`s` and :math:`t` are\n    combined to form cluster :math:`u`. Let :math:`v` be any\n    remaining cluster in the forest that is not :math:`u`.\n\n    The following are methods for calculating the distance between the\n    newly formed cluster :math:`u` and each :math:`v`.\n\n      * method=\'single\' assigns\n\n        .. math::\n           d(u,v) = \\min(dist(u[i],v[j]))\n\n        for all points :math:`i` in cluster :math:`u` and\n        :math:`j` in cluster :math:`v`. This is also known as the\n        Nearest Point Algorithm.\n\n      * method=\'complete\' assigns\n\n        .. math::\n           d(u, v) = \\max(dist(u[i],v[j]))\n\n        for all points :math:`i` in cluster u and :math:`j` in\n        cluster :math:`v`. This is also known by the Farthest Point\n        Algorithm or Voor Hees Algorithm.\n\n      * method=\'average\' assigns\n\n        .. math::\n           d(u,v) = \\sum_{ij} \\frac{d(u[i], v[j])}\n                                   {(|u|*|v|)}\n\n        for all points :math:`i` and :math:`j` where :math:`|u|`\n        and :math:`|v|` are the cardinalities of clusters :math:`u`\n        and :math:`v`, respectively. This is also called the UPGMA\n        algorithm.\n\n      * method=\'weighted\' assigns\n\n        .. math::\n           d(u,v) = (dist(s,v) + dist(t,v))/2\n\n        where cluster u was formed with cluster s and t and v\n        is a remaining cluster in the forest. (also called WPGMA)\n\n      * method=\'centroid\' assigns\n\n        .. math::\n           dist(s,t) = ||c_s-c_t||_2\n\n        where :math:`c_s` and :math:`c_t` are the centroids of\n        clusters :math:`s` and :math:`t`, respectively. When two\n        clusters :math:`s` and :math:`t` are combined into a new\n        cluster :math:`u`, the new centroid is computed over all the\n        original objects in clusters :math:`s` and :math:`t`. The\n        distance then becomes the Euclidean distance between the\n        centroid of :math:`u` and the centroid of a remaining cluster\n        :math:`v` in the forest. This is also known as the UPGMC\n        algorithm.\n\n      * method=\'median\' assigns :math:`d(s,t)` like the ``centroid``\n        method. When two clusters :math:`s` and :math:`t` are combined\n        into a new cluster :math:`u`, the average of centroids s and t\n        give the new centroid :math:`u`. This is also known as the\n        WPGMC algorithm.\n\n      * method=\'ward\' uses the Ward variance minimization algorithm.\n        The new entry :math:`d(u,v)` is computed as follows,\n\n        .. math::\n\n           d(u,v) = \\sqrt{\\frac{|v|+|s|}\n                               {T}d(v,s)^2\n                        + \\frac{|v|+|t|}\n                               {T}d(v,t)^2\n                        - \\frac{|v|}\n                               {T}d(s,t)^2}\n\n        where :math:`u` is the newly joined cluster consisting of\n        clusters :math:`s` and :math:`t`, :math:`v` is an unused\n        cluster in the forest, :math:`T=|v|+|s|+|t|`, and\n        :math:`|*|` is the cardinality of its argument. This is also\n        known as the incremental algorithm.\n\n    Warning: When the minimum distance pair in the forest is chosen, there\n    may be two or more pairs with the same minimum distance. This\n    implementation may chose a different minimum than the MATLAB\n    version.\n\n    Parameters\n    ----------\n    y : ndarray\n        A condensed or redundant distance matrix. A condensed distance matrix\n        is a flat array containing the upper triangular of the distance matrix.\n        This is the form that ``pdist`` returns. Alternatively, a collection of\n        :math:`m` observation vectors in n dimensions may be passed as an\n        :math:`m` by :math:`n` array.\n    method : str, optional\n        The linkage algorithm to use. See the ``Linkage Methods`` section below\n        for full descriptions.\n    metric : str or function, optional\n        The distance metric to use in the case that y is a collection of\n        observation vectors; ignored otherwise. See the ``distance.pdist``\n        function for a list of valid distance metrics. A custom distance\n        function can also be used. See the ``distance.pdist`` function for\n        details.\n\n    Returns\n    -------\n    Z : ndarray\n        The hierarchical clustering encoded as a linkage matrix.\n\n    Notes\n    -----\n    1. For method \'single\' an optimized algorithm called SLINK is implemented,\n       which has :math:`O(n^2)` time complexity.\n       For methods \'complete\', \'average\', \'weighted\' and \'ward\' an algorithm\n       called nearest-neighbors chain is implemented, which too has time\n       complexity :math:`O(n^2)`.\n       For other methods a naive algorithm is implemented with :math:`O(n^3)`\n       time complexity.\n       All algorithms use :math:`O(n^2)` memory.\n       Refer to [1]_ for details about the algorithms.\n    2. Methods \'centroid\', \'median\' and \'ward\' are correctly defined only if\n       Euclidean pairwise metric is used. If `y` is passed as precomputed\n       pairwise distances, then it is a user responsibility to assure that\n       these distances are in fact Euclidean, otherwise the produced result\n       will be incorrect.\n\n    References\n    ----------\n    .. [1] Daniel Mullner, "Modern hierarchical, agglomerative clustering\n           algorithms", `arXiv:1109.2378v1 <http://arxiv.org/abs/1109.2378v1>`_\n           , 2011.\n    ' #NEWLINE# if ( method not in _LINKAGE_METHODS ) : #NEWLINE# #INDENT# raise ValueError ( 'Invalid method: {0}' . format ( method ) ) #NEWLINE# #UNINDENT# y = _convert_to_double ( np . asarray ( y , order = 'c' ) ) #NEWLINE# if ( y . ndim == 1 ) : #NEWLINE# #INDENT# distance . is_valid_y ( y , throw = True , name = 'y' ) #NEWLINE# [ y ] = _copy_arrays_if_base_present ( [ y ] ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( y . ndim == 2 ) : #NEWLINE# #INDENT# if ( ( method in _EUCLIDEAN_METHODS ) and ( metric != 'euclidean' ) ) : #NEWLINE# #INDENT# raise ValueError ( "Method '{0}' requires the distance metric to be Euclidean" . format ( method ) ) #NEWLINE# #UNINDENT# y = distance . pdist ( y , metric ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# raise ValueError ( '`y` must be 1 or 2 dimensional.' ) #NEWLINE# #UNINDENT# #UNINDENT# n = int ( distance . num_obs_y ( y ) ) #NEWLINE# method_code = _LINKAGE_METHODS [ method ] #NEWLINE# if ( method == 'single' ) : #NEWLINE# #INDENT# return _hierarchy . slink ( y , n ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( metric in [ 'complete' , 'average' , 'weighted' , 'ward' ] ) : #NEWLINE# #INDENT# return _hierarchy . nn_chain ( y , n , method_code ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# return _hierarchy . linkage ( y , n , method_code )