利用基于局部梯度更新规则的伪元胞自动机进行数据挖掘
1、简介
分类是一种基于特征的监督机器学习分析数据的方法。分类算法对数据点进行分类，并常常根据这些分类做出决策。神经网络、K近邻、朴素贝叶斯算法和支持向量机是目前比较流行的数据分类技术。这些方法适用于各种领域的各种问题，包括文本分析，多媒体，社交网络和生物数据分析等。因此，这些方法是有价值的数据挖掘工具。
一种不常用于数据分类的技术是元胞自动机（也称细胞自动机）。元胞自动机模拟可以用于“grow”分类区域，当数据只能用复杂的非线性边界划分为分类时，这将会有很大的帮助。Fawcett在一篇文章中介绍了一种使用细胞自动机作为数据挖掘工具的简单形式，其中局部决策可以有效地定义特定二维数据集的总体分类。然而，这种元胞自动机的设计非常简单，当属于不同类的数据点之间没有非常清晰的分隔时，可能会导致不准确。此外，多吸引子细胞自动机(MACA)作为生物信息学问题的潜在分类器已引起人们的关注。这种方法依赖于遗传算法来创建一个状态系统，可以用来对数据进行分类。然而，这个过程涉及到许多具有大量基础理论的组件。论文提出了一种用于数据分类的伪元胞自动机方法，旨在弥补分类器精度、实际实现和理论复杂性之间的差距。
1.1元胞自动机
有许多方法可以构元胞自动机。然而，所有元胞自动机都遵循相同的基本原理：它们在空间和时间上都是离散的，它们在空间和时间上是同质的，并且它们在它们的相互作用中是局部的。可以在二维网格上进行简单形式的元胞自动机，网格中的每个“块”代表一个cell。cell通常表示为处于两种状态之一：死亡（“0”）或存活（“1”）。对于每个经过时间步，更新每个cell（0或1）的状态。细胞自动机的“同质”特性意味着对每个细胞应用相同的更新规则。此外，对于给定的时间步长，更新同时应用于所有cells。
给定cell的更新规则通常基于“相邻”cells的状态。相邻的cell是该cell的一定“半径”内的任何cell。此外，重要的是指定半径是仅沿cell格空间的轴应用还是可以对角地应用。这些规范分别被称为“冯·诺依曼邻域”和“摩尔邻域”。在二维中，最常用的邻域是radius-1 von Neumann邻域和radius-1 Moore邻域，如下图所示。
图2：冯·诺依曼邻域(左)和摩尔邻域(右)的图解
可以用来更好地解释更新规则和社区的一个流行的元胞自动机示例是Conway的生命游戏。此游戏使用radius-1 Moore邻域，并具有以下更新规则[6]：
康威的《生活游戏》(Game of Life)是细胞自动机的一个流行例子。这个游戏使用radius-1 Moore邻居与以下更新规则:
- 当一个cell 恰好有三个活的邻居时，它就“born”了(一个死cell 变成活cell )
- 如果活着的邻居少于两个，或者三个以上的邻居，活cell 会死亡
- 如果一个活着的cell 有两个或三个活着的邻居，它就会活着
建立一套像康威的《生命游戏》(Game of Life)中使用的规则，可以创建一组有趣的属性。此外，这些属性可能导致全局现象，这很有趣，因为单元格每次更新的规则仅依赖于局部条件。
图3：根据Conway的生命游戏规则更新到3×3网格的细胞的例子——黑cell是活的，白cell是死的
1.2元胞自动机的数学表示
为了更好地解释元胞自动机的规则及其产生的属性，一些数学定义是有用的。元胞自动机的定义如下:
d为维数，S为状态的有限集，N为更新规则中使用的m个邻域的向量，f为局部更新函数，生成形式的映射:
因此，在Conways Game的情况下，元胞自动机定义具有以下属性：
这是因为所使用的网格是二维的，唯一可能的状态是死（“0”）或活（“1”），并且在更新函数中考虑了八个相邻的单元。还应注意，全局转换函数可以定义为：
该函数是“main object of study”，用于定义整个单元空间的变化配置。
2、方法
在Python版本3.5.2中开发了一个模型。该模型的目的是首先重建由Fawcett引入的分类方法，然后将该方法扩展到cells不一定呈现离散状态而是状态混合的情况。因此，没有使用“真正的”元胞自动机，而是使用伪元胞自动机。将基于细胞自动机的分类方法扩展到n维情况也是一个主要目标。第二个目标是将分类器函数拟合到由模拟生成的类边界。
2.1数据集
从多元正态分布中随机抽取样本建立二维数据集。这是使用Numpy Python库的内置功能完成的。每个类的数据都是从高斯分布中提取的，该分布具有任意但唯一的均值向量和协方差矩阵。此外，每个类被指定具有相同数量的样本。
为了更好地与Fawcett方法进行比较，我们创建了另一个数据集。此数据集包含由边界分隔的两个类。下图显示了以这种方式生成的数据示例。
流行的Iris flower机器学习数据集是用于测试模型的最后一组数据。可以使用sklearn python库直接导入这组数据。之所以选择它，是因为它可以用于测试模型在4维(不可可视化)数据上的性能，并且易于导入和操作。
2.2定义Cell Space
构建此模型的第一步是确定如何将标准数据集映射到“Cell Space”。为此，开发了一个初始化函数，为数据的每个维度创建“bins”。预先指定每个维度的bins数，并且基于最大和最小数据值（加上一些额外的边距）的均匀间隔值被分配给每个bin。例如，假设二维（x，y）数据集中的所有点都落在x值x = 2和x = 4之间， y值落在y = -1和y = 3之间。这些数据点可以分为x方向的两个bins 和y方向的两个bins ，如下所示：
2.3初始化和更新规则
在建立cell分配之后，定义了元胞自动机的属性。为此，元胞自动机的传统特性被忽略了。这是由许多原因造成的。
对cell使用离散状态意味着每个cell专属于一个类。出于分类的目的，为每个cell定义两个属性是有意义的 - 第一个属性是“species”，它定义了细胞所属的类，第二个属性是“适应性（fitness）”，它定义了cell属于类的程度。那个班。以下符号将用于表示这些属性:
这里，第一组代表“species”，而第二组代表“适应性”。给定第二个属性，cells可以在cel空间上形成每个类的成员资格的“梯度”。这类似于模糊K均值算法中的“模糊性”，其中在每个类中引入“degrees”可以提高整体聚类性能。
这些属性用于为元胞自动机定义的更新规则。唯一更新规则:
用于初始化系统。为了开始模拟，cells以一种“摩尔式”的方式生长，利用同种cells之间的全局排斥原理。为了达到这种“排斥力”效应，使用了库仑定律。电荷所受总力的库仑定律如下式所示。
这里，k是常数。通过将cell i和cell j各自的适应度定义为两个charges，该想法可以应用于元胞自动机的初始化步骤。在这种情况下，常数k从等式中去掉，并且charge的位置被n维cell索引替换。最终的“排斥向量”也被归一化，因为它被用于方向性而不是幅度。有关两个cells的系统的初始化步骤示例如下图所示。该图还有助于可视化应用更新规则的“摩尔式”邻域。
重要的是要注意，应用此初始更新规则（以及所有后续更新规则），使得每个cell用于定义其邻域的状态，而不是由cell的邻居定义cell的状态。这种全局初始化规则的原因是确保所有cells都具有冯诺依曼邻域
图7：以二维方式应用的基于全局排斥的函数的示例。cell中较暗的颜色意味着更高的适应性。使用类似于库仑定律的形式计算“Force”向量。然后，在这些向量的方向上将cell的适应性提供给它们的摩尔邻域内的cell。
它们的配置方式非常适合标准更新步骤。标准更新步骤使用“局部”排斥规则，其中“排斥向量”的计算方法与“全局”初始化相同。然而，在标准更新步骤和初始化步骤之间存在一些差异。这些差异如下:
- 仅使用相邻cells来定义所应用的“排斥”向量
- 使用冯诺依曼邻域
- 应用梯度函数来确定传播到相邻cells的适应度
由于更高维度的摩尔邻域计算所需的计算量更大，因此使用冯诺依曼邻域。对于von Neumann情况，要考虑的邻居数是2d，其中“d”是维数。摩尔模拟需要考虑3 ^ d - 1个邻域，这对于大的“d”值而言在计算上要大得多。
应用的梯度确保在每组cells内形成“质心”，其中cells的适应度在该中心附近最高，而在类边界附近最低。这是基于冯·诺伊曼或摩尔邻域简单地growing cells的改进，因为它产生更“平滑”的边界以“保留”训练数据的形状，并且得到的“拟合”图类似于估计的概率分布。整个更新函数 - 涉及此梯度，局部排斥规则和冯诺依曼邻域 - 可以用以下方法定性地描述所讨论的cell的单个邻域:
这可以比解释更容易可视化。因此，下图用于在一个维度中显示此更新规则的效果：
图8：在一维上应用的局部梯度函数的示例。cell中较暗的颜色意味着更高的适应性。两个相邻cells之间的适合度差异用于定义两个cells两侧的适应度。
可以从下图中的全局视角观察以这种方式应用梯度的总体效果。
2.4Cell 冲突
当多个cells尝试填充网格上的空间时，将使用单独的函数来定义结果。该函数使给定物种的所有cells（包括可能已占据该空间的 cells）的适应性总计。然后，给予具有最大适应值的物种控制空间。得到的cell具有一个适应度值，即其物种的所有cells的总适应度减去试图占据该空间的其他物种的cells的总适应度。这可以描述如下:
重要的是要注意，如果所有竞争cells属于同一物种，则所得cell的适合度仅仅是它们各自适合度的总和。
2.5关于维度的说明
虽然这个过程在应用于二维数据时最容易可视化，但它可以扩展到任何n维特征空间。python模型专门设计用于迭代具有任意数量维度的cell空间以及这些维度内的任何大小的数据。这样，结果无法可视化，但任何数据点都可用于定位所属的bin并提取该bin的属性。
2.6在数据挖掘中的使用
这里应用的规则所产生的元胞自动机可以用于分类目的。通过对包含数据类的训练数据集使用不同的“species”cells进行模拟，可以绘制这些类之间的自然边界。元胞自动机的结果连同用于将数据集映射到cell空间的区间可用于开发训练集之外的数据点的类预测。这可以简单地通过确定哪个“species”被分配给对应于数据点落在其中的bins 的空间来完成。
此外，物种间的边界可以被提取出来，用于多项式的分类。
3、结果
为了确定这种分类方法的可行性，进行了几个实验。这些实验的目的是在给定不同数据大小的情况下，与其他细胞自动机相比，与其他分类方法相比，评估该方法作为分类器的性能。
3.1通过冯诺依曼和摩尔邻域对简单细胞生长的比较
使用“梯度”cell growth法和简单的冯·诺依曼和摩尔邻域生长法进行了并行模拟，以确定增加更新规则的复杂性是否有利于分类结果。在这种情况下，“简单”growth 意味着cell的种类由cell附近最常见的种类决定的。
所有试验使用300个数据点，从三个高斯分布中等量绘制。另外，使用20×20网格的cells，并进行100个growth 周期的模拟。下图显示了一个特定的模拟，其中“梯度”方法似乎表现出比简单cell growth更好的性能：
图11：模拟的具体示例，其中l论文提出的“梯度”方法从分类角度优于标准冯诺依曼和摩尔cell growth。每个类有100个数据点，20个20 grid of cells和100个growth 周期进行模拟。
从定性的角度来看，有几个因素表明“梯度”方法的性能更好。如图11和附录1所示，不同类别的数据之间的重叠导致简单的growth方法产生在其类别的“边界”之外的cells。对于“梯度”方法也是如此，但程度要小得多。另外，可以看出，“梯度”方法产生更平滑的边界，这对于分类而言似乎更优化并且更适合于将分类函数拟合到所得到的cell边界。
3.2随着数据量的增加，精度得到提高
与大多数分类方法的情况一样，作为分类器的元胞自动机的性能随着训练集中的观察数量的增加而提高。为了显示训练集大小对元胞自动机分类器性能的影响，数据是从矩形空间中随机抽取的，其中y>x²表示数据点属于“绿色”类，y <x²表示数据点属于如图4所示的“红色”类。对训练集中的10,50,100和1000个数据点进行了模拟。
图12：尝试grow 抛物线分类器的结果。对于随机选择的数据(每个类中的数据点数量不一定相等)，图中对应的起始数据点数量如下(两个类之间):10(左上)、50(右上)、100(左下)、1000(右下)
这种观察到的性能改进是值得注意的，因为当使用大型数据集训练模型时，类之间的边界几乎是实际类边界的完美再现。显然，对于一组训练数据，1000个数据点是过多的。然而，从上面的图像可以看出，即使对于非常少量的可用输入数据，该方法也产生合理形状的cell边界。随着训练数据量的增加，精确度的提高是显着的，如第三幅图所示，其显示了非常精确的cell边界，仅在两类之间总共有100次观察。
3.3Iris Flower数据集的预测
众所周知的Iris Flower机器学习数据集用于测试模型对多维数据进行分类的能力。Iris数据集包含具有四个特征向量的观测值。使用sklearn python库导入一组Iris Flower数据。该数据包含150个样本，均匀分为3个类。为了测试该模型的有效性，使用不同大小的该数据的子集训练元胞自动机，然后用于预测剩余数据的类别。这两个数据子集将被称为“训练数据”和“测试数据”。
sklearn库还包含支持向量机（SVM）和决策树模型的内置功能。利用这种内置功能将这些模型的准确性与本文中提出的元胞自动机模型进行比较。SVM和决策树模型使用相同的“训练数据”集训练，然后使用与元胞自动机模型相同的“测试数据”集进行测试。对于Iris数据集的随机子集的这些模拟结果可以在下表中看到：
图13：利用50次迭代和12×12×12×12的cell空间对虹膜花数据集的随机子集进行分类的结果。SVM准确度和决策树准确性通过内置的sklearn功能确定。这些方法的准确性是在0到1的范围内测量的。
使用12×12×12×12大小的cell空间和50个growth 周期进行元胞自动机方法（上图中缩写为CA）。可以看出，由于训练集的小尺寸，该方法的准确性在第一次试验中非常低。然而，在随后的试验中，元胞自动机方法的准确性与SVM和决策树方法的准确性相当。鉴于sklearn库包含这些方法的优化和准确的实现，这是一项值得注意的成就。
另外，应该注意的是，训练数据大小的增加不是提高元胞自动机方法准确性的唯一方法。增加cell空间的大小和growth周期的数量也可以产生非常积极的影响。为了证明这一点，运行单个模拟训练数据大小为15，测试数据大小为135，具有20×20×20×20大小的cell空间和100个growth周期。结果是精确度提高了0.942。对于相同的数据集，SVM和决策树方法分别达到0.958和0.942的准确度。这表明，通过增加用于元胞自动机的cell和周期的数量，可以弥补创建具有少量训练数据的分类器的困难。然而，值得注意的是，准确度度的提高伴随着计算时间的大幅增加。这个更大的模拟需要花费一小时十分钟才能完成（在intel core i7处理器和8 GB RAM的Windows 8机器上）。
3.4Moving Forward
研究表明，元胞自动机方法可以较准确地对数据进行分类。然而，关于这个主题还有很多可以探索的地方。该模型中使用的“适应度”参数可以通过归一化每个物种的适应度来创建每个类的概率分布估计值，从而使cell空间在每个cell索引处包含0到1之间的值。
此外，第2.5节中简要提到的将函数拟合到最终cell边界的方法可用于深入了解被分类数据的性质。如果正确地实现用于确定函数项的方法，则由该模型产生的cell边界可以用于以数学术语定义的分类器，而不仅仅用于cell空间中的“bin”值。
4、结论
python编程语言实现了一种使用元胞自动机来“grow”类边界的分类方法。通过将模拟结果与其他元胞自动机和其他数据挖掘方法的结果进行比较，评价了该方法的可行性。很明显，考虑到这种简单实现的相对准确性，以及进一步分析结果单元边界和cell拟合的潜力，这种方法是有潜力的。这种方法的效率有待提高。但是，通过设计将计算次数限制为仅需要的函数并以一种能够实现快速矩阵乘法等方法来执行许多计算的方法来构建模型，可以大大加快代码的速度，更有效的步骤。该模型目前是一种方法的良好起点，可以进行更深入的研究。
附录1 元胞自动机方法比较