機器學習期末報告算法實驗.doc

機器學習期末報告（一）決策樹一、決策樹簡介決策樹是一種用來表示人們?yōu)榱俗龀瞿硞€決策而進行的一系列判斷過程的樹形圖。決策樹方法的基本思想是：利用訓練集數(shù)據(jù)自動地構造決策樹，然后根據(jù)這個決策樹對任意實例進行判定。決策樹算法是一種逼近離散函數(shù)值的方法。它是一種典型的分類方法，首先對數(shù)據(jù)進行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對新數(shù)據(jù)進行分析。本質上決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程。決策樹方法最早產(chǎn)生于上世紀60年代，到70年代末。由J Ross Quinlan提出了ID3算法，此算法的目的在于減少樹的深度。但是忽略了葉子數(shù)目的研究。C4.5算法在ID3算法的基礎上進行了改進，對于預測變量的缺值處理、剪枝技術、派生規(guī)則等方面作了較大改進，既適合于分類問題，又適合于回歸問題。決策樹算法構造決策樹來發(fā)現(xiàn)數(shù)據(jù)中蘊涵的分類規(guī)則如何構造精度高、規(guī)模小的決策樹是決策樹算法的核心內(nèi)容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數(shù)據(jù)集是根據(jù)實際需要有歷史的、有一定綜合程度的，用于數(shù)據(jù)分析處理的數(shù)據(jù)集。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數(shù)扼集（稱為測試數(shù)據(jù)集）中的數(shù)據(jù)校驗決策樹生成過程中產(chǎn)生的初步規(guī)則，將那些影響預衡準確性的分枝剪除二、決策樹的工作原理決策樹一般都是自上而下的來生成的。選擇分割的方法有多種，但是目的都是一致的，即對目標類嘗試進行最佳的分割。從根節(jié)點到葉子節(jié)點都有一條路徑，這條路徑就是一條“規(guī)則”。決策樹可以是二叉的，也可以是多叉的。對每個節(jié)點的衡量：1) 通過該節(jié)點的記錄數(shù)；2) 如果是葉子節(jié)點的話，分類的路徑；3) 對葉子節(jié)點正確分類的比例。有些規(guī)則的效果可以比其他的一些規(guī)則要好。YYYYNNNNw1Tx0 w4Tx0 w3Tx0 w2Tx0 二叉決策樹框圖三、決策樹算法 決策樹的典型算法有ID3，C4.5，CART等。國際權威的學術組織，數(shù)據(jù)挖掘國際會議ICDM （the IEEE International Conference on Data Mining）在2006年12月評選出了數(shù)據(jù)挖掘領域的十大經(jīng)典算法中，C4.5算法排名第一。C4.5算法是機器學習算法中的一種分類決策樹算法,其核心算法是ID3算法。C4.5算法產(chǎn)生的分類規(guī)則易于理解，準確率較高。不過在構造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，在實際應用中因而會導致算法的低效。決策樹算法的優(yōu)點如下：（1）分類精度高；（2）生成的模式簡單；（3）對噪聲數(shù)據(jù)有很好的健壯性。因而是目前應用最為廣泛的歸納推理算法之一，在數(shù)據(jù)挖掘中受到研究者的廣泛關注。1. ID3算法ID3算法是一個眾所周之的決策樹算法，該算法是澳大利亞悉尼大學的Ross Quinlan于1986年提出，也是國際上最早、最有影響力的決策樹算法，其他的許多算法如C4.5、CART算法等都是在ID3算法基礎上的改進。在ID3算法中，決策節(jié)點屬性的選擇運用了信息論中的熵概念作為啟發(fā)式函數(shù)。在這種屬性選擇方法中，選擇具有最大信息增益（information gain）的屬性作為當前劃分節(jié)點。通過這種方式選擇的節(jié)點屬性可以保證決策樹具有最小的分枝數(shù)量，使得到的決策樹冗余最小。公式1：設數(shù)據(jù)劃分D為類標記的元組的訓練集。假定類標號屬性具有M個不同值，定義m個不同的類Ci（I1，2，m），Ci,D是Ci類的元組的集合。和分別表示D和Ci,D中元組的個數(shù)。對D中的元組分類所需的期望信息由下式給出：公式2：假設屬性A具有v個不同的離散屬性值，可使用屬性A把數(shù)據(jù)集D劃分成v個子集D1, D2，Dv。設子集Dj中全部的記錄數(shù)在A上具有相同的值aj?；诎碅劃分對D的元組分類所需要的期望信息由下式給出：公式3：信息增益定義為原來的信息需求（基于類比例）與新的信息需求（對A劃分之后得到的）之間的差，即 Gain(A)=Info（D）-InfoA（D）ID3算法大概的流程就是在屬性集A中尋找信息增益值最大的屬性，作為根節(jié)點，按照根節(jié)點屬性的取值將樣本集合分成幾個子集，將此屬性從屬性集中去掉，在每個子集中選擇信息增益值最大的屬性，作為當前子集的根節(jié)點，上層集合的根節(jié)點的子節(jié)點，如此循環(huán)遞歸，如果得到的子集中所有的樣本屬于一個類別，則遞歸停止。ID3算法對數(shù)據(jù)的要求：所有屬性必須為離散量； 所有的訓練例的所有屬性必須有一個明確的值；相同的因素必須得到相同的結論且訓練例必須唯一。實例：假如有一個網(wǎng)球愛好者，天氣狀況（天氣、溫度、濕度、風力）是決定他是否去打球的重要因素，利用ID3算法構筑決策樹。以往部分打球數(shù)據(jù)庫類標記的訓練元組統(tǒng)計如表所示：類標號打球有兩個取值（即是，否），因此有兩個不同的類，即m=2，設C1類對應與是，C2類對應于否。C1有9個元組，C2有5個元組。我們根據(jù)公式1可以計算D中元組分類所需要的期望信息：如果根據(jù)天氣屬性劃分，根據(jù)公式2則對D的元組進行分類所需要的期望信息為：根據(jù)公式3這種劃分的信息增益是：Gain（天氣）=info（D）-info天氣（D）=0.940-0.694=0.246位類似地，可以計算：Gain(溫度) = 0.029Gain(濕度)=0.151Gain(風力)=0.048由于天氣在屬性中具有最高信息增益，它被選作測試屬性。創(chuàng)建一個節(jié)點，用天氣標記，并根據(jù)每個屬性值，引出一個分枝。注意，落在分區(qū)天氣= 多云”的樣本都屬于同一類，根據(jù)算法，要在該分支的端點創(chuàng)建一個樹葉，并用“是”標記。同理，在“晴朗”和“雨天” 這兩個分支上，分別對“溫度”、“濕度”、“風力”屬性計算其信息增益，分別選取下一個測試屬性。依算法全部計算后返回的最終決策樹如圖所示2. C4.5算法由于ID3算法在實際應用中存在一些問題，于是Quilan提出了C4.5算法，嚴格上說C4.5只能是ID3的一個改進算法。C4.5算法繼承了ID3算法的優(yōu)點，并在以下幾方面對ID3算法進行了改進： 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；在樹構造過程中進行剪枝；能夠完成對連續(xù)屬性的離散化處理；能夠對不完整數(shù)據(jù)進行處理。C4.5算法的優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準確率較高。C4.5算法的缺點：在構造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當訓練集大得無法在內(nèi)存容納時程序無法運行。分類決策樹算法：C4.5算法是機器學習算法中的一種分類決策樹算法，其核心算法是ID3算法。分類決策樹算法是從大量事例中進行提取分類規(guī)則的自上而下的決策樹。四、實現(xiàn)在Visual Studio2013中C+語言ID3算法實現(xiàn)決策樹：代碼：#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;class ID3class Nodepublic:string value;bool isLeaf;map map;public:Node() :value(), isLeaf(false);private:vector attribute;/vectorvector attributevalue;vectorvectordata;int decatt;Node *root;public:ID3()/ 從文件中加載數(shù)據(jù)ifstream fin(C:UsersAdministratorDesktopplayData.txt);string line, str;getline(fin, line); /read a line from the inputfin to lineistringstream istring(line); / bind to istring to the line we readwhile (!istring.eof()istring str; /read a word from lineattribute.push_back(str); while (!fin.eof()getline(fin, line);vector vecStr;istringstream istring(line);while (!istring.eof()istring str;vecStr.push_back(str);data.push_back(vecStr);fin.close();void run()setDec(4);vector subSet;for (int i = 0; idata.size(); i+)subSet.push_back(i);vector candidateAtt;for (int i = 0; iattribute.size(); i+)if (i != decatt)candidateAtt.push_back(i);Node *tree = buildDT(subSet, candidateAtt);/ 輸出樹結構root = tree;vector s;printTreeDepth(root, s);void setDec(int n)if (n= attribute.size()cout 指定決策樹變量錯誤! endl;exit(0);decatt = n;double getEntropy(vector subSet)/ 獲得子集信息熵double entropy = 0;double p, n;p = n = 0;vector vec;for (int i = 0; isubSet.size(); i+)if (datasubSetidecatt = yes)p+;elsen+;/ 判斷屬于同一類，熵為零的情況if (0 = p | 0 = n)return 0;double pR = p / (p + n), nR = n / (p + n);entropy = -pR*(log(pR) / log(2.0) - nR*(log(nR) / log(2.0);return entropy;bool isPure(vector subset)string value = datasubset0decatt;for (int i = 1; isubset.size(); i+)if (datasubsetidecatt != value)return false;return true;double gain(vector subset, int index) / 返回以index為節(jié)點的信息增益/ 統(tǒng)計正例個數(shù)和范例個數(shù)double entropy = getEntropy(subset);double sum = 0;/ 求可能的所有屬性值mapstring, vector mapSub;for (int i = 0; isubset.size(); i+)mapSubdatasubsetiindex.push_back(subseti);for (mapstring, vector:iterator iter = mapSub.begin();iter != mapSub.end(); +iter)double tt = (iter-second.size() / (double)subset.size()*getEntropy(iter-second);/coutfirst:ttendl;sum += tt;return entropy - sum;/ suSet 指子集， value:屬性值 attribute: 候選屬性 tree: 根節(jié)點指針的指針Node* buildDT(vector subSet, vector attr)Node *p = new Node();if (isPure(subSet)p-isLeaf = true;p-value = datasubSet0decatt;/*if(*tree!=NULL)(*tree)-mapvalue=p;else(*tree)=p;*/return p;if (attr.size() = 0)int y, n;y = n = 0;for (int i = 0; i= n)p-isLeaf = true;p-value = yes;elsep-isLeaf = true;p-value = no;return p;/ 選擇一個最優(yōu)的屬性int best = 0;double dmax = 0;int bestIndex = 0;for (int i = 0; idmax)dmax = dd;best = attri;bestIndex = i;/ 獲得這個屬性的所有屬性值和其所對應的子集mapstring, vector mapAttValue;for (int i = 0; ivalue = this-attributebest;for (mapstring, vector:iterator iter = mapAttValue.begin();iter != mapAttValue.end(); +iter)p-mapiter-first = buildDT(iter-second, attr);/ 遍歷每個屬性值被選擇后的子集，遞歸的創(chuàng)建樹return p;private:void space(int n)for (int i = 0; in; i+)cout ;public:/ 輸出從根節(jié)點到葉子節(jié)點的所有路徑void printTree()Node *t = root;queue que;que.push(t);Node *q = t, *p;while (!que.empty()p = que.front();que.pop();cout setw(10) value;bool flag = false;if (p = q)cout endl;flag = true;for (map:iterator iter = p-map.begin();iter != p-map.end(); +iter)que.push(iter-second);if (flag)map:iterator iter1 = iter;iter1+;if (iter1 = p-map.end()q = iter-second;flag = false;void printTreeDepth(Node *t, vector vec)if (t-isLeaf)for (int i = 0; ivec.size(); i += 2)if (i != 0)cout ;cout veci : veci + 1;cout value;cout endl;cout value);for (map:iterator iter = t-map.begin();iter != t-map.end(); +iter)vec.push_back(iter-first);printTreeDepth(iter-second, vec);vec.pop_back();int main()ID3 id3;id3.run();return 0;playData.txt中訓練數(shù)據(jù)：outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnormalFALSEyesrainycoolnormalTRUEnoovercastcoolnormalTRUEyessunnymildhighFALSEnosunnycoolnormalFALSEyesrainymildnormalFALSEyessunnymildnormalTRUEyesovercastmildhighTRUEyesovercasthotnormalFALSEyesrainymildhighTRUEno結果：（二）概念學習一、定義及一些描述1. 定義：概念學習是指從有關某個布爾函數(shù)的輸入輸出訓練樣例中推斷出該布爾函數(shù)。通俗的說，就是給定一個樣例集合以及每個樣例是否屬于某個概念的標注，怎樣推斷出該概念的一般定義。又稱從樣例中逼近布爾函數(shù)。2. 概念學習任務的描述：任何概念學習任務能被描述為：實例的集合、實例集合上的目標函數(shù)、候選假設的集合以及訓練樣例的集合。具體以Enjoy Sport為例，如圖表2-1：表2-1 目標概念EnjoySport的訓練樣例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes那么Enjoy Sport學習任務可以描述為：已知：實例集X：可能的日子，每個日子由下面的屬性描述：sky:(可取值 sunny,Cloudy和Rainy)AirTemp:(可取值為Warm和Cold)Humidity:(可取值為Normal和High)Wind:(可取值為：Strong和Weak)Water：(可取值為Warm和Cold)Forecast:(可取值為Same和Change)假設集H：每個假設描述為6個屬性：Sky,AirTemp,Humidity,Wind,Water和Forecast的值約束的合取。約束可以為“？”（表示接受任意值），“”（表示拒絕所有值），或一特定值目標概念C:EnjoySport: X-0,1訓練樣例集D：目標函數(shù)的正例和反例求解：H中的一假設h，使對于X中任意x，h(x)=c(x)3. 一些術語概念：實例集（X）:概念定義的實例集合目標概念（c）：待學習概念或函數(shù)訓練樣例（D）:每個樣例為X中的一個實例x以及它的目標概念值c(x)。c(x)=1的實例被稱為正例（positive example），c(x)=0的實例為反例（negative example），經(jīng)常用序偶來描述訓練樣例。H表示所有可能假設的集合。H中每個假設H表示X上定義的布爾函數(shù)，即h:X-0,1。機器學習的目標就是尋找一個假設h，使對于X中的所有x，h(x)=c(x)。歸納學習假設：任一假設如果在足夠大的訓練樣例集中很好地逼近目標函數(shù)，它也能在未見實例中很好地逼近目標函數(shù)。二、 作為搜索的概念學習1. 概念學習可以看作一個在假設空間上搜索的過程，目標是找到能夠最好地擬合訓練樣例的假設，學習的過程可以看作是一個從訓練樣例到假設空間選取的一個過程。2. 關系的“更一般”任給實例x和假設h，說x滿足h，當且僅當h(x)=1。令hj和hk為在X上定義的布爾函數(shù)，稱hj more_general_than_or_equal_to hk（記做hjghk），當且僅當(xX)(hk(x)=1)(hj(x)=1)利用這個關系，無需列舉所有假設，就能在無限的假設空間中進行徹底的搜索三、 FIND-S：尋找極大特殊假設使用more_general_than偏序的搜索算法：從H中最特殊假設開始，然后在該假設覆蓋正例失敗時將其一般化（當一假設能正確地劃分一個正例時，稱該假設“覆蓋”該正例）。1. FIND-S算法描述：1) 將h初始化為H中最特殊假設2) 對每個正例x：對h的每個屬性約束ai，如果x滿足ai，那么不做任何處理；否則將h中ai替換為x滿足的下一個更一般的約束3). 輸出假設h2. Find-S算法演示了一種利用more_general_than偏序來搜索假設空間的方法，沿著偏序鏈，從較特殊的假設逐漸轉移到較一般的假設。因此，每一步得到的假設都是在那一點上與訓練樣例一致的最特殊的假設。Find-S的重要特點：對以屬性約束的合取式描述的假設空間H，保證輸出為H中與正例一致的最特殊的假設。四、 變換空間和候選消除算法（CANDIDATE-ELIMINATION）FIND-S輸出的假設只是H中能夠擬合訓練樣例的多個假設中的一個。而在候選消除算法中，輸出的是與訓練樣例一致的所有假設的集合，且候選消除算法在描述這一集合時不需要明確列舉所有成員，利用more_general_than偏序結構，可以維護一個一致假設集合的簡潔表示1.幾個定義一致：一個假設h與訓練樣例集合D一致，當且僅當對D中每一個樣例都有h(x)=c(x)。Consistent(h,D)(D) h(x)=c(x)變型空間:關于假設空間H和訓練樣例集D的變型空間，標記為VSH,D，是H中與訓練樣例D一致的所有假設構成的子集。VSH,DhH|Consistent(h,D)2.列表后消除算法（LIST-THEN-ELIMINATE）描述（1）變型空間VersionSpace-包含H中所有假設的列表（2）對每個訓練樣例，從變型空間中移除所有h(x)c(x)的假設h（3）輸出VersionSpace中個假設列表3. 變型空間的更簡潔表示變型空間被表示為它的極大一般和極大特殊的成員，這些成員形成了一般和特殊邊界的集合，這些邊界在整個偏序結構中劃分出變型空間。關于假設空間H和訓練數(shù)據(jù)D的一般邊界G，是在H中與D相一致的極大一般成員的集合。關于假設空間H和訓練數(shù)據(jù)D的特殊邊界S，是在H中與D相一致的極大特殊成員的集合4. 候選消除學習算法-初始化G和S-如果d是一個正例從G中移去所有與d不一致的假設對S中每個與d不一致的假設s-從S中移去s-把s的所有的極小泛化式h加入到S中，其中h滿足：h與 d一致，而且G的某個成員比h更一般-從S中移去所有這樣的假設：它比S中另一個假設更一般-如果d是一個反例從S中移去所有與d不一致的假設對G中每個與d不一致的假設g-從G中移去g-把g的所有的極小特殊化式h加入到G中，其中h滿足：h與d一致，而且S的某個成員比h更特殊-從G中移去所有這樣的假設：它比G中另一個假設更特殊5. 示例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes把S集合初始化為H中極大特殊假設：把G集合初始化為H中極大一般假設：首先加載第一條和第二條樣本：這個過程是特殊向一般的轉變，這個過程非常地類似FIND-S算法接著我們處理第三條樣本：回到數(shù)據(jù)，我們發(fā)現(xiàn)，Sky，AirTemp和Foreast和以前的數(shù)據(jù)不一致，我們可以懷疑是這三個數(shù)據(jù)導致最后結果的變化。所以，我們就針對這3個數(shù)據(jù)進行一次特殊化：接著，我們輸入第四條樣本：在處理第四條樣本的時候，我們先對于S集合進行一般化：然后，為了讓G集合覆蓋S集合，我們需要剔除，過程為：在處理完了這四個樣本后，我們就可以獲取所有的假設：當前為6個假設，當我們可以獲取到更多的訓練集的時候，我們可以劃出更小的設計空間。六、實現(xiàn)在Visual Studio2013中實現(xiàn)：/ bianxingspace.cpp#pragma warning (disable: 4996)#include using namespace std;#define A_CHAR_MAX 16#define A_VALUE_MAX 16#define A_NUM_MAX 32#define SAMPLES_MAX 256#define ALL -1#define NUL -2#define YES 1#define NO 0#define NUKOWN -1/ 屬性struct Attributechar nameA_CHAR_MAX; / 屬性名稱int num; / 屬性值個數(shù)char attA_VALUE_MAXA_CHAR_MAX; / 屬性值;/ 假設struct Hypothesisint num; / 屬性個數(shù)Attribute anA_NUM_MAX; / 屬性集合;/ 假設值struct HypoValueint valueA_NUM_MAX;/ 樣本struct SampleHypoValue ev; / 假設int result; / 正例/反例;Hypothesis g_Hypo; / 假設集合Sample g_saSAMPLES_MAX; / 樣本空間int g_sn; / 樣本數(shù)list g_G; / 一般邊界Glist g_S; / 特殊邊界S/ 從文件中讀取假設集合/*/ 文件格式屬性個數(shù)n屬性名稱1 屬性值個數(shù) 屬性值1 屬性值2 屬性值3 屬性名稱2 屬性值個數(shù) 屬性值1 屬性值2 屬性值3 屬性名稱n 屬性值個數(shù) 屬性值1 屬性值2 屬性值3 /*/bool ReadHypothesis(const char* filename)FILE* file;if (fopen_s(&file, filename , r) return false;int i,j,k;fscanf(file, %dn, &g_Hypo.num);for (i=0; ig_Hypo.num ; i+) fscanf(file, %s%d, g_H, &k); g_Hypo.ani.num = k; for (j=0; jk; j+) fscanf(file, %s, g_Hypo.ani.attj); fscanf(file, n);fclose(file);return true;/ 從文件中讀取樣本/*/ 文件格式樣本個數(shù)m樣本1屬性1的值的序號 樣本1屬性2的值的序號 樣本1屬性n的值的序號 1（正例）或者0（反例）樣本2屬性1的值的序號 樣本2屬性2的值的序號 樣本2屬性n的值的序號 1（正例）或者0（反例）樣本m屬性1的值的序號 樣本m屬性2的值的序號 樣本m屬性n的值的序號 1（正例）或者0（反例）/*/bool ReadSamples(const char* filename)FILE* file;if (fopen_s(&file, filename , r) return false;int i,j;fscanf(file, %dn, &g_sn);for (i=0; ig_sn ; i+) for (j=0; jg_Hypo.num; j+) fscanf(file, %d, &g_sai.ev.valuej); fscanf(file, %dn,&g_sai.result);fclose(file);return true;/ 初始化G和Svoid InitGandS()HypoValue* evg = new HypoValue();HypoValue* evs = new HypoValue();for (int i=0; ivaluei = ALL; evs-valuei = NUL;g_G.push_back(evg);g_S.push_back(evs);/ 正例ps與假設h是否一致bool PositiveisConsistent(HypoValue h, HypoValue ps)for (int i=0; ig_Hypo.num; i+) if (h.valuei=ALL) continue; else if (h.valuei!=ps.valuei) return false;return true;/ 反例ns與假設h是否一致bool NegativeisConsistent(HypoValue h, HypoValue ns)for (int i=0; ig_Hypo.num; i+) if (h.valuei!=ALL & h.valuei!=ns.valuei) return true;return false;/ G的某個成員是否比h更一般bool GMemberMoreGeneral(HypoValue h)int i;list:iterator it;HypoValue mem;for (it=g_G.begin(); it!=g_G.end(); it+) mem = *it; for (i=0; ig_Hypo.num; i+) if (mem.valuei=h.valuei) continue; else if (mem.valuei=ALL | h.valuei=NUL) continue; else break; if (i=g_Hypo.num) return true;return false;/ 把s的所有的極小泛化式h加入到S中，并且滿足h與d一致，而且G的某個成員比h更一般void MiniGeneral(HypoValue s, HypoValue d)HypoValue* h = new HypoValue();for (int i=0; ivaluei = ALL; else h-valuei = d.valuei;if (GMemberMoreGeneral(*h) g_S.push_front(h);else delete h;/ 從S中移去所有這樣的假設：它比S中另一個假設更一般void RemoveMoreGeneralFromS()bool r1,r2;int i;HypoValue e1, e2;list:iterator it;list:iterator next;list:iterator temp;for (it=g_S.begin(); it!=g_S.end();) e1 = * *it; next = it; r1 = r2 = false; for (next+; next!=g_S.end();) e2 = * *next; r1 = r2 = false; for (i=0; ig_Hypo.num; i+) /if (e1.valuei=ALL & e2.valuei=ALL) / continue; /else if (e1.valuei=e2.valuei) continue; else if (e1.valuei=ALL) r1 = true; if (r2) break; else if (e2.valuei=ALL) r2 = true; if (r1) break; else r1 = r2 = true; break; if (r1=true & r2=false) /it比next更一般 break; if (r1=false) /next比it更一般或兩者相同 temp = next; next+; g_S.remove(*temp); else /兩者沒有誰比誰更一般的關系 next+; if (r1=true & r2=false) /it比next更一般 temp = it; it+; g_S.remove(*temp); else it+;/ S的某個成員是否比h更特殊bool SMemberMoreSpecial(HypoValue h)int i;list:iterator it;HypoValue mem;for (it=g_S.begin(); it!=g_S.end(); it+) mem = *it; for (i=0;