论文部分内容阅读
摘 要 通过识别一组代表点来聚类数据对于探测数据模式是非常重要的，随机抽取数据点集合后反复修正可以找到这些代表点。传统的聚类算法存在聚类速度慢、效果差的问题，Frey与Dueck在Science发表的仿射传播（Affinity propagation，簡称AP）算法对数据聚类的误差要小于其它方法，并且所用时间较短。本文将分析和对比K-means、AP算法两种聚类算法，并利用AP算法分析航空公司运营的国内城市航空便利性问题，城市的相似值用国内43个城市营运机场之间航班预估时间负值标记。
关键词 聚类；仿射传播算法；K-means算法；航线
中图分类号：TP391.41 文献标识码：A 文章编号：1671—7597（2013）051-072-03
航空公司的航线网络对其盈利能力、运行效率和客户服务质量有着重要的影响。近些年，国内航空业务增长性趋势明显，各航空公司不断加强航线的拓展和航空枢纽的建设，航线网络越趋复杂，目前国内对航线网络的研究相对落后，缺乏对航线网络运行数据的定量分析，在航线的制定、评估和设计上仍以粗放的感性认识和经验判断为主。因此，以市场需求以及航空公司的机队规模、运力为参考，合理布局航线网络尤为重要。本文仅以航空公司生产排班计划为基础，采用先进的聚类算法，对城市航空便利性进行初步的探讨和分析。
1 聚类算法
聚类（Clustering）是指根据“物以类聚”的原理，将本身没有类别的数据聚集成不同的组，聚集后的一组数据对象称为类（Cluster），其结果需满足同一个类内的数据对象之间高度相似，并且不同类之间的数据对象有较高的差异性。
聚类分析的算法可以分为：划分法（Partitioning Methods）、层次法（Hierarchical Methods）、基于密度的方法（density-based methods）、基于网格的方法（grid-based methods）、基于模型的方法（Model-Based Methods）。
经典的K-means和K-centers都是划分法。
1.1 K-means算法
由于该算法的计算复杂度是O（nkt），其中n是对象的总数，k是预期结果聚类中心的个数，t是迭代的次数，通常k< 1.2 AP算法
Affinity Propagation （AP） 算法是Brendan J. Frey和Delbert Dueck在Science杂志上提出的一种新的聚类算法。与k-means算法不同的是，AP算法无需事先设定k值，其核心思路是根据n个数据点之间的相似度进行聚类，数据点间的相似度既可以是对称的，也可以是不对称的，如在本文后续描述中的城市对间的距离（航班时间）就是不对称的。这些相似度组成n×n的相似度矩阵S。AP算法将所有的数据点都作为潜在的聚类中心，称之为exemplar，因此不需要事先指定聚类数目，而需要为每个点设置个实数值s（k，k），该值也被称作参考度p （preference），s（k，k）值较大的点更有可能选为中心点。中心点的数量受preference影响。若已知所有的点被选为中心点的概率相同，则可将所有点的preference设置为相同的值（不同的值可能会导致不同的聚类数量），该值可以为所有相似度的中值或者最小值。AP算法通过吸引度r （responsiility）和归属度a（availability）控制算法的收敛。r（i，k）是从点i发送到点k的数值消息，反映的是k点对i点的吸引程度。a（i，k）则从点k发送到点i的数值消息，反映的是i点对k点的归属程度。r（i，k）与a（i，k）越强，代表k点成为聚类中心的机会就越大，同时i点隶属于以k点为聚类中心的聚类的机会也越大。该算法就是通过不断的迭代过程来更新数据点之间的吸引度和归属度，逐步精炼产生m个高质量的聚类中心，同时将其余的数据点归类给这m个聚类中心，形成以这m个聚类中心为中心的聚类。
基于来自邻居的正的响应度来评价k是否适于作中心点。
3 结束语
本文利用AP聚类算法对国航通航的国内43个城市航空便利性进行聚类分析，实验结果较客观的反映出各城市航空便利性的真实情况，进一步的研究分析可以考虑覆盖国内所有通航城市，并通过引入航班实际飞行时间数据以及调整s（i，i）值优化算法，提高算法的精确性。另外，也可通过采集和分析城市GDP数据、城市流动人口数据、客座率、航班生产成本数据、收入数据等，辅助航空公司航线分析与优化。
参考文献
[1]FREY B J，DUECK D.Clustering by passing messages between data point[J].Science，2007，315（5814）：972-976.
[2]王开军，张军英，李丹，等.自适应仿射传播聚类[J].自动化学报，2007，33（12）：1242-1246. [3]董俊，王锁萍，熊范纶.可变相似性度量的近邻传播聚类[J].电子与信息学报，2010，32（3）：509-514.
作者简介
郑志敏（1980-），男，浙江温州人，主要从事信息技术研究和企业信息系统的开发。
徐青（1979-），男，浙江杭州人，主要从事信息技术研究和企业信息系统的开发。
关键词 聚类；仿射传播算法；K-means算法；航线
中图分类号：TP391.41 文献标识码：A 文章编号：1671—7597（2013）051-072-03
航空公司的航线网络对其盈利能力、运行效率和客户服务质量有着重要的影响。近些年，国内航空业务增长性趋势明显，各航空公司不断加强航线的拓展和航空枢纽的建设，航线网络越趋复杂，目前国内对航线网络的研究相对落后，缺乏对航线网络运行数据的定量分析，在航线的制定、评估和设计上仍以粗放的感性认识和经验判断为主。因此，以市场需求以及航空公司的机队规模、运力为参考，合理布局航线网络尤为重要。本文仅以航空公司生产排班计划为基础，采用先进的聚类算法，对城市航空便利性进行初步的探讨和分析。
1 聚类算法
聚类（Clustering）是指根据“物以类聚”的原理，将本身没有类别的数据聚集成不同的组，聚集后的一组数据对象称为类（Cluster），其结果需满足同一个类内的数据对象之间高度相似，并且不同类之间的数据对象有较高的差异性。
聚类分析的算法可以分为：划分法（Partitioning Methods）、层次法（Hierarchical Methods）、基于密度的方法（density-based methods）、基于网格的方法（grid-based methods）、基于模型的方法（Model-Based Methods）。
经典的K-means和K-centers都是划分法。
1.1 K-means算法
由于该算法的计算复杂度是O（nkt），其中n是对象的总数，k是预期结果聚类中心的个数，t是迭代的次数，通常k<
Affinity Propagation （AP） 算法是Brendan J. Frey和Delbert Dueck在Science杂志上提出的一种新的聚类算法。与k-means算法不同的是，AP算法无需事先设定k值，其核心思路是根据n个数据点之间的相似度进行聚类，数据点间的相似度既可以是对称的，也可以是不对称的，如在本文后续描述中的城市对间的距离（航班时间）就是不对称的。这些相似度组成n×n的相似度矩阵S。AP算法将所有的数据点都作为潜在的聚类中心，称之为exemplar，因此不需要事先指定聚类数目，而需要为每个点设置个实数值s（k，k），该值也被称作参考度p （preference），s（k，k）值较大的点更有可能选为中心点。中心点的数量受preference影响。若已知所有的点被选为中心点的概率相同，则可将所有点的preference设置为相同的值（不同的值可能会导致不同的聚类数量），该值可以为所有相似度的中值或者最小值。AP算法通过吸引度r （responsiility）和归属度a（availability）控制算法的收敛。r（i，k）是从点i发送到点k的数值消息，反映的是k点对i点的吸引程度。a（i，k）则从点k发送到点i的数值消息，反映的是i点对k点的归属程度。r（i，k）与a（i，k）越强，代表k点成为聚类中心的机会就越大，同时i点隶属于以k点为聚类中心的聚类的机会也越大。该算法就是通过不断的迭代过程来更新数据点之间的吸引度和归属度，逐步精炼产生m个高质量的聚类中心，同时将其余的数据点归类给这m个聚类中心，形成以这m个聚类中心为中心的聚类。
基于来自邻居的正的响应度来评价k是否适于作中心点。
3 结束语
本文利用AP聚类算法对国航通航的国内43个城市航空便利性进行聚类分析，实验结果较客观的反映出各城市航空便利性的真实情况，进一步的研究分析可以考虑覆盖国内所有通航城市，并通过引入航班实际飞行时间数据以及调整s（i，i）值优化算法，提高算法的精确性。另外，也可通过采集和分析城市GDP数据、城市流动人口数据、客座率、航班生产成本数据、收入数据等，辅助航空公司航线分析与优化。
参考文献
[1]FREY B J，DUECK D.Clustering by passing messages between data point[J].Science，2007，315（5814）：972-976.
[2]王开军，张军英，李丹，等.自适应仿射传播聚类[J].自动化学报，2007，33（12）：1242-1246. [3]董俊，王锁萍，熊范纶.可变相似性度量的近邻传播聚类[J].电子与信息学报，2010，32（3）：509-514.
作者简介
郑志敏（1980-），男，浙江温州人，主要从事信息技术研究和企业信息系统的开发。
徐青（1979-），男，浙江杭州人，主要从事信息技术研究和企业信息系统的开发。