The clusters Reference Manual

Table of Contents

The clusters Reference Manual

This is the clusters Reference Manual, version 1.0.0, generated automatically by Declt version 3.0 "Montgomery Scott" on Sun May 15 04:27:16 2022 GMT+0.

1 Introduction

clusters

Variety of clustering tools for the Common Lisp

Distances

Package clusters.distance presentes distance functions, intended for use in clustering algorithms. This includes:

• bhattacharyya
• sinkhorn

Metrics

Package clusters.metric also presents functions intended for use in clustering algorithms, However, these functions also happen to be true metrics.

• average
• group-average
• earth-mover
• euclid
• hausdorff
• hellinger
• lcs
• levenshtein
• svr

Clustering algorithms

Each clustering algorithm has its own package exporting PARAMETERS symbol. This symbol names the class used to hold the algorithm parameters. To use the algorithm, first construct instance of this class, then call CLUSTER function passing the PARAMETERS instance into it along with the DATA. The returned object contains the clusters, and they can be extracted using the CLUSTER-CONTENTS function. The following example has been taken from the tests.

(defun metric (a b)
  (coerce (abs (- a b))
          'single-float))

(let* ((data (~> (concatenate 'vector
                              (iota 100 :start 0)
                              (iota 300 :start 500)
                              (iota 100 :start 200))
                 shuffle))
       (parameters (make-instance 'clusters.clarans:parameters
                                  :parallelp nil
                                  :medoids-count 10
                                  :max-neighbor 200
                                  :distance-function #'metric))
       (clusters (clusters:cluster parameters data))
       (cluster-contents (clusters:cluster-contents clusters)))
    ...)

All PARAMETERS classes contain slots intended bootsrapping silhouette values for the clusters. To obtain the silhouette value from the clustering results simply call the CLUSTERS:SILHOUETTE function. This is particulary useful if you are attempting to find the optimal number of clusters.

PARALLELP

Majority of the algorithms in this system have rudementary parallelization, made with the ever so useful LPARALLEL library. Please notice, that this means that (unless you are certain that NIL has been passed as :PARALLELP value) you must avoid calling CLUSTER on the LPARALLEL worker thread. Otherwise: deadlocks.

Silhouette

You can use clusters:silhouette to obtain silhouette values for each of the constructed clusters.

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 clusters

Maintainer

Marek Kochanowicz

Author

Marek Kochanowicz

License

BSD simplified

Description

Cluster algorithms in CL, for CL.

Version

1.0.0

Dependencies

• iterate
• alexandria
• serapeum
• documentation-utils-extensions
• metabang-bind
• bordeaux-threads
• lparallel
• cl-data-structures

Source

clusters.asd (file)

Components

• aux-package.lisp (file)
• utils (module)
• metric (module)
• distance (module)
• common (module)
• pam (module)
• clarans (module)
• k-means (module)

3 Modules

Modules are listed depth-first from the system components tree.

3.1 clusters/utils

Dependency

aux-package.lisp (file)

Parent

clusters (system)

Location

utils/

Components

• package.lisp (file)
• maps.lisp (file)
• matrix.lisp (file)
• random.lisp (file)
• utils.lisp (file)
• partition.lisp (file)

3.2 clusters/metric

Dependency

utils (module)

Parent

clusters (system)

Location

metric/

Components

• package.lisp (file)
• docstrings.lisp (file)
• euclid.lisp (file)
• svr.lisp (file)
• levenshtein.lisp (file)
• lcs.lisp (file)
• hellinger.lisp (file)
• earth-mover.lisp (file)
• average.lisp (file)
• group-average.lisp (file)
• hausdorff.lisp (file)

3.3 clusters/distance

Dependency

metric (module)

Parent

clusters (system)

Location

distance/

Components

• package.lisp (file)
• docstrings.lisp (file)
• bhattacharyya.lisp (file)
• sinkhorn.lisp (file)

3.4 clusters/common

Dependency

distance (module)

Parent

clusters (system)

Location

common/

Components

• package.lisp (file)
• generics.lisp (file)
• types.lisp (file)
• utils.lisp (file)
• functions.lisp (file)
• silhouette.lisp (file)
• methods.lisp (file)

3.5 clusters/pam

Dependency

common (module)

Parent

clusters (system)

Location

pam/

Components

• package.lisp (file)
• generics.lisp (file)
• types.lisp (file)
• utils.lisp (file)
• methods.lisp (file)

3.6 clusters/clarans

Dependency

pam (module)

Parent

clusters (system)

Location

clarans/

Components

• package.lisp (file)
• generics.lisp (file)
• types.lisp (file)
• utils.lisp (file)
• methods.lisp (file)

3.7 clusters/k-means

Dependency

clarans (module)

Parent

clusters (system)

Location

k-means/

Components

• package.lisp (file)
• types.lisp (file)
• utils.lisp (file)
• methods.lisp (file)

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.

4.1 Lisp

4.1.1 clusters.asd

Location

/home/quickref/quicklisp/dists/quicklisp/software/clusters-20220331-git/clusters.asd

Systems

clusters (system)

4.1.2 clusters/aux-package.lisp

Parent

clusters (system)

Location

aux-package.lisp

Packages

• clusters.aux-package
• clusters.fancy

Exported Definitions

defpackage (macro)

4.1.3 clusters/utils/package.lisp

Parent

utils (module)

Location

utils/package.lisp

Packages

clusters.utils

4.1.4 clusters/utils/maps.lisp

Parent

utils (module)

Location

utils/maps.lisp

Exported Definitions

• pmap (function)
• pmap-into (function)
• transform (function)

4.1.5 clusters/utils/matrix.lisp

Parent

utils (module)

Location

utils/matrix.lisp

Exported Definitions

• distance-matrix (function)
• half-matrix-index->square-row/column (function)
• half-matrix-size->count (function)
• make-half-matrix (function)
• map-into-half-matrix (function)
• mref (function)
• (setf mref) (function)
• square-row/column->half-matrix-index (function)

Internal Definitions

• column-index (function)
• count->half-matrix-size (function)
• element-in-i-rows (function)
• row-index (function)

4.1.6 clusters/utils/random.lisp

Parent

utils (module)

Location

utils/random.lisp

Exported Definitions

• draw-random-vector (function)
• lazy-shuffle (function)

4.1.7 clusters/utils/utils.lisp

Parent

utils (module)

Location

utils/utils.lisp

Exported Definitions

• copy-into (function)
• swap-if (function)

4.1.8 clusters/utils/partition.lisp

Parent

utils (module)

Location

utils/partition.lisp

Exported Definitions

seed (function)

4.1.9 clusters/metric/package.lisp

Parent

metric (module)

Location

metric/package.lisp

Packages

clusters.metric

4.1.10 clusters/metric/docstrings.lisp

Parent

metric (module)

Location

metric/docstrings.lisp

4.1.11 clusters/metric/euclid.lisp

Parent

metric (module)

Location

metric/euclid.lisp

Exported Definitions

euclid (function)

4.1.12 clusters/metric/svr.lisp

Parent

metric (module)

Location

metric/svr.lisp

Exported Definitions

svr (function)

Internal Definitions

• array-sum (function)
• count-of-all-possible-subvectors-upto-length (function)
• grid-mapping (function)
• same-events (function)
• update-grid (function)
• with-grid-mapping-resources (macro)

4.1.13 clusters/metric/levenshtein.lisp

Parent

metric (module)

Location

metric/levenshtein.lisp

Exported Definitions

levenshtein (function)

4.1.14 clusters/metric/lcs.lisp

Parent

metric (module)

Location

metric/lcs.lisp

Exported Definitions

lcs (function)

4.1.15 clusters/metric/hellinger.lisp

Parent

metric (module)

Location

metric/hellinger.lisp

Exported Definitions

hellinger (function)

Internal Definitions

+sqrt2+ (constant)

4.1.16 clusters/metric/earth-mover.lisp

Parent

metric (module)

Location

metric/earth-mover.lisp

Internal Definitions

earth-mover-metric (function)

4.1.17 clusters/metric/average.lisp

Parent

metric (module)

Location

metric/average.lisp

Exported Definitions

average (function)

4.1.18 clusters/metric/group-average.lisp

Parent

metric (module)

Location

metric/group-average.lisp

Exported Definitions

group-average (function)

4.1.19 clusters/metric/hausdorff.lisp

Parent

metric (module)

Location

metric/hausdorff.lisp

Exported Definitions

hausdorff (function)

4.1.20 clusters/distance/package.lisp

Parent

distance (module)

Location

distance/package.lisp

Packages

clusters.distance

4.1.21 clusters/distance/docstrings.lisp

Parent

distance (module)

Location

distance/docstrings.lisp

4.1.22 clusters/distance/bhattacharyya.lisp

Parent

distance (module)

Location

distance/bhattacharyya.lisp

Exported Definitions

bhattacharyya (function)

4.1.23 clusters/distance/sinkhorn.lisp

Parent

distance (module)

Location

distance/sinkhorn.lisp

Exported Definitions

sinkhorn (function)

Internal Definitions

• max-condition (function)
• sinkhorn-optimal-transport-matrix (function)
• sum-row (function)

4.1.24 clusters/common/package.lisp

Parent

common (module)

Location

common/package.lisp

Packages

clusters

4.1.25 clusters/common/generics.lisp

Parent

common (module)

Location

common/generics.lisp

Exported Definitions

• algorithm-state-class (generic function)
• algorithm-state-initialization-list (generic function)
• calculate-silhouette* (generic function)
• cluster-contents (generic function)
• cluster-indexes (generic function)
• data (generic function)
• (setf data) (generic function)
• indexes (generic function)
• (setf indexes) (generic function)
• key-function (generic function)
• parameters (generic function)
• result-class (generic function)
• result-initialization-list (generic function)
• run-algorithm (generic function)
• silhouette (generic function)

Internal Definitions

parallel-p (generic function)

4.1.26 clusters/common/types.lisp

Parent

common (module)

Location

common/types.lisp

Exported Definitions

• algorithm-state (class)
• cluster-indexes (method)
• data (method)
• data (method)
• (setf data) (method)
• indexes (method)
• (setf indexes) (method)
• indexes (method)
• key-function (method)
• parallelp (method)
• parameters (method)
• parameters (class)
• result (class)
• silhouette (method)
• silhouette-sample-count (method)
• silhouette-sample-size (method)

Internal Definitions

parameters-holder (class)

4.1.27 clusters/common/utils.lisp

Parent

common (module)

Location

common/utils.lisp

Internal Definitions

cluster-values (function)

4.1.28 clusters/common/functions.lisp

Parent

common (module)

Location

common/functions.lisp

Exported Definitions

• calculate-silhouette (function)
• cluster (function)
• make-algorithm-state (function)
• obtain-result (function)

4.1.29 clusters/common/silhouette.lisp

Parent

common (module)

Location

common/silhouette.lisp

Exported Definitions

silhouette (method)

Internal Definitions

• average-distance-to-element (function)
• distance-matrix (function)
• inter-cluster-distances (function)
• intra-cluster-distances (function)
• select-random-cluster-subsets (function)

4.1.30 clusters/common/methods.lisp

Parent

common (module)

Location

common/methods.lisp

Exported Definitions

• algorithm-state-initialization-list (method)
• calculate-silhouette* (method)
• cluster-contents (method)
• distance-function (method)
• key-function (method)
• parallelp (method)
• result-class (method)
• result-class (method)
• result-initialization-list (method)
• silhouette-sample-count (method)
• silhouette-sample-size (method)

4.1.31 clusters/pam/package.lisp

Parent

pam (module)

Location

pam/package.lisp

Packages

clusters.pam

4.1.32 clusters/pam/generics.lisp

Parent

pam (module)

Location

pam/generics.lisp

4.1.33 clusters/pam/types.lisp

Parent

pam (module)

Location

pam/types.lisp

Exported Definitions

parameters (class)

Internal Definitions

• access-cluster-contents (method)
• (setf access-cluster-contents) (method)
• access-cluster-size (method)
• (setf access-cluster-size) (method)
• access-distance-matrix (method)
• (setf access-distance-matrix) (method)
• access-medoids-count (method)
• (setf access-medoids-count) (method)
• access-unfinished-clusters (method)
• (setf access-unfinished-clusters) (method)
• algorithm-state (class)
• medoids-count (method)
• (setf medoids-count) (method)
• merge-threshold (method)
• (setf merge-threshold) (method)
• pam-result (class)
• read-distance-matrix (method)
• read-medoids-count (method)
• read-medoids-count (method)
• read-merge-threshold (method)
• read-select-medoids-attempts-count (method)
• read-split-merge-attempts-count (method)
• read-split-threshold (method)
• select-medoids-attempts-count (method)
• (setf select-medoids-attempts-count) (method)
• split-merge-attempts-count (method)
• (setf split-merge-attempts-count) (method)
• split-threshold (method)
• (setf split-threshold) (method)

4.1.34 clusters/pam/utils.lisp

Parent

pam (module)

Location

pam/utils.lisp

Internal Definitions

• assign-data-points-to-medoids (method)
• build-clusters (function)
• choose-effective-medoid (function)
• choose-effective-medoids (function)
• choose-initial-medoids (function)
• clear-cluster-contents (function)
• clear-unfinished-clusters (function)
• closest-medoid (function)
• fill-reclustering-index-vector (function)
• medoidp (function)
• order-medoids (function)
• prepare-reclustering-index-vector (function)
• recluster-clusters-of-invalid-size (function)
• reset (function)
• scan-for-clusters-of-invalid-size (function)
• unfinished-clusters-p (function)

4.1.35 clusters/pam/methods.lisp

Parent

pam (module)

Location

pam/methods.lisp

Exported Definitions

• algorithm-state-class (method)
• algorithm-state-initialization-list (method)
• calculate-silhouette* (method)
• result-class (method)
• result-initialization-list (method)
• run-algorithm (method)

Internal Definitions

• read-merge-threshold (method)
• read-select-medoids-attempts-count (method)
• read-split-merge-attempts-count (method)
• read-split-threshold (method)

4.1.36 clusters/clarans/package.lisp

Parent

clarans (module)

Location

clarans/package.lisp

Packages

clusters.clarans

4.1.37 clusters/clarans/generics.lisp

Parent

clarans (module)

Location

clarans/generics.lisp

Internal Definitions

• d (generic function)
• (setf d) (generic function)
• distortion (generic function)
• (setf distortion) (generic function)
• medoids (generic function)
• (setf medoids) (generic function)
• y (generic function)
• (setf y) (generic function)

4.1.38 clusters/clarans/types.lisp

Parent

clarans (module)

Location

clarans/types.lisp

Exported Definitions

• distance-function (method)
• parameters (class)

Internal Definitions

• algorithm-state (class)
• d (method)
• (setf d) (method)
• distance-function (method)
• (setf distance-function) (method)
• distortion (method)
• (setf distortion) (method)
• index-array (type)
• max-neighbor (method)
• (setf max-neighbor) (method)
• medoids (method)
• (setf medoids) (method)
• medoids-count (method)
• (setf medoids-count) (method)
• y (method)
• (setf y) (method)

4.1.39 clusters/clarans/utils.lisp

Parent

clarans (module)

Location

clarans/utils.lisp

Internal Definitions

• contains (function)
• random-medoid (function)
• random-neighbor (function)
• to-cluster-contents (function)

4.1.40 clusters/clarans/methods.lisp

Parent

clarans (module)

Location

clarans/methods.lisp

Exported Definitions

• algorithm-state-class (method)
• result-initialization-list (method)
• run-algorithm (method)

Internal Definitions

• max-neighbor (method)
• medoids-count (method)

4.1.41 clusters/k-means/package.lisp

Parent

k-means (module)

Location

k-means/package.lisp

Packages

clusters.k-means

4.1.42 clusters/k-means/types.lisp

Parent

k-means (module)

Location

k-means/types.lisp

Exported Definitions

parameters (class)

Internal Definitions

• access-medoids (method)
• (setf access-medoids) (method)
• algorithm-state (class)
• distortion-epsilon (method)
• (setf distortion-epsilon) (method)
• iterations (method)
• (setf iterations) (method)
• medoids-count (method)
• (setf medoids-count) (method)
• read-clusters (method)
• read-distortion-epsilon (method)
• read-iterations (method)
• read-medoids-count (method)

4.1.43 clusters/k-means/utils.lisp

Parent

k-means (module)

Location

k-means/utils.lisp

Internal Definitions

• assign-data-points-to-medoids (function)
• distortion (function)
• select-initial-medoids (function)
• select-new-medoids (function)

4.1.44 clusters/k-means/methods.lisp

Parent

k-means (module)

Location

k-means/methods.lisp

Exported Definitions

• algorithm-state-class (method)
• algorithm-state-initialization-list (method)
• distance-function (method)
• result-initialization-list (method)
• run-algorithm (method)

Internal Definitions

• read-distortion-epsilon (method)
• read-iterations (method)
• read-medoids-count (method)

5 Packages

Packages are listed by definition order.

5.1 clusters.aux-package

Source

aux-package.lisp (file)

Used By List

• clusters.k-means
• clusters.clarans
• clusters.pam
• clusters
• clusters.distance
• clusters.metric
• clusters.utils

5.2 clusters.fancy

Source

aux-package.lisp (file)

Exported Definitions

defpackage (macro)

5.3 clusters.utils

Source

package.lisp (file)

Use List

• clusters.aux-package
• common-lisp

Exported Definitions

• copy-into (function)
• distance-matrix (function)
• draw-random-vector (function)
• half-matrix-index->square-row/column (function)
• half-matrix-size->count (function)
• lazy-shuffle (function)
• make-half-matrix (function)
• map-into-half-matrix (function)
• mref (function)
• (setf mref) (function)
• pmap (function)
• pmap-into (function)
• seed (function)
• square-row/column->half-matrix-index (function)
• swap-if (function)
• transform (function)

Internal Definitions

• column-index (function)
• count->half-matrix-size (function)
• element-in-i-rows (function)
• row-index (function)

5.4 clusters.metric

Source

package.lisp (file)

Use List

• clusters.aux-package
• common-lisp

Exported Definitions

• average (function)
• euclid (function)
• group-average (function)
• hausdorff (function)
• hellinger (function)
• lcs (function)
• levenshtein (function)
• svr (function)

Internal Definitions

• +sqrt2+ (constant)
• array-sum (function)
• count-of-all-possible-subvectors-upto-length (function)
• earth-mover-metric (function)
• grid-mapping (function)
• same-events (function)
• update-grid (function)
• with-grid-mapping-resources (macro)

5.5 clusters.distance

Source

package.lisp (file)

Use List

• clusters.aux-package
• common-lisp

Exported Definitions

• bhattacharyya (function)
• sinkhorn (function)

Internal Definitions

• max-condition (function)
• sinkhorn-optimal-transport-matrix (function)
• sum-row (function)

5.6 clusters

Source

package.lisp (file)

Use List

• clusters.aux-package
• common-lisp

Exported Definitions

• algorithm-state (class)
• algorithm-state-class (generic function)
• algorithm-state-class (method)
• algorithm-state-class (method)
• algorithm-state-class (method)
• algorithm-state-initialization-list (generic function)
• algorithm-state-initialization-list (method)
• algorithm-state-initialization-list (method)
• algorithm-state-initialization-list (method)
• calculate-silhouette (function)
• calculate-silhouette* (generic function)
• calculate-silhouette* (method)
• calculate-silhouette* (method)
• cluster (function)
• cluster-contents (generic function)
• cluster-contents (method)
• cluster-indexes (generic function)
• cluster-indexes (method)
• data (generic function)
• data (method)
• data (method)
• (setf data) (generic function)
• (setf data) (method)
• distance-function (generic function)
• distance-function (method)
• distance-function (method)
• distance-function (method)
• indexes (generic function)
• indexes (method)
• (setf indexes) (method)
• indexes (method)
• (setf indexes) (generic function)
• key-function (generic function)
• key-function (method)
• key-function (method)
• make-algorithm-state (function)
• obtain-result (function)
• parallelp (generic function)
• parallelp (method)
• parallelp (method)
• parameters (generic function)
• parameters (method)
• parameters (class)
• result (class)
• result-class (generic function)
• result-class (method)
• result-class (method)
• result-class (method)
• result-initialization-list (generic function)
• result-initialization-list (method)
• result-initialization-list (method)
• result-initialization-list (method)
• result-initialization-list (method)
• run-algorithm (generic function)
• run-algorithm (method)
• run-algorithm (method)
• run-algorithm (method)
• silhouette (generic function)
• silhouette (method)
• silhouette (method)
• silhouette-sample-count (generic function)
• silhouette-sample-count (method)
• silhouette-sample-count (method)
• silhouette-sample-size (generic function)
• silhouette-sample-size (method)
• silhouette-sample-size (method)

Internal Definitions

• average-distance-to-element (function)
• cluster-values (function)
• distance-matrix (function)
• inter-cluster-distances (function)
• intra-cluster-distances (function)
• parallel-p (generic function)
• parameters-holder (class)
• select-random-cluster-subsets (function)

5.7 clusters.pam

Source

package.lisp (file)

Use List

• clusters.aux-package
• common-lisp

Exported Definitions

parameters (class)

Internal Definitions

• access-cluster-contents (generic function)
• access-cluster-contents (method)
• (setf access-cluster-contents) (method)
• (setf access-cluster-contents) (generic function)
• access-cluster-size (generic function)
• access-cluster-size (method)
• (setf access-cluster-size) (method)
• (setf access-cluster-size) (generic function)
• access-distance-matrix (generic function)
• access-distance-matrix (method)
• (setf access-distance-matrix) (method)
• (setf access-distance-matrix) (generic function)
• access-medoids-count (generic function)
• access-medoids-count (method)
• (setf access-medoids-count) (method)
• (setf access-medoids-count) (generic function)
• access-unfinished-clusters (generic function)
• access-unfinished-clusters (method)
• (setf access-unfinished-clusters) (method)
• (setf access-unfinished-clusters) (generic function)
• algorithm-state (class)
• assign-data-points-to-medoids (generic function)
• assign-data-points-to-medoids (method)
• build-clusters (function)
• choose-effective-medoid (function)
• choose-effective-medoids (function)
• choose-initial-medoids (function)
• clear-cluster-contents (function)
• clear-unfinished-clusters (function)
• closest-medoid (function)
• fill-reclustering-index-vector (function)
• medoidp (function)
• medoids-count (generic function)
• medoids-count (method)
• (setf medoids-count) (method)
• (setf medoids-count) (generic function)
• merge-threshold (generic function)
• merge-threshold (method)
• (setf merge-threshold) (method)
• (setf merge-threshold) (generic function)
• order-medoids (function)
• pam-result (class)
• prepare-reclustering-index-vector (function)
• read-distance-matrix (generic function)
• read-distance-matrix (method)
• read-medoids-count (generic function)
• read-medoids-count (method)
• read-medoids-count (method)
• read-merge-threshold (generic function)
• read-merge-threshold (method)
• read-merge-threshold (method)
• read-select-medoids-attempts-count (generic function)
• read-select-medoids-attempts-count (method)
• read-select-medoids-attempts-count (method)
• read-split-merge-attempts-count (generic function)
• read-split-merge-attempts-count (method)
• read-split-merge-attempts-count (method)
• read-split-threshold (generic function)
• read-split-threshold (method)
• read-split-threshold (method)
• recluster-clusters-of-invalid-size (function)
• reset (function)
• scan-for-clusters-of-invalid-size (function)
• select-medoids-attempts-count (generic function)
• select-medoids-attempts-count (method)
• (setf select-medoids-attempts-count) (method)
• (setf select-medoids-attempts-count) (generic function)
• split-merge-attempts-count (generic function)
• split-merge-attempts-count (method)
• (setf split-merge-attempts-count) (method)
• (setf split-merge-attempts-count) (generic function)
• split-threshold (generic function)
• split-threshold (method)
• (setf split-threshold) (method)
• (setf split-threshold) (generic function)
• unfinished-clusters-p (function)

5.8 clusters.clarans

Source

package.lisp (file)

Use List

• clusters.aux-package
• common-lisp

Exported Definitions

parameters (class)

Internal Definitions

• algorithm-state (class)
• contains (function)
• d (generic function)
• d (method)
• (setf d) (method)
• (setf d) (generic function)
• distance-function (generic function)
• distance-function (method)
• (setf distance-function) (method)
• (setf distance-function) (generic function)
• distortion (generic function)
• distortion (method)
• (setf distortion) (method)
• (setf distortion) (generic function)
• index-array (type)
• max-neighbor (generic function)
• max-neighbor (method)
• max-neighbor (method)
• (setf max-neighbor) (method)
• (setf max-neighbor) (generic function)
• medoids (generic function)
• medoids (method)
• (setf medoids) (method)
• (setf medoids) (generic function)
• medoids-count (generic function)
• medoids-count (method)
• medoids-count (method)
• (setf medoids-count) (method)
• (setf medoids-count) (generic function)
• random-medoid (function)
• random-neighbor (function)
• to-cluster-contents (function)
• y (generic function)
• y (method)
• (setf y) (method)
• (setf y) (generic function)

5.9 clusters.k-means

Source

package.lisp (file)

Use List

• clusters.aux-package
• common-lisp

Exported Definitions

parameters (class)

Internal Definitions

• access-medoids (generic function)
• access-medoids (method)
• (setf access-medoids) (method)
• (setf access-medoids) (generic function)
• algorithm-state (class)
• assign-data-points-to-medoids (function)
• distortion (function)
• distortion-epsilon (generic function)
• distortion-epsilon (method)
• (setf distortion-epsilon) (method)
• (setf distortion-epsilon) (generic function)
• iterations (generic function)
• iterations (method)
• (setf iterations) (method)
• (setf iterations) (generic function)
• medoids-count (generic function)
• medoids-count (method)
• (setf medoids-count) (method)
• (setf medoids-count) (generic function)
• read-clusters (generic function)
• read-clusters (method)
• read-distortion-epsilon (generic function)
• read-distortion-epsilon (method)
• read-distortion-epsilon (method)
• read-iterations (generic function)
• read-iterations (method)
• read-iterations (method)
• read-medoids-count (generic function)
• read-medoids-count (method)
• read-medoids-count (method)
• select-initial-medoids (function)
• select-new-medoids (function)

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

6.1 Exported definitions

6.1.1 Macros

Macro: defpackage PACKAGE &rest OPTIONS

Package

clusters.fancy

Source

aux-package.lisp (file)

6.1.2 Functions

Function: average FN A B &key TEST KEY

Description:
Calculates average distance between two sets, based around the FN metric function

Returns:
Average distance between two sets.

Notes:
–Algorithm described in https://doi.org/10.1007/s13160-012-0089-6
–KEY function is used in conjuction with the TEST function to construct unions and differences between sets. Not for extracting values for the FN itself. This allows FN to operate on the weight, count or other secondary attribute of the set element. –Quadratic time complexity, suitable only for small sets.

Package

clusters.metric

Source

average.lisp (file)

Function: bhattacharyya H1 H2

Arguments:
–H1, Frequency vector representing distribution.
–H2, Frequency vector representing distribution.

Description:
Calculates Bhattacharyya distance between two distributions represented as frequency vector.

Returns:
Bhattacharyya distance as single-float.

Package

clusters.distance

Source

bhattacharyya.lisp (file)

Function: calculate-silhouette RESULT &optional DISTANCE-MATRIX

Package

clusters

Source

functions.lisp (file)

Function: cluster PARAMETERS DATA &rest ARGUMENTS

Package

clusters

Source

functions.lisp (file)

Function: copy-into DESTINATION SOURCE

Package

clusters.utils

Source

utils.lisp (file)

Function: distance-matrix PARALLEL DISTANCE-FUNCTION DATA

Package

clusters.utils

Source

matrix.lisp (file)

Function: draw-random-vector INPUT SIZE &optional RESULT

Package

clusters.utils

Source

random.lisp (file)

Function: euclid A B

Description:
Calculates the Euclid distance between two simple-arrays of single-float

Returns:
Non-negative-single-float distance.

Package

clusters.metric

Source

euclid.lisp (file)

Function: group-average FN A B &key KEY ELEMENT-TYPE DISTANCE-MATRIX

Package

clusters.metric

Source

group-average.lisp (file)

Function: half-matrix-index->square-row/column COUNT INDEX

Package

clusters.utils

Source

matrix.lisp (file)

Function: half-matrix-size->count SIZE

Package

clusters.utils

Source

matrix.lisp (file)

Function: hausdorff FN A B &key KEY ELEMENT-TYPE DISTANCE-MATRIX

Description:
Hausdorff distance. Accepts vectors as arguments.

Package

clusters.metric

Source

hausdorff.lisp (file)

Function: hellinger Q P

Arguments:
–Q, Frequency vector.
–P, Frequency vector.

Description:
Calculates hellinger distance between two distributions, both represented as histograms.

Returns:
Hellinger distance.

Package

clusters.metric

Source

hellinger.lisp (file)

Function: lazy-shuffle FROM TO

Package

clusters.utils

Source

random.lisp (file)

Function: lcs A B &key TEST KEY A-START A-END B-START B-END BASE

Description:
Largest common subsequence metric for vectors.

Package

clusters.metric

Source

lcs.lisp (file)

Function: levenshtein STR1 STR2

Description:
Traditional edit distance for strings.

Package

clusters.metric

Source

levenshtein.lisp (file)

Function: make-algorithm-state PARAMETERS DATA &rest ARGUMENTS

Package

clusters

Source

functions.lisp (file)

Function: make-half-matrix COUNT &rest ALL &key ELEMENT-TYPE INITIAL-ELEMENT INITIAL-CONTENTS

Package

clusters.utils

Source

matrix.lisp (file)

Function: map-into-half-matrix PARALLEL HALF-MATRIX FUNCTION

Package

clusters.utils

Source

matrix.lisp (file)

Function: mref HALF-MATRIX FROM TO &optional COUNT

Function: (setf mref) NEW-VALUE HALF-MATRIX FROM TO &optional COUNT

Package

clusters.utils

Source

matrix.lisp (file)

Function: obtain-result STATE

Package

clusters

Source

functions.lisp (file)

Function: pmap PARALLEL TYPE FUNCTION &rest SEQUENCES

Package

clusters.utils

Source

maps.lisp (file)

Function: pmap-into PARALLEL SEQUENCE FUNCTION &rest SEQUENCES

Package

clusters.utils

Source

maps.lisp (file)

Function: seed DATA INDEXES MEDOIDS Y DISTANCE-FUNCTION

Package

clusters.utils

Source

partition.lisp (file)

Function: sinkhorn COST FIRST-VECTOR SECOND-VECTOR REGULARIZATION-STRENGTH &optional EPSILON

Package

clusters.distance

Source

sinkhorn.lisp (file)

Function: square-row/column->half-matrix-index COUNT J I

Package

clusters.utils

Source

matrix.lisp (file)

Function: svr A B

Arguments:
–A, Vector.
–B, Vector.

Description:
Calculates the subvector representation based metric.

Returns:
Single-float (between 0.0 and 1.0) representing the distance.

Notes:
–Content of a and b vectors must be comparable using EQUAL.
–Algorithm described in https://doi.org/10.1177%2F0049124114540707 –Will return 1.0 if one of the vectors is empty and the second is not empty.

Package

clusters.metric

Source

svr.lisp (file)

Function: swap-if VECTOR TEST &key KEY START END

Package

clusters.utils

Source

utils.lisp (file)

Function: transform PARALLEL FUNCTION SEQUENCE &rest SEQUENCES

Package

clusters.utils

Source

maps.lisp (file)

6.1.3 Generic functions

Generic Function: algorithm-state-class PARAMETERS

Package

clusters

Source

generics.lisp (file)

Methods

Method: algorithm-state-class (PARAMETERS parameters)

Source

methods.lisp (file)

Method: algorithm-state-class (PARAMETERS parameters)

Source

methods.lisp (file)

Method: algorithm-state-class (PARAMETERS parameters)

Source

methods.lisp (file)

Generic Function: algorithm-state-initialization-list PARAMETERS DATA &rest ARGUMENTS &key DISTANCE-MATRIX &allow-other-keys

Package

clusters

Source

generics.lisp (file)

Method Combination

append (short method combination)

Options: :most-specific-first

Methods

Method: algorithm-state-initialization-list (PARAMETERS parameters) DATA &rest ALL &key &allow-other-keys append

Source

methods.lisp (file)

Method: algorithm-state-initialization-list (PARAMETERS parameters) DATA &rest ALL &key DISTANCE-MATRIX &allow-other-keys append

Source

methods.lisp (file)

Method: algorithm-state-initialization-list (PARAMETERS parameters) DATA &rest ARGUMENTS &key &allow-other-keys append

Source

methods.lisp (file)

Generic Function: calculate-silhouette* PARAMETERS RESULT &optional DISTANCE-MATRIX

Package

clusters

Source

generics.lisp (file)

Methods

Method: calculate-silhouette* (PARAMETERS parameters) CLUSTERING-RESULT &optional DISTANCE-MATRIX around

Source

methods.lisp (file)

Method: calculate-silhouette* (PARAMETERS parameters) CLUSTERING-RESULT &optional DISTANCE-MATRIX

Source

methods.lisp (file)

Generic Function: cluster-contents RESULT

Package

clusters

Source

generics.lisp (file)

Methods

Method: cluster-contents (RESULT result)

Source

methods.lisp (file)

Generic Function: cluster-indexes RESULT

Package

clusters

Source

generics.lisp (file)

Methods

Method: cluster-indexes (RESULT result)

automatically generated reader method

Source

types.lisp (file)

Generic Function: data RESULT

Generic Function: (setf data) NEW-VALUE ALGORITHM-STATE

Package

clusters

Source

generics.lisp (file)

Methods

Method: data (ALGORITHM-STATE algorithm-state)

automatically generated reader method

Source

types.lisp (file)

Method: data (RESULT result)

automatically generated reader method

Source

types.lisp (file)

Method: (setf data) NEW-VALUE (ALGORITHM-STATE algorithm-state)

automatically generated writer method

Source

types.lisp (file)

Generic Function: distance-function INSTANCE

Package

clusters

Methods

Method: distance-function (PARAMETERS parameters)

Source

methods.lisp (file)

Method: distance-function (PARAMETERS parameters)

automatically generated reader method

Source

types.lisp (file)

Method: distance-function (INSTANCE parameters-holder)

Source

methods.lisp (file)

Generic Function: indexes ALGORITHM-STATE

Generic Function: (setf indexes) NEW-VALUE ALGORITHM-STATE

Package

clusters

Source

generics.lisp (file)

Methods

Method: indexes (ALGORITHM-STATE algorithm-state)

automatically generated reader method

Source

types.lisp (file)

Method: (setf indexes) NEW-VALUE (ALGORITHM-STATE algorithm-state)

automatically generated writer method

Source

types.lisp (file)

Method: indexes (RESULT result)

automatically generated reader method

Source

types.lisp (file)

Generic Function: key-function PARAMETERS

Package

clusters

Source

generics.lisp (file)

Methods

Method: key-function (INSTANCE parameters-holder)

Source

methods.lisp (file)

Method: key-function (PARAMETERS parameters)

automatically generated reader method

Source

types.lisp (file)

Generic Function: parallelp OBJECT

Package

clusters

Methods

Method: parallelp (INSTANCE parameters-holder)

Source

methods.lisp (file)

Method: parallelp (PARAMETERS parameters)

automatically generated reader method

Source

types.lisp (file)

Generic Function: parameters RESULT

Package

clusters

Source

generics.lisp (file)

Methods

Method: parameters (PARAMETERS-HOLDER parameters-holder)

automatically generated reader method

Source

types.lisp (file)

Generic Function: result-class PARAMETERS

Package

clusters

Source

generics.lisp (file)

Methods

Method: result-class (PARAMETERS parameters)

Source

methods.lisp (file)

Method: result-class (STATE algorithm-state)

Source

methods.lisp (file)

Method: result-class (PARAMETERS parameters)

Source

methods.lisp (file)

Generic Function: result-initialization-list STATE

Package

clusters

Source

generics.lisp (file)

Method Combination

append (short method combination)

Options: :most-specific-first

Methods

Method: result-initialization-list (STATE algorithm-state) append

Source

methods.lisp (file)

Method: result-initialization-list (STATE algorithm-state) append

Source

methods.lisp (file)

Method: result-initialization-list (STATE algorithm-state) append

Source

methods.lisp (file)

Method: result-initialization-list (STATE algorithm-state) append

Source

methods.lisp (file)

Generic Function: run-algorithm STATE

Package

clusters

Source

generics.lisp (file)

Methods

Method: run-algorithm (STATE algorithm-state)

Source

methods.lisp (file)

Method: run-algorithm (STATE algorithm-state)

Source

methods.lisp (file)

Method: run-algorithm (STATE algorithm-state)

Source

methods.lisp (file)

Generic Function: silhouette RESULT

Package

clusters

Source

generics.lisp (file)

Methods

Method: silhouette (OBJECT result) before

Source

silhouette.lisp (file)

Method: silhouette (RESULT result)

automatically generated reader method

Source

types.lisp (file)

Generic Function: silhouette-sample-count OBJECT

Package

clusters

Methods

Method: silhouette-sample-count (INSTANCE parameters-holder)

Source

methods.lisp (file)

Method: silhouette-sample-count (PARAMETERS parameters)

automatically generated reader method

Source

types.lisp (file)

Generic Function: silhouette-sample-size OBJECT

Package

clusters

Methods

Method: silhouette-sample-size (INSTANCE parameters-holder)

Source

methods.lisp (file)

Method: silhouette-sample-size (PARAMETERS parameters)

automatically generated reader method

Source

types.lisp (file)

6.1.4 Classes

Class: algorithm-state ()

Package

clusters

Source

types.lisp (file)

Direct superclasses

parameters-holder (class)

Direct subclasses

• algorithm-state (class)
• algorithm-state (class)
• algorithm-state (class)

Direct methods

• initialize-instance (method)
• result-class (method)
• result-initialization-list (method)
• indexes (method)
• indexes (method)
• (setf data) (method)
• data (method)

Direct slots

Slot: %data

Initargs

:data

Readers

data (generic function)

Writers

(setf data) (generic function)

Slot: %indexes

Initargs

:indexes

Readers

indexes (generic function)

Writers

(setf indexes) (generic function)

Direct Default Initargs

Initarg	Value
:data	(serapeum:vect)
:indexes	nil

Class: parameters ()

Package

clusters

Source

types.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

• parameters (class)
• parameters (class)
• parameters (class)

Direct methods

• calculate-silhouette* (method)
• result-class (method)
• algorithm-state-initialization-list (method)
• silhouette-sample-size (method)
• silhouette-sample-count (method)
• key-function (method)
• parallelp (method)

Direct slots

Slot: %parallelp

Initargs

:parallelp

Readers

parallelp (generic function)

Slot: %key-function

Initargs

:key-function

Readers

key-function (generic function)

Slot: %silhouette-sample-count

Initargs

:silhouette-sample-count

Readers

silhouette-sample-count (generic function)

Slot: %silhouette-sample-size

Initargs

:silhouette-sample-size

Readers

silhouette-sample-size (generic function)

Direct Default Initargs

Initarg	Value
:key-function	(function identity)
:parallelp	nil
:silhouette-sample-count	15
:silhouette-sample-size	500

Class: parameters ()

Package

clusters.pam

Source

types.lisp (file)

Direct superclasses

parameters (class)

Direct methods

• initialize-instance (method)
• calculate-silhouette* (method)
• result-class (method)
• algorithm-state-initialization-list (method)
• algorithm-state-class (method)
• medoids-count (method)
• medoids-count (method)
• read-medoids-count (method)
• split-merge-attempts-count (method)
• split-merge-attempts-count (method)
• read-split-merge-attempts-count (method)
• select-medoids-attempts-count (method)
• select-medoids-attempts-count (method)
• read-select-medoids-attempts-count (method)
• merge-threshold (method)
• merge-threshold (method)
• read-merge-threshold (method)
• split-threshold (method)
• split-threshold (method)
• read-split-threshold (method)

Direct slots

Slot: %split-threshold

Initargs

:split-threshold

Readers

• read-split-threshold (generic function)
• split-threshold (generic function)

Writers

(setf split-threshold) (generic function)

Slot: %merge-threshold

Initargs

:merge-threshold

Readers

• read-merge-threshold (generic function)
• merge-threshold (generic function)

Writers

(setf merge-threshold) (generic function)

Slot: %select-medoids-attempts-count

Initargs

:select-medoids-attempts-count

Readers

• read-select-medoids-attempts-count (generic function)
• select-medoids-attempts-count (generic function)

Writers

(setf select-medoids-attempts-count) (generic function)

Slot: %split-merge-attempts-count

Initargs

:split-merge-attempts-count

Readers

• read-split-merge-attempts-count (generic function)
• split-merge-attempts-count (generic function)

Writers

(setf split-merge-attempts-count) (generic function)

Slot: %medoids-count

Initargs

:medoids-count

Readers

• read-medoids-count (generic function)
• medoids-count (generic function)

Writers

(setf medoids-count) (generic function)

Direct Default Initargs

Initarg	Value
:split-threshold	nil
:merge-threshold	nil
:select-medoids-attempts-count	20
:split-merge-attempts-count	0

Class: parameters ()

Package

clusters.clarans

Source

types.lisp (file)

Direct superclasses

parameters (class)

Direct methods

• initialize-instance (method)
• algorithm-state-class (method)
• medoids-count (method)
• medoids-count (method)
• max-neighbor (method)
• max-neighbor (method)
• distance-function (method)
• distance-function (method)
• distance-function (method)

Direct slots

Slot: %distance-function

Initargs

:distance-function

Readers

• distance-function (generic function)
• distance-function (generic function)

Writers

(setf distance-function) (generic function)

Slot: %max-neighbor

Initargs

:max-neighbor

Readers

max-neighbor (generic function)

Writers

(setf max-neighbor) (generic function)

Slot: %medoids-count

Initargs

:medoids-count

Readers

medoids-count (generic function)

Writers

(setf medoids-count) (generic function)

Class: parameters ()

Package

clusters.k-means

Source

types.lisp (file)

Direct superclasses

parameters (class)

Direct methods

• initialize-instance (method)
• distance-function (method)
• algorithm-state-initialization-list (method)
• algorithm-state-class (method)
• distortion-epsilon (method)
• distortion-epsilon (method)
• read-distortion-epsilon (method)
• iterations (method)
• read-iterations (method)
• iterations (method)
• medoids-count (method)
• read-medoids-count (method)
• medoids-count (method)

Direct slots

Slot: %medoids-count

Type

alexandria:non-negative-fixnum

Initargs

:medoids-count

Readers

• medoids-count (generic function)
• read-medoids-count (generic function)

Writers

(setf medoids-count) (generic function)

Slot: %iterations

Initargs

:iterations

Readers

• iterations (generic function)
• read-iterations (generic function)

Writers

(setf iterations) (generic function)

Slot: %distortion-epsilon

Type

single-float

Initargs

:distortion-epsilon

Readers

• read-distortion-epsilon (generic function)
• distortion-epsilon (generic function)

Writers

(setf distortion-epsilon) (generic function)

Direct Default Initargs

Initarg	Value
:iterations	nil

Class: result ()

Package

clusters

Source

types.lisp (file)

Direct superclasses

parameters-holder (class)

Direct subclasses

pam-result (class)

Direct methods

• cluster-contents (method)
• silhouette (method)
• silhouette (method)
• data (method)
• indexes (method)
• cluster-indexes (method)

Direct slots

Slot: %cluster-indexes

Type

vector

Initargs

:cluster-indexes

Readers

cluster-indexes (generic function)

Slot: %indexes

Initargs

:indexes

Readers

indexes (generic function)

Slot: %data

Type

vector

Initargs

:data

Readers

data (generic function)

Slot: %silhouette

Type

(vector single-float)

Initargs

:silhouette

Readers

silhouette (generic function)

6.2 Internal definitions

6.2.1 Constants

Constant: +sqrt2+

Package

clusters.metric

Source

hellinger.lisp (file)

6.2.2 Macros

Macro: with-grid-mapping-resources MAX-LENGTH (&key G1 G2 G3 TO-SUM) &body BODY

Package

clusters.metric

Source

svr.lisp (file)

6.2.3 Functions

Function: array-sum ITERATION SUM-SIZE TO-SUM GRID

Package

clusters.metric

Source

svr.lisp (file)

Function: assign-data-points-to-medoids STATE

Package

clusters.k-means

Source

utils.lisp (file)

Function: average-distance-to-element DISTANCE-MATRIX ELEMENT CLUSTER

Package

clusters

Source

silhouette.lisp (file)

Function: build-clusters STATE &optional SPLIT-MERGE

Package

clusters.pam

Source

utils.lisp (file)

Function: choose-effective-medoid STATE CLUSTER

Package

clusters.pam

Source

utils.lisp (file)

Function: choose-effective-medoids STATE

Package

clusters.pam

Source

utils.lisp (file)

Function: choose-initial-medoids STATE

Package

clusters.pam

Source

utils.lisp (file)

Function: clear-cluster-contents STATE

Package

clusters.pam

Source

utils.lisp (file)

Function: clear-unfinished-clusters STATE

Package

clusters.pam

Source

utils.lisp (file)

Function: closest-medoid STATE INDEX

Package

clusters.pam

Source

utils.lisp (file)

Function: cluster-values DATA INDEX-VECTOR

Package

clusters

Source

utils.lisp (file)

Function: column-index K I N

Package

clusters.utils

Source

matrix.lisp (file)

Function: contains MEDOIDS MEDOID

Package

clusters.clarans

Source

utils.lisp (file)

Function: count->half-matrix-size COUNT

Package

clusters.utils

Source

matrix.lisp (file)

Function: count-of-all-possible-subvectors-upto-length LENGTH-OF-VECTOR LENGTH-OF-SUBVECTOR &optional BUFFER

Package

clusters.metric

Source

svr.lisp (file)

Function: distance-matrix RESULT &optional INDEXES

Package

clusters

Source

silhouette.lisp (file)

Function: distortion STATE

Package

clusters.k-means

Source

utils.lisp (file)

Function: earth-mover-metric A B

Package

clusters.metric

Source

earth-mover.lisp (file)

Function: element-in-i-rows I N

Package

clusters.utils

Source

matrix.lisp (file)

Function: fill-reclustering-index-vector STATE INDEXES COUNT-OF-ELIMINATED

Package

clusters.pam

Source

utils.lisp (file)

Function: grid-mapping FIRST-SEQUENCE SECOND-SEQUENCE &optional GRID FIRST-GRID PREV-GRID TO-SUM

Package

clusters.metric

Source

svr.lisp (file)

Function: inter-cluster-distances DISTANCE-MATRIX CLUSTER SAMPLE

Package

clusters

Source

silhouette.lisp (file)

Function: intra-cluster-distances DISTANCE-MATRIX CLUSTER

Package

clusters

Source

silhouette.lisp (file)

Function: max-condition U SUM-ROW N EPSILON

Package

clusters.distance

Source

sinkhorn.lisp (file)

Function: medoidp STATE INDEX

Package

clusters.pam

Source

utils.lisp (file)

Function: order-medoids STATE

Package

clusters.pam

Source

utils.lisp (file)

Function: prepare-reclustering-index-vector STATE

Package

clusters.pam

Source

utils.lisp (file)

Function: random-medoid N MEDOIDS

Package

clusters.clarans

Source

utils.lisp (file)

Function: random-neighbor PARALLELP DATA INDEXES MEDOIDS Y D DISTANCE-FUNCTION

Package

clusters.clarans

Source

utils.lisp (file)

Function: recluster-clusters-of-invalid-size STATE

Package

clusters.pam

Source

utils.lisp (file)

Function: reset OBJECT

Package

clusters.pam

Source

utils.lisp (file)

Function: row-index K N

Package

clusters.utils

Source

matrix.lisp (file)

Function: same-events GRID SEQUENCE-A SEQUENCE-B TO-SUM

Package

clusters.metric

Source

svr.lisp (file)

Function: scan-for-clusters-of-invalid-size STATE

Package

clusters.pam

Source

utils.lisp (file)

Function: select-initial-medoids STATE

Package

clusters.k-means

Source

utils.lisp (file)

Function: select-new-medoids STATE

Package

clusters.k-means

Source

utils.lisp (file)

Function: select-random-cluster-subsets RESULT DISTANCE-MATRIX-SUPPLIED

Package

clusters

Source

silhouette.lisp (file)