Improve Your Training Set with Unsupervised Learning
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
On my previous post Advanced Survey Design and Application to Big Data I mentioned unsupervised learning can be used to generate a stratification variable. In this post I want to elaborate on this point and how they can work together to improve estimates and training data for predictive models.
SRS and stratified samples
Consider the estimators of the total from an SRS and stratified sample.
![\[ \begin{array}{l l} \hat{T}_{\text{srs}} & = \sum^n_{i = 1} {\frac{N}{n}} y_{i} \\ \hat{T}_{\text{str}} & = \sum^H_{h = 1} \sum^{n_h}_{i \in S_h} {\frac{N_h}{n_h}} y_{ih} \end{array} \]](https://i0.wp.com/gradientdescending.com/wp-content/ql-cache/quicklatex.com-09350c9324eab395c605834d3f8833bd_l3.png?resize=208%2C49 "Rendered by QuickLaTeX.com")
The variance of these estimators are given by
![\[ \begin{array}{l l} \text{Var} \left( \hat{T}_{\text{srs}} \right) & = \left( 1 - \frac{n}{N} \right) N^2 \frac{s^2}{n} \\ \text{Var} \left( \hat{T}_{\text{str}} \right) & = \sum^H_{h = 1}{ \left( 1 - \frac{n_h}{N_h} \right)} N^2_h \frac{s^2_h}{n_h} \end{array} \]](https://i1.wp.com/gradientdescending.com/wp-content/ql-cache/quicklatex.com-cbe21e07df25f5ffb7d1af07a1f11b10_l3.png?resize=279%2C65 "Rendered by QuickLaTeX.com")
The variance of the stratification estimator is made up of two components, the within and between strata sum of squares.
![\[ \begin{array}{r l} SSB & = \sum^H_{h = 1} \sum^{N_h}_{i \in S_h}{\left( \bar{y}_h - \bar{y} \right)^2} = \sum^H_{h = 1}{N_h \left( \bar{y}_h - \bar{y} \right)^2} \\ SSW & = \sum^H_{h = 1} \sum^{N_h}_{i \in S_h}{\left( \bar{y}_{ih} - \bar{y}_h \right)^2} = \sum^H_{h = 1} \left( N_h - 1 \right) s^2_h \\ SSTO & = SSB + SSW = \left( N - 1 \right) s^2 \end{array} \]](https://i1.wp.com/gradientdescending.com/wp-content/ql-cache/quicklatex.com-07765dc9ef710e46f9749b25509cf905_l3.png?resize=427%2C70 "Rendered by QuickLaTeX.com")
With some algebra it can be shown
![\[ \begin{array}{r l} \text{Var}\left( \hat{T}_{\text{srs}} \right) & = \left( 1 - \frac{n}{N} \right) N^2 \frac{s^2}{n} \\ & = \left( 1 - \frac{n}{N} \right) \frac{N^2}{n} \frac{SSTO}{N - 1} \\ & = \left( 1 - \frac{n}{N} \right) \frac{N^2}{n \left(N - 1 \right)} \left( SSB + SSW \right) \\ & = \text{Var} \left( \hat{T}_{\text{str}} \right) + \left( 1 - \frac{n}{N} \right) \frac{N}{n \left(N - 1 \right)} \left[ N \left( SSB \right) - \sum^H_{h = 1}{\left( N - N_h \right)s^2_h} \right] \\ & = \text{Var} \left( \hat{T}_{\text{str}} \right) + \left( 1 - \frac{n}{N} \right) \frac{N^2}{n \left(N - 1 \right)} \left[ SSB - \sum^H_{h = 1}{\left( 1 - \frac{N_h}{N} \right)s^2_h} \right] \\ \end{array} \]](https://i2.wp.com/gradientdescending.com/wp-content/ql-cache/quicklatex.com-9b45af581680aafef49d223574b9a922_l3.png?resize=450%2C149 "Rendered by QuickLaTeX.com")
This result shows that 
while 
0″ title=”Rendered by QuickLaTeX.com” height=”33″ width=”235″ style=”vertical-align: -12px;”/> and as 
increases the stratified estimator improves on the SRS estimator.
Unsupervised Learning
Unsupervised learning attempts to uncover hidden structure in the observed data by sorting the observations into a chosen number of clusters. The simplest algorithm to do this is k-means. The k-means algorithm is as follows:
- Choose
(number of clusters) - Choose random points and assign as centers
- Compute the distance between each point and each center
- Assign each observation to the center they are closest to
- Compute the new centers given the cluster allocation
where 
contains the points allocated to cluster 
- Compute the between and within sum of squares
- Repeat 3-6 until the clusters do not change, meet a specified tolerance or max iterations met
The algorithm will minimise the within sum of squares and maximise the between sum of squares.
![\[ \begin{array}{l l} SSW & = \sum^K_{k = 1} \sum^{n_k}_{i \in S_k} (x_i - c_k)^2 \\ SSB & = \sum^K_{k = 1} n_k(c_k - \bar{c})^2 \\ SSTO & = SSW + SSB \end{array} \]](https://i0.wp.com/gradientdescending.com/wp-content/ql-cache/quicklatex.com-6a1df0c97aec8149326eb7e091f37b36_l3.png?resize=257%2C67 "Rendered by QuickLaTeX.com")
As we saw from the formula above the estimator under a stratified sample performs better than an SRS when
\sum^N_{h=1} \left( 1- \frac{N_h}{N} \right) S^2_h \]” title=”Rendered by QuickLaTeX.com”/>
From here it’s easy to see that if we construct a stratification variable which aims to minimise 
and maximise , the estimator for the corresponding sample will also perform better than by using a less efficient variable. There may be practical reasons why this isn’t possible and it makes more sense to use a natural stratification variable however there are many examples where using unsupervised learning to construct a stratification variable can improve the estimator or the training set to be used for modelling. This isn’t isolated to k-means, most clustering algorithms aim to do the same thing in different ways, and each has it’s benefits given the structure of the data. This can be expanded to more sophisticated sampling techniques and not confined to simple stratified samples.
The post Improve Your Training Set with Unsupervised Learning appeared first on Daniel Oehm | Gradient Descending.
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.