元胞自动机
计 算 机 工 程 第 35 卷 第16期
Vol.35 No.16 Computer Engineering ·人工智能及识别技术·
文章编号:1000—3428(2009)16—0180—03
文献标识码:A
2009年8月
August 2009
中图分类号:TP311
基于元胞自动机的分布式数据挖掘分类器
杨明新,周莲英
(江苏大学计算机科学与通信工程学院,镇江 212013)
摘 要:针对常用分类方法分类精度较低和内存消耗较高的问题,设计一种基于多吸引子元胞自动机(MACA)的模式分类器tsPCM,把它应用于分布式数据挖掘。通过改变MACA的描述方法,用依赖串和依赖向量将分类过程设计成两阶段,用遗传算法优化设计。实验结果表明tsPCM具有较高的分类精度和较低的内存消耗,分类复杂度由O(n3) 降低到线性级O(n),具有较好的应用价值。 关键词:多吸引子元胞自动机;模式分类器;分布式数据挖掘
Classifier for Distributed Data Mining
Based on Cellular Automata
YANG Ming-xin, ZHOU Lian-ying
(School of Computer Science and Telecommunication Engineering, Jiangsu University, Zhenjiang 212013)
【Abstract】Owing to low classification accuracy and high memory overhead of the normal classifier, a Pattern Classifying Machine(PCM) namedtsPCM based on Multiple Attractor Cellular Automata(MACA) for Distributed Data Mining(DDM) is designed, by changing the characterization of aMACA to two stage with two linear operators of Dependency String(DS) and Dependency Vector(DV), and employing Genetic Algorithm(GA)formulation. Plentiful experimental results prove the potential of tsPCM. Its classification complexity is declined from O(n3) to O(n), and it has therespect to excellent classification accuracy and low memory overhead established the availability of the classifier to manipulate the distributed datamining.
【Key words】Multiple Attractor Cellular Automata(MACA); Pattern Classifying Machine(PCM); Distributed Data Mining(DDM)
分类是数据挖掘技术的常用方法,也是要解决的主要问题之一。本文提出一种基于多吸引子元胞自动机(Mutiple Attractor Cellular Automata, MACA)的模式分类器tsPCM,其原型是孟加拉工学院元胞自动机研究实验室设计的,在集中式数据挖掘领域得到应用,分类的计算复杂度为O(n3)[1]。本文所设计的tsPCM应用于分布式数据挖掘环境,通过改进MACA的分类过程,提高了分类器的分类性能。
胞自动机[3]。
如果包含n个元胞的CA的t时刻状态St可表示为一个 n个二进制位的a字符串,CA的下一状态St+1可以这样得到:St+1= T St。T是一个n×n的特征矩阵(依赖矩阵),可表示为
Tij=
j's present state
{10 next state of idepend on otherwise
1 元胞自动机基础
元胞自动机(Cellular Automata, CA)是由一定数量的元胞
组成的自治的有限状态机[2]。在三近邻依属关系中,一个元胞的下一状态Si(t+1)被假定只依赖于它自己当前的状态及左右2个邻居的状态,可表示为
Si(t+1)=f(Si 1(t),Si(t),Si+1(t))
如果第i个元胞的下一状态依赖于第j个元胞的当前时刻状态(i, j=1, 2, …, n),那么Tij是非0值,如果限制到三近邻的元胞依属关系,那么Tij仅仅在j=(i-1), i或(i+1)时取非0值,其他情况下,Tij的值取0,T称为三对角矩阵。它的特征多项式可通过计算det(T+Ix)得到[4]。
2 基于MACA的数据挖掘分类器tsPCM
2.1 多吸引子元胞自动机MACA
如果一个CA的状态转换图中的所有状态都存在于许多循环中,称之为有组织CA,反之,一个非组织CA的状态转换图循环和非循环状态共存,见图1。一个MACA的状态转换图包含一些循环和非循环状态。一组非循环状态以循环状态为根形成一些倒置树。这些循环态被称作吸引子。图1描
基金项目:国家“863”计划基金资助项目“分布式企业信息系统中的复杂授权机制研究”(2003AA414031);江苏省科技攻关计划基金资助项目“面向成套电气大型企业集团的数字化综合集成系统开发与应用”( BE2007071)
作者简介:杨明新(1982-),男,硕士研究生,主研方向:电子商务,系统集成;周莲英,教授
收稿日期:2009-01-28 E-mail:mx-sju1982@163.com
其中,Si(t)表示第i个元胞在t时刻的状态;‘f’是下一状态函
数,被看作是元胞的自动转换规则。‘f’是一个包含3个变量的函数,每个CA的元胞有28种,即256种可能的转换规则。这256种规则中仅包含如下7种逻辑异或规则:
Rule 60:Si (t+1)= Si-1 (t)⊕Si (t) Rule 90:Si (t+1)= Si-1 (t)⊕Si+1(t) Rule 102:Si (t+1)= Si (t)⊕Si+1 (t) Rule 150:Si (t+1)= Si-1 (t)⊕Si (t)⊕Si+1(t) Rule 170:Si (t+1)= Si+1(t) Rule 204:Si (t+1)=Si (t) Rule 240:Si (t+1)= Si-1 (t)
使用逻辑异或规则的CA称为线性元胞自动机。上文提到的MACA就是源于Wofram提出的二状态三近邻的线性元 ——180
针对常用分类方法分类精度较低和内存消耗较高的问题,设计一种基于多吸引子元胞自动机(MACA)的模式分类器tsPCM,把它应用于分布式数据挖掘。针对常用分类方法分类精度较...
基于元胞自动机的分布式水文模型研究 张文明1 潘文俊 1 王宏2 钱蔚3 (1.珠江水利科学研究院 广东 广州 510611;2.水利部珠江水利委员会 广东 广州 510611;3....
基于元胞自动机的分布式... 3页 1下载券 DMStar组-数据挖掘newsg... 24页...基于单层感知器 的数 据挖掘分类 的设 计和实现 王必强,硕本,学士 毕董( ...
基于空间数据挖掘的分区异步元胞自动机模型研究 - 第 15卷 第 6期 2010年 6月 中国图象图形学报 Journa l o f I age and G raphics m V o . ...
元胞自动机-计算材料_工学_高等教育_教育专区。自己...如分类,分级,以便于建立元胞自动机模型; (5)同步...(Multi-Agent System,简称MAS)是分布式人 工智能的...
5基于元胞自动机的分布式 元宝自动机元宝自动机隐藏>> 第五章 基于元胞自动机的 林火蔓延模拟 引线中央电视台关于美国和国内森林大火的 报道 美国相关机构进行林火...
搜索信息量更大的爬虫显得十分迫切.本文实现了一种基于多个分类器的分布式主题爬虫方法.实验结果表明,该爬虫的速度和精度均较为良好,特别适合于对大数据量的特定...
提出了将数据挖掘技术应用于元胞自动机( CA) 进行...分类与预测研究[ 9[ 8] 10] 2 元胞数据库定义...嵌入播放器: 普通尺寸(450*500pix) 较大尺寸(630*...
基于GIS的地理元胞自动机模拟框架及其应用_专业资料。...NET 开发而成, 可以 集成遥感和 GIS 数据以 及新...遥感分类 基准图 总体精度 K appa 系数 通过与遥感...
关键词: 元胞自动机; 时空数据模型; 土地使用决策; 电力负荷预测 中图分类号...国外目前主要集中在 扩展元胞自动机模型如何用于土地开发利用进行数 据挖掘方面的...
热门文档