数据挖掘中的聚类算法的研究

山东科技大学 王子墨

数据挖掘中的聚类算法的研究

山东科技大学 王子墨

本文主要研究了据挖掘中的聚类算法，利用密度以及均匀抽样方法来缩减数据规模，从而提高了聚类的运行效率；并将粒子群算法与及模拟退火算法相结合，在原有算法的基础上进行改进进而获取更佳的初始中心；进一步将算法应用到和真实数据集，例证了本文方法的正确性和有效性，并进行对比，证明新算法的高效性，也进一步证明了新算法的正确性，对以后的研究起到了正确的指引作用。

聚类算法；粒子群算法；模拟退火法；数据挖掘

聚类分析近些年来被广泛运用到客户划分领域，对客户群体的划分，从客户的购买行为、浏览记录等属性划分为不同的客户群体。本文以数据抽样为核心，比较分析了现存抽样算法性能的优劣，同时研究抽样技术在海量数据聚类分析中的应用，结合密度以及均匀抽样方法来缩减数据量为了减少K-means 算法对初始聚类中心的依赖性和敏感性，对K-means算法初始聚类中心的优化选择进行理论研究。提出基于自然选择和基于模拟退火的粒子群算法来选取更佳的初始中心。针对K-means算法在实际应用中算法存在的不足，结合三角不等式来减少迭代次数，提高运算效率并提出改进算法，使新算法具有更好的全局收敛,并将其应用到实际问题中，从而证明新算法的实用性。

根据以上主要内容，拟解决的关键技术是对大数据抽样和K-means算法进行理论研究，通过对国内外关于聚类分析的研究文献，对大数据抽样和K-means算法的理论成果做进一步的总结。针对大多数聚类算法在面对海量高维数据所表现的不足以及K-means算法初始中心选取的随机性，利用抽样缩减数据量后，结合粒子群算法，提出改进算法，最后对人工数据集和真实数据集进行挖掘，并将其应用到实际问题中，从而证明新算法的实用性。

从航空公司系统内的客户基本信息、乘机信息以及积分信息等详细数据，根据末次飞行日期，抽取2006年4月1日至2008年4月1日内所有乘客的详细数据，总共16382条记录，63个属性其中包含了如卡号、入会时间、性别、年龄、会员卡级别、工作地城市、工作地所在省份、工作地所在国家、观测窗口结束时间、观测窗口乘积积分、飞行公里数、飞行次数、飞行时间、乘机时间间隔、平均折扣率等。对数据预处理的过程主要包括数据清洗、数据选择以及数据转换等操作。首先对数据进行缺失值分析与异常值分析。由于原始数据量大，而空缺值所占比例较小，对该问题影响不大，因此对其进行丢弃处理；由于原始数据中属性过多，根据航空公司客户价值相关属性，删除与其不相关、弱相关或冗余的属性。例如：卡号、性别、工作地城市、工作地所在省份、年龄等属性；最后根据方法进行属性约简，简化为5个属性指标，给定样本的数据特点，从已知的样本属性中提炼出L、R、F、M、C五个指标作为航空公司客户细分的参数。L代表客户关系长度（会员入会时间距观测窗口结束的月数），R代表客户最近一次消费距今时间长度，F代表客户在观测时间内的消费频率，M代表客户在观测时间内的飞行里程，C代表客户在观测时间内所乘航班的平均舱位折扣系数五个属性维。

由于原始数据中并没有直接给出L、R、F、M、C五个指标，需要通过原始数据来提取这五个指标，具体计算方法如下：

（1）L=LOAD_TIME-FFP_DATE

会员入会时间距观测窗口结束的月数=观测窗口结束时间-入会时间

（2）R=DAYS_FROM_LAST_TO_END

客户最近一次消费距今时间长度=最后一次乘机时间至观测窗口末端时长

（3）F=FLIGHT_COUNT

客户在观测时间内的消费频率=飞行次数

（4）M=SEG_KM_SUM

客户在观测时间内的飞行里程=观测窗口总飞行公里数

（5）C=AVG_DISCOUNT

客户在观测时间内所乘航班的平均舱位折扣系数=平均折扣率

待分析的客户数据被整理成如表所示。这样每一条客户数据就被表示成由五个特征属性组成的向量

根据聚类结果进行分析如下，第1类客户入会时长（L）长、平均折扣率（C）较高但是乘坐的次数（F）少、飞行里程（M）较短。这类客户是否在本航空公司消费的不确定性较大，可能是对本航空公司没有较为全面的认知，无所谓选择哪个航空公司，所以维持与此类客户的互动尤为重要，航空公司需要定期向此类客户普及本公司较其他公司的优势，针对他们不定期的推出系列优惠，增加此类客户选择本公司的次数。

第2类客户飞行里程（M）长、最近乘坐过本公司航班（R）少。这类客户要么不选择本公司，要选择的话必定会给公司带来较大的利益，是较为理想的消费群体，因此航空公司要考虑将精力放在他们身上，一对一联系此类客户，了解他们不满意的地方，及时改进，给他们更好的乘机体验，提高其满意度，客户自然会在以后的出行时选择本公司，持续给公司带来较高的利益。

第3类客户和第4类客户的平均折扣率（C）较高、最近乘坐过本公司航班（R）少、但飞行里程（M）较短或乘坐的次数（F）少。这类客户需要航空公司发掘其潜在价值，提高其满意度，使得此类客户再次或者多次选择本公司。

第5类客户的最近乘坐过本公司航班（R）少、里程（M）较短、乘坐的次数（F）少。这类客户是航空公司的一般客户或低价值客户，可能是在航空公司打折促销时才会乘坐该公司的航班。所以公司最好掌握此类客户的最新信息，在出行率较高的时期，错开乘机高峰时段推出优惠力度较大的航班，通过短信或者公众号的方式告知此类客户。

两种不同算法的收敛性比较情况如图，从图中可以看出本文改进的聚类算法比k-means算法具有更快的收敛速度。

以对航空客户数据进行客户细分为主要内容，将基于优化初始聚类中心的加权k-means算法与传统k-means算法均应用到航空公司客户细分上，通过数值实验结果，分析了客户细分的实验结果，对聚类产生的客户类型进行了解释，说明了应用的合理性。

[1]朱玉全,杨鹤标等.数据挖掘技术[M].南京:东南大学出版社,2006,163-167.

[2]章兢,张小刚等.数据挖掘算法及其工程应用[M].北京:机械工业出版社,2006,6-9.

[3]陈安,陈宁等.数据挖掘技术及应用[M].北京:科学出版社,2006,179-190.