|
花了兩天時(shí)間將cart算法中離散數(shù)據(jù)分類寫完（后面還有連續(xù)數(shù)據(jù)的處理和決策樹裁剪）。這次感覺比id3實(shí)現(xiàn)要更有成就感，畢竟一般以上的代碼自己寫的。不過看看寫好的代碼還是有些不堪回首啊。寫代碼還不熟練以后要多加鍛煉！
cart算法介紹： 與id3相比cart主要在度量參數(shù)方面不同，cart用gini指標(biāo)用作屬性劃分的標(biāo)準(zhǔn)。 對(duì)于元素的二元分裂由另一公式判斷： 對(duì)于單列屬性的二元分裂要選取GiniA(D)最小的一個(gè)來最為該屬性列上的一個(gè)合理劃分。而選擇作為節(jié)點(diǎn)的屬性列也要根據(jù)最小的gini指標(biāo)判斷。 大致的特點(diǎn)就是這樣。
1 for (int i = 0; i < columns.size(); i++) {
但是，算法實(shí)現(xiàn)的外有一個(gè)難點(diǎn)，就是在選擇二元分裂時(shí)，對(duì)屬性項(xiàng)的真子集選擇。對(duì)于有n個(gè)屬性值的屬性，會(huì)有2^n種不同的組合方式。 因?yàn)樗惴ㄋ竭€沒那么高，這個(gè)我就直接借鑒別人的代碼了。大致思想就是將每個(gè)屬性用二進(jìn)制位（n個(gè)屬性就用n個(gè)二進(jìn)制為來表示）來表示，1表示選擇該屬性，0表示不選擇該屬性。
package BaseStructure.Tree;
import java.util.BitSet; import java.util.HashSet; import java.util.Set; public class ProperSubsetCombination { private static Integer[] array; private static BitSet startBitSet; // 比特集合起始狀態(tài) private static BitSet endBitSet; // 比特集合終止?fàn)顟B(tài)，用來控制循環(huán) private static Set<Set<Integer>> properSubset; // 真子集集合 /** * 計(jì)算得到一個(gè)集合的非空真子集集合 * * @param n * 真子集的大小 * @param itemSet * 一個(gè)頻繁項(xiàng)集元素 * @return 非空真子集集合 */ public static Set<Set<Integer>> getProperSubset(int n, Set<Integer> itemSet) { Integer[] array = new Integer[itemSet.size()]; ProperSubsetCombination.array = itemSet.toArray(array); properSubset = new HashSet<Set<Integer>>(); startBitSet = new BitSet(); endBitSet = new BitSet(); // 初始化startBitSet，左側(cè)占滿1 for (int i = 0; i < n; i++) { startBitSet.set(i, true); } // 初始化endBit，右側(cè)占滿1 for (int i = array.length - 1; i >= array.length - n; i--) { endBitSet.set(i, true); } // 根據(jù)起始startBitSet，將一個(gè)組合加入到真子集集合中 get(startBitSet); while (!startBitSet.equals(endBitSet)) { int zeroCount = 0; // 統(tǒng)計(jì)遇到10后，左邊0的個(gè)數(shù) int oneCount = 0; // 統(tǒng)計(jì)遇到10后，左邊1的個(gè)數(shù) int pos = 0; // 記錄當(dāng)前遇到10的索引位置 // 遍歷startBitSet來確定10出現(xiàn)的位置 for (int i = 0; i < array.length; i++) { if (!startBitSet.get(i)) { zeroCount++; } if (startBitSet.get(i) && !startBitSet.get(i + 1)) { pos = i; oneCount = i - zeroCount; // 將10變?yōu)?1 startBitSet.set(i, false); startBitSet.set(i + 1, true); break; } } // 將遇到10后，左側(cè)的1全部移動(dòng)到最左側(cè) int counter = Math.min(zeroCount, oneCount); int startIndex = 0; int endIndex = 0; if (pos > 1 && counter > 0) { pos--; endIndex = pos; for (int i = 0; i < counter; i++) { startBitSet.set(startIndex, true); startBitSet.set(endIndex, false); startIndex = i + 1; pos--; if (pos > 0) { endIndex = pos; } } } get(startBitSet); } return properSubset; } /** * 根據(jù)一次移位操作得到的startBitSet，得到一個(gè)真子集 * * @param bitSet */ private static void get(BitSet bitSet) { Set<Integer> set = new HashSet<Integer>(); for (int i = 0; i < array.length; i++) { if (bitSet.get(i)) { set.add(array[i]); } } properSubset.add(set); } } |
|
|
，其中pi為D中元素屬于Ci類的概率。
