som (empty) → 1.0

raw patch · 6 files changed

+353/−0 lines, 6 filesdep +MonadRandomdep +QuickCheckdep +basesetup-changed

Dependencies added: MonadRandom, QuickCheck, base, base-unicode-symbols, binary, containers, grid, random, som, test-framework, test-framework-quickcheck2

Files

• LICENSE +27/−0
• Setup.hs +2/−0
• som.cabal +50/−0
• src/Data/Datamining/Clustering/SOM.hs +77/−0
• src/Data/Datamining/Clustering/SOMInternal.hs +182/−0
• test/Main.hs +15/−0

@@ -0,0 +1,27 @@+Copyright (c) 2010-2012, Amy de Buitléir+All rights reserved.++Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions +are met:++* Redistributions of source code must retain the above copyright +  notice, this list of conditions and the following disclaimer.+* Redistributions in binary form must reproduce the above copyright+  notice, this list of conditions and the following disclaimer in the+  documentation and/or other materials provided with the distribution.+* Neither the name of the author nor the names of other contributors+  may be used to endorse or promote products derived from this software+  without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,50 @@+name:           som+version:        1.0+synopsis:       Self-Organising Maps+description:    A Kohonen Self-organising Map (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.+                .+                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+copyright:      (c) Amy de Buitléir 2010-2012+license:        BSD3+stability:      experimental+maintainer:     amy@nualeargais.ie+license-file:   LICENSE++library+  hs-source-dirs:  src+  build-depends:   base ==4.*,+                   base-unicode-symbols ==0.2.*,+                   binary == 0.5.*,+                   containers ==0.4.2.*,+                   grid ==1.1.* || ==2.0,+                   MonadRandom ==0.1.*+  ghc-options:     -Wall -rtsopts+  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.*,+                   som,+                   grid ==1.1.* || ==2.0,+                   base-unicode-symbols ==0.2.*,+                   MonadRandom ==0.1.*,+                   random ==1.0.*+  hs-source-dirs:  test+  ghc-options:     -Wall -rtsopts+  main-is:         Main.hs+

@@ -0,0 +1,77 @@+-----------------------------------------------------------------------------+-- |+-- Module      :  Data.Datamining.Clustering.SOM+-- Copyright   :  (c) Amy de Buitléir 2012+-- License     :  BSD-style+-- Maintainer  :  amy@nualeargais.ie+-- Stability   :  experimental+-- 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.+--+-- 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.+--+-----------------------------------------------------------------------------++{-# LANGUAGE UnicodeSyntax #-}++module Data.Datamining.Clustering.SOM+  (+    -- Patterns+    Pattern(..),+    -- * Using the SOM+    train,+    trainBatch,+    classify,+    classifyAndTrain,+    differences,+    -- * Numeric vectors as patterns+    -- ** Normalised vectors+    normalise,+    NormalisedVector,+    -- ** Scaled vectors+    scale,+    ScaledVector,+    -- ** Useful functions+    -- $Vector+    adjustVector,+    euclideanDistanceSquared,+    gaussian+  ) where++import Data.Datamining.Clustering.SOMInternal (adjustVector, classify, +  classifyAndTrain, differences, 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.+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:++> instance (Floating a, Fractional a, Ord a, Eq a) ⇒ Pattern [a] a where+>   difference = euclideanDistanceSquared+>   makeSimilar = adjustVector+-}+

@@ -0,0 +1,182 @@+-----------------------------------------------------------------------------+-- |+-- Module      :  Data.Datamining.Clustering.SOMInternal+-- Copyright   :  (c) Amy de Buitléir 2012+-- License     :  BSD-style+-- Maintainer  :  amy@nualeargais.ie+-- Stability   :  experimental+-- Portability :  portable+--+-- 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 #-}++module Data.Datamining.Clustering.SOMInternal+  (+    adjustNode,+    adjustVector,+    classify,+    classifyAndTrain,+    differences,+    euclideanDistanceSquared,+    magnitudeSquared,+    normalise,+    NormalisedVector,+    scale,+    scaleAll,+    ScaledVector,+    train,+    trainBatch,+    Pattern(..)+  ) where++import Data.Eq.Unicode ((≡))+import Data.List (foldl', minimumBy)+import Data.Ord (comparing)+import Math.Geometry.Grid (distance, Grid)+import Math.Geometry.GridMap (GridMap, mapWithKey, toList)+import qualified Math.Geometry.GridMap as GM (map)++-- | 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.+  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@.+  makeSimilar ∷ p → v → p → p++-- | @'classify' pattern c@ 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 = +  fst $ minimumBy (comparing snd) $ toList $ differences pattern c++-- | @pattern \`'differences'\` c@ returns the positions of all nodes in +--   @c@, paired with the difference between @pattern@ and the node's +--   pattern.+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@.+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++-- | Same as @train@, but applied to multiple patterns.+trainBatch ∷ (Ord v, Grid g s k, Pattern p v) ⇒+  (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@.+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+        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++--+-- Using numeric vectors as patterns.+-- ++magnitudeSquared ∷ Num a ⇒ [a] → a+magnitudeSquared xs =  sum $ map (\x → x*x) xs++-- | 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 ∷ (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++-- | A vector that has been normalised, i.e., the magnitude of the vector = 1.+data NormalisedVector a = NormalisedVector [a] deriving Show++-- | Normalises a vector+normalise ∷ Floating a ⇒ [a] → NormalisedVector a+normalise xs = NormalisedVector $ map (/x) xs+  where x = norm xs++norm ∷ Floating a ⇒ [a] → a+norm xs = sqrt $ sum (map f xs)+  where f x = x*x++instance (Floating a, Fractional a, Ord a, Eq a) ⇒ +    Pattern (NormalisedVector a) a where+  difference (NormalisedVector xs) (NormalisedVector ys) = +    euclideanDistanceSquared xs ys+  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'@.+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.+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.+scaleAll ∷ (Fractional a, Ord a) ⇒ [[a]] → [ScaledVector a]+scaleAll xss = map (scale qs) xss+  where qs = quantify xss++scaleValue ∷ Fractional a ⇒ (a,a) → a → a+scaleValue (minX,maxX) x = (x - minX) / (maxX-minX)++quantify ∷ Ord a ⇒ [[a]] → [(a,a)]+quantify xss = foldl' quantify' qs (tail xss)+  where qs = zip (head xss) (head xss)++quantify' ∷ Ord a ⇒ [(a,a)] → [a] → [(a,a)]+quantify' = zipWith f+  where f (minX, maxX) x = (min minX x, max maxX x)++instance (Fractional a, Ord a, Eq a) ⇒ Pattern (ScaledVector a) a where+  difference (ScaledVector xs) (ScaledVector ys) = +    euclideanDistanceSquared xs ys+  makeSimilar (ScaledVector xs) r (ScaledVector ys) =+    ScaledVector $ adjustVector xs r ys+

@@ -0,0 +1,15 @@+{-# LANGUAGE UnicodeSyntax #-}+module Main where++import Data.Datamining.Clustering.SOMQC ( test )++import Test.Framework as TF ( defaultMain, Test )++tests ∷ [TF.Test]+tests = +  [ +    Data.Datamining.Clustering.SOMQC.test+  ]++main ∷ IO ()+main = defaultMain tests