本文章是由機器翻譯。
測試回合
使用 C# 的 Winnow 分類
.jpg)
在機器學習 （毫升），一個分類問題是其中一個目標是要創建一個模型，預測對離散、 非數位值的結果。例如，你可能想要預測一個人的政黨 （民主黨人或共和黨人）。有許多不同的分類演算法和技術，包括，例如，樸素貝葉斯分類、 分類 logistic 迴歸分析和神經網路分類。
一種非常簡單和有趣的分類技術使用的 Winnow 演算法。（英語單詞簸手段來刪除不需要的物品）。獲取什麼揚分類是一種感覺，看看這篇文章將走向何方是最好的方法是看一看該演示程式中圖 1。
.png "簸演算法分類演示")
圖 1 簸演算法分類演示
該演示程式的目標是預測政黨，民主黨還是共和黨，美國的一名成員 眾院基於代表投票 16 項法案。眾議院有 435 名成員。一個知名的基準資料集包含存儲在一個簡單的文字檔中的 435 項。第三個數據專案是：
republican,n,y,n,y,y,y,n,n,n,y,?,y,y,y,n,y
republican,n,y,n,y,y,y,n,n,n,n,n,y,y,y,n,?
democrat,?,y,y,?,y,y,n,n,n,n,y,n,y,y,n,n
行中的第一列是民主黨人或共和黨人。下一步 16 列是要麼 n （沒有表決），y （贊成票），或嗎？（丟失，未知或投棄權票)。第一清單示的成員與殘疾嬰兒相關法案進行表決。第二是與水專案有關的條例草案。等等。你不需要知道什麼條例草案是與每一列，但如果你有興趣你可以發現到在互聯網上的很多地方這個資料集 （與描述） 通過搜索"UCI 投票資料"。
簸分類設計的非常特定類型的分類問題：一個地方要預測的類可以拿走一個兩個可能的值 （這些被稱為二進位分類問題），並預測變數 （通常稱為毫升術語中的"功能"） 也可以採取兩個可能值之一。原始的投票資料集滿足這些要求，如果缺失值處理。缺失值處理最常見的方法就是刪除任何具有一個或多個缺失值的資料項目。不過，表決缺少的值的資料往往代表隱含的"否"投票，所以該演示程式將所有缺少的值替換"反對"票。
該演示程式使用中投票的設置而不是所有 435 項的第一個 100 資料項目目。演示將編碼獨立變數"反對"票為 0 和"yes"票為 1，並編碼依賴政黨 X 變數的值為 1 0 以及"共和主義""民主黨人"。 該演示將移動依賴于 Y 變數從第一列的最後一列使用的最後一列 y 是因為更方便進行編碼時，更為常見。
演示隨機分成 80 專案訓練集，以生成模型和 20 項測試集模型的精度評價的 100 項編碼的資料集。演示使用的 Winnow 演算法查找 16 權重 （一個用於每個輸入）：0.2500, 0.500, . . , 0.0625. 使用這些重量，展示模型正確地預測 97.50%的培訓專案 (78 個 80） 和 95.00%的測試專案 （19，20） 的政黨。
演示程式最後利用模型來預測假設的代表投票"是"所有 16 帳單的政黨。基於該模型，預測是的人是一名共和黨人。
這篇文章假設你有至少中級程式設計技巧，但並不認為你知道任何關於 Winnow 分類演算法。該演示編碼使用 C# 中，但你不應該有很多麻煩，如果你想要到另一種語言，如Visual Basic.NET 或 JavaScript 代碼進行重構。
理解的 Winnow 演算法
為簡單起見，假設訓練資料基於只有五票，而不是 16。 舉個例子：
1, 0, 1, 1, 0 -> 0
1, 1, 1, 0, 1 -> 1
0, 0, 0, 1, 0 -> 1
因此，第一行就意味著"贊成票"，"不投票，""是的票，""贊成票"，"無票"，"民主黨"。現在假設模型進行訓練和收益率權重 {0.75、 3.00、 1.00、 0.50、 0.40}。計算預測的輸出，該演算法只是將每個輸入的值乘以相應的重量，總結條款，然後進行了比較反對一個門限值的累計的總和。例如，對於第一個專案，積累的總和是：
(1 * 0.75) + (0 * 3.00) + (1 * 1.00) + (1 * 0.50) + (0 * 0.40) = 2.25
如果閾值值為 5.0 然後，因為累積的總和 (2.25) 小於閾值，預測的 Y 為 0，在這種情況下是正確的預測。
培養模式涉及到找到一套權重，以便應用於訓練資料輸出值已知時，計算的輸出密切與已知的輸出相匹配。在高級別偽代碼中揚演算法是：
initialize weights
loop until done
for each training item
compute Y
if correct do nothing
else if incorrect
if computed Y is too large
divide all relevant weights by 2.0
else if computed Y is too small
multiply all relevant weights by 2.0
end for
end loop
假設三個數據專案前面提到的權重將被初始化為：
{ 2.50, 2.50, 2.50, 2.50, 2.50 }
培訓的第一個項的計算的 Y （1，0，1，1，0-> 0) 是：
Y = (1 * 2.50) + (0 * 2.50) + (1 * 2.50) + (1 * 2.50) + (0 * 2.50) = 7.50 -> 1
這是不正確的預測太 1 的計算的 Y 相比所需 Y 為 0，所以有關的重量除以 2.0 的一個因素。相關的權重是有那些所占權重與其 1 投入。新的權值是：
{ 2.50 / 2, (no change), 2.50 / 2, 2.50 / 2, (no change) }
= { 1.25, 2.50, 1.25, 1.25, 2.50 }
現在，第二個訓練專案 （1，1，1，0，1-> 1） 被處理以新權數：
Y = (1 * 1.25) + (1 * 2.50) + (1 * 1.25) + (0 * 1.25) + (1 * 2.50) = 7.50 -> 1
這是一個正確的預測，所以離開了所有的權重孤獨。第三個培訓專案 （0，0，0，1，0-> 1） 是使用當前的權重處理：
Y = (0 * 1.25) + (0 * 2.50) + (0 * 1.25) + (1 * 1.25) + (0 * 2.50) = 1.25 -> 0
這是 1 的不正確的預測 0 的計算的 Y 在哪裡太小相比所需，y 染色體，因此相關權重都乘以 2.0：
{ (no change), (no change), (no change), 1.25 * 2.0, (no change) }
= { 1.25, 2.50, 1.25, 2.50, 2.50 }
如果你有點想揚訓練的過程中，你會注意到兩個關鍵特徵。首先，該演算法使用只有不正確的資訊。第二，該演算法本質上是駕駛不相干的預測因數的權重到 0，簸出來。這往往使得揚分類在許多預測變數無關的情況下非常有效。雖然基本簸演算法是很簡單，有幾個執行細節，去解決，比如決定如何初始化權重和決定何時停止訓練。
程式的整體結構
演示程式，與幾個應使用 WriteLine 語句刪除和次要編輯為了節省空間，整體結構在圖 2。若要創建該演示程式，我推出Visual Studio，並創建一個新 C# 主控台應用程式命名為 WinnowPredict。這個演示網站有沒有重大的.NET 版本依賴性，所以任何版本的Visual Studio工作。載入到編輯器中的範本代碼後，我刪除了所有使用除了頂級的 System 命名空間的單個引用的語句。在解決方案資源管理器視窗中，我將 Program.cs 檔重命名為 WinnowProgram.cs 和Visual Studio自動重命名類程式，對我來說。
圖 2 整體演示程式結構
using System;
namespace WinnowPredict
{
class WinnowProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin Winnow algorithm demo");
int[][] data = new int[100][];
data[0] = new int[] { 0, 1, 0, 1, 1, 1, 0, 0,
0, 1, 0, 1, 1, 1, 0, 1, 1 };
// Etc.
// Create, train and test matrices from data
// Instantiate Winnow classifier
// Train using training data
// Compute accuracy
// Predict party of hypothetical person
Console.WriteLine("End Winnow demo");
Console.ReadLine();
} // Main
static void MakeTrainTest(int[][] data, int seed,
out int[][] trainData, out int[][] testData) { . . }
static void ShowVector(double[] vector, int decimals,
int valsPerRow, bool newLine) { . . }
static void ShowMatrix(int[][] matrix, int numRows,
bool indices) { . . }
}
public class Winnow
{
private int numInput;
private double[] weights;
private double threshold;
private double alpha;
private static Random rnd;
public Winnow(int numInput, int rndSeed) { . . }
public int ComputeOutput(int[] xValues) { . . }
public double[] Train(int[][] trainData) { . . }
public double Accuarcy(int[][] trainData) { . . }
private static void Shuffle(int[][] trainData) { . . }
}
}
該演示程式是有點太長，無法顯示其整體在這篇文章，但您可以找到完整的原始程式碼 （WinnowProgram.cs） 在隨附的檔下載。所有揚分類邏輯都包含在一個名為揚的程式定義的類。
Main 方法開始設立 100 個專案的資料集，如中所示圖 3。
圖 3 的主要方法設置了 100 項資料集
using System;
namespace WinnowPredict
{
class WinnowProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin Winnow algorithm prediction demo");
int[][] data = new int[100][];
data[0] = new int[] { 0, 1, 0, 1, 1, 1, 0, 0,
0, 1, 0, 1, 1, 1, 0, 1, 1 };
...
若要創建的資料，我位於 UCI 投票在 Web 上的資料集、 複製和粘貼到記事本中，，然後使用編輯替換，將資料放入一個陣列的陣列樣式矩陣直接。即使你是有經驗的程式師，你可能不熟悉 C# 的語法矩陣，但你可能會得到很快的適應編碼模式。在非演示的情況下，您將編寫某種方法來將資料從文字檔載入到一個矩陣。
接下來，使用一種 helper 方法，顯示的前四行和最後一行的整個資料集和資料集分成訓練集 （80 項） 和測試集 （20 項）：
Console.WriteLine("\nFirst few lines of all data are: \n");
ShowMatrix(data, 4, true);
Console.WriteLine("\nSplitting data into 80% train" +
" and 20% test matrices");
int[][] trainData = null;
int[][] testData = null;
MakeTrainTest(data, 0, out trainData, out testData);
方法 MakeTrainTest 有 （你可能想 %使用作為訓練資料的參數化） 的硬編碼 80%到 20%拆分。後顯示部分訓練資料來驗證什麼出了錯，該演示具現化一個揚分類器物件，並使用火車方法來創建一個模型，就是要找出一套良好的重量：
Console.WriteLine("First few rows of training data are:");
ShowMatrix(trainData, 3, true);
Console.WriteLine("Begin training using Winnow algorithm");
int numInput = 16;
Winnow w = new Winnow(numInput, 0);
weights = w.Train(trainData);
Console.WriteLine("Training complete");
揚建構函式需要 x 變數和一個種子值的數目為亂數字生成，用於處理中按照隨機的順序的培訓專案。接下來，演示顯示發現火車法的最終權重，然後再計算模型的準確性對訓練集和測試集：
Console.WriteLine("Final model weights are:");
ShowVector(weights, 4, 8, true);
double trainAcc = w.Accuarcy(trainData);
double testAcc = w.Accuarcy(testData);
Console.WriteLine("Prediction accuracy on training data = " +
trainAcc.ToString("F4"));
Console.WriteLine("Prediction accuracy on test data = " +
testAcc.ToString("F4"));
演示程式最後預測的假設美國的政黨 眾議院投票"是"所有 16 法案方面，如中所示的人圖 4。
圖 4 預測政治党
...
Console.WriteLine("Predicting party of Representative" + "
with all 'yes' votes");
int[] unknown = new int[] { 1, 1, 1, 1, 1, 1, 1, 1,
1 , 1, 1, 1, 1, 1, 1, 1 };
int predicted = w.ComputeOutput(unknown);
if (predicted == 0)
Console.WriteLine("Prediction is 'democrat'");
else
Console.WriteLine("Prediction is 'republican'");
Console.WriteLine("End Winnow demo");
Console.ReadLine();
} // Main
揚類
揚類具有五個資料成員：
private int numInput;
private double[] weights;
private double threshold;
private double alpha;
private static Random rnd;
資料成員閾值保存的值，用於確定是否計算 Y 是 0 （低於閾值) 或 1 (高於閾值）。資料成員阿爾法時不正確的 Y 計算 （研究文獻中被稱為降級） 減少或增加 （稱為促進） 權重的因素。阿爾法的標準值是 2.0，早些時候在這篇文章中所示。你可能想要嘗試通過使用兩個不同的值用於升級和降級，而不是單一的 Alpha 值為兩個。
揚定義建構函式就像這樣：
public Winnow(int numInput, int rndSeed)
{
this.numInput = numInput;
this.weights = new double[numInput];
for (int i = 0; i < weights.Length; ++i)
weights[i] = numInput / 2.0;
this.threshold = 1.0 * numInput;
this.alpha = 2.0;
rnd = new Random(rndSeed);
}
門檻值初始化為輸入變數，例如 16.0 在演示中的數目。此值是標準的 Winnow 演算法，但你可能想要嘗試的可選值。無效果乘以 1.0 是有建議可以使用不同的值，但他們應該與相關的輸入變數數。
權重陣列分配使用的輸入變數，在演示中的 16 號。每個權值初始化為輸入變數除以 2 或在演示 8.0 的數目。此值是任意的並再一次，你可能想要嘗試。Winnow 演算法尚未被開發的研究很多相對於眾多其他，較常用的分類演算法。
方法 ComputeOutput 非常簡單：
public int ComputeOutput(int[] xValues)
{
double sum = 0.0;
for (int i = 0; i < numInput; ++i)
sum += weights[i] * xValues[i];
if (sum > this.threshold)
return 1;
else
return 0;
}
請注意，返回 1 的值是否嚴格大於閾值的值，而大於或等於閾值的累積的總和。這是專斷，而且使用"> ="而不是">"不會顯著影響的演算法。
培訓方法
揚的例行訓練演算法是最短和最簡單的所有毫升分類演算法之一。方法定義開始：
public double[] Train(int[][] trainData)
{
int[] xValues = new int[numInput];
int target;
int computed;
Shuffle(trainData);
...
本地陣列"xValues"擁有一個培訓專案，從輸入的值，但不是目標輸出值。本地變數"目標"可保存從培訓資料項目目所需的 Y 值。"計算"的本地變數存儲計算的 Y 值，為一組給定的輸入的 x 值和當前的權重集。法洗牌隨機使用 Fisher 茨最小化演算法的訓練資料的順序。
下一步，主要培訓迴圈開始：
for (int i = 0; i < trainData.Length; ++i)
{
Array.Copy(trainData[i], xValues, numInput); // Inputs
target = trainData[i][numInput]; // Last value is target
computed = ComputeOutput(xValues);
// Update weights here
}
正如前面提到的它不是完全清楚多長時間來訓練。演示只是一次遍歷訓練資料。另一種是迴圈多次通過訓練資料，停止後固定數目的反覆運算，或者也許當一些所需精度已達到。
在主要培訓迴圈中，使用中的代碼更新權重圖 5。
圖 5 更新權重
if (computed == 1 && target == 0) // Decrease
{
for (int j = 0; j < numInput; ++j)
{
if (xValues[j] == 0) continue; // Not relevant
weights[j] = weights[j] / alpha; // Demotion
}
}
else if (computed == 0 && target == 1) // Increase
{
for (int j = 0; j < numInput; ++j)
{
if (xValues[j] == 0) continue; // Not relevant
weights[j] = weights[j] * alpha; // Promotion
}
}
方法火車通過複製到一個本地的返回陣列的最佳權重得出結論：
...
} // end for
double[] result = new double[numInput]; // = number weights
Array.Copy(this.weights, result, numInput);
return result;
} // Train
總結
這篇文章基於原先提出的 Winnow 演算法的研究論文"學習很快當無關的屬性比比皆是：一種新的線性閾值演算法"(1998 年) ； Littlestone。 你能找到本文在幾個地點在網站上的 PDF 格式。
雖然做這篇文章的背景研究，我碰到有趣的使用 F # 語言編寫的 Winnow 演算法實現。執行是在個人的博客，寫的 Mathias Brandewinder (bit.ly/1z8hfj6)。
雖然揚分類專門為獨立的 x 變數在哪裡所有二進位二進位分類問題而設計的你可能想要嘗試對一個或多個 x 變數分類的問題。例如，假設一個預測變數是"色"和可以採取三個可能值之一："紅"、"綠色，"或"blue"。如果你使用 N 1 編碼，紅色成為 （1，0，0），綠色成為 （0，1，0），藍色成為 （0，0，1），並可以應用的 Winnow 演算法。
James McCaffrey 適合在雷德蒙的微軟研究院 他曾在幾個 Microsoft 產品包括 Internet Explorer 和冰。他可以在達成 jammc@microsoft.com。
衷心感謝以下技術專家在微軟研究院對本文的審閱：彌敦道布朗和KirkOlynyk