刘强（1979－）
男，辽宁工业大学研究生，（辽宁工业大学信息科学与工程学院，辽宁  锦州  121001 ）,研究方向为智能控制。

摘要：论文基于免疫网络理论和克隆选择原理，建立了一种人工免疫数据聚类分析算法，并详细阐述了聚类算法在城市交通时段自动划分中的具体应用。实例分析表明，该算法可以有效减少聚类数据的冗余信息，特别适合于解决分级聚类等传统方法不适应的大数据量聚类问题，对解决城市交通时段的自动划分等数据聚类问题是可行的和有效的。

关键词：聚类；人工免疫系统；模式识别；交通控制

Abstract: An artificial immune algorithm for data clustering is proposed in this paper. This work is mainly based on the immune network theory and the clone selection principle extracted from vertebrate immune systems. Experiments show that the given clustering algorithm can effectively reduce the redundant information of data, and thus, especially fit to the mass data clustering applications where hierarchical clustering algorithm or other traditional clustering algorithms may be ineffective.

Key words: clustering；artificial immune system；pattern recognition；traffic signal control

1 引言

    目前城市交通信号控制应用较为普遍的是多时段定时控制方案。多时段定时控制(time of day，TOD)是根据车流量等交通信息把一天划分为若干个时间段，不同的时段采用不同的信号优化控制方案。TOD控制的前提是交通时段的合理划分。传统上，交通工程技术人员根据收集到的交通流量，绘制流量时间曲线图，根据曲线的特征人工划分交通时段。传统方法具有很大的主观性，极易产生不合理的时段划分，难以满足现代城市交通模式快速变化的需求。

    以生物免疫系统为基础的人工免疫系统(artificial immune systems, AIS) [1]已成为目前国内外计算智能领域一个新的研究热点。本文在详细研究生物免疫学和AIS的最新研究成果的基础上，建立了一种人工免疫数据聚类分析算法，该算法可以有效减少聚类数据的冗余信息，特别适合于解决分级聚类等传统聚类方法不适应的大数据量聚类问题。论文把建立的人工免疫算法用于城市交通时段的自动划分[2]，克服了人工时段划分的不合理性，为TOD交通时段的划分及城市交通控制方案的制定提供了一条新的思路[3]。

2 免疫系统的基本理论

    生物免疫系统是一个由细胞、分子和器官组成的复杂系统，其主要功能是限制异物对肌体的侵害[4]。免疫系统抵御外部入侵，使其机体免受病原侵害的应答反应称为免疫(immunity)。外部有害病原入侵机体并激活免疫细胞，诱导其发生反应的过程称为免疫应答。诱导免疫系统产生免疫应答的物质称为抗原(antigen,简称Ag)，能与抗原进行特异性结合的免疫细胞称为抗体(antibody, 简称Ab)。抗原与抗体的结合强度用亲和度（affinity）度量。AIS主要涉及T细胞和B细胞的相关免疫特性。B细胞的作用是识别抗原和分泌抗体，T细胞能够促进和抑制B细胞的产生与分化。免疫系统的结构示意如图1所示。生物免疫学的研究成果是AIS的理论基础。本文给出的数据聚类算法，主要基于生物免疫隐喻的克隆选择理论[5]和免疫网络理论[6]。当淋巴细胞实现对抗原的识别，即抗体与抗原的亲和度(affinity)超过一定阈值后，B细胞被激活并增殖复制产生细胞克隆。由于遗传和免疫细胞在增殖中的基因突变，形成了免疫细胞的多样性。当每一种抗原侵入机体后都能在机体内选择出能识别和消灭相应抗原的免疫细胞克隆，使之激活、分化和增殖，进行免疫应答以最终清除抗原。克隆选择的主要特征是免疫细胞在抗原刺激下产生克隆扩增，随后通过遗传变异分化为多样性效应细胞和记忆细胞。

图1   免疫系统的基本结构

    把上述96个平均交通流量作为抗原应用于3节的人工免疫聚类算法，进行免疫识别和记忆。算法中的参数设置如下：初始化抗体个数N=20；最佳抗体选择率opR=20%；克隆乘数因子α =1；再次选择率rsR=20%，wsR=10%；最大迭代次数NA=15；为保证抗体的多样性，σd取0.001，σs为0.05。表1是交通流数据的人工免疫计算过程，共分15代。

    表1   聚类数据的人工免疫计算过程：

图3   交通流记忆细胞集的聚类谱系图

5 结束语

    人工免疫数据聚类算法可以有效减少聚类数据的冗余信息，特别适合于解决分级聚类等传统方法不适应的大数据量聚类问题。作者把建立的人工免疫聚类算法应用于城市交通时段的自动划分，克服了人工时段划分的不合理性。合理设置参数的取值范围可以满足不同聚类问题的需要。

其它作者：

    王艳秋（1955-），女，教授，辽宁工业大学信息科学与工程学院院长，博士，硕士研究生导师，研究方向：近代交流调速系统；智能控制。
张健（1981- ），男，辽宁工业大学研究生，研究方向：智能控制。

参考文献

    [1]肖人彬, 王磊.人工免疫系统:原理、模型、分析及展望[J]. 计算机学报, 2002, 25 (12) : 1282 - 1291. 

    [2]HAUSER T, SCHERER W. Data mining tools for real time traffic signal decision support and maintenance[C]//Proc of IEEE Int Conf on Systems, Man, and Cybernetics. Tucson, USA: IEEE Press, 2001:1471-1477.

    [3]PARK.B, LEE Do-Hoon, YUN Hsoo. Enhancement of Time of Day Based Traffic Signal Control [C]// Proc of IEEE Int Conf on Systems, Man, and Cybernetics. USA: IEEE Press, 2003:3619 - 3624.

    [4]林学颜, 张玲. 现代细胞与分子免疫学[M].北京:科学出版社, 1999:46-62. 

    [5]CASTROL, ZUBENF. An evolutionary immune network for data clustering[C]// Proc of the Sixth Brazilian Symposium on Neural Networks. Janeiro: IEEE Press, 2000: 84-89.

    [6]DASGU PTAD, FORRESTS. Artificial immune systems in industrial applications[C]//Proc of Second In t Conf on Intelligent Processing and Manufacturing of Materials. Honolulu, USA: IEEE Press, 1999: 257-267.

    [7]Dasnupta D. Artificial Immune Systems and Their Applications[M].New York: Sprinner~Verlan, 1999.

    [8]TIMM IS J, N EAL M. Artificial immune systems for data analysis [J]. B io System s, 2000, 55 (2): 143 - 150.

    [9]D. K. Merchant, G. L. Nemhauser. Optimality conditions for a dynamic traffic assignment model [J]. Transportation Science B, 1978, 12: 200-207.