Modul 8 (ann1)

Module 8 k-means RBF networks PNN SOM

Non-Hierarchical Cluster Analysis: k-means

+ +

1. 2. 3. 4.

A

B +: centroid

Select number of clusters (centroids) Calculate centroids µk of partitions Mk Assign cluster members x to centroids Minimize distance function K 2 D = ∑∑ ( xk − µ k ) → Min. k =1 x k

http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/kmeans.html

Example: k-means Clustering Data ID A1 A2 B1 B2 B3

x1 1 2 4 5 7

x2 1 1 5 7 7

B2

B3

B1

x2 A1

• 2 centroids (k = 2) • Euclidian Distance

+

+

A2

x1 Cluster Boundary (Classifier)

k-Nearest Neighbors • Pick k nearest objects to a reference point • Problem: reasonable choice of K

x2

k=3 k=6 x1

Kernel-based Nearest Neighbors • Pick nearest objects to a reference point according to a Kernel function • Problem: reasonable choice of the Kernel & parameters Kernel function f( A,B) → scalar value f( A,B) = 0 if A = B f( A,B) > 0 if A ≠ B

+ µB x2

Gaussian Kernel φ  x −µ j  Φ j ( x ) = exp − 2σ 2j  

2

   

Kernel Discrimination Methods

σB +µ

A

σA x1

Probabilistic Neural Network (PNN) one standardized Gaussian basis function placed on the location of each pattern (xi = µi)

yclass = f class (x) =

∑ j∈CLASS

 x−x 1 class , j  exp − D D 2σ 2j  M (2π ) σ j 

2

   

φ1 Optional: softmax y1

x1

yc

xd Inputs

φM Basis functions

Outputs

zclass =

exp( y class ) C

∑ exp( y

k

)

k =1

smoothed version of „winner-take-all“

Probabilistic Neural Network (PNN) cytoplasmic proteins (class1) secreted proteins (class2) property 2

fclass1(x) fclass2(x)

property 1

P(x)


ity >



decision boundary

Radial Basis Function (RBF) Network M

y ( x ) = ∑ w kj Φ j ( x ) + w k 0 j =1

Gaussian basis function φ

M basis functions φ

 x −µ j  Φ j ( x ) = exp − 2σ 2j  

φ1 y1

x1

w yc

xd Inputs

φM Basis functions

Outputs

2

  ( x − µ j )T ( x − µ j )     2  = exp −  2σ j   

Standardized Gaussian φ  x −µ 1 j  Φ j (x ) = exp − 2σ 2j  (2π )D σ Dj  D : dimension of X

2

   

The Self-Organizing Map (SOM)

Data Analysis by Self-Organizing Maps (Kohonen networks) Z

Y

X

SOM

Properties of Kohonen Networks • Projection of high-dimensional space • Self-organized feature extraction and cluster formation • Non-linear, topology-preserving mapping

Other Projection Techniques • Principal Component Analysis (linear) • Projection to Latent Structures (linear, non-linear) • Encoder networks (non-linear) • Sammon mapping (non-linear)

Architecture of Kohonen Networks w

Input

A=6 (A • B) neuron array

x1 x2 x3 x4

B=5

1/0

Output

One neuron fires at a time

Neighborhood Definition in Kohonen Networks

Square neuron array

Hexagonal neuron array

second neighborhood first neighborhood central (active) neuron

Toroidal Topology of 2D-Kohonen Maps

An “endless plane”

Competitive Learning 1. Randomly select an input pattern x 2. Determine the “winner” neuron (competitive stage)

dim  2 i* ← min  ∑ x j − wij ; i = 1,2, ... , n  j =1 

(

)

3. Update network weights (cooperative stage)

 wold + η x j  ij new  w old + η x wij =  i   wijold  4. Goto Step 1 or terminate

if i ∈ N i * if i ∉ N i *

(Normalization of w)

Scaling Functions

“connection kernel” h

• Neighborhood (N) correction

 d1 (r , s ) 2   h(t , r , s ) = exp  −  2σ 2 (t )     σ fin 

σ (t ) = σ ini 

  σ ini  

r h

t / t max s

r h

•Time-dependent learning rate

 η fin   η (t ) = ηini   η ini  

s

“Mexican Hat” (not in SOM)

t / t max r

s

Vectorial Representation of Competitive Learning

Neuron 2

x2

x2

Neuron 2

x1

x1

Neuron 1

Neuron 1

Learning Time

unit sphere

SOM Adaptation to Probability Distributions

t = 500

t = 400

t = 300

t = 200

t = 100

Learning time

0

B

Voronoi tesselation A

SOM - Issues • Neighboring neurons code for neighboring input positions, but the inverse does not hold • Best results: input dimensionality = lattice dimensionality • Neighborhood decay & shape

local minima

• Problems with capturing the fine-structure of input space (oversampling of low-probability regions) • “dead” or “empty” neurons • features are not invariant to, e.g., translations of the input signal

Mapping Chemical Space: “Drugs” and “Nondrugs”

120-dimensional data, Ghose & Crippen parameters 5’000 drugs, 5’000 nondrugs (Sadowski & Kubinyi, 1998)

Visualizing Combinatorial Libraries (UGI) R1

O

O

+

N C

+

R2

+

R3

R2

O

H

MeOH / RT

R1

H N

NH2

R4 OH

+

R4 O

+

R1

R3

R2

H N

NH R3

O

Thrombin binding assay

7 6

IC50 < 10 µM

PC2

5 4 3 2 1 PC1

PCA

1

2

3

4

5

6

7

Kohonen-Map

Self-organizing neural networks demo 1) University of Bochum http://www.neuroinformatik.ruhr-unibochum.de/ini/VDM/research/gsn/DemoGNG/GNG 2) SOMMER

Link on modlab software page www.modlab.de