K-Modes算法[聚类算法]

聚类算法k-Modes的实现

 

<?php
/*
*Kmodes算法（聚类算法的实现）
*/


/*
*获取簇的数目
*/
//--------------------------------------------------------------------    
function Category($train)
{
    $category = array(NULL);//存放不同的类别
    array_splice($category,0,1);
    
    for($i=1;$i<count($train);$i++)
    {
        $flags = true;//标志，用于标记将要存入的类别是否已经存在
        for($j=0;$j<count($category);$j++)
        {
            if($category[$j]==$train[$i][count($train[$i])-1])
            {
                $flags = false;
                 break;
            }
        }
        if($flags)
        {
            array_push($category,$train[$i][count($train[$i])-1]);
        }
    }
    return $category;
}
//--------------------------------------------------------------------

/*
*获得初始矩阵M
*/
//--------------------------------------------------------------------
function first_M($train)
{
    $category = Category($train);
    $M = array(NULL);
    array_splice($M,0,1);
    $num = 1;
    for($j=0;$j<count($category);$j++)
    {
        while($num<count($train))
        {
            if($train[$num][count($train[$num])-1]==$category[$j])
            {
                $temp = $train[$num];
                //print_r($temp);
                array_splice($temp,0,1);
                array_splice($temp,count($temp)-1,1);
                array_push($M,$temp);
                $num++;
                break;
            }else{
                $num++;
            }
        }
    }
/*    echo "<pre>";
    print_r($M);
*/
    return $M;
}
//--------------------------------------------------------------------


/*
*获得距离dis(ml,ei)
*/
//--------------------------------------------------------------------
function dis($array,$e)
{
    $temp = $array;
    $sum = 0;
    for($i=1;$i<count($array)-1;$i++)
    {
        if($array[$i]!=$e[$i-1])
        {
            $sum++;
        }
    }
    return $sum;
}
//--------------------------------------------------------------------

/*
*获得新的矩阵W
*/
//--------------------------------------------------------------------
function W($train,$M)
{
    $W = array(NULL);

    for($i=1;$i<count($train);$i++)
    {
        $flags = true;
        $min = dis($train[$i],$M[0]);
        for($j=2;$j<=count($M);$j++)
        {
            if(dis($train[$i],$M[$j-1])<$min)
            {
                $min = dis($train[$j],$M[$j-1]);
            }
        }
        
        for($j=1;$j<=count($M);$j++)
        {
            if(dis($train[$i],$M[$j-1])==$min)
            {
                $num = $j;
                break;
            }
        }
        for($j=1;$j<=count($M);$j++)
        {
            
            if($j!=$num)
            {
                $W[$j][$i] = 0;
            }else{
                 $W[$j][$i] = 1;
            }
            
        }
    }
/*
    for($i=1;$i<=count($M);$i++)
    {
        $flags = true;
        for($j=2;$j<count($train);$j++)
        {
            $flags = true;
            $min = dis($train[$j],$M[$i-1]);
            for($k=1;$k<=count($M);$k++)
            {
                if((dis($train[$j],$M[$k-1])<=$min)&&($k!=$i))
                {
                    $flags = false;
                    break;
                }
            }
            if($flags)
            {
                $W[$i][$j] = 1;
            }else $W[$i][$j] = 0;
        }
    }
*/    
    return $W;
}
//--------------------------------------------------------------------


/*
*获得 F_W_M
*/
//--------------------------------------------------------------------
function F_W_M($train,$M,$W)
{
    $fwm = 0;
    for($i=1;$i<=count($M);$i++)
    {
        for($j=1;$j<count($train);$j++)
        {
            $fwm += dis($train[$j],$M[$i-1])*$W[$i][$j];
        }
    }
/*    echo "<pre>";
    //print_r($W);
    echo "<pre>";
    print_r($fwm);
*/    
    return $fwm;
}
//--------------------------------------------------------------------


/*
*获得新的矩阵M单行元素
*/
//--------------------------------------------------------------------
function New_SingleM($array)
{
    $new_m = array();
    array_splice($new_m,0,1);
    for($i=1;$i<count($array[0])-1;$i++)
    {
        $temp = array();
        array_splice($temp,0,1);
        for($j=0;$j<count($array);$j++)
        {
            $flags = true;
            for($k=0;$k<count($temp);$k++)
            {
                if($temp[$k][0]==$array[$j][$i])
                {
                    $flags = false;
                    $temp[$k][1]++;
                }
            }
            if($flags)
            {
                array_push($temp,array($array[$j][$i],1));
            }
        }
        $max[0]=$temp[0][0];
        $max[1]=$temp[0][1];
        for($j=1;$j<count($temp);$j++)
        {
            if($temp[$j][1]>$max[1])
            {
                $max[0]=$temp[$j][0];
                $max[1]=$temp[$j][1];
            }
        }
        array_push($new_m,$max[0]);
/*    
        echo "<pre>";
        print_r($temp);
        print_r($max[0]);
*/
    }
/*
    echo "<pre>";
    print_r($new_m);
*/
    return $new_m;
}
//--------------------------------------------------------------------


/*
*获得新的矩阵M
*/
//--------------------------------------------------------------------
function New_M($train,$W)
{
    $new_train = array(NULL);
    array_splice($new_train,0,1);
    for($i=1;$i<count($W);$i++)
    {
        $array = array(NULL);
        array_splice($array,0,1);
        for($j=1;$j<=count($W[1]);$j++)
        {
            if($W[$i][$j]==1)
            {
                array_push($array,$train[$j]);
            }
        }
        array_push($new_train,$array);
    }
    $new_M = array();
    array_splice($new_M,0,1);
    for($i=0;$i<count($new_train);$i++)
    {
        array_push($new_M,New_SingleM($new_train[$i]));
    }
/*    echo "<pre>";
    print_r($new_train);
    
    echo "<pre>";
    print_r($new_M);
*/
    return $new_M;
}
//--------------------------------------------------------------------


/*
*Kmodes算法
*$m,&$w,返回矩阵M,W
*/
//--------------------------------------------------------------------
function  Kmodes($train,&$m,&$w)
{
    $M = first_M($train);
    $FWM = 1;
    $FWM2 =0;
    while(abs($FWM2 - $FWM)>0)
    {
        $W = W($train,$M);
        $FWM = F_W_M($train,$M,$W);
        $M = New_M($train,$W);
        $FWM2 = F_W_M($train,$M,$W);

        if(abs($FWM2 - $FWM )>0)
        {
            $FWM = $FWM2;
            $W = W($train,$M2);
            $FWM2 = F_W_M($train,$M,$W);
        }
    }
    $m = $M;
    $w = $W;
}
//--------------------------------------------------------------------


/*
*把.txt中的内容读到数组中保存
*$filename:文件名称
*/
//--------------------------------------------------------------------
function  getFileContent($filename)
{
    $array = array(null);
    $content = file_get_contents($filename);
    $result = explode("\r\n",$content);
    //print_r(count($result));
    for($j=0;$j<count($result);$j++)
    {
        //print_r($result[$j]."<br>");
        $con = explode(" ",$result[$j]);
        array_push($array,$con);
    }
    array_splice($array,0,1);
    return $array;
}
//--------------------------------------------------------------------


/*
*把数组中内容写到.txt中保存
*$result:要存储的数组内容
*$filename:文件名称
*/
//--------------------------------------------------------------------
function Array_Totxt($result,$filename)
{
    $fp= fopen($filename,'wb');
    for($i=0;$i<count($result);$i++)
    {
        $temp = NULL;
        for($j=0;$j<=count($result[$i]);$j++)
        {
            $temp =  $result[$i][$j]."\t";
            fwrite($fp,$temp);
        }
        fwrite($fp,"\r\n");
    }
    fclose($fp);
}
//--------------------------------------------------------------------
    $train = getFileContent("train.txt");
    Kmodes($train,$M,$W);
    Array_Totxt($M,"M.txt");
    Array_Totxt($W,"w.txt");
        
?>

 

 

 M矩阵：

 

W矩阵: