---
# System prepended metadata

title: Clustering. Main points

---

Lecture Notes

# Clustering. Main points

Clustering - grouping similar data by some common pattern

## K-means clustering

1. Choose number of clusters *K*. Choose centers *C*  wherever.

2. Assign observations that are closer to c_k than other centroid

3. Revise cluster center as mean of assigned observations
   $$
   c_i = \frac {1} {|C_i|} \sum{x}
   $$

4. Repeat *2* and *3* until *C* no longer changes.

*Objective of K-means* : to minimize heterogeneity. Converges at local minimum

## K-means ++

1a. Take center c1, chosen uniformly at random from X.
1b. Take a new center based on probability of $$ \frac {D(x)^2} {\sum_X D(x)^2} $$
1c. Repeat 1b until all *K* centers placed.
2 - 4. Same as in _K-means_ 
**Increases the runtime, converges rapidly, slow at initialization. Be caareful while increasing K. It may lead to overfitting if K == Number of observations**

## Hierarchical clustering

Better in complex shaped clusters

### Has two clustering approaches:

1. *Top-down (Divisive)*:
   * complexity O(2^n) with exhaustive search
   * divides one super cluster recursively to small ones
2. *Bottom-up (Agglomerative)*:
   * complexity O(n^2logn) with a heap at increased memory cost
   * assembles cluster in three ways:
     - Single Link: `D` between the two most closest pts in the clusters,suffers from *chaining*, clusters too spread out
     - Complete Link: `D` between the two most farthest pts in the cluster, suffers from *crowding*, clusters are not far enough
     - Average link: average `D` of all pair wise, it uses average pairwise dissimilarity, so clusters tend to be relatively compact and relatively far apart

## DBSCAN (Density-based spatial clustering of applications with noise)

Same as Hierarchical Clustering
Detects outliers and doesn't let them impact the cluster
Works on idea of density estimation

**DBSCAN Algo:**

1. Find the points in the $$\epsilon$$ neighborhood of every point, and identify core points within the *minPts* value
2. Find the connect components of *core points* on the neighborhood graph, ignoring all non core points
3. Assign each non core point to a nearby cluster if the cluster is within the $$\epsilon$$ neighbor, otherwise assign to noise



------

# Neural Networks

Intercept in Perceptron is *bias* - measure of how easy to get output 1
To avoid quick changing behavior we use Activation functions.

### Activation Functions:

**Sigmoid/Logistic**. 

* Pros
  - smooth gradient, preventing "jumps" on output values
  - output bound between 1 and 0
  - clear predictions
* Cons
  - vanishing gradient - happens for very low || high values of X -> slower downs the learning
  - output not zero centered
  - computationally expensive

**TanH | Hyperbolic func**

* Pros
  - zero centered - easier to model inputs that have strongly negative | neutral | positive
  - like sigmoid
* Cons
  - like sigmoid

**ReLU (Rectified Linear Unit)**

* Pros
  - computationally efficient - converges very quickly
  - non-linear
* Cons
  - when input approaches zero or negative, the gradient of the func becomes zero - model can't learn and backprop

**LeakyReLU**

* Pros
  - no cons of ReLU
  - like ReLu
* Cons
  - not consistent results for negative values

**Parametric ReLU**

* Pros
  - fixes the cons of leakyReLU
  - like ReLU
* Cons
  - Dependant on the problem domain

**Softmax**

* Pros
  - able to handle multiple classes 
  - usually used only for output layer, to classify inputs into multiple categories

