som 1.0 → 2.0

raw patch · 3 files changed

+123/−81 lines, 3 filesdep ~QuickCheckdep ~containersdep ~gridPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: QuickCheck, containers, grid, test-framework, test-framework-quickcheck2

API changes (from Hackage documentation)

Files

• som.cabal +10/−9
• src/Data/Datamining/Clustering/SOM.hs +27/−22
• src/Data/Datamining/Clustering/SOMInternal.hs +86/−50

@@ -1,5 +1,5 @@ name:           som-version:        1.0+version:        2.0 synopsis:       Self-Organising Maps description:    A Kohonen Self-organising Map (SOM) maps input patterns                  onto a regular grid (usually two-dimensional) where each@@ -12,6 +12,7 @@                 In layman's terms, a SOM can be useful when you you want                 to discover the underlying structure of some data. category:       Math+ cabal-version:  >=1.8 build-type:     Simple author:         Amy de Buitléir@@ -26,25 +27,25 @@   build-depends:   base ==4.*,                    base-unicode-symbols ==0.2.*,                    binary == 0.5.*,-                   containers ==0.4.2.*,-                   grid ==1.1.* || ==2.0,+                   containers ==0.4.2.* || ==0.5.*,+                   grid ==3.*,                    MonadRandom ==0.1.*-  ghc-options:     -Wall -rtsopts+  ghc-options:     -Wall   exposed-modules: Data.Datamining.Clustering.SOM,                    Data.Datamining.Clustering.SOMInternal  test-suite som-tests   type:            exitcode-stdio-1.0   build-depends:   base ==4.*,-                   test-framework-quickcheck2 == 0.2.*,-                   QuickCheck == 2.4.*,-                   test-framework == 0.*,+                   test-framework-quickcheck2 == 0.3.*,+                   QuickCheck == 2.5.*,+                   test-framework == 0.8.*,                    som,-                   grid ==1.1.* || ==2.0,+                   grid ==3.*,                    base-unicode-symbols ==0.2.*,                    MonadRandom ==0.1.*,                    random ==1.0.*   hs-source-dirs:  test-  ghc-options:     -Wall -rtsopts+  ghc-options:     -Wall   main-is:         Main.hs 

@@ -1,4 +1,4 @@------------------------------------------------------------------------------+------------------------------------------------------------------------ -- | -- Module      :  Data.Datamining.Clustering.SOM -- Copyright   :  (c) Amy de Buitléir 2012@@ -8,21 +8,22 @@ -- Portability :  portable -- -- A Kohonen Self-organising Map (SOM). A SOM maps input patterns onto a --- regular grid (usually two-dimensional) where each node in the grid is a--- model of the input data, and does so using a method which ensures that any--- topological relationships within the input data are also represented in the--- grid. This implementation supports the use of non-numeric patterns.+-- regular grid (usually two-dimensional) where each node in the grid is+-- a model of the input data, and does so using a method which ensures +-- that any topological relationships within the input data are also +-- represented in the grid. This implementation supports the use of +-- non-numeric patterns. ----- In layman's terms, a SOM can be useful when you you want to discover the--- underlying structure of some data. A tutorial is available at+-- In layman's terms, a SOM can be useful when you you want to discover+-- the underlying structure of some data. A tutorial is available at -- <https://github.com/mhwombat/som/wiki> -- -- References: ----- * Kohonen, T. (1982). Self-organized formation of topologically correct--- feature maps. Biological Cybernetics, 43 (1), 59–69.+-- * Kohonen, T. (1982). Self-organized formation of topologically +--   correct feature maps. Biological Cybernetics, 43 (1), 59–69. --------------------------------------------------------------------------------+------------------------------------------------------------------------  {-# LANGUAGE UnicodeSyntax #-} @@ -35,7 +36,9 @@     trainBatch,     classify,     classifyAndTrain,-    differences,+    diffs,+    differences, -- TO BE REMOVED+    diffAndTrain,     -- * Numeric vectors as patterns     -- ** Normalised vectors     normalise,@@ -51,24 +54,26 @@   ) where  import Data.Datamining.Clustering.SOMInternal (adjustVector, classify, -  classifyAndTrain, differences, euclideanDistanceSquared, normalise, -  NormalisedVector, scale,ScaledVector, train, trainBatch, Pattern(..))+  classifyAndTrain, diffs, differences, diffAndTrain, +  euclideanDistanceSquared, normalise, NormalisedVector, scale,+  ScaledVector, train, trainBatch, Pattern(..))  -- | Calculates @c/e/^(-d^2/2w^2)@.---   This form of the Gaussian function is useful as a learning rate function.---   In @'gaussian' c w d@, @c@ specifies the highest learning rate, which---   will be applied to the SOM node that best matches the input pattern.---   The learning rate applied to other nodes will be applied based on their---   distance @d@ from the best matching node. The value @w@ controls the ---   \'width\' of the Gaussian. Higher values of @w@ cause the learning rate---   to fall off more slowly with distance.+--   This form of the Gaussian function is useful as a learning rate+--   function. In @'gaussian' c w d@, @c@ specifies the highest learning+--   rate, which will be applied to the SOM node that best matches the+--   input pattern. The learning rate applied to other nodes will be +--   applied based on their distance @d@ from the best matching node. +--   The value @w@ controls the \'width\' of the Gaussian. Higher values+--   of @w@ cause the learning rate to fall off more slowly with +--   distance. gaussian ∷ Double → Double → Int → Double gaussian c w d = c * exp (-d'*d'/(2*w*w))   where d' = fromIntegral d  {- $Vector-If you wish to use a SOM with raw numeric vectors, use @no-warn-orphans@ and-add the following to your code:+If you wish to use a SOM with raw numeric vectors, use @no-warn-orphans@+and add the following to your code:  > instance (Floating a, Fractional a, Ord a, Eq a) ⇒ Pattern [a] a where >   difference = euclideanDistanceSquared

@@ -1,4 +1,4 @@------------------------------------------------------------------------------+------------------------------------------------------------------------ -- | -- Module      :  Data.Datamining.Clustering.SOMInternal -- Copyright   :  (c) Amy de Buitléir 2012@@ -10,7 +10,7 @@ -- A module containing private @SOM@ internals. Most developers should -- use @SOM@ instead. This module is subject to change without notice. --------------------------------------------------------------------------------+------------------------------------------------------------------------ {-# LANGUAGE UnicodeSyntax, MultiParamTypeClasses, FlexibleInstances,      FunctionalDependencies #-} @@ -20,7 +20,9 @@     adjustVector,     classify,     classifyAndTrain,-    differences,+    differences, -- TO BE REMOVED+    diffs,+    diffAndTrain,     euclideanDistanceSquared,     magnitudeSquared,     normalise,@@ -42,20 +44,20 @@  -- | A pattern to be learned or classified by a self-organising map. class Pattern p v | p → v where-  -- | Compares two patterns and returns a /non-negative/ number representing -  --   how different the patterns are. A result of @0@ indicates that the -  --   patterns are identical.+  -- | Compares two patterns and returns a /non-negative/ number +  --   representing how different the patterns are. A result of @0@ +  --   indicates that the patterns are identical.   difference ∷ p → p → v   -- | @'makeSimilar' target amount pattern@ returns a modified copy of   --   @pattern@ that is more similar to @target@ than @pattern@ is. The -  --   magnitude of the adjustment is controlled by the @amount@ parameter,-  --   which should be a number between 0 and 1. Larger values for @amount@-  --   permit greater adjustments. If @amount@=1, the result should be -  --   identical to the @target@. If @amount@=0, the result should be the-  --   unmodified @pattern@.+  --   magnitude of the adjustment is controlled by the @amount@ +  --   parameter, which should be a number between 0 and 1. Larger +  --   values for @amount@ permit greater adjustments. If @amount@=1,+  --   the result should be identical to the @target@. If @amount@=0,+  --   the result should be the unmodified @pattern@.   makeSimilar ∷ p → v → p → p --- | @'classify' pattern c@ returns the position of the node in @c@ +-- | @classify c pattern@ returns the position of the node in @c@  --   whose pattern best matches the input @pattern@. classify ∷ (Ord v, Pattern p v) ⇒ GridMap g k p → p → k classify c pattern = @@ -63,14 +65,22 @@  -- | @pattern \`'differences'\` c@ returns the positions of all nodes in  --   @c@, paired with the difference between @pattern@ and the node's ---   pattern.+--   pattern. This function has been replaced with @'diffs'@, which+--   swaps the parameter order to be consistent with @'classify'@.+{-# DEPRECATED differences "Use diffs instead" #-} differences ∷ Pattern p v ⇒ p → GridMap g k p → GridMap g k v differences pattern = GM.map (pattern `difference`) --- | If @f d@ is a function that returns the learning rate to apply to a node ---   based on its distance @d@from the node that best matches the input ---   pattern, then @'train' f c pattern@ returns a modified copy of the---   classifier @c@ that has partially learned the @target@.+-- | @'diffs' c pattern@ returns the positions of all nodes in +--   @c@, paired with the difference between @pattern@ and the node's +--   pattern.+diffs ∷ Pattern p v ⇒ GridMap g k p → p → GridMap g k v+diffs c pattern = GM.map (pattern `difference`) c++-- | If @f d@ is a function that returns the learning rate to apply to a+--   node based on its distance @d@from the node that best matches the+--   input pattern, then @'train' f c pattern@ returns a modified copy+--   of the classifier @c@ that has partially learned the @target@. train ∷ (Ord v, Pattern p v, Grid g s k) ⇒   (Int → v) → GridMap g k p → p → GridMap g k p train f c pattern = snd $ classifyAndTrain f c pattern@@ -80,20 +90,43 @@   (Int → v) → GridMap g k p → [p] → GridMap g k p trainBatch f = foldl' (train f) --- | If @f@ is a function that returns the learning rate to apply to a node---   based on its distance from the node that best matches the @target@, then ---   @'classifyAndTrain' f c target@ returns a tuple containing the position---   of the node in @c@ whose pattern best matches the input @target@, and a---   modified copy of the classifier @c@ that has partially learned the ---   @target@.+-- | If @f@ is a function that returns the learning rate to apply to a+--   node based on its distance from the node that best matches the +--   @target@, then @'classifyAndTrain' f c target@ returns a tuple +--   containing the position of the node in @c@ whose pattern best +--   matches the input @target@, and a modified copy of the classifier +--   @c@ that has partially learned the @target@.+--   Invoking @classifyAndTrain f c p@ may be faster than invoking+--   @(p `classify` c, train f c p)@, but they should give identical+--   results. classifyAndTrain ∷ (Eq k, Ord v, Pattern p v, Grid g s k) ⇒    (Int → v) → GridMap g k p → p → (k, GridMap g k p) classifyAndTrain f c pattern = (bmu, c')   where bmu = classify c pattern-        dMap = mapWithKey (\k p → (distance k bmu c, p)) c+        dMap = mapWithKey (\k p → (distance c k bmu, p)) c         lrMap = GM.map (\(d,p) → (f d, p)) dMap         c' = GM.map (adjustNode pattern) lrMap +-- | If @f@ is a function that returns the learning rate to apply to a+--   node based on its distance from the node that best matches the +--   @target@, then @'diffAndTrain' f c target@ returns a tuple +--   containing:+--   1. The positions of all nodes in @c@, paired with the difference+--      between @pattern@ and the node's pattern+--   2. A modified copy of the classifier @c@ that has partially+--      learned the @target@.+--   Invoking @diffAndTrain f c p@ may be faster than invoking+--   @(p `differences` c, train f c p)@, but they should give identical+--   results.+diffAndTrain ∷ (Eq k, Ord v, Pattern p v, Grid g s k) ⇒ +  (Int → v) → GridMap g k p → p → (GridMap g k v, GridMap g k p)+diffAndTrain f c pattern = (ds, c')+  where ds = pattern `differences` c+        bmu = fst $ minimumBy (comparing snd) $ toList ds+        dMap = mapWithKey (\k p → (distance c k bmu, p)) c+        lrMap = GM.map (\(d,p) → (f d, p)) dMap+        c' = GM.map (adjustNode pattern) lrMap+ adjustNode ∷ (Pattern p v) ⇒ p → (v,p) → p adjustNode target (r,p) = makeSimilar target r p @@ -104,25 +137,28 @@ magnitudeSquared ∷ Num a ⇒ [a] → a magnitudeSquared xs =  sum $ map (\x → x*x) xs --- | Calculates the square of the Euclidean distance between two vectors.+-- | Calculates the square of the Euclidean distance between two +--   vectors. euclideanDistanceSquared ∷ Num a ⇒ [a] → [a] → a euclideanDistanceSquared xs ys = magnitudeSquared $ zipWith (-) xs ys --- | @'adjustVector' target amount vector@ adjusts @vector@ to move it closer ---   to @target@. The amount of adjustment is controlled by the learning rate---   @r@, which is a number between 0 and 1. Larger values of @r@ permit more---   adjustment. If @r@=1, the result will be identical to the @target@. If ---   @amount@=0, the result will be the unmodified @pattern@.+-- | @'adjustVector' target amount vector@ adjusts @vector@ to move it +--   closer to @target@. The amount of adjustment is controlled by the+--   learning rate @r@, which is a number between 0 and 1. Larger values+--   of @r@ permit more adjustment. If @r@=1, the result will be +--   identical to the @target@. If @amount@=0, the result will be the+--   unmodified @pattern@. adjustVector ∷ (Num a, Ord a, Eq a) ⇒ [a] → a → [a] → [a] adjustVector xs r ys-  | r < 0 = error "Negative learning rate"-  | r > 1 = error "Learning rate > 1"-  | r ≡ 1 = xs-  | otherwise        = zipWith (+) ys deltas-      where diffs = zipWith (-) xs ys-            deltas = map (r *) diffs+  | r < 0     = error "Negative learning rate"+  | r > 1     = error "Learning rate > 1"+  | r ≡ 1     = xs+  | otherwise = zipWith (+) ys deltas+      where ds = zipWith (-) xs ys+            deltas = map (r *) ds --- | A vector that has been normalised, i.e., the magnitude of the vector = 1.+-- | A vector that has been normalised, i.e., the magnitude of the +--   vector = 1. data NormalisedVector a = NormalisedVector [a] deriving Show  -- | Normalises a vector@@ -141,24 +177,24 @@   makeSimilar (NormalisedVector xs) r (NormalisedVector ys) =      normalise $ adjustVector xs r ys --- | A vector that has been scaled so that all elements in the vector are---   between zero and one. To scale a set of vectors, use @'scaleAll'@.---   Alternatively, if you can identify a maximum and minimum value for---   each element in a vector, you can scale individual vectors using---   @'scale'@.+-- | A vector that has been scaled so that all elements in the vector +--   are between zero and one. To scale a set of vectors, use +--   @'scaleAll'@. Alternatively, if you can identify a maximum and +--   minimum value for each element in a vector, you can scale +--   individual vectors using @'scale'@. data ScaledVector a = ScaledVector [a] deriving Show --- | Given a vector @qs@ of pairs of numbers, where each pair represents the---   maximum and minimum value to be expected at each position in @xs@,---   @'scale' qs xs@ scales the vector @xs@ element by element, mapping the ---   maximum value expected at that position to one, and the minimum value to ---   zero.+-- | Given a vector @qs@ of pairs of numbers, where each pair represents+--   the maximum and minimum value to be expected at each position in +--   @xs@, @'scale' qs xs@ scales the vector @xs@ element by element, +--   mapping the maximum value expected at that position to one, and the+--   minimum value to zero. scale ∷ Fractional a ⇒ [(a,a)] → [a] → ScaledVector a scale qs xs = ScaledVector $ zipWith scaleValue qs xs --- | Scales a set of vectors by determining the maximum and minimum values at---   each position in the vector, and mapping the maximum value to one, and ---   the minimum value to zero.+-- | Scales a set of vectors by determining the maximum and minimum+--   values at each position in the vector, and mapping the maximum +--   value to one, and the minimum value to zero. scaleAll ∷ (Fractional a, Ord a) ⇒ [[a]] → [ScaledVector a] scaleAll xss = map (scale qs) xss   where qs = quantify xss