<?php
/*
*决策树ID3算法（分类算法的实现）
*/
/*
*求信息增益Grain(S1,S2)
*/
//--------------------------------------------------------------------
function Grain($train,$attriname,$flagsyes,$flagsno)
{
$attributename = array(NULL);//用来存放属性$attriname不同的属性值
array_splice($attributename,0,1);
for($i=1;$i<count($train[0]);$i++)
{
if($attriname==$train[0][$i])
{
$num = $i;//记录$train第几个属性是$attriname
for($j=1;$j<count($train);$j++)
{
$flags = true;//用于判断将要存放的属性值是否已经存在
for($k=0;$k<count($attributename);$k++)
{
if($attributename[$k]==$train[$j][$i])//即将存入的属性值已经存在
{
$flags = false;
break;
}
}
if($flags)//新的属性值不存在,$attributename存入新的属性值
{
array_push($attributename,$train[$j][$i]);
}
}
break;
}
}
for($i=0;$i<count($attributename);$i++)
{
$count[$i][0] = $attributename[$i];//属性名称
$count[$i][1] = 0;//用来统计$attributename[$i] $flagsyes的个数
$count[$i][2] = 0;//用来统计$attributename[$i] $flagsno的个数
}
for($i=1;$i<count($train);$i++)
{
for($j=0;$j<count($attributename);$j++)
{
//print_r($train[$i][count($train[$i])-1]."<br>");
if(($train[$i][$num]==$attributename[$j])&&($train[$i][count($train[$i])-1]==$flagsyes))
{
$count[$j][1]++;
}else if(($train[$i][$num]==$attributename[$j])&&($train[$i][count($train[$i])-1]==$flagsno)){
$count[$j][2]++;
}
}
}
$num_yes = 0;//类别为$flagsyes的个数
$num_no = 0;//类别为$flagsno的个数
for($i=1;$i<count($train);$i++)
{
if($train[$i][count($train[$i])-1]==$flagsyes)
{
$num_yes++;
}else {
$num_no++;
}
}
//分类所需要的 信息量
$I=0;
$s[0] = $num_yes;
$s[1] = $num_no ;
for($i=0;$i<2;$i++)
{
if($s[$i]!=0)$I += -$s[$i] / ($num_yes+$num_no) * log($s[$i]/($num_yes+$num_no)) / log(2);
}
$EA = 0 ;
for($i=0;$i<count($count);$i++)
{
$si = 0;
for($j=1;$j<count($count[$i]);$j++)
{
if($count[$i][$j]!=0)$si += -$count[$i][$j] / ($count[$i][1]+$count[$i][2]) * log($count[$i][$j]/($count[$i][1]+$count[$i][2])) / log(2);
}
$EA += ($count[$i][1]+$count[$i][2])/($num_yes+$num_no) * $si;
}
//信息增益Gain
$Gain = $I - $EA;
return $Gain;
}
//--------------------------------------------------------------------
/*
*求几个属性信息增益最大的那一个
*/
//--------------------------------------------------------------------
function Attributelist($train,$flagsyes,$flagsno)
{
$array_attribute_grain = array(array(NULL,NULL));//存放属性值以及属性值对应的信息增益
for($i=1;$i<count($train[0])-1;$i++)
{
$array_attribute_grain[$i-1][0] = $train[0][$i];
$array_attribute_grain[$i-1][1] = Grain($train,$train[0][$i],$flagsyes,$flagsno);
}
for($i=1;$i<count($array_attribute_grain);$i++)
{
if($array_attribute_grain[$i][1]>$array_attribute_grain[0][1])
{
$array_attribute_grain[0][0] = $array_attribute_grain[$i][0];
$array_attribute_grain[0][1] = $array_attribute_grain[$i][1];
}
}
/*
echo "<pre>";
print_r($array_attribute_grain[0]);
echo "<pre>";
*/
return $array_attribute_grain[0];
}
//--------------------------------------------------------------------
/*
*构建ID3决策树(数组存储)
*/
//--------------------------------------------------------------------
function DecisionTree($train,$flagsyes,$flagsno,&$array_tree)
{
$flags = true;
/*
*if所有样本均为同一类别C，返回N作为一个椰子结点并标志为C类别
*/
$num_yes = 0;//用于统计同一$flagsyes类别的数目
$num_no = 0;//用于统计同一$flagsno类别的数目
for($i=1;$i<count($train);$i++)
{
if($train[$i][count($train[$i])-1]==$flagsyes) $num_yes++;
else if($train[$i][count($train[$i])-1]==$flagsno) $num_no++;
}
if($num_yes==(count($train)-1))//所有样本均为同一类别
{
array_push($array_tree,array($flagsyes));
$count++;
$flags = false;
}else if($num_no==(count($train)-1)){
array_push($array_tree,array($flagsno));
$count++;
$flags = false;
}
/*
*else if attribute /为空,则返回n作为一个叶子节点，并标记为该节点所含样本中类别最多的类别
*/
if($flags)
{
$num_attribute = count($train)-2;
if($num_attribute==0)
{
if($num_yes>$num_no)
{
array_push($array_tree,array($flagsyes));
$count++;
$flags = false;
}else {
array_push($array_tree,array($flagsno));
$count++;
$flags = false;
}
}
}
/*
*从样本中选择分类能力最好的的属性
*/
if($flags)
{
$attribute = Attributelist($train,$flagsyes,$flagsno);
$attribute_name = array(NULL);
array_splice($attribute_name,0,1);
for($i=1;$i<count($train[0])-1;$i++)
{
if($train[0][$i]==$attribute[0])
{
$num = $i;
break;
}
}
for($i=1;$i<count($train);$i++)
{
$flags2 = true;
for($j=0;$j<count($attribute_name);$j++)
{
if($train[$i][$num]==$attribute_name[$j])
{
$flags2 = false;
break;
}
}
if($flags2)array_push($attribute_name,$train[$i][$num]);
}
//print_r($attribute_name);
$array_new = array(NULL);
array_splice($array_new,0,1);
for($i=0;$i<count($attribute_name);$i++)
{
$arraybranch = array(array());
array_splice($arraybranch,0,1);
$arraytemp = array(NULL);
array_splice($arraytemp,0,1);
array_push($arraybranch,$train[0]);
for($j=1;$j<count($train);$j++)
{
if($train[$j][$num]==$attribute_name[$i])
{
array_push($arraybranch,$train[$j]);
}
}
for($j=0;$j<count($arraybranch);$j++)
{
array_splice($arraybranch[$j],$num,1);
}
array_push($array_new,$arraybranch);
$num_branch_yes = 0;
$num_branch_no =0;
for($j=1;$j<count($arraybranch);$j++)
{
if($arraybranch[$j][count($arraybranch[$j])-1]==$flagsyes) $num_branch_yes++;
else $num_branch_no++;
}
if($num_branch_yes==count($arraybranch)-1)array_push($array_tree,array($attribute[0],$attribute_name[$i],$flagsyes));
else if($num_branch_no==count($arraybranch)-1)array_push($array_tree,array($attribute[0],$attribute_name[$i],$flagsno));
else {
$temp = Attributelist($arraybranch,$flagsyes,$flagsno);
array_push($array_tree,array($attribute[0],$attribute_name[$i],$temp[0]));
DecisionTree($arraybranch,$flagsyes,$flagsno,$array_tree,$count);
}
}
}
/*
echo "<pre>";
print_r($array_tree);
echo "<pre>";
//print_r("<br>".$count);
*/
return $array_tree;
}
//--------------------------------------------------------------------
/*
*判断一个测试样本的类别
*/
//--------------------------------------------------------------------
function ID3_Judge($test,$co,$decisiontree,$flagsyes,$flagsno)
{
//找寻根节点
$boot = $decisiontree[0][0];
for($i=1;$i<count($test[0])-1;$i++)
{
if($boot==$test[0][$i])
{
$num = $i;
break;
}
}
for($i=0;$i<count($decisiontree);$i++)
{
if(($decisiontree[$i][0]==$boot)&&($decisiontree[$i][1]==$test[$co][$num]))
{
if($decisiontree[$i][2]==$flagsyes)
{
$result = $flagsyes;
}else if($decisiontree[$i][2]==$flagsno){
$result = $flagsno;
}else{
$attributename = $decisiontree[$i][2];
$mid = $i;
}
}
}
while($attributename!=NULL)
{
$boot = $attributename;
for($i=1;$i<count($test[0])-1;$i++)
{
if($boot==$test[0][$i])
{
$num = $i;
break;
}
}
for($i=$mid;$i<count($decisiontree);$i++)
{
if(($decisiontree[$i][0]==$boot)&&($decisiontree[$i][1]==$test[$co][$num]))
{
if($decisiontree[$i][2]==$flagsyes)
{
$attributename = NULL;
$result = $flagsyes;
}else if($decisiontree[$i][2]==$flagsno){
$attributename = NULL;
$result = $flagsno;
}else{
$attributename = $decisiontree[$i][2];
$mid = $i;
}
}
}
}
return $result;
}
//--------------------------------------------------------------------
/*
*把.txt中的内容读到数组中保存
*$filename:文件名称
*/
//--------------------------------------------------------------------
function gerFileContent($filename)
{
$array = array(NULL);
$content = file_get_contents($filename);
$result = explode("\r\n",$content);
for($j=0;$j<count($result);$j++)
{
$con = explode(" ",$result[$j]);
array_push($array,$con);
}
array_splice($array,0,1);
return $array;
}
//--------------------------------------------------------------------
$train = gerFileContent("train.txt");
$test = gerFileContent("test.txt");
$array_tree = array(array(NULL,NULL,NULL));
array_splice($array_tree,0,1);
$decisiontree = DecisionTree($train,Y,N,$array_tree);
for($i=1;$i<count($test);$i++)
{
$test[$i][count($test[0])-1] = ID3_Judge($test,$i,$decisiontree,Y,N);
}
/*
*将数组中的内容读到.txt中
*/
//--------------------------------------------------------------------
$fp= fopen('result.txt','wb');
for($i=0;$i<count($test);$i++)
{
$temp = NULL;
for($j=0;$j<count($test[$i]);$j++)
{
$temp = $test[$i][$j]."\t";
fwrite($fp,$temp);
}
fwrite($fp,"\r\n");
}
fclose($fp);
//--------------------------------------------------------------------
/*
*打印输出决策树
*/
//--------------------------------------------------------------------
echo "<pre>";
print_r($decisiontree);
echo "<pre>";
//--------------------------------------------------------------------
/*
*打印输出
*/
//--------------------------------------------------------------------
echo "<pre>";
print_r($test);
echo "</pre>";
//--------------------------------------------------------------------
?>