摘要:针对历史灾害记录的描述性、简约性问题，提出一种基于蚁群聚类的历史灾害分级方法。利用灰色关联分析方法对灾害数据进行归一化处理后，再通过蚁群自动聚类的结果来划分历史灾害的等级，以避免人为的主观任意性干扰。通过与其他分级方法的性能对比，实验结果证明该方法具有较高的精确性和实用性。
关键词:历史灾害；分级；聚类；蚁群算法；灰色关联分析
中图分类号: TP311；TP18文献标志码:A
�
Historical disaster classification method based on ant colony clustering
�
JIA Zhi.juan�1�*, HU Ming.sheng�2, LIU Si�2
1. School of Computer Science and Technology, Wuhan University of Technology, Wuhan Hubei 430070, China�;�
2. Network Center, Zhengzhou Normal University, Zhengzhou Henan 450044, China
Abstract:
Aiming at the descriptiveness and parsimony problems of historical disaster records a historical disaster classification method which based on ant colony clustering is proposed in this paper. The disaster data are normalized by using gray relational analysis approach, and then the levels of historical disasters are divided by the results of ant colony automatic clustering, so as to avoid the arbitrary man-made interference. In comparison with other classification methods in performance, experimental results show that this method has high accuracy and practicality.Concerning the description and simplicity of historical disaster records, a historical disaster classification method based on ant colony clustering was proposed in this paper. The disaster data were normalized by using gray relational analytical approach, and then the levels of historical disasters were divided by the results of ant colony automatic clustering, so as to avoid the arbitrary man.made interference. In comparison with other classification methods in performance, the experimental results show that this method has higher precision and practicality.�Key words:
historical disaster; classification; clustering; ant colony algorithm; gray relational analysis
�
0 引言�
我国历史文化悠久，历代正史中都有关于灾害发生、危害情况的记载，形成了一个序列长、内容丰富的资料库，这些历史灾害信息对我们认识灾害、研究灾害和减轻灾害有着非常重要的参考价值，国内外灾害研究者都对此给予了高度评价。2011年5月国家减灾委发表了《国家自然灾害空间信息基础设施总体构思》主旨报告�［1］，进一步把历史灾害信息平台作为我国灾害空间信息系统建设的重要组成部分。�
然而由于古代科技水平的限制，长期以来灾害记录一直处于定性描述阶段，这使得对历史灾害信息的还原、提取、量化难度很大，基于现代翔实灾害记录的各类灾害分级方法因而难以套用于历史灾害记录。现代灾害记录中的各种灾害属性如伤亡人数、受灾面积、倒房数量、直接经济损失等作为灾害分级方法的重要依据，都有着客观准确的统计结果，量化程度很高，可比性较强；然而历史灾害记录的各项灾害属性则以描述性语言为主，并且存在大量属性值缺失，可比性较差。例如一条典型的洪涝灾害记录：“十二月戊戌，开封府陈留等六县水灾，诏免其田租”，仅包含了灾种，时间，地点，政府响应等信息，既未提及伤亡人数，也未提及倒房数量，而经常作为灾害分级关键属性的“直接经济损失”更无从得出，数据量化难度很高，这使得现有的一些历史灾害分级方法人为观念介入较多，难以令人信服，而基于现代灾害记录的分级方法�［2-5］则适应性较差，神经网络�［6］则因为其较强的逼近非线性函数的能力、模式识别能力以及分类能力，成为理论上较为适用的方法，但是由于历史灾害记录的特殊性，神经网络必须先通过专家人工分级的结果进行训练，依然无法摆脱对主观因素的依赖。�
鉴于此，本文尝试用另一种思路即先聚类再分级的方法来解决历史灾害分级问题，目前已有学者提出相关的模糊聚类�［7-8］、灰色聚类�［9-10］等灾害聚类分级方法，然而这些方法仍离不开人为的参数干预，如模糊聚类必须手动设置合适的�α�值，并且其应用背景都是灾害记录已经过高度量化的情况。因此本文提出一种蚁群聚类算法对历史灾害记录进行自动聚类，再根据聚类结果中各聚类中心的层次性完成分级，从而有效减免了灾害分级流程中的主观因素介入，并通过实验证明了本方法的有效性。�
1 蚁群聚类分级算法�
1.1 蚁群聚类思想�
历史灾害分级问题可以归结如下。1）分级标准问题。由于历史灾害记录以描述性为主，不可避免地加入了记录人的主观看法，因此对这些记录难以制定出较客观的分级标准，不同的历史专家对同一条记录也很可能根据各自的标准而产生不同的评级结果。而通过聚类可以不依赖于具体的分级标准，是一个很好的解决思路。2）数据量化问题。历史灾害记录叙述简约且无统一格式，这就要求既要提取出能体现灾害特征的关键信息，又要兼顾其他重要信息以补不足。3）批量处理问题。现有的一些分级方法都是基于小样本进行分析的，当样本量较大时其运算效率就会大大降低，而历史灾害记录浩如烟海，对其进行分级处理就必然要考虑到算法时效性问题。4）专家监督问题。在历史灾害数据自身系统性，表述性不足的情况下，历史专家的专业意见就显的格外重要，而且聚类结果本身也要获得历史专家的认可才有意义。但是由于历史灾害记录固有的主观性特点，专家与专家之间也存在着一定的分歧，这使得在分级过程中过多参入专家的意见又可能使所得出的分级结果成为“一家之言”，客观性不足，因此需要加以权衡，本文认为让专家的指导作用尽量体现在大方向上是一种较为理想的解决方式。�
聚类是指将物理或抽象的数据集合按有关特性的相似程度进行分组的过程。通过聚类可以使同一组中各数据的特性尽可能地相似，而不同组数据间的特性差异尽可能地大，灾害分级对等级内和等级间灾害数据的期望与聚类思想是一致的，可见灾害分级问题可以被视为一种层次聚类问题。�
自1991年蚁群算法�［11-12］提出以来，已在多个领域得到了广泛的应用，并衍生出了各种蚂蚁行为模型。孵化分类(brood sorting)是一种可以在许多种类的蚂蚁中观察到的行为，蚂蚁将卵和小幼虫紧密地排列成束并且放置在巢穴孵化区的中心，而最大的幼虫位于孵化束的外围。Deneubourg等�［13-15］提出了一个模拟这一现象的模型，其中蚂蚁根据周围物品的数量来收集或丢弃某个物品。例如，如果一只蚂蚁带有一个小卵，那它极有可能将其放置在排布了许多相同的卵的区域；相反，如果一只未携带任何物品的蚂蚁在一堆小卵中发现了一只大幼虫，那么它带走这只幼虫的概率非常大。在其他任何情况中，蚂蚁收集或丢弃物品的概率值都非常小。�
受上述模型的启发，本文提出了一种基于蚁群聚类行为的历史灾害分级算法。算法思想是先根据历史专家的意见，将历史灾害划分为“轻灾、中灾、重灾和特重灾”4个等级，即聚为4类，然后把历史灾害数据随机放到4个组中，通过令蚂蚁从一个组中选出一个数据再放入一个组，引导蚂蚁把初始混乱无章的各组整理成有序。算法中蚂蚁的各种行为仿照上述模型，是按概率进行的，如蚂蚁要选择某个组进行整理时，评价越混乱的组被蚂蚁整理的概率越大，然而蚂蚁并非一定会选择最混乱的组进行整理，这样可以很好地避免算法陷入局部最优，同时保证算法向较好的方向上收敛。与�K�.means聚类算法不同，蚁群聚类算法受初始聚类中心选取质量的影响不大，蚂蚁会根据各组混乱度自适应地对聚类中心进行调整，因而很适用于解决大批量问题，样本量越大，聚类中心层次性越强，蚂蚁聚类出的结果也越有意义。�
1.2 历史灾害信息提取�
通过对历史灾害记录的大量分析，并结合历史专家的意见，我们对灾害信息的各项特征进行了标准化编码，并归纳出以下4项属性来提取各条记录的灾害信息。�
1)“受灾范围”指灾害波及的地域，以县为单位，通过地理信息系统转化现代的县制大小，该项为灾害记录必有属性，具有较高的量化程度。�
2)“物情”包括对灾害的物态及影响描述，如“伤禾苗”、“水漂民居”、“决堤四十余丈”等。�
3)“民情”指对灾民生存情况的描述，如“民饥”、“溺死人畜”等。�
4)“政情”指对政府响应灾害情况的描述，如“诏免其租”、“祈祷雨泽”、“发仓赈济”等。�
后3项属性为可缺失属性，能有效涵盖住每条历史灾害记录的基本灾情信息。为了实现这3项属性的合理量化，先为各项属性分别编制出各自的特征区分码，再利用命名实体识别技术将历史灾害记录编入数据库。以“政情”属性为例，分为“无记录、祈祭、遣官、减租税粮、免租税粮和赈济”6级，分别编码为“0/1/2/3/4/5”，凡是在历史灾害记录中出现“诏免盐粮、诏免税粮、免粮、免征秋粮、免征田粮”等描述的都视为“免租税粮”，在“政情”属性部分统一记为“4”。需要注意的是，“0/1/2/3/4/5”这种递增方式可能并不符合实际灾情严重程度的上升幅度，因此还可能需要根据所得出的聚类结果和专家的评估意见对各等级所对应的编码进行适当的调整。�
至此将历史灾害分为4级，每条历史灾害数据有4项属性，属性值通过上述方法实现了初步量化，进而可以进行对历史灾害数据的聚类处理。在这里先默认这4项属性的权重是一样的，而在实际历史灾害聚类时，可以根据所得出的聚类结果和专家反馈的评估意见进行权值修正，以进一步保证聚类的质量，即着重于在灾害信息量化过程中借鉴和利用历史专家的专业意见，而在聚类过程中则尽量实现快速的自动化处理，以使专家的指导和监督作用更多地体现在大方向上。�
1.3 蚁群聚类算法描述�
�
算法描述如下，设灾害数据集合为S，每条灾害数据有p（此处p=4）个属性，首先将数据集S随机分配为k（此处k=4）个组，各组的灾害数据数量设为t�n（n∈［1,k］）。依次进行如下处理。�
1）数据预处理。�
因为大量的历史灾害记录都至少存在一项属性值缺失，0值较多，数据聚合性差，为了改善这一问题，利用灰色关联系数的定义，按照式（1）进行归一化处理。�
第n个灾害数据的第i个初始属性值设为x�ni，预处理后，变为y�ni:�
y�ni =1/(2-(x�ni-x�mini)/(x�maxi-x�mini))（1）
其中x�maxi，x�mini分别为灾害数据集合S中第i个属性的最大值和最小值。�
2)选择一个出数据组。�
蚂蚁按照式（2）评估各个灾害数据组的混乱度，用chaos�n （n∈［1,k］）来表示，chaos值越大表示此组越混乱，那么其被蚂蚁整理的概率也就越大。第n个组的混乱度表示为：�
chaos�n=∑t�ni=1(x�i－avg�n)�2t�n （2）
其中:x�i=∑pj=1y�2�j，表示第n组中第i条数据各属性的平方和；avg�n=(∑t�ni=1x�i)/t�n表示第n组各x�i的平均值；chaos�n表示第n组中各灾害数据属性平方和的标准差。�
然后蚂蚁根据各个组的chaos值采用赌轮选择法�［13］，选出一个出数据组。�
3)选出一个灾害数据。�
在选出的组中，蚂蚁按照式（3）评估其中每个灾害数据对该组的混乱度的影响，用influence来表示，influence值越大表示此灾害数据影响越大，那么蚂蚁把此数据从组中取出的概率也就越大。组中第i个数据的影响力表示为： �
influence�i=(x�i－avg�n)�2（3）
其中求得x�i，avg�n的方法与第2)步相同。�
然后蚂蚁就组中各个灾害数据的influence值采用赌轮选择法，选出一个数据。�
4)选择一个入数据组。�
蚂蚁按照式（4）评估所选出的灾害数据与各个组的拟合度，用similarity� n （n∈［1,k］）来表示，similarity值越大表示与该组拟合度越高，那么把该灾害数据放入对应组的概率就越大。与第n个组的拟合度表示为：�
similarity�n=1(x�i－avg�n)�2 （4）
其中求得x�i，avg�n的方法与第2)步相同。�
然后蚂蚁就各个组的similarity值采用赌轮选择法，选出一个数据入组。把选出的灾害数据放入此组中。�
5)选择蚂蚁。�
为了使算法收敛，需要使用一定数量的蚂蚁(�Agent�)，让它们分别进行2)～4)步，然后按照式（5）评估各个蚂蚁整理的质量，用fitness来表示， fitness值越大表示此蚂蚁整理的质量越高，采用fitness值最大的蚂蚁的整理方案来改变原聚类。第n只蚂蚁的整理质量表示为：�
fitness�n=1t�n*chaos�n（5）
其中:t�n为第n个组的大小，chaos�n为此组的混乱值。这些值都是蚂蚁整理后的值。�
6)算法收敛。�
循环蚂蚁的整理行为，当算法收敛时，蚂蚁选出的灾害数据会被一直放回到原组，灾害聚类结果不再发生变化。此时根据各组聚类中心的大小顺序把各组数据依次划分为“轻灾、中灾、重灾、特重灾”。�
�
1.4 蚁群聚类算法实现�
为了方便理解算法的实现流程，列出了蚂蚁的数据结构及算法流程伪代码。
定义蚂蚁的数据结构如下：
2 实例分析�
为了验证本文算法的性能，使用了神经网络和模糊聚类算法进行对比，测试数据来源于依托基金项目所建设的历史灾害数据库，并请来3位历史灾害专家对其中随机抽取的500条明代旱灾记录进行了人工评级，一方面用来判断本文算法的准确率;一方面用来作为进行性能比较的神经网络算法的训练及测试集。�
为了更好地实现对比，根据3位专家的评级结果分别训练了3个神经网络，并用每个神经网络分别对3位专家的评级结果进行了测试。实验结果如表1所示。利用与专家分级结果的匹配率来作为历史灾害分级准确率的参考，可以看到模糊聚类算法表现较差，各个神经网络则与各自所对应专家的评级结果匹配率很高，但是与非对应专家的评级结果匹配率则明显降低，这一方面反映出了神经网络对训练集的依赖性；另一方面体现出了专家评级的主观任意性。而蚁群聚类算法则表现出了比较稳定的性能，参考与专家匹配率可以认为具备了不错的准确率。各算法的运算效率比较如图1所示，可以看到蚁群聚类算法收敛很快，而神经网络算法则明显需要经过较高次数的训练，蚁群聚类算法的高时效性对于大样本量的历史灾害分级是非常关键的优势。�