二進制特徵的組合（向量）

Question

主題的源數據是一個m×n的二進制矩陣（只允許0和1）。 m行代表觀測值，n列 - 特徵。有些觀察被標記爲需要與其餘部分分開的目標。

雖然看起來像一個典型的神經網絡，支持向量機等問題，我不需要泛化。我需要的是一種有效的算法，可以儘可能多地找到將目標與其他觀測值完全分開的列（特徵）組合，即分類，即。

例如：

f1 f2 f3 
o1 1 1 0 
t1 1 0 1 
o2 0 1 1 

這裏{F1，F3}是從靜止（O1，O2）（順便說一句分離靶T1可接受的組合，{F2}不是如由任務定義的特徵必須出現在目標中）。換句話說，

t1(f1) & t1(f3) = 1 and o1(f1) & o1(f3) = 0, o2(f1) & o2(f3) = 0 
where '&' represents logical conjunction (AND). 

該m約爲100,000，n爲1,000。目前，數據被壓縮成沿着m的128位字，並且搜索使用sse4和什麼來優化。然而，獲得這些功能組合需要太長的時間。 經過20億次調用樹下降例程後，它已覆蓋約15％的根節點。並且發現了大約8,000個連擊，這對我的特殊應用來說是一個不錯的結果。

我使用一些經驗標準來切斷不太可能的下降路徑，但不是沒有有限的成功，但有沒有更好的辦法？我很確定那裏肯定有？..任何幫助，以任何形式，參考或建議，將不勝感激。

Answer 1

我相信你描述的問題是NP-Hard，所以你不應該指望在合理的時間內找到最佳的解決方案。我不明白你目前的算法，但這裏有一些建議在我頭上：

1）構造一個決策樹。將目標標記爲A，將非目標標記爲B，並讓決策樹學習分類。在每個節點選擇特徵，使得P（目標特徵）和P（目標'特徵'）的函數最大。 （即儘可能多的目標落到正面，儘可能多的非目標落到負面）

2）使用貪婪算法。從空集開始，每次添加殺死大多數非目標行的方法。

3）使用隨機算法。從某個目標的一小部分正特徵開始，使用該集作爲貪心算法的種子。重複很多次。選擇最佳解決方案。貪婪算法會很快，所以它會好的。

4）使用遺傳算法。爲3中的貪婪算法生成隨機種子，以生成好的解決方案並交叉生成它們（按位和可能）以生成新的候選種子。記住最好的解決方案。保持現有人口的良好解決方案。重複數代。

您需要快速找到答案「有多少給定行具有給定功能f」，因此可能需要專門的數據結構，可能使用每個功能的BitArray。