【正文】 E和NE是E的兩個(gè)子集，分別叫做正例集和反例集。假設(shè)向量空間E中的正例集PE和反例集NE的大小分別為p和n，id3基于下列兩個(gè)假設(shè)：（1）在向量空間E上的一棵正確決策樹對(duì)任意例子的分類概率同E種正反例的概率相一致，（2）一棵決策樹能對(duì)一個(gè)例子做出正確類別判斷所需要的信息量為如果以屬性A作為決策樹的根，A具有V個(gè)值{v1，v2，…v v}, 它將E分成v個(gè)子集{E1，E2,…Ev}，假設(shè)Ei中含有Pi個(gè)正例和ni個(gè)反例，那么子集Ei所需要的信息期望是I(pi，ni)，以屬性A為根所需的期望信息是：因此，以A為根的信息增益是： gain（A）=I(p，n)E(A)ID3選擇使gain（A）最大的屬性作為根節(jié)點(diǎn)，對(duì)的不同取值對(duì)應(yīng)的E的V各子集Ei遞歸調(diào)用上述生成的子節(jié)點(diǎn)B1,B2,…Bv。ID3是一個(gè)典型的決策樹學(xué)習(xí)系統(tǒng)，其核心是在決策樹的各級(jí)節(jié)點(diǎn)上選擇屬性，用信息增益作為屬性選擇標(biāo)準(zhǔn)，使得在每個(gè)非葉節(jié)點(diǎn)上進(jìn)行測(cè)試時(shí)，能獲得關(guān)于被測(cè)試?yán)幼畲蟮念悇e信息，使用該屬性將例子集分成子集后，系統(tǒng)的熵值最小，期望該非葉節(jié)點(diǎn)到達(dá)各后代葉節(jié)點(diǎn)的平均深度最小，搜索全部空間的一部分，分類速度也比較快。ID3算法運(yùn)用信息熵理論，選擇當(dāng)前樣本集中最大信息增益的屬性值作為測(cè)試屬性；樣本集的劃分則依據(jù)測(cè)試屬性的值進(jìn)行，測(cè)試屬性有多少不同取值就將樣本集劃分為多少子樣本集，同時(shí)，決策樹上相應(yīng)于該樣本集的節(jié)點(diǎn)長(zhǎng)出新的葉子節(jié)點(diǎn)。由于決策樹的結(jié)構(gòu)越簡(jiǎn)單越能從本質(zhì)的層次上概括事物的規(guī)律，期望非葉節(jié)點(diǎn)到達(dá)后代節(jié)點(diǎn)的平均路徑總是最短，即生成的決策樹的平均深度最小，這就要求在每個(gè)節(jié)點(diǎn)選擇好的劃分。 ID3算法在本系統(tǒng)中的體現(xiàn)在決策樹當(dāng)中，本系統(tǒng)對(duì)消費(fèi)者的滿意度進(jìn)行了分析，將影響消費(fèi)者滿意度的因素分成年齡 ，購(gòu)買資金，購(gòu)買折扣，交貨日期，付款方式，教育程度這六大類，并以決策樹的形式將結(jié)果進(jìn)行展現(xiàn)，提升消費(fèi)者的滿意度，提高消費(fèi)者的購(gòu)買意愿，進(jìn)而形成消費(fèi)者的購(gòu)買行為。具體如下(1)將顧客的年齡劃分為018，1924，2530，3140，40以上這幾個(gè)時(shí)間段(2)購(gòu)買的資金：非常充裕，充裕，一般，很少。(3)商品的總的折扣： 低于6折。，(4)交貨期限和運(yùn)費(fèi) ：12日高，34日中，57日低(5)付款方式： 貨到付款，支付寶，網(wǎng)上銀行，信用卡，充值卡(6)教育程度 高中以下，高中， 本科 ，本科以上由這6個(gè)要素來(lái)對(duì)消費(fèi)者的滿意度進(jìn)行實(shí)例研究，對(duì)消費(fèi)者是否滿意從上面6個(gè)方面進(jìn)行分析歸類。為提高消費(fèi)者的滿意程度。 算法的實(shí)現(xiàn)過(guò)程（1）將數(shù)據(jù)庫(kù)中的部分?jǐn)?shù)據(jù)以視圖的方式顯示出來(lái)SELECT AS Money, CASE WHEN 18 THEN 39。01839。 WHEN 18 THEN 39。01839。 WHEN 24 THEN 39。182439。 WHEN 30 THEN 39。253039。 WHEN 40 THEN 39。314039。 ELSE 39。4010039。 END AS Age, AS Education, CASE WHEN THEN 39。低于6折39。 WHEN THEN 39。6075折39。 WHEN THEN 39。7580折39。 WHEN THEN 39。8085折39。 ELSE 39。85折以上39。 END AS Discount, AS LimitTime, AS PayType, CASE WHEN THEN 39。unacc39。 WHEN THEN 39。acc39。 WHEN THEN 39。good39。 ELSE 39。vgood39。 END AS SatisfactionFROM INNER JOIN ON = （2）前臺(tái)顯示代碼 //將生成的決策樹圖形顯示，即顯示為一棵樹 private void printNode(DTreeNode root, string tabs) { if ( != null) { for (int i = 0。 i 。 i++) { DTreeNode childNode = ([i])。 printNode(childNode, \t + tabs)。 } }} protected void roadData() { samples = getDataTable()。 String sql = select * from DecisionTreeView。 ()。 samples = (samples, sql)。 ()。 } //根據(jù)選定的算法生成相應(yīng)的決策樹 protected void btnGenerateTree_Click(object sender, EventArgs e) { // btnReadData_Click(sender, e)。 roadData()。 if ( != 0) ()。 id3 = new DTree_ID3()。 // = ()。 // = ()。 //samples是全部裝載進(jìn)來(lái)的數(shù)據(jù) root = (samples, result, attributes, attributeSelectionMethod)。 (root)。}（3）后臺(tái)決策樹主體部分 public class DTree_ID3 { private DataTable mSamples。 private string mTargetAttribute = result。 public Entropy en = new Entropy()。 public TreeNode roots。 private Attribute getBestAttribute(DataTable samples, Attribute[] attributes, string attributeSelectionMethod) { double maxGain = 。 Attribute result = null。 if (attributeSelectionMethod == gain) { foreach (Attribute attribute in attributes) { double aux = (samples, attribute)。 if (aux maxGain) { maxGain = aux。 result = attribute。 } } } else if (attributeSelectionMethod == gainRatio) { foreach (Attribute attribute in attributes) { double aux = (samples, attribute)。 if (aux maxGain) { maxGain = aux。 result = attribute。 } } } return result。 } /// 判斷樣例集是否都屬于同一類,是則返回此屬性值，否則返回null private string allSamplesSameClass(DataTable samples, string targetAttribute) { string targetValue = [0][targetAttribute].ToString()。 for (int i = 1。 i 。 i++) { if (!([i][targetAttribute].ToString())) return null。 } return targetValue。 } private ArrayList getDistinctValues(DataTable samples, string targetAttribute) { ArrayList distinctValues = new ArrayList()。 foreach (DataRow row in ) { if ((row[targetAttribute]) == 1) (row[targetAttribute])。 } return distinctValues。 } private object getMostCommonValue(DataTable samples, string targetAttribute) { ArrayList distinctValues = getDistinctValues(samples, targetAttribute)。 int[] count = new int[]。 foreach (DataRow row in ) { int index = (row[targetAttribute])。 count[index]++。 } int MaxIndex = 0。 int MaxCount = 0。 for (int i = 0。 i 。 i++) { if (count[i] MaxCount) { MaxCount = count[i]。 MaxIndex = i。 } } return distinctValues[MaxIndex]。 } private TreeNode buildTree(DataTable samples, string targetAttribute, Attribute[] attributes, string attributeSelectionMethod) { TreeNode temp = new TreeNode()。 // if samples中的元組都是同一類C then string c = allSamplesSameClass(samples, targetAttribute)。 if ( c!=null) //返回N作為葉節(jié)點(diǎn)，以類C標(biāo)記 return new