ASSearch????? ?????????? 搜索算法類(lèi)

ASEvaluation?? ?????????? 特征結(jié)果集評(píng)價(jià)算法類(lèi)。該類(lèi)有接口接受樣本輸入

AttributeEvaluation??????? 單個(gè)特征的評(píng)價(jià)類(lèi)

AttributeSetEvaluation??? 特征集的評(píng)價(jià)類(lèi)

AttributeSelection????????? 特征選擇類(lèi)， 接受ASSearch與ASEvaluation作為輸入

AttributeTransformer???? 數(shù)據(jù)轉(zhuǎn)換類(lèi)

?

Best First Search：

m_bestMerit， 記錄評(píng)價(jià)最高的得分

m_cacheSize， 已評(píng)價(jià)了多少組不同的特征； lookup記錄已評(píng)價(jià)屬性集及其評(píng)價(jià)分的集合

m_searchDirection， 搜索方向：正向，后向，雙向

m_starting， 初始結(jié)果集

m_totalEvals， 已評(píng)價(jià)次數(shù)>= m_cacheSize

?

1)??? 初始化

如果已給出初始結(jié)果集，則此輪結(jié)果集就是初始結(jié)果集；若未給出初始結(jié)果集且為雙向搜索，則此輪結(jié)果集就是所有的屬性集。

計(jì)算此輪結(jié)果集的評(píng)價(jià)得分， 將該結(jié)果集與得分放入已查數(shù)據(jù)中； 將該結(jié)果集放入待搜索隊(duì)列中

?

?

2)??? 迭代搜索

迭代退出條件是， 如果連續(xù)多次擴(kuò)展得到的結(jié)果集都沒(méi)有比當(dāng)前最好的更優(yōu)，則退出，Stale < m_max_stale；? 或者待擴(kuò)展隊(duì)列已為空。

2.0）取得待擴(kuò)展隊(duì)列頭

2.1）根據(jù)搜索方向擴(kuò)展該屬性集得到新的屬性集：順序掃描每個(gè)屬性，如果未處理過(guò)該屬性， 則將該屬性增加到待擴(kuò)展集中。（如果是backward搜索， 則是將該屬性從待擴(kuò)展集中移除；后面類(lèi)同）

2.2）如果該新的屬性集未曾處理過(guò)， 則計(jì)算其評(píng)價(jià)分、將其增加到lookup中； 將該屬性集加入到待擴(kuò)展集中。 判斷此次擴(kuò)展是否比當(dāng)前最好的更優(yōu)、更優(yōu)則記錄相關(guān)信息。

2.3）恢復(fù)到迭代2.0）狀態(tài)時(shí)的屬性集，迭代2.1）中掃描下一個(gè)未曾處理的屬性

Notes：如果是雙向搜索時(shí)，則步驟2中，都是在步驟2.0）的基礎(chǔ)之上先正向?qū)λ袑傩宰鰷y(cè)試；然后逆向?qū)λ袑傩宰鰷y(cè)試。就是把雙向分為了先正向后逆向兩個(gè)完全分開(kāi)的過(guò)程。

?

3）步驟2退出時(shí)， 得到了最佳屬性集合

?

code

while (stale < m_maxStale) {added = false;if (m_searchDirection == SELECTION_BIDIRECTIONAL) {// bi-directional searchdone = 2;sd = SELECTION_FORWARD;} else {done = 1;}// finished search?if (bfList.size() == 0) {stale = m_maxStale;break;}// copy the attribute set at the head of the listtl = bfList.getLinkAt(0);temp_group = (BitSet)(tl.getData()[0]);temp_group = (BitSet)temp_group.clone();// remove the head of the listbfList.removeLinkAt(0);// count the number of bits set (attributes)//TODO 計(jì)算temp_group中已處理過(guò)的屬性個(gè)數(shù) sizedo {for (i = 0; i < m_numAttribs; i++) {//測(cè)試第i個(gè)屬性是否已處理過(guò)。 z==true時(shí)表示未處理過(guò)、待處理if (sd == SELECTION_FORWARD) {z = ((i != m_classIndex) && (!temp_group.get(i)));} else {z = ((i != m_classIndex) && (temp_group.get(i)));}if (z) {// set the bit (attribute to add/delete)// 如果待處理， 則對(duì)正向搜索而言就是增加到屬性集中； 逆向搜索就是從屬性集中刪除if (sd == SELECTION_FORWARD) {temp_group.set(i);size++;} else {temp_group.clear(i);size--;}/* if this subset has been seen before, then it is already in the list (or has been fully expanded) *///如果該擴(kuò)展后的屬性集已見(jiàn)過(guò)，則取出其評(píng)價(jià)分； 未見(jiàn)過(guò)則處理：tt = (BitSet)temp_group.clone();hashC = tt.toString();if (lookup.containsKey(hashC) == false) {merit = ASEvaluator.evaluateSubset(temp_group);m_totalEvals++;} else {merit = ((Double)lookup.get(hashC)).doubleValue();cacheHits++; }// insert this one in the list。 增加到待擴(kuò)展集中Object[] add = new Object[1];add[0] = tt.clone();bfList.addToList(add, merit);// is this better than the best?if (sd == SELECTION_FORWARD) {z = ((merit - best_merit) > 0.00001);} else if (merit == best_merit) {z = (size < best_size);} else {z = (merit > best_merit);} }if (z) //比當(dāng)前最佳更好， 則記錄相關(guān)信息{added = true;stale = 0;best_merit = merit;best_size = size;best_group = (BitSet)(temp_group.clone());}// unset this addition(deletion)//重置當(dāng)前選擇， 以便進(jìn)行下一個(gè)屬性測(cè)試if (sd == SELECTION_FORWARD) {temp_group.clear(i);size--;} else {temp_group.set(i);size++;}}end forif (done == 2) {sd = SELECTION_BACKWARD;}done--;} while (done > 0); ///end do/* if we haven't added a new attribute subset then full expansion of this node hasen't resulted in anything better */if (!added) {stale++;}}///end whilem_bestMerit = best_merit;return attributeList(best_group);

總結(jié)

以上是生活随笔為你收集整理的weka: best first search的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。