## Saturday, 28 February 2015

### Review 3.1: Find Independant Features - Understand Non-Negative Matrix Factorization

Find Independant Features: Understand Non-Negative Matrix Factorization

Before start, I think we need to take a look at something seems meaningless. For example, there is a target number 5, but you guess a number 10 . So how far is your guess number to the target number. We can use 5/10 to measure this distance. It is 0.5. And the orginal target number is [You guess] * [The distance]=10 * 0.5 =5.

For single number, the idea is ridiculous. However, this is just the way how Non-Negative Matrix Factorization works. Non-Negative Matrix Factorization(NMF) is a unsupervised learning algorthm. Given a matrix M, NMF can factorize M to a weight matrix W multiplied by a feature matrix F. e.g :
| 29 , 29 |
| 43 , 33 |   can be factorized to
| 15 , 25 |

| 5, 2 |    | 3,5|
| 5, 4 | *  | 7,2|
| 5, 0 |

How the algorthm works to get W and F. Here is the steps:
1. Generate two random matrix as W and F seperately. The column count of W(cw) and the row count of F(rf) is the same as feature count (specified by youself, depends on how many features you want). The row count of W(rw) is the same as M's and the column count of F(cf) is also the same as M's
2. Let Fn = W.transpose * M, (cw (or rf) rows, cf columns) , Fd = W.transpose * (W * H)(cw (or rf) rows, cf columns) , Next H = Array(H) * (Array(Fn)/Array(Fd))(cw (or rf) rows, cf columns). (Here, you can take Fn as the orginal thing, Fd as the guessed thing, Next H is the [guessed thing] * [distance])
3. Let Wn = M * F.transpose, (rw rows, rf or (or cw) columns) , Wd = W * F * F.transpose (rw rows, rf or (or cw) columns), Next W = Array(W) * (Array(Wn)/Array(Wd)), (rw rows, rf or (or cw) columns)
4. Let H = Next H, W = Next W
5. repeat step 2~4 until then difference between W*H and M is small enough.

Source code of NMF algorthm - NMF.scala:
```import Jama._
import java.util.Random

object NMF {
def main(args:Array[String]) {
val wa = Array(Array(1.,2.,3.),Array(4.,5.,6.))
val wb = Array(Array(2.,4.),Array(2.,5.),Array(4.,7.))
val data = (new Matrix(wa)).times(new Matrix(wb))
val result = factorize(data)
display(result._1.getArray)
println()
display(result._2.getArray)
}

implicit def array2SuperArray(arg:Array[Array[Double]]) = new SuperArray(arg)

def factorize(data:Matrix,
fc:Int=2,
maxItr:Int = 500):(Matrix,Matrix) = {
val rc = data.getRowDimension
val cc = data.getColumnDimension

var w = randomMatrix(rc,fc)
var h = randomMatrix(fc,cc)

for ( i ← 0 until maxItr ) {
print( "iteration:"+i+"  ")
println(distance(w.times(h).getArray,data.getArray))
if(distance(w.times(h).getArray,data.getArray)<0 class="" data-blogger-escaped-.001="" data-blogger-escaped-0="" data-blogger-escaped-a="" data-blogger-escaped-arg.foreach="" data-blogger-escaped-arg:array="" data-blogger-escaped-arr.length="" data-blogger-escaped-arr:="" data-blogger-escaped-arr="" data-blogger-escaped-array="" data-blogger-escaped-b="" data-blogger-escaped-colcount:int="" data-blogger-escaped-colcount="" data-blogger-escaped-def="" data-blogger-escaped-display="" data-blogger-escaped-distance="" data-blogger-escaped-for="" data-blogger-escaped-h.getarray="" data-blogger-escaped-h="" data-blogger-escaped-hd.getarray="" data-blogger-escaped-hd="w.transpose.times(w).times(h)" data-blogger-escaped-hn.getarray="" data-blogger-escaped-hn="w.transpose.times(data)" data-blogger-escaped-i="" data-blogger-escaped-j="" data-blogger-escaped-length="" data-blogger-escaped-math.pow="" data-blogger-escaped-math.sqrt="" data-blogger-escaped-matrix.toarray="" data-blogger-escaped-matrix="" data-blogger-escaped-new="" data-blogger-escaped-original:array="" data-blogger-escaped-original="" data-blogger-escaped-ouble="" data-blogger-escaped-pre="" data-blogger-escaped-print="" data-blogger-escaped-println="" data-blogger-escaped-rand.nextdouble="" data-blogger-escaped-rand:random="new" data-blogger-escaped-random="" data-blogger-escaped-randommatrix="" data-blogger-escaped-result.toarray="" data-blogger-escaped-result="for" data-blogger-escaped-return="" data-blogger-escaped-rowcount:int="" data-blogger-escaped-rowcount="" data-blogger-escaped-rray="" data-blogger-escaped-superarray="" data-blogger-escaped-that:array="" data-blogger-escaped-that="" data-blogger-escaped-tmp.toarray="" data-blogger-escaped-tmp="for" data-blogger-escaped-until="" data-blogger-escaped-val="" data-blogger-escaped-var="" data-blogger-escaped-w.getarray="" data-blogger-escaped-w="" data-blogger-escaped-wd.getarray="" data-blogger-escaped-wd="w.times(h).times(h.transpose)" data-blogger-escaped-wh.length="" data-blogger-escaped-wh:array="" data-blogger-escaped-wh="" data-blogger-escaped-wn.getarray="" data-blogger-escaped-wn="(data).times(h.transpose)" data-blogger-escaped-x.foreach="" data-blogger-escaped-x="" data-blogger-escaped-y="" data-blogger-escaped-yield="" data-blogger-escaped-ystem.currenttimemillis="">

Here is a screenshot of running above source code. The last four lines is the weight matrix(the first two rows) and the feature matrix(the second two rows).

Reference: http://book.csdn.net/bookfiles/880/10088027646.shtml```