张慧的博客

BlogJava :: 首页 :: 联系 :: 聚合

:: 管理

45 Posts :: 0 Stories :: 24 Comments :: 0 Trackbacks

机器学习-手写和本机数字识别-K均值和欧氏距离

一、欧氏距离

二维的公式

　　ρ = sqrt( (x1-x2)^2+(y1-y2)^2 )

三维的公式

　　ρ = sqrt( (x1-x2)^2+(y1-y2)^2+(z1-z2)^2 )

n维空间的公式

　　n维欧氏空间是一个点集,它的每个点 X 可以表示为 (x[1]，x[2]，…，x[n]) ，其中 x[i](i = 1，2，…，n) 是实数，称为 X 的第i个坐标，两个点 A = (a[1]，a[2]，…，a[n]) 和 B = (b[1]，b[2]，…，b[n]) 之间的距离 ρ(A，B) 定义为下面的公式。

　　ρ(A，B) =sqrt [ ∑( a[i] - b[i] )^2 ] (i = 1，2，…，n)

二、K均值算法

k均值(k-means)是聚类算法的一种，聚类分析是根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的，而不同组中的对象是不同的。组内的相似性越大，组间差别越大，聚类就越好。

举个例子，在二维平面上有几百个点，在笛卡儿坐标系中有(x,y)坐标，把它们点到纸上，问题是如何把它们分成不同组，每个组里点彼此之前都比较相近，而离其它组的成员又比较远。下面介绍的k均值就能干这种事。

基本k均值

基本k均值思想很简单，首先，选择k个初始质心，其中k是用户指定的参数，即所期望的簇的个数。每个点被指派到最近的质心，而指派到一个质心的点集为一个簇。然后根据指派到簇的点，更新每个簇的质心。重复指派和更新步骤，直到簇不发生变化，或等价的，直到质心不发生变化。

三、特征提取

1、第一步，参照网上曾经有人的做法:

为简单起见，我们使用了最简单的图像特征——黑色像素在图像中的分布来进行训练和测试。首先，我们把图像规范化为 32*32 像素的图片，然后按 2*2 分切成 16*16 共 256 个子区域，然后统计这 4 个像素中黑色像素的个数，组成 256 维的特征矢量，如下是数字 2 的一个特征矢量：
0 0 4 4 4 2 0 0 0 0 0 0 0 0 2 4 0 0 4 4 4 2 0 0 0 0 0 0 0 0 2 4 2 2 4 4 2 1 0 0 0 0 0 0 1 2 3 4 4 4 4 4 0 0 0 0 0 0 0 0 2 4 4 4 4 4 4 4 0 0 0 0 0 0 0 0 2 4 4 4 4 4 0 0 0 0 0 0 0 0 0 0 2 4 4 4 4 4 0 0 0 0 0 0 0 0 0 0 2 4 4 4 4 4 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 4 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 4 2 2 2 2 2 2 2 4 4 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 0 2 4 4 4 2 2 2 2 4 3 2 2 2 2 2 0 2 4 4 4 0 0 0 0 4 2 0 0 0 0 0 0 2 4 4 4 0 0 0 0 4 2 0 0 0 0 0 0 2 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 2 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 2 4 4 4
相应地，因为我们只需要识别 0~9 共 10 个数字，所以创建一个 10 维的矢量作为结果，数字相应的维置为 1 值，其它值为 0。数字 2 的结果如下：0 0 1 0 0 0 0 0 0 0

核心代码为:

Vb.net代码  
For m_i As Integer = 1 To 16  
     myinitwidth = myendwidth  
     myendwidth += jiange  
     For myi As Integer = myinitwidth To myendwidth  
         For myj As Integer = myinitheight To myendheight  
             mycolor = myybcominfo.mybitmap.GetPixel(myi, myj)  
             If mycolor.B = 0 And mycolor.R = 255 And mycolor.G = 0 Then  
                 While (Not Monitor.TryEnter(mymonitorobj))  
                     Thread.Sleep(1)  
                 End While  
                 myjgtz(mycount) += 1  
                 Monitor.Exit(mymonitorobj)  
                 Thread.Sleep(1)  
             End If  
         Next  
     Next  
     mycount += 1  
     myendwidth += 1  
 Next  

2、在第一步的特征基础上进一步加工，加上位置信息，以位置做为权重，调整第一步的特征矢量，核心代码为:

Vb.net代码  
For mi As Integer = 0 To 15  
    If myjgtz(mi) > 0 Then  
        pictz(myii, myjj, m_j) += mi * myjgtz(mi)  
    End If  
    myjgtz(mi) = 0  
Next  

3、第三步计算每个数字的K均值，核心代码为:

Vb.net代码  
'计算K均值  
       Dim mmsum As Double = 0  
       For myii As Integer = 0 To 9  
           mystr &= vbCrLf & myii & "的样本均值是：" & vbCrLf  
           For myk As Integer = 0 To 15  
               mmsum = 0  
               For myjj As Integer = 0 To 9  
                   mmsum += pictz(myii, myjj, myk)  
                   ProgressBar1.Value = count  
                   count += 1  
               Next  
               mmsum /= 10  
               ktz(myii, myk) = mmsum  
               mystr &= ktz(myii, myk) & ","  
           Next  
           mystr &= vbCrLf  
       Next  

最后，进行待识别数字的特征值，然后进行欧氏距离对比

Vb.net代码  
Dim jqtz(16) As Integer  
                '欧氏距离   
        Dim mys(10) As Integer  
        Dim temp As Integer = 1000000000  
        Dim jgnum As Integer = -1  
        For m_iii As Integer = 0 To 9  
            mys(m_iii) = 0  
            For m_jjj As Integer = 0 To 15  
                mys(m_iii) += Pow(ktz(m_iii, m_jjj) - jqtz(m_jjj), 2)  
            Next  
            If mys(m_iii) < temp Then  
                temp = mys(m_iii)  
                jgnum = m_iii  
            End If  
        Next  
        jg.Text = ""  
        For m_iii = 0 To 9  
            jg.Text &= m_iii & ":" & mys(m_iii) & vbCrLf  
        Next  
        jg.Text &= "结果是：" & jgnum  