《集體智慧編程》讀書筆記7
最近重讀《集體智慧編程》，這本當年出版的介紹推薦系統(tǒng)的書，在當時看來很引領潮流，放眼現(xiàn)在已經(jīng)成了各互聯(lián)網(wǎng)公司必備的技術。
這次邊閱讀邊嘗試將書中的一些Python語言例子用C#來實現(xiàn)，利于自己理解，代碼貼在文中方便各位園友學習。
由于本文可能涉及到的與原書版權(quán)問題，請第三方不要以任何形式轉(zhuǎn)載，謝謝合作。
第七部分 kNN算法
上一節(jié)的最后，給出了一個用方差來作為結(jié)果為數(shù)值的決策樹評價的方法。這一部分我們針對結(jié)果為數(shù)值的數(shù)據(jù)集給出一種更好的預測算法。
針對數(shù)值型結(jié)果預測的算法最關鍵的工作就是確定哪些變量對結(jié)果的影響最大，這個可以通過前面文章介紹的“優(yōu)化技術“（如模擬退火和遺傳算法）來自動確定變量的權(quán)重。
這一部分將以商品價格預測作為例子，這是多個特征決定一個數(shù)值的結(jié)果的典型例子。
構(gòu)造數(shù)據(jù)集
這個例子中我們模擬構(gòu)造了一個關于葡萄酒價格的數(shù)據(jù)集。價格模型的確定方式是：酒的價格根據(jù)酒的等級及其儲藏的年代共同決定，另外假設葡萄酒有”峰值年“概念，較之峰值年，年代早的葡萄酒品質(zhì)更高，而峰值年之后的則品質(zhì)稍差。高等級的葡萄酒的價格將從高位隨著越接近峰值年價格越高。而低等級的葡萄酒價格從低位逐漸走低。
我們創(chuàng)建一個名為NumPredict的類并在其中加入WinePrice來模擬生成葡萄酒價格：
public double WinePrice(double rating, double age)
{
var peakAge = rating - 50;
//根據(jù)等級計算價格
var price = rating / 2;
if (age > peakAge)
{
//經(jīng)過“峰值年”，后繼5年里其品質(zhì)將會變差
price = price * (5 - (age - peakAge) / 2); //原書配書源碼有/2，印刷版中沒有是個錯誤，會導致為0的商品過多
}
else
{
//價格在接近“峰值年”時會增加到原值的5倍
price = price * (5 * (age + 1) / peakAge);
}
if (price < 0)
price = 0;
return price;
}
然后再添加一個名為WineSet1用于模擬生產(chǎn)一批葡萄酒，并使用上面的方法制定葡萄酒的價格。最終的價格會在上面函數(shù)確定的價格基礎上隨機加減20%，這一是模擬稅收，市場供應的客觀情況對價格的影響，二來可以使數(shù)據(jù)更真實增加數(shù)值型預測的難度。
public List<PriceStructure> WineSet1()
{
var rows = new List<PriceStructure>(300);
var rnd = new Random();
for (int i = 0; i < 300; i++)
{
//隨機生成年代和等級
var rating = rnd.NextDouble() * 50 + 50;
var age = rnd.NextDouble() * 50;
//得到參考價格
var price = WinePrice(rating, age);
//增加“噪聲”
price *= rnd.NextDouble() * 0.9 + 0.2; //配書代碼的實現(xiàn)
//加入數(shù)據(jù)集
rows.Add(new PriceStructure()
{
Input = new[] { rating, age },
Result = price
});
}
return rows;
}
上面代碼中我們還添加了一個內(nèi)部類PriceStructure用于表示一瓶酒的價格形成結(jié)構(gòu)。
接著我們測試下上面的代碼，保證可以生成葡萄酒的價格數(shù)據(jù)集以用于后續(xù)的預測：
var numPredict = new NumPredict();
var price = numPredict.WinePrice(95, 3);
Console.WriteLine(price);
price = numPredict.WinePrice(95, 8);
Console.WriteLine(price);
price = numPredict.WinePrice(99, 1);
Console.WriteLine(price);
var data = numPredict.WineSet1();
Console.WriteLine(JsonConvert.SerializeObject(data[0]));
Console.WriteLine(JsonConvert.SerializeObject(data[1]));
由于是隨機生成，每次構(gòu)造的價格數(shù)據(jù)集都是不一樣的。
k-最鄰近算法
k-最鄰近算法(k-nearest neighbors)，簡稱kNN，的思想很簡單，找到與所預測商品最近似的一組商品，對這些近似商品價格求均值來作為價格預測。
近鄰數(shù) - k
kNN中的k表示所查找的最近似的一組商品的數(shù)量，理想狀況下，設置k為1會查找與待預測商品最近似的商品價格作為預測結(jié)果。
但實際情況中，會有如本例中故意加入的”噪聲“這種干擾情況，使得最為進行的一個商品的價格不能最準確的反應待預測商品的價格。所以就需要通過選取k(k>1)個近似的商品并取其價格的均值來減少”噪聲“影響。
當然如果選擇過多的相似商品（較大的k值），也會導致均值產(chǎn)生不應有的偏差。
定義相似度
要使用kNN算法，第一個要做的就是確定判斷兩個商品相似度的方法。我們使用之前文章介紹過的歐幾里德距離算法。
我們將算法函數(shù)Euclidean加入NumPredict：
public double Euclidean(double[] v1, double[] v2)
{
var d = v1.Select((t, i) => (double)Math.Pow(t - v2[i], 2)).Sum();
return (double)Math.Sqrt(d);
}
接著來測試下歐幾里德距離算法計算到的相似度：
var numPredict = new NumPredict();
var data = numPredict.WineSet1();
var similar = numPredict.Euclidean(data[0].Input, data[1].Input);
Console.WriteLine(similar);
目前的kNN算法所使用的相似度算法存在的問題，就是對不同因素的同樣量度差別是同等看待的，而現(xiàn)實情況是一種因素往往產(chǎn)生的影響比另一種更大（同樣量度下），后文將會介紹解決此問題的方法。
實現(xiàn)kNN算法
kNN的實現(xiàn)很簡單，而且雖然其計算量較大，但可以進行增量訓練。
首先，我們在NumPredict中添加計算距離列表的方法GeetDistances：
private SortedDictionary<double, int> GetDistances(List<PriceStructure> data, double[] vec1)
{
var distancelist = new SortedDictionary<double, int>(new RankComparer());
for (int i = 0; i < data.Count; i++)
{
var vec2 = data[i].Input;
distancelist.Add(Euclidean(vec1, vec2), i);
}
return distancelist;
}
class RankComparer : IComparer<double>
{
public int Compare(double x, double y)
{
if (x == y) //這樣可以讓SortedList保存重復的key
return 1;
return x.CompareTo(y); //從小到大排序
}
}
方法中我們使用SortedDictionary按距離進行了排序方便后面取前k個最近的項。
接著是knnestimate函數(shù)，其取上面列表的前k項并求平均值。
public double KnnEstimate(List<PriceStructure> data, double[] vec1, int k = 5)
{
//得到經(jīng)過排序的距離值
var dlist = GetDistances(data, vec1);
return dlist.Values.Take(k).Average(dv => data[dv].Result);
}
有了這些方法就可以對商品進行估價了。
var numPredict = new NumPredict();
var data = numPredict.WineSet1();
var estimate = numPredict.KnnEstimate(data, new [] { 95d, 3});
Console.WriteLine(estimate);
estimate = numPredict.KnnEstimate(data, new[] { 99d, 3});
Console.WriteLine(estimate);
estimate = numPredict.KnnEstimate(data, new[] { 99d, 5});
Console.WriteLine(estimate);
var real = numPredict.WinePrice(99, 5);
Console.WriteLine(real);
estimate = numPredict.KnnEstimate(data, new[] { 99d, 5}, 1);
Console.WriteLine(estimate);
上面的方法對比了預測價格與真實價格，并可以看到不同的k值對結(jié)果的影響。
為近鄰分配權(quán)重
上面的算法中計算預測價格時采用k個近似的商品的均價而沒有考慮這些商品的近似度不同。這一部分我們對這個問題進行一些修正，我們按照近似程度對這些商品的價格賦予一定的權(quán)重。將“距離”（相似度指標）轉(zhuǎn)為權(quán)重有如下三種方法。
反函數(shù)
反函數(shù)即取距離的倒數(shù)作為權(quán)重。由于當距離極小（相似度極高）時，權(quán)重會極具變大（分母減小過快，會使倒數(shù)明顯增大）。我們在計算權(quán)重前，給距離加上一個初始常量來避免這個問題。
將反函數(shù)的實現(xiàn)方法InverseWeight加入NumPredict中：
public double InverseWeight(double dist, double num = 1, double @const = 0.1f)
{
return num / (dist + @const);
}
反函數(shù)計算速度很快，但其明顯的問題是，隨著相似度降低，權(quán)重衰減很快，有些情況下這可能會帶來問題。
減法函數(shù)
減法函數(shù)是一個更簡單的函數(shù)，其用一個常量值減去距離，如果結(jié)果大于0，則將結(jié)果作為權(quán)重，否則權(quán)重為0。
NumPredict中的SubtractWeight方法是減法函數(shù)的實現(xiàn)：
public double SubtractWeight(double dist, double @const = 1)
{
if (dist > @const) return 0;
return @const - dist;
}
這個方法的缺陷是，如果權(quán)重值都降為0，可能無法找到足夠的近似商品來提供預測數(shù)據(jù)。
高斯函數(shù)
當距離為1時，高斯函數(shù)計算的權(quán)重為1；權(quán)重值隨著距離增加而減小，但始終不會減小到0。這就避免了減法函數(shù)中那樣出現(xiàn)無法預測的問題。
將高斯函數(shù)的實現(xiàn)方法Gaussian加入NumPredict中：
public double Gaussian(double dist, double sigma = 10)
{
var exp = (double)Math.Pow(Math.E, -dist * dist / (2 * sigma * sigma));
return exp;
}
通過代碼也可以看出，高斯函數(shù)的速度不像之前的方法那樣快。
在實現(xiàn)加權(quán)kNN前先來測試下這些權(quán)值計算函數(shù)：
var numPredict = new NumPredict();
var weight = numPredict.SubtractWeight(0.1f);
Console.WriteLine(weight);
weight = numPredict.InverseWeight(0.1f);
Console.WriteLine(weight);
weight = numPredict.Gaussian(0.1f);
Console.WriteLine(weight);
weight = numPredict.Gaussian(1);
Console.WriteLine(weight);
weight = numPredict.SubtractWeight(1);
Console.WriteLine(weight);
weight = numPredict.InverseWeight(1);
Console.WriteLine(weight);
weight = numPredict.Gaussian(3);
Console.WriteLine(weight);
三個函數(shù)都符合距離越遠，權(quán)重越小這一要求。
加權(quán)kNN
加權(quán)kNN與之前的普通kNN就在于對于最類似的k個商品的價格是求加權(quán)評價，而非普通的求平均。
加權(quán)平均的做法就是把每個商品的價格乘以其權(quán)重，累加所有加權(quán)價格后再除以權(quán)重的和。
在NumPredict中加入加權(quán)kNN計算方法Weightedknn
public double Weightedknn(List<PriceStructure> data, double[] vec1, int k = 5,
Func<double, double, double> weightf = null)
{
if (weightf == null) weightf = Gaussian;
//得到經(jīng)過排序的距離值
var dlist = GetDistances(data, vec1);
var avg = 0d;
var totalweight = 0d;
//得到加權(quán)平均
foreach (var kvp in dlist.Take(k))
{
var dist = kvp.Key;
var idx = kvp.Value;
var weight = weightf(dist, 10);
avg += weight * data[idx].Result;
totalweight += weight;
}
if (totalweight == 0) return 0;
avg /= totalweight;
return avg;
}
我們用下面的代碼測試下加權(quán)kNN計算的結(jié)果：
var numPredict = new NumPredict();
var data = numPredict.WineSet1();
var price = numPredict.Weightedknn(data, new []{99d, 5});
Console.WriteLine(price);
可以看到Weightedknn比KnnEstimate有更好的預測效果。
下面會介紹怎么去驗證這些不同預測方法的優(yōu)劣。
交叉驗證
交叉驗證是將數(shù)據(jù)集拆分為訓練集和測試集。使用訓練集來訓練算法，并將測試集的每一項傳入算法得到一個預測結(jié)果，將這個預測結(jié)果與真實值進行對比，最后得到一個誤差分值。通過這個分值可以評估預測的準確程度。
通常交叉驗證會進行多測，每次使用不同的數(shù)據(jù)集劃分方式，結(jié)果分值也是幾次交叉驗證分值的平均值。在劃分上一般訓練集數(shù)據(jù)占數(shù)據(jù)集的95%，剩下的是測試集。
首先在NumPredict中實現(xiàn)數(shù)據(jù)劃分方法DivideData：
public Tuple<List<PriceStructure>, List<PriceStructure>> DivideData(List<PriceStructure> data,
double test = 0.05f)
{
var trainSet = new List<PriceStructure>();
var testSet = new List<PriceStructure>();
var rnd = new Random();
foreach (var row in data)
{
if (rnd.NextDouble() < test)
testSet.Add(row);
else
trainSet.Add(row);
}
return Tuple.Create(trainSet, testSet);
}
接著是一次測試的方法TestAlgorithm，仍然是放在NumPredict中：
public double TestAlgorithm(Func<List<PriceStructure>, double[], double> algf,
List<PriceStructure> trainSet, List<PriceStructure> testSet)
{
var error = 0d;
foreach (var row in testSet)
{
var guess = algf(trainSet, row.Input);
error += Math.Pow(row.Result - guess, 2);
}
return error / testSet.Count;
}
這個方法使用訓練集訓練，并在測試集上進行測試，使用預測結(jié)果與真實結(jié)果進行比較。我們在計算差異值時選擇了平方差。方差給傾向于給所有測結(jié)果和真實結(jié)果都比較接近的算法更高的分值。如果不在意個別預測結(jié)果與真實值有較大起伏，可以使用差值絕對值的平均值代替方差。
最后是交叉測試的主方法CrossValidate，這個方法實際上就是將上面兩個方法反復調(diào)用多并給出結(jié)果的平均值。
public double CrossValidate(Func<List<PriceStructure>, double[], double> algf,
List<PriceStructure> data, int trials = 100, double test = 0.05f)
{
var error = 0d;
for (int i = 0; i < trials; i++)
{
var setDiv = DivideData(data, test);
error += TestAlgorithm(algf, setDiv.Item1, setDiv.Item2);
}
return error / trials;
}
有了這些方法就可以測試不同的算法，或者是同一個算法給予不同的參數(shù)的預測效果。
var numPredict = new NumPredict();
var data = numPredict.WineSet1();
Func<List<NumPredict.PriceStructure>, double[], double> knnEstiDefault =
(dataset, vec) => numPredict.KnnEstimate(dataset, vec);
var score = numPredict.CrossValidate(knnEstiDefault, data);
Console.WriteLine(score);
Func<List<NumPredict.PriceStructure>, double[], double> knnEsti3 =
(dataset, vec) => numPredict.KnnEstimate(dataset, vec, 3);
score = numPredict.CrossValidate(knnEsti3, data);
Console.WriteLine(score);
Func<List<NumPredict.PriceStructure>, double[], double> knnEsti1 =
(dataset, vec) => numPredict.KnnEstimate(dataset, vec, 1);
score = numPredict.CrossValidate(knnEsti1, data);
Console.WriteLine(score);
在博主的測試中，默認參數(shù)的kNN算法效果最好（分值最低，表示預測和實際誤差最小）。
也可以試試加權(quán)kNN，以及使用非默認權(quán)重函數(shù)（高斯函數(shù)）的加權(quán)kNN。
var numPredict = new NumPredict();
var data = numPredict.WineSet1();
Func<List<NumPredict.PriceStructure>, double[], double> weightedKnnDefault =
(dataset, vec) => numPredict.Weightedknn(dataset, vec);
var score = numPredict.CrossValidate(weightedKnnDefault, data);
Console.WriteLine(score);
Func<double, double, double> inverseWeight = (d, n) => numPredict.InverseWeight(d);
Func<List<NumPredict.PriceStructure>, double[], double> weightedKnnInverse =
(dataset, vec) => numPredict.Weightedknn(dataset, vec, 5, inverseWeight);
score = numPredict.CrossValidate(weightedKnnInverse, data);
Console.WriteLine(score);
上面的測試數(shù)據(jù)集只有兩個不同的選項 - 等級和年份。當商品有更多選項時，在比較相似度時怎樣自動給予不同的選項不同的權(quán)重是下一部分要討論的話題。
多種輸入變量
之前的例子中我們的輸入變量只有兩種，而且這兩種變量是經(jīng)過特意設計。顯示中輸入可能有多種變量，而且這些變量可能有以下問題：
- 不同變量的值域差異較大，這會導致臨近距離值不能真實反應兩條記錄的差異，即值域較大的變量所帶來的影響會影響其他變量，即使這個變量本身不是與結(jié)果關系最大的變量。
- 有些變量與結(jié)果幾乎沒有關系，但之前的方法仍然會將其影響計算在內(nèi)。
新的數(shù)據(jù)集
我們實現(xiàn)一個名為WineSet2的方法生成一個存在上文描述問題的輸入集。
public List<PriceStructure> WineSet2()
{
var rows = new List<PriceStructure>(300);
var rnd = new Random();
for (int i = 0; i < 300; i++)
{
//隨機生成年代和等級
var rating = rnd.NextDouble() * 50 + 50;
var age = rnd.NextDouble() * 50;
var aisle = (double)rnd.Next(1, 20);
var sizeArr = new[] { 375d, 750d, 1500d, 3000d };
var bottleSize = sizeArr[rnd.Next(0, 3)];
//得到參考價格
var price = WinePrice(rating, age);
price *= (bottleSize / 750);
//增加“噪聲”
price *= (rnd.NextDouble() * 0.9d + 0.2d); //配書代碼的實現(xiàn)
//加入數(shù)據(jù)集
rows.Add(new PriceStructure()
{
Input = new[] { rating, age, aisle, bottleSize },
Result = price
});
}
return rows;
}
新的數(shù)據(jù)集添加了兩個列，其中第三列模擬葡萄酒桶存放的通道。第四列模擬葡萄酒桶的尺寸。
試試生成一個新的數(shù)據(jù)集：
var numPredict = new NumPredict();
var data = numPredict.WineSet2();
Console.WriteLine(JsonConvert.SerializeObject(data));
在新的數(shù)據(jù)集上測試下之前的算法：
var numPredict = new NumPredict();
var data = numPredict.WineSet2();
Func<List<NumPredict.PriceStructure>, double[], double> knnEsti3 =
(dataset, vec) => numPredict.KnnEstimate(dataset, vec, 3);
var score = numPredict.CrossValidate(knnEsti3, data);
Console.WriteLine(score);
Func<List<NumPredict.PriceStructure>, double[], double> weightedKnnDefault =
(dataset, vec) => numPredict.Weightedknn(dataset, vec);
score = numPredict.CrossValidate(weightedKnnDefault, data);
Console.WriteLine(score);
通過結(jié)果可以看出交叉驗證結(jié)果很不理想，這是因為我們沒有對不同的變量區(qū)別對待。
按比例縮放
結(jié)果變量值域不一致的簡單做法就是對輸入值進行縮放，即類似歸一化的操作。具體到實現(xiàn)上就是將變量乘以一個縮放比例。
下面的ReScale方法對每個列的變量進行了縮放：
public List<PriceStructure> ReScale(List<PriceStructure> data, double[] scale)
{
return (from row in data
let scaled = scale.Select((s, i) => s * row.Input[i]).ToArray()
select new PriceStructure()
{
Input = scaled,
Result = row.Result
}).ToList();
}
數(shù)組參數(shù)scale保存了每個列的縮放比例。
我們可以試著構(gòu)造一個縮放比例，如過道信息與價格無關，將其縮放比例設為0。
var numPredict = new NumPredict();
var data = numPredict.WineSet2();
var sdata = numPredict.ReScale(data, new[] { 10, 10, 0, 0.5 });
Func<List<NumPredict.PriceStructure>, double[], double> knnEsti3 =
(dataset, vec) => numPredict.KnnEstimate(dataset, vec, 3);
var score = numPredict.CrossValidate(knnEsti3, sdata);
Console.WriteLine(score);
Func<List<NumPredict.PriceStructure>, double[], double> weightedKnnDefault =
(dataset, vec) => numPredict.Weightedknn(dataset, vec);
score = numPredict.CrossValidate(weightedKnnDefault, sdata);
Console.WriteLine(score);
優(yōu)化縮放比例
上面的代碼中，由于輸入集是我們子集構(gòu)造的，所以知道如何選擇最佳的縮放比例。現(xiàn)實中確定縮放比例就需要其他技巧。
利用之前文章介紹的優(yōu)化算法可以幫我們選擇最佳的縮放比例。
優(yōu)化算法需要一個值域范圍，即每個例的縮放比例的范圍以及一個成本函數(shù)。
對于值域范圍，如下代碼生成的結(jié)果就很適合比例：
public List<Tuple<int, int>> GetWeightDomain(int count)
{
var domains = new List<Tuple<int, int>>(count);
for (var i = 0; i < 4; i++)
{
domains.Add(Tuple.Create(0, 20));
}
return domains;
}
權(quán)重最小值0表示此項與結(jié)果毫無關系。
對于成本函數(shù)，我們可以用如下方法包裝下之前實現(xiàn)的CrossValidate就能快速得到一個非常好用的成本函數(shù)。
public Func<double[], double> CreateCostFunction(Func<List<PriceStructure>, double[], double> algf,
List<PriceStructure> data)
{
Func<double[], double> Costf = scale =>
{
var sdata = ReScale(data, scale);
return CrossValidate(algf, sdata, 10);
};
return Costf;
}
另外我們還需要之前文章實現(xiàn)的優(yōu)化算法，由于參數(shù)類型的問題，我們不能直接使用之前的代碼，而需要對參數(shù)類型稍作調(diào)整：
public List<double> AnnealingOptimize(List<Tuple<int, int>> domain, Func<double[], double> costf,
float T = 10000.0f, float cool = 0.95f, int step = 1)
{
//隨機初始化值
var random = new Random();
var vec = domain.Select(t => (double)random.Next(t.Item1, t.Item2)).ToArray();
while (T > 0.1)
{
//選擇一個索引值
var i = random.Next(0, domain.Count - 1);
//選擇一個改變索引值的方向
var dir = random.Next(-step, step);
//創(chuàng)建一個代表題解的新列表，改變其中一個值
var vecb = vec.ToArray();
vecb[i] += dir;
if (vecb[i] < domain[i].Item1) vecb[i] = domain[i].Item1;
else if (vecb[i] > domain[i].Item2) vecb[i] = domain[i].Item2;
//計算當前成本和新成本
var ea = costf(vec);
var eb = costf(vecb);
//是更好的解？或是退火過程中可能的波動的臨界值上限？
if (eb < ea || random.NextDouble() < Math.Pow(Math.E, -(eb - ea) / T))
vec = vecb;
//降低溫度
T *= cool;
}
return vec.ToList();
}
public List<double> GeneticOptimize(List<Tuple<int, int>> domain, Func<double[], double> costf,
int popsize = 50, int step = 1, float mutprob = 0.2f, float elite = 0.2f, int maxiter = 100)
{
var random = new Random();
//變異操作
Func<double[], double[]> mutate = vec =>
{
var i = random.Next(0, domain.Count - 1);
if (random.NextDouble() < 0.5 && vec[i] > domain[i].Item1)
return vec.Take(i).Concat(new[] { vec[i] - step }).Concat(vec.Skip(i + 1)).ToArray();
else if (vec[i] < domain[i].Item2)
return vec.Take(i).Concat(new[] { vec[i] + step }).Concat(vec.Skip(i + 1)).ToArray();
return vec;
};
//配對操作
Func<double[], double[], double[]> crossover = (r1, r2) =>
{
var i = random.Next(1, domain.Count - 2);
return r1.Take(i).Concat(r2.Skip(i)).ToArray();
};
//構(gòu)造初始種群
var pop = new List<double[]>();
for (int i = 0; i < popsize; i++)
{
var vec = domain.Select(t => (double)random.Next(t.Item1, t.Item2)).ToArray();
pop.Add(vec);
}
//每一代中有多少勝出者？
var topelite = (int) (elite*popsize);
Func<double, double, int> cf = (x, y) => x == y ? 1 : x.CompareTo(y);
var scores = new SortedList<double, double[]>(cf.AsComparer());
//主循環(huán)
for (int i = 0; i < maxiter; i++)
{
foreach (var v in pop)
scores.Add(costf(v),v);
var ranked = scores.Values;
//從勝出者開始
pop = ranked.Take(topelite).ToList();
//添加變異和配對后的勝出者
while (pop.Count<popsize)
{
if (random.NextDouble() < mutprob)
{
//變異
var c = random.Next(0, topelite);
pop.Add(mutate(ranked[c]));
}
else
{
//配對
var c1 = random.Next(0, topelite);
var c2 = random.Next(0, topelite);
pop.Add(crossover(ranked[c1],ranked[c2]));
}
}
//打印當前最優(yōu)值
//Console.WriteLine(scores.First().Key);
}
return scores.First().Value.ToList();
}
好了，現(xiàn)在可以試著用優(yōu)化算法得到縮放比例了：
首先來試一下模擬退火算法：
var numPredict = new NumPredict();
var data = numPredict.WineSet2();
Func<List<NumPredict.PriceStructure>, double[], double> knnEstimate =
(dataset, vec) => numPredict.KnnEstimate(dataset, vec);
var costf = numPredict.CreateCostFunction(knnEstimate, data);
var optimization = new Travel();
var optDomain = optimization.AnnealingOptimize(numPredict.GetWeightDomain(4), costf, step: 2);
Console.WriteLine(JsonConvert.SerializeObject(optDomain));
接著可以試試速度慢但效果更好的遺傳算法：
var numPredict = new NumPredict();
var data = numPredict.WineSet2();
Func<List<NumPredict.PriceStructure>, double[], double> knnEstimate =
(dataset, vec) => numPredict.KnnEstimate(dataset, vec);
var costf = numPredict.CreateCostFunction(knnEstimate, data);
var optimization = new Travel();
var optDomain = optimization.GeneticOptimize(numPredict.GetWeightDomain(4), costf, popsize: 5);
Console.WriteLine(JsonConvert.SerializeObject(optDomain));
這種自動確定縮放比例的方法也可以讓我們了解到哪些因素與結(jié)果關系密切，從而采取更好的市場策略。
不對稱分布
在之前的例子中，預測價格通過取相似商品價格的平均值或加權(quán)平均值來進行。但是對于如下假設這種處理方法就會有問題。
假設一部分葡萄酒是從折扣店購買，其價格只有正常價格的50%，但是這個折扣沒有作為變量出現(xiàn)在輸入數(shù)據(jù)中。
我們用方法WineSet3模擬這樣一個數(shù)據(jù)集：
public List<PriceStructure> WineSet3()
{
var rows = WineSet1();
var rnd = new Random();
foreach (var row in rows)
{
if (rnd.NextDouble() < 0.5)
// 模擬從折扣店購得的葡萄酒
row.Result *= 0.5;
}
return rows;
}
這個數(shù)據(jù)集是在WineSet1生成的數(shù)據(jù)基礎上改造而來。
我們?nèi)匀豢梢杂弥暗乃惴ㄌ幚磉@個數(shù)據(jù)集：
var numPredict = new NumPredict();
var data = numPredict.WineSet3();
var price = numPredict.WinePrice(99, 20);
Console.WriteLine(price);
price = numPredict.Weightedknn(data, new[] { 99d, 20 });
Console.WriteLine(price);
可以看到真實價格和預測價格之間可能有較大差異。而且由于平均我們平均處理預測價格可能被進行了25%的折扣。
估計密度概率
我們需要實現(xiàn)一個方法來確定價格位于一個區(qū)間的概率。我們首先找出一定數(shù)量的相似商品，然后用價格處于區(qū)間內(nèi)的相似商品的權(quán)重和處于所有相似商品的權(quán)重和得到商品處于這個價格區(qū)間的概率。
我們在ProbGuess方法中實現(xiàn)這個概率估計過程：
public double ProbGuess(List<PriceStructure> data, double[] vec1, double low,
double high, int k = 5, Func<double, double, double> weightf = null)
{
if (weightf == null) weightf = Gaussian;
var dlist = GetDistances(data, vec1);
var nweight = 0d;
var tweight = 0d;
for (int i = 0; i < k; i++)
{
var dlistCurr = dlist.Skip(i).First();
var dist = dlistCurr.Key;
var idx = dlistCurr.Value;
var weight = weightf(dist, 10);
var v = data[idx].Result;
// 當前數(shù)據(jù)點在指定范圍嗎？
if (v >= low && v <= high)
nweight += weight;
tweight += weight;
}
if (tweight == 0) return 0;
//概率等于位于指定范圍內(nèi)的權(quán)重值除以所有權(quán)重值
return nweight / tweight;
}
參數(shù)low和high就是要判斷的價格區(qū)間。嘗試下這個概率預測函數(shù)：
var numPredict = new NumPredict();
var data = numPredict.WineSet3();
var prob = numPredict.ProbGuess(data, new[] { 99d, 20 }, 40, 80);
Console.WriteLine(prob);
prob = numPredict.ProbGuess(data, new[] { 99d, 20 }, 80, 120);
Console.WriteLine(prob);
prob = numPredict.ProbGuess(data, new[] { 99d, 20 }, 120, 1000);
Console.WriteLine(prob);
prob = numPredict.ProbGuess(data, new[] { 99d, 20 }, 30, 120);
Console.WriteLine(prob);
通過一小段一小段的傳入價格區(qū)間進行概率計算，可以確定整個數(shù)據(jù)集的價格分布情況。
下節(jié)將通過一種直觀的方法來展示概率分布情況：
繪制概率分布
通過繪制概率分布圖，可以避免上節(jié)逐段猜測價格區(qū)間的做法。
關于C#函數(shù)圖的繪制，經(jīng)過一番尋找在GitHub發(fā)現(xiàn)了這個名為MatplotlibCS的項目。
MatplotlibCS采用了一種很特殊的方式對matplotlib進行封裝，關于這個項目的起源，可以看這篇博文。
這里簡單介紹下MatplotlibCS的工作方式，MatplotlibCS的代碼分兩部分，C#編寫的客戶端，以及Python編寫的服務器端。C#端將Python庫matplotlib所需要的數(shù)據(jù)通過http傳輸?shù)交赑ython庫Flask編寫的服務器端。Flask接收客戶端傳來的數(shù)據(jù)并在內(nèi)部調(diào)用matplotlib完成實際的坐標圖像繪制。
這種方式可以擴展到其他有C#調(diào)用Python庫需求的常見。
下面來說說博主配置MatplotlibCS的曲折經(jīng)歷。博主電腦上安裝有官方2.7.4版本的Python，于是直接使用如下命令安裝matplotlib：
python -m pip install matplotlib
當然這會毫無意外的報錯（博主我也是折騰到后來才知道），基本上常見的錯誤如：
The following required packages can not be built:
freetype, png
去matplotlib官網(wǎng)看看，文檔中說Windows平臺建議使用如WinPython等第三方發(fā)行版，這些版本中一般都集成了matplotlib及一些常用的庫。于是下載了一個基于3.6.0的64位WinPython。
試了下集成的matplotlib可以使用。開始進行下一步。
可以使用下面的代碼測試matplotlib是否可用：
from pylab import *
a=[1,2,3,4]
b=[2,3,4,1]
plot(a,b)
show()
MatplotlibCS的服務器端部分，使用
python.exe matplotlib_cs.py
這樣的格式來啟動基于Python的Web服務。其中，文件matplotlib_cs.py位于MatplotlibCS-master/MatplotlibCS/Python內(nèi)。
運行上述命令，報錯說找不到名為task的庫。使用pip安裝后，繼續(xù)報錯無法由task導入Task。很是無解，百思不得姐后，放棄這種方法。
就在這山窮水盡之時，靈機一動想到了WSL(好多地方直接稱其Windows Bash)。既然是Python部分只是作為一個服務端，我們完全可以把其獨立運行。而WSL就是一個很好的運行環(huán)境。
MatplotlibCS的代碼也做了判斷，如果檢測到服務端在運行（不管是何種方式啟動的），C#代碼就不會再去啟動Python服務端了。
使用WSL的一個非常妙的地方時，WSL中發(fā)布的Python服務也是在127.0.0.1，也就是本機，這個域名下。由于這個服務端地址在MatplotlibCS代碼中是寫死的，使用WSL就不需要我們重新修改、編譯MatplotlibCS代碼。而是可以直接使用MatplotlibCS的Nuget包。
使用Docker for Windows可以實現(xiàn)和WSL一致的效果，它們兩個也是各有所長。
WSL中有2.7.6和3.4.3兩個版本的Python，命令分別為python和python3，對應的pip分別為pip和pip3。博主使用Python3運行MatplotlibCS的Python服務成功。下面是步驟：
在WSL中使用pip3安裝matplotlib
sudo pip3 install matplotlib #注意需要root權(quán)限
一般來說會報如下錯誤：
The following required packages can not be built:
freetype, png
需要在WSL單獨安裝這個包：
sudo apt-get install libfreetype6-dev
這個包及其依賴包可以滿足安裝matplotlib的需要。安裝完成后，重試matplotlib安裝，一般都會成功。
順便安裝后面需要用到的flask
sudo pip3 install flask
環(huán)境裝好，下面就可以啟動服務了。
首先進入MatplotlibCS源碼中包含matplotlib_cs.py這個文件的目錄。執(zhí)行：
python3 matplotlib_cs.py
不出意外服務可以正常啟動。可以看到如下提示：
Running on http://127.0.0.1:57123/ (Press CTRL+C to quit)
不得不說，可以和Windows共用同一套文件是WSL最大特色。如果使用Docker for Windows免不了要掛載主機目錄。
服務端完成，開始編寫客戶端代碼，首先在項目中安裝MatplotlibCS。
可以直接使用Nuget安裝：
Install-Package MatplotlibCS
還需要自行安裝下NLog（MatplotlibCS使用了NLog但沒有在Nuget包中聲明這個依賴）
Install-Package NLog
安裝后，我們寫一段簡單的代碼進行測試（這個代碼繪制的圖像，和之前測試matplotlib的Python代碼是相同的）：
public List<Axes> BuildAxes()
{
return new List<Axes>()
{
new Axes(1, "X", "Y")
{
Title = "MatplotlibCS Test",
PlotItems =
{
new Line2D("Line 1")
{
X = new List<object>() {1,2,3,4},
Y = new List<double>() {2,3,4,1}
}
}
}
};
}
public void Draw(List<Axes> plots)
{
// 由于我們在外部啟動Python服務，這兩個參數(shù)傳空字符串就可以了
var matplotlibCs = new MatplotlibCS.MatplotlibCS("", "");
var figure = new Figure(1, 1)
{
FileName = $"/mnt/e/Temp/result{DateTime.Now:ddHHmmss}.png",
OnlySaveImage = true,
DPI = 150,
Subplots = plots
};
var t = matplotlibCs.BuildFigure(figure);
t.Wait();
}
這其中BuildAxes用于構(gòu)造要繪制的坐標數(shù)據(jù)，Draw用于實際完成調(diào)用來生成圖片。
使用下面的代碼測試：
var numPredict = new NumPredict();
var axes = numPredict.BuildAxes();
numPredict.Draw(axes);
執(zhí)行成功后就會在FileName指定的目錄種看到圖片。
注意這個圖片輸出目錄，我們寫的是一個WSL樣式的絕對路徑（代碼種表示E盤下的Temp目錄）。這樣可以讓WSL中的Python服務直接把輸出的文件寫到本地磁盤中。而如果使用相對路徑，客戶端會把其變成基于Windows文件系統(tǒng)的絕對路徑并傳給WSL，而WSL無法識別這種路徑，導致Python服務報錯。
書歸正題，我們開始實現(xiàn)繪制本例的概率分布圖，我們將繪制兩種不同類型的概率分布圖：
第一種稱為累計概率，累計圖顯示的是價格小于給定值的概率，所以隨著給定價格（x軸）的增加，概率值（y軸）會逐漸升高直到1。
繪制累計概率圖的方法很簡單，只需要逐漸增大價格區(qū)段并循環(huán)調(diào)用ProbGuess方法，將得到概率值作為Y軸值即可，具體實現(xiàn)見CumulativeGraph
public void CumulativeGraph(List<PriceStructure> data, double[] vec1,
double high, int k = 5, Func<double, double, double> weightf = null)
{
if (weightf == null) weightf = Gaussian;
var t1 = new List<object>();
for (var i = 0d; i < high; i += 0.1)
t1.Add(i);
var cprob = t1.Select(v => ProbGuess(data, vec1, 0, (double)v, k, weightf)).ToList();
var axes = new Axes(1, "Price", "Cumulative Probility")
{
Title = "Price Cumulative Probility",
PlotItems =
{
new Line2D("")
{
X = t1,
Y = cprob
}
}
};
Draw(new List<Axes>() { axes });
}
調(diào)用這個方法也很簡單：
生成概率累加圖如下：
可以看到在20-40及60-80區(qū)間概率和發(fā)生了變動，可以確定這兩個價格區(qū)間就是商品價格的主要分布區(qū)間，這樣就避免了之前的無緒猜測。
另一種概率圖繪制方法就是繪制該價格位置處的實際概率。但如果直接繪制，所顯示圖像將是一個個跳躍的小點。所以我們采取將一個價格對應的概率與左右的概率進行加權(quán)平均，這樣可以使繪制的函數(shù)圖像更連續(xù)。
我們在ProbabilityGraph中實現(xiàn)了概率值的加權(quán)平均處理及函數(shù)圖的繪制：
public void ProbabilityGraph(List<PriceStructure> data, double[] vec1,
double high, int k = 5, Func<double, double, double> weightf = null,double ss=5)
{
if (weightf == null) weightf = Gaussian;
// 價格值域范圍
var t1 = new List<object>();
for (var i = 0d; i < high; i += 0.1)
t1.Add(i);
// 整個值域范圍的所有概率
var probs = t1.Cast<double>()
.Select(v => ProbGuess(data, vec1, v, v+0.1, k, weightf)).ToList();
// 通過加上近鄰概率的高斯計算結(jié)果，對概率值做平滑處理
var smoothed = new List<double>();
for (int i = 0; i < probs.Count; i++)
{
var sv = 0d;
for (int j = 0; j < probs.Count; j++)
{
var dist = Math.Abs(i - j)*0.1;
var weight = Gaussian(dist, sigma: ss);
sv += weight*probs[j];
}
smoothed.Add(sv);
}
var axes = new Axes(1, "Price", "Probility")
{
Title = "Price Probility",
PlotItems =
{
new Line2D("")
{
X = t1,
Y = smoothed
}
}
};
Draw(new List<Axes>() { axes });
}
開始繪圖吧
var numPredict = new NumPredict();
var data = numPredict.WineSet3();
numPredict.ProbabilityGraph(data, new[] { 1d, 1 }, 120);
生成的圖像如下：
可以看到商品所處的價格區(qū)間和概率累計圖所反映的價格區(qū)間一致，但是這個圖像還能更直觀的反應出落在哪個價格區(qū)間的商品更多。
通過商品價格概率分布圖，還能看出我們的輸入數(shù)據(jù)缺少了一定的關鍵因素。所以這樣的圖可以給決策者提供更好的銷售策略，定價策略支持。
總結(jié)
kNN算法的缺點在于要計算每個點之間的相似度（距離），計算量很大。另外如果需要通過優(yōu)化算法確定輸入列的權(quán)重，又會增加很大的計算量。在數(shù)據(jù)集很大時，計算將會非常緩慢。
而kNN的優(yōu)點時可以增量的進行訓練。通過繪制概率分布，還可以看出輸入中是否缺乏的必要的因素。
浙公網(wǎng)安備 33010602011771號