2015-03-22

此文章由机器翻译。

测试运行

多粒子群优化的逻辑回归分类

James McCaffrey Logistic 回归分析（LR）分类是机器学习的最基本形式之一。LR 分类的目标是创建一个模型，预测变量，可以在两个可能值之一。例如，您可能想要预测哪两位候选人的选民将选择（"史密斯"= 0，"琼斯"= 1）基于选民的年龄 (x1)、性别 (2) 和年收入 (3)。

如果 Y 预测的值，LR 模型为这一问题将采取的形式：

z = b0 + b1(x1) + b2(x2) + b3(x3)
Y = 1.0 / (1.0 + e^-z)

在这里，b0、 b1、 b2 和 b3 是权重，是必须确定的只是数字值。换句话说，你计算是输入的值的总和值 z 次 b-权重，再加上一个 b0 常数，然后喂给使用数学常数 e 的方程的 z 值。原来 Y 总是会介于 0 和 1 之间。如果 Y 是小于 0.5，你得出结论的输出为 0，如果 Y 大于 0.5 你得出结论的输出是 1。

例如，假设选民是 32 岁，性别是男性（-1）和每年数以万计的美元收入是 48.0。 And suppose b0 = -9.0, b1 = 8.0, b2 = 5.0, and b3 = -5.0.然后 z = -9.0 + （8.0)(32) + (5.0)(-1) + (-5.0)(48.0) = 2.0，所以 Y = 1.0 / （1.0 + e ^-2.0) = 0.88。

因为 Y 大于 0.5，你就会发现选民将选出候选人 1 （"琼斯"）。但是 b 重量值来自哪里呢？训练 LR 分类是寻找 b 权重值的过程。这个想法是使用具有已知输出值的训练数据，然后找到的 b 值的集合，以便计算的输出值和已知的输出值之间的差异最小化。这是通常被称为数值优化的数学问题。

有大约十几个主要的优化算法在机器学习中使用。Logistic 回归分析分类培训，两个最常用的算法被称为迭代牛顿-拉夫逊法和 L BFGS。在这篇文章中，我提出了一种叫做多群优化算法（MSO）技术。MSO 是变异的粒子群优化算法（PSO）。一个虚粒子在 MSO，对应于一组 b 权重值的位置。一大群是以鸟的灵感等植绒群体行为的方式移动的粒子的集合。MSO 维护彼此在一起，而不是粒子群优化算法，它使用只是一群之间进行交互的几种蜂拥而至。

一个好的方法，请参见这篇文章将走向何方，并得到一个想法的 LR 跟美索是什么，是来看一看该演示程序中图 1。该演示程序的目标是使用 MSO 打造为一套综合的（以编程方式生成）数据预测 Y LR 模型。

图 1 Logistic 回归分析与多群优化算法在行动

该演示程序开始通过创建 10,000 的随机数据项目有五个预测变量（常常被称为特征在 ML 的术语）。每个特性值介于-10.0 和 + 10.0，Y 值，0 或 1，并在数据集的最后一列。特性值不对应于一个现实的问题。

10000 个元素数据集随机分成 8,000 项目训练集，用来创建 LR 模型和 2,000 项目拿测试集，用来训练后评价模型的准确性。该演示程序创建 LR 分类器，然后使用四个群，每个都有三个粒子来训练分类器。MSO 是一个迭代过程和迭代，maxEpochs，最大数目设置为 100。

演示显示找到的任何粒子每 10 世纪最好（最小）错误。培训完毕后，发现最佳权重是（4.09、 10.00、 8.43、 1.86、-9.27、 1.84)。使用这些重量，LR 模型的准确性计算训练数据（99.98%正确，这为 7,998 出的 8000）和测试数据（99.85%正确，这是 1,997，2000）。该模型与试验数据的准确性给你的表现如何，该模型会时提出了一种具有未知的新数据的粗糙近似的输出值。

这篇文章假设你有至少中级编程技能，但不会假设你知道任何有关 logistic 回归分析分类或多群优化算法。该演示程序编码使用 C# 中，但你不应该有太大的困难，到另一种语言（如 Visual Basic.NET 或者 Python 代码进行重构。

演示代码太长，在座的全部内容，但完整的源代码是本文附带的代码下载中提供。演示代码具有所有正常的错误检查已删除，以保持较小的代码的大小并尽可能清楚的主要思想。

程序的整体结构

程序的整体结构，与一些少量的编辑，以节省空间，提出了图 2。若要创建演示，我发起了 Visual Studio 并创建一个新 C# 控制台应用程序命名为 LogisticWithMulti。演示有没有重大的 Microsoft.NET 框架依赖关系，因此，任何新版本的 Visual Studio 会工作。

图 2 程序的整体结构

using System;
namespace LogisticWithMulti
{
  class LogisticMultiProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin demo");
      int numFeatures = 5;
      int numRows = 10000;
      int seed = 0;
      Console.WriteLine("Generating " + numRows +
        " artificial data items with " + numFeatures + " features");
      double[][] allData = MakeAllData(numFeatures, numRows, seed);
      Console.WriteLine("Done");
      Console.WriteLine("Creating train and test matrices");
      double[][] trainData;
      double[][] testData;
      MakeTrainTest(allData, 0.80, seed, out trainData, out testData);
      Console.WriteLine("Done");
      Console.WriteLine("Training data: ");
      ShowData(trainData, 4, 2, true);
      Console.WriteLine("Test data: ");
      ShowData(testData, 3, 2, true);
      Console.WriteLine("Creating Logistic Regression classifier");
      LogisticClassifier lc = new LogisticClassifier(numFeatures);
      int numSwarms = 4;
      int numParticles = 3;
      int maxEpochs = 100;
      Console.WriteLine("Setting numSwarms = " + numSwarms);
      Console.WriteLine("Setting numParticles = " + numParticles);
      Console.WriteLine("Setting maxEpochs = " + maxEpochs);
      Console.WriteLine("\nStarting training");
      double[] bestWeights = lc.Train(trainData, maxEpochs,
        numSwarms, numParticles);
      Console.WriteLine("Training complete");
      Console.WriteLine("Best weights found:");
      ShowVector(bestWeights, 4, true);
      double trainAcc = lc.Accuracy(trainData, bestWeights);
      Console.WriteLine("Accuracy on training data = " +
        trainAcc.ToString("F4"));
      double testAcc = lc.Accuracy(testData, bestWeights);
      Console.WriteLine("Accuracy on test data = " +
        testAcc.ToString("F4"));
      Console.WriteLine("End demo");
      Console.ReadLine();
    } // Main
    static double[][] MakeAllData(int numFeatures,
      int numRows, int seed) { . . }
    static void MakeTrainTest(double[][] allData, 
      double trainPct, int seed,
      out double[][] trainData, out double[][] testData) { . . }
    static void ShowData(double[][] data, int numRows,
      int decimals, bool indices) { . . }
    static void ShowVector(double[] vector, int decimals,
      bool newLine) { . . }
  } // Program
  public class LogisticClassifier { . . }
} // ns

模板代码加载到 Visual Studio 编辑器后，在解决方案资源管理器窗口中我将 Program.cs 文件重命名为更具描述性的 LogisticMultiProgram.cs，Visual Studio 将自动重命名类程序对我来说。顶部的源代码中，删除所有使用指向不需要命名空间的语句，留下只对顶级的 System 命名空间的引用。

程序类具有 MakeAllData 的帮助器方法，使TrainTest、 ShowData 和 ShowVector。所有 logistic 回归逻辑都包含在一个单独的 LogisticClassifier 类。LogisticClassifier 类包含嵌套的帮助器类粒子、群，并 MultiSwarm 封装的 MSO 数据和在训练过程中使用的逻辑。这些帮助程序类可能已经在 LogisticClassifier 类外定义。

Main 方法有很多 WriteLine 噪音。关键的调用语句都十分简单。合成数据已生成，像这样：

int numFeatures = 5;
int numRows = 10000;
int seed = 0; // Gives representative demo
double[][] allData = MakeAllData(numFeatures, numRows, seed);

方法 MakeAllData 创建随机 b 重量值之间-10.0 和 + 10.0，然后为每个数据项之间-10.0 和 + 10.0 的随机 x 值生成并结合的 b 重量值，然后用来生成 Y 值。合成数据对应于一个数据集，x 值已恢复至正常，那里有大致相当数量的 Y = 0 和 Y = 1 的值。

数据被划分为训练和测试设置这些语句：

double[][] trainData;
double[][] testData;
MakeTrainTest(allData, 0.80, seed, out trainData, out testData);

LR 模型是创建和培训这些语句：

LogisticClassifier lc = new LogisticClassifier(numFeatures);
int numSwarms = 4;
int numParticles = 3;
int maxEpochs = 100;
double[] bestWeights = lc.Train(trainData, 
  maxEpochs, numSwarms, numParticles);

并且该模型的精度计算与这两个语句：

double trainAcc = lc.Accuracy(trainData, bestWeights);
double testAcc = lc.Accuracy(testData, bestWeights);

理解 MSO 算法

这里是 MSO 优化高级别的伪代码中：

for-each swarm
  initialize each particle to a random position
end-for
for-each swarm
  for-each particle in swarm
    compute new velocity
    use new velocity to compute new position
    check if position is a new best
    does particle die?
    does particle move to different swarm?
  end-for
end-for
return best position found

MSO 算法的关键部分计算粒子的速度，是只是一组控件添加到一个粒子将搬哪里的值。例如，对于一个问题只是两个 x 尺寸，如果一个粒子处于 8.0 6.0）和速度 1.0-2.0），粒子的新职位将在 9.0 4.0）。

速度是经过计算的所以一个粒子倾向于移动在其当前的方向；倾向于走向它最好的位置，发现到目前为止；倾向于走向通过其任何成员同群；发现的最佳位置倾向于走向在任何群中发现的任何粒子的最佳位置。

在数学术语中，如果 x (t) 是一个粒子的位置在时间 t，然后一个新的速度，v(t+1) 被计算如下：

v(t+1) = w * v(t) +
         (c1 * r1) * (p(t) - x(t)) +
         (c2 * r2) * (s(t) - x(t)) +
         (c3 * r3) * (g(t) - x(t))

词 p(t) 是粒子的最著名的位置。术语 s (t) 是任何粒子的粒子群中的最佳位置。词 g(t) 是全局最优位置的任何粒子在任何群。术语 w 是一个常数，称为惯性因子。术语 c1、 c2 和 c3 是速度的建立新每个组件的最大变化的常数。术语 r1、 r2 和 r3 和介于 0 和 1 之间的随机值，提供每次更新时速度的随机效果。

假设一个粒子目前 30.0 20.0）和其流速是 1.0-3.0）。最著名的粒子的位置也 10.0 12.0），任何粒子群中最著名的立场是 9.0 8.0）和任何粒子中任何群的著名位置是 6.0 5.0）。并且假设常数 w 具有价值 0.7、常数 c1 和 c2 是两个 1.4 和恒定的 c3 是 0.4。最后，假定随机值 r1、 r2 和 r3 所有 0.2。

新（与舍入为一个十进制）粒子速度：

v(t+1) = 0.7 * (-1.0, -3.0) +
         (1.4 * 0.2) * ((10.0, 12.0) - (20.0, 30.0)) +
         (1.4 * 0.2) * ((8.0, 9.0) - (20.0, 30.0)) +
         (0.4 * 0.2) * ((5.0, 6.0) - (20.0, 30.0))
       = 0.7 * (-1.0, -3.0) +
         0.3 * (-10.0, -18.0) +
         0.3 * (-12.0, -21.0) +
         0.1 * (-15.0, -24.0)
       = (-8.8, -16.2)

于是，粒子的新位置是：

x(t+1) = (20.0, 30.0) + (-8.8, -16.2)
       = (11.2, 13.8)

在图图 3 MSO 过程进行了说明有两个 x 值的问题，三个群与五粒子，每个和场合的最佳位置是在（0，0）。图显示了如何在每个群中的第一个粒子关闭在最佳位置上。螺旋运动是 MSO 的特征。

图 3 所示的多群优化算法

在 MSO 的伪代码中，粒子可以死一些概率低的风险。当一个粒子死后时，它将被替换一种新的粒子在随机的位置。一个粒子就可移居一些概率低的风险。入境事务处时，粒子是已换用另一个粒子，从不同的群。死亡和移民机制向 MSO 添加元素的随机性和帮助防止陷入一个非最优解的算法。

使用 MSO 执行 Logistic 回归分析

方法火车的定义开始：

public double[] Train(double[][] trainData, int maxEpochs,
  int numSwarms, int numParticles)
{
  int dim = numFeatures + 1;
  double minX = -10.0;
  double maxX = 10.0;
  MultiSwarm ms = new MultiSwarm(numSwarms, numParticles, dim);
...

问题的维度是预测功能，加上一个，占 b0 常数的数目。变量这个混蛋和 maxX 举行一个粒子的位置数组中的任何单个值的最小和最大值。LogisticClassifier 类包含嵌套的 MultiSwarm 类。MultiSwarm 类的构造函数创建数组的数组的粒子对象，每一种最初有一个随机的位置和一个随机的速度。因为 logistic 回归分析误差的方法不是对嵌套的粒子定义直接可见的 MultiSwarm 的构造函数并不提供每个粒子的错误值，所以火车方法添加信息时出错。第一，每个粒子获取错误值：

for (int i = 0; i < numSwarms; ++i)
{
  for (int j = 0; j < numParticles; ++j)
  {
    Particle p = ms.swarms[i].particles[j];
    p.error = Error(trainData, p.position);
    p.bestError = p.error;
    Array.Copy(p.position, p.bestPosition, dim);
...

下一步，计算出了电流群最好和全球整体的最佳误差：

...
    if (p.error < ms.swarms[i].bestError) // Swarm best?
    {
      ms.swarms[i].bestError = p.error;
      Array.Copy(p.position, ms.swarms[i].bestPosition, dim);
    }
    if (p.error < ms.bestError) // Global best?
    {
      ms.bestError = p.error;
      Array.Copy(p.position, ms.bestPosition, dim);
    }
  } // j
} // i

主要培训回路没有做好准备，就像这样：

int epoch = 0;
double w = 0.729; // inertia
double c1 = 1.49445; // particle
double c2 = 1.49445; // swarm
double c3 = 0.3645; // multiswarm
double pDeath = 1.0 / maxEpochs;
double pImmigrate = 1.0 / maxEpochs;
int[] sequence = new int[numParticles];
for (int i = 0; i < sequence.Length; ++i)
  sequence[i] = i;

常数 w、 c1 和 c2 的值是一些粒子群优化算法研究的结果。有趣的是，与许多数值优化算法相比，粒子群优化算法和 MSO 是相对不敏感的用于内部的魔术常量（称为自由参数或超参数）的值。研究尚少可用的 c3 常数，影响粒子走向的最著名的位置，任何粒子到目前为止任何群中发现的趋势。使用时的值 0.3645，是价值的惯性时间常数，一半和我工作得很好在实践中。

序列数组保存的培训数据的指数。此数组将被搞乱，这样就可以在每个群粒子会处理以不同的顺序在每个循环迭代中主要的培训。

主要培训循环开始：

while (epoch < maxEpochs)
{
  ++epoch;
  // Optionally print best error here
  for (int i = 0; i < numSwarms; ++i) // Each swarm
  {
    Shuffle(sequence);
    for (int pj = 0; pj < numParticles; ++pj) // Each particle
    {
      int j = sequence[pj];
      Particle p = ms.swarms[i].particles[j];
...

知道何时停止训练是机器学习中最困难的挑战之一。在这里，使用固定，maxEpochs，迭代次数。这是一种简单的方法，但你不可能训练足够的风险。或者你可能太训练太多，会导致极其适合培训数据的模型，但作品很差在新的数据。这就被所谓过度拟合。有很多可以用来打击过度拟合的技术。

下一步，当前粒子的新速度计算，正如刚才解释（见图 4)。

图 4 新速度为当前的粒子被计算

for (int k = 0; k < dim; ++k)
{
  double r1 = rnd.NextDouble();
  double r2 = rnd.NextDouble();
  double r3 = rnd.NextDouble();
  p.velocity[k] = (w * p.velocity[k]) +
    (c1 * r1 * (p.bestPosition[k] - p.position[k])) +
    (c2 * r2 * (ms.swarms[i].bestPosition[k] - p.position[k])) +
    (c3 * r3 * (ms.bestPosition[k] - p.position[k]));
  if (p.velocity[k] < minX)
    p.velocity[k] = minX;
  else if (p.velocity[k] > maxX)
    p.velocity[k] = maxX;
} // k

计算出速度后，每个组件值检查看是否规模很大，如果如此，值勒住。这可以防止粒子移动很大的距离，在任何一次迭代中。对于一些毫升培训任务，消除速度约束似乎加速培训，但没有扎实的研究结果给任何具体的建议。

接下来，新的速度用来计算当前粒子的新位置和关联的错误：

for (int k = 0; k < dim; ++k)
{
  p.position[k] += p.velocity[k];
  if (p.position[k] < minX)
    p.position[k] = minX;
  else if (p.position[k] > maxX)
    p.position[k] = maxX;
}

当前的粒子具有移动后，其新的误差的计算方法：

p.error = Error(trainData, p.position); // Expensive
if (p.error < p.bestError) // New best position for particle?
{
  p.bestError = p.error;
  Array.Copy(p.position, p.bestPosition, dim);
}

当前粒子新错误可能最好是最好或全球的新群：

if (p.error < ms.swarms[i].bestError) // New best for swarm?
{
  ms.swarms[i].bestError = p.error;
  Array.Copy(p.position, ms.swarms[i].bestPosition, dim);
}
if (p.error < ms.bestError) // New global best?
{
  ms.bestError = p.error;
  Array.Copy(p.position, ms.bestPosition, dim);
}

当前的粒子具有移动后，选项是可能杀了那种粒子，并生成一个新。如果一个随机值是以下一些较小的阈值，则会生成一种新粒子：

double p1 = rnd.NextDouble();
if (p1 < pDeath)
{
  Particle q = new Particle(dim); // A replacement
  q.error = Error(trainData, q.position);
  Array.Copy(q.position, q.bestPosition, dim);
  q.bestError = q.error;

而不是死亡的死亡的使用一个固定的可能性，另一个方法是死亡的死亡的逐渐增加概率为例：

double pDeath = (maxProbDeath / maxEpochs) * epoch;

在创建替换粒子后，那种粒子可能，纯粹是靠运气，最好或全球的新群最好：

if (q.error < ms.swarms[i].bestError) // Best swarm error by pure luck?
{
  ms.swarms[i].bestError = q.error;
  Array.Copy(q.position, ms.swarms[i].bestPosition, dim);
  if (q.error < ms.bestError) // Best global error?
  {
    ms.bestError = q.error;
    Array.Copy(q.position, ms.bestPosition, dim);
  }
}

通过交换置换，有效杀死当前粒子的当前粒子监测死亡机制得出结论：

...
  ms.swarms[i].particles[j] = q;
} // Die

接下来，（可选）入境事务机制入手：

double p2 = rnd.NextDouble();
if (p2 < pImmigrate)
{
  int ii = rnd.Next(0, numSwarms); // rnd swarm
  int jj = rnd.Next(0, numParticles); // rnd particle
  Particle q = ms.swarms[ii].particles[jj]; // q points to other
  ms.swarms[i].particles[j] = q;
  ms.swarms[ii].particles[jj] = p; // the exchange
...

入境事务处机制是很粗鲁的。该代码选择一个随机的群然后从那一个随机粒子群，然后互换与当前的粒子的随机粒子。编码，是随机选的粒子将会在一大群不同于当前的粒子不能保证。

入境事务处机制完成通过检查在一个或两个新的群最佳位置，但是否交换两个群粒子造成：

...
  if (q.error < ms.swarms[i].bestError) // Curr has new position
  {
    ms.swarms[i].bestError = q.error;
    Array.Copy(q.position, ms.swarms[i].bestPosition, dim);
  }
  if (p.error < ms.swarms[ii].bestError) // Other has new position
  {
    ms.swarms[ii].bestError = p.error;
    Array.Copy(p.position, ms.swarms[ii].bestPosition, dim);
  }
} // Immigrate

方法火车最后返回发现任何粒子的最佳位置：

...
      } // j - each particle
    } // i - each swarm
  } // while
  return ms.bestPosition;
} // Train

返回值是对一个数组表示的 logistic 回归分析权重集的引用。一个轻微的替代方法，以减少不需要的可能性是副作用的将值复制到一个本地的数组并返回到本地的数组的引用。

总结

这篇文章和随附的代码应该得到你，然后运行如果您想要探索 logistic 回归分析分类多群优化算法用于训练。MSO 是真正的元启发式算法相比更多。我的意思是美索是一套可以在许多不同的方式实现的设计原则。有很多的修改，您可以调查基本的 MSO 设计。

Logistic 回归分析是机器学习分类最简单的形式之一。对于很多分类问题，LR 就不灵了。然而，很多毫升的从业人员，包括我在内，通常开始调查使用 LR，一个分类问题，然后使用更先进的技术，如有必要。

相比老、演算基于数值优化技术梯度下降法和 L BFGS，基于我的经验，培训使用 MSO 倾向于产生更好的 ML 模型，但 MSO 几乎总是慢一个数量级。

博士。 James McCaffrey 适合在雷德蒙的微软研究院他曾在几个 Microsoft 产品包括 Internet Explorer 和冰。博士。麦卡弗里也可以拨打 jammc@microsoft.com。

衷心感谢以下 Microsoft 技术专家对本文的审阅：托德 · 贝略和艾莉森溶胶

通过

测试运行

多粒子群优化的逻辑回归分类

程序的整体结构

理解 MSO 算法

使用 MSO 执行 Logistic 回归分析

总结

其他资源