Posted: 11/15/21

Due: 11/22/21, 11:55PM

Science usually arises from observation of regularity in data. A first step in all scientific analysis is the organization of such observations into groups based upon some similarity criterion. Grouping through quantitative mathematical procedures requires the definition of a distance between observations and a procedure to form observation clusters. This project is an introduction to this basic task in data science using classification of letter images as an example.

Figure 1. First 400 characters in Kaggle data base (First Steps With Julia | Kaggle)

Tasks:

• Establish a distance function suitable for character identification

• Establish number of clusters

• Test clustering procedure for new character images

1Introduction

(Read First Steps With Julia | Kaggle and research $k$-Means algorithm, e.g., Wikipedia)

2Methods

2.1Import data

∴ 

import Pkg; Pkg.add("ImageMagick")

∴ 

Once the Julia environment has been updated to contain the ImageMagick and Images packages, they can be used to analyze the character image data.

∴ 

using Images, ImageMagick

∴ 

cd(homedir()*"/courses/MATH089/clustering/testResized")

∴ 

files=readdir(); c=load(files[1]); nFiles=size(files); mx,my=size(c); [nFiles mx my]

∴ 

c[1,1]

∴ 

Gray(c[1,1])

∴ 

Float64(Gray(c[1,1]))

∴ 

C=Float64.(Gray.(c)); imshow(C,cmap="gray");

2.2$k$-means algorithm

∴ 

import Pkg; Pkg.add("Clustering")

∴ 

The $k$-means algorithm seeks to group $n$ observations, each of dimension $d$ into $k$ clusters. For this application an observation is one of the character images and $d=3m_x{m}_y$ using all color channels.

∴ 

using Clustering

∴ 

2.2.1Single vector representation of color image

Each pixel in the image contains three color channels

∴ 

c[1,1]

∴ 

red(c[1,1])

∴ 

Float64(red(c[1,1]))

Define a function to form a single vector of size $3m_x{m}_y$ from an image of size $m_x\times m_y$

∴ 

function FormObs(c)
  mx,my = size(c); d = 3*mx*my; 
  r=Float64.(red.(c)); g=Float64.(green.(c)); b=Float64.(blue.(c));
  reshape([r g b],(d,1))
end

∴ 

x=FormObs(c);

∴ 

size(x)

∴ 

size(c)

2.2.2Apply $k$-means on data subset

The data set contains vectors ${𝒙}_i$ for $i=1,\dots ,n$, where $n$ is the number of images, and each ${𝒙}_i$ contains $d=1200$ numbers. The goal of the $k$-means algorithm is to define sets $S_j$ for $j=1,\dots ,k$ that contain similar images, presumably of the same letter. Let $S=\{S_1,\dots ,S_k\}$. The $k$-means algorithm minimizes the variance in each cluster

∴ 

function FormDataSet(n0,n,f)
  c = load.(f[n0:n0+n-1])
  X = FormObs(c[1])
  for i=2:n
    X = [X FormObs(c[i])]
  end
  return(X)
end

∴ 

n0=200; n=100; X=FormDataSet(n0,n,files); size(X)

∴ 

kGroups=2; K=kmeans(X,kGroups);

∴ 

S=assignments(K); nS=counts(K); C=K.centers;

∴ 

S[1:10]'

∴ 

size(C)

∴ 

2.3Display $k$-means results

2.3.1Display centers

Each center represents an image. Display it.

3Results

4Discussion

(Present your conclusions on the use of random numbers to simulate real-life models)