【正文】 E和NE是E的兩個子集，分別叫做正例集和反例集。假設(shè)向量空間E中的正例集PE和反例集NE的大小分別為p和n，id3基于下列兩個假設(shè)：（1）在向量空間E上的一棵正確決策樹對任意例子的分類概率同E種正反例的概率相一致，（2）一棵決策樹能對一個例子做出正確類別判斷所需要的信息量為如果以屬性A作為決策樹的根，A具有V個值{v1，v2，…v v}, 它將E分成v個子集{E1，E2,…Ev}，假設(shè)Ei中含有Pi個正例和ni個反例，那么子集Ei所需要的信息期望是I(pi，ni)，以屬性A為根所需的期望信息是：因此，以A為根的信息增益是： gain（A）=I(p，n)E(A)ID3選擇使gain（A）最大的屬性作為根節(jié)點(diǎn)，對的不同取值對應(yīng)的E的V各子集Ei遞歸調(diào)用上述生成的子節(jié)點(diǎn)B1,B2,…Bv。ID3是一個典型的決策樹學(xué)習(xí)系統(tǒng)，其核心是在決策樹的各級節(jié)點(diǎn)上選擇屬性，用信息增益作為屬性選擇標(biāo)準(zhǔn)，使得在每個非葉節(jié)點(diǎn)上進(jìn)行測試時，能獲得關(guān)于被測試?yán)幼畲蟮念悇e信息，使用該屬性將例子集分成子集后，系統(tǒng)的熵值最小，期望該非葉節(jié)點(diǎn)到達(dá)各后代葉節(jié)點(diǎn)的平均深度最小，搜索全部空間的一部分，分類速度也比較快。ID3算法運(yùn)用信息熵理論，選擇當(dāng)前樣本集中最大信息增益的屬性值作為測試屬性；樣本集的劃分則依據(jù)測試屬性的值進(jìn)行，測試屬性有多少不同取值就將樣本集劃分為多少子樣本集，同時，決策樹上相應(yīng)于該樣本集的節(jié)點(diǎn)長出新的葉子節(jié)點(diǎn)。由于決策樹的結(jié)構(gòu)越簡單越能從本質(zhì)的層次上概括事物的規(guī)律，期望非葉節(jié)點(diǎn)到達(dá)后代節(jié)點(diǎn)的平均路徑總是最短，即生成的決策樹的平均深度最小，這就要求在每個節(jié)點(diǎn)選擇好的劃分。 ID3算法在本系統(tǒng)中的體現(xiàn)在決策樹當(dāng)中，本系統(tǒng)對消費(fèi)者的滿意度進(jìn)行了分析，將影響消費(fèi)者滿意度的因素分成年齡 ，購買資金，購買折扣，交貨日期，付款方式，教育程度這六大類，并以決策樹的形式將結(jié)果進(jìn)行展現(xiàn)，提升消費(fèi)者的滿意度，提高消費(fèi)者的購買意愿，進(jìn)而形成消費(fèi)者的購買行為。具體如下(1)將顧客的年齡劃分為018，1924，2530，3140，40以上這幾個時間段(2)購買的資金：非常充裕，充裕，一般，很少。(3)商品的總的折扣： 低于6折。，(4)交貨期限和運(yùn)費(fèi) ：12日高，34日中，57日低(5)付款方式： 貨到付款，支付寶，網(wǎng)上銀行，信用卡，充值卡(6)教育程度 高中以下，高中， 本科 ，本科以上由這6個要素來對消費(fèi)者的滿意度進(jìn)行實例研究，對消費(fèi)者是否滿意從上面6個方面進(jìn)行分析歸類。為提高消費(fèi)者的滿意程度。 算法的實現(xiàn)過程（1）將數(shù)據(jù)庫中的部分?jǐn)?shù)據(jù)以視圖的方式顯示出來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）前臺顯示代碼 //將生成的決策樹圖形顯示，即顯示為一棵樹 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)來的數(shù)據(jù) root = (samples, result, attributes, attributeSelectionMethod)。 (root)。}（3）后臺決策樹主體部分 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