基于空问定位的聚类算法在电信业客户划分中的应用

第8卷第1期2008年1月科学技术与工程Vol 8 No. 1 Jan. 20081671-1819(2008)1-0207-06Science Technology and Engineeringc 2008 Sci. Tech. Engng基于空间定位的聚类算法在电信业客户划分中的应用常晓磊闫仁武”杨苏宁(江苏科技大学电子信息学院,镇江212003)摘要随着电信市场竞争的不断加剧,电信企业传统的营销模式正在间主动、精确营销模式转变。因此,客户划分显得至关重要。釆用数据挖掘中聚类的方法对电信业的客户进行划分,在比较了现有聚类算法计算复杂度普遍较高的的基础上,采用了一种基于空间定位的方法,将客户数据对象映射到特征空间中,并利用空间立方体的某些特殊顶点定位任意数据,通过计算数据点与空间立方体顶点群的距离差异,完成聚类过程。为了适合电信业客户的特殊性质,改进对客户属性数据的处理过程。通过电信客户的数据实验结果表明,算法的时间复杂度降至0(N)级别。关键词数据挖掘聚类客户划分空间定位电信业中图法分类号TP311.52;文献标志码A随着各种现代生产管理手段和技术的发展,企种,其中比较典型的有关联分析、预测分析、聚类分业之间产品的差别越来越难以区分,产品同质化的析等。趋势越来越明显,通过产品差别来细分市场,从而数据挖掘主要应用在CRM中大量的客户数据创造企业的竞争优势也就变得越来越困难2。随分析,以及客户价值的挖掘方面。作用主要有新客着市场态势从卖方市场向买方市场的转变,如何确户的获取和保持、个性化营销、客户忠诚度分析以定高价值和忠诚度高的客户,对企业的发展有着非及客户市场划分等常重要的作用。为此许多企业开始实施客户关系本文在已有的基于空间定位的聚类算法的基管理( Customer relation- -ship managemen,CRM)。础上,把该算法具体应用到网通客户的划分上,为客户划分作为CRM中的重要组成部分,对CRM的了适合冈通的客户特性,并改进了该算法的数据处成功实施有着重要的作用理过程。本文的数据来源于网通电信增值业务服面对海量的各种客户、销售等数据,为了对客务商的无锡汇隆信息技术有限公司近年来的客户户进行有效的划分,为经营者实施更具有针对性的数据库。销售措施提供理论依据,有必要依赖于数据挖掘( Data mining,DM)的强大数据分析能力。数据挖1基于空间定位的聚类分析掘作为一种工具,是从大量的数据中抽取潜在的、有价值的知识、模型或规则。数据挖掘方法有多聚类将数据对象分组为多个类或簇,使同一个簇中的对象之间的相识度最高,而不同簇中的对象2007年9月17日收到其相识性最低。由于大型数据库中存放了大量的第一作者简介:常晓磊(1983-),男,汉族,江苏镇江人,硕士研数据,聚类分析已经成为数据挖掘研究领域的一个究生,研究方向:智能信息处理。Eml: changxiaolei30非常活跃的课题。但是,面对电信行业的海量数163.c0m。据,就一般的聚类算法而言,算法的复杂度制约了科学技术与工程卷额的商业数据挖掘软件的聚类算法仅仅是有限的高的问题。几种:K- means算法、高斯混合算法和基于SⅤM的本算法解决以上两个问题的方法是:按照包含算法等元素数的多少,选取出所有大于总元素数一定比例1.1算法思路Q的所有类(称为有效类),对无效类包含的所有元目前的聚类算法时间复杂度高的主要原因是素,予以重新分配。事先指定的比例Q是这样确定需要计算任意两个点之间的距离。从另外一个角的:根据无锡市网通的具体情况和业务发展要求,度出发,聚类算法的核心思想就是用某种机制划分在业务开展实践中,公司比较理想的客户群数量是数据空间,划分完毕后,该子空间内的所有数据点4~6个,根据用定位法进行聚类计算的经验,要达即为一类。因此,只要能把数据映射成是空间中的到以上的业务要求,Q的取值范围必须在2.5%~点,然后划分空间中的点集,得到的每个子空间5%之间。Q值越大,类数就会单调减少,聚类更加就可以看作是一个簇(正交框架等名词的定义请参集中;反之Q越小,类数会单调增大,聚类越分散。阅参考文献[4])。重新分配的方法是计算有效类的中心。由于有效1.1.1属性归一化类中心已经是空间立方体内密度最大点之一,因为了能把元素映射到空间立方体和便于距离此,以这些中心作为最终聚类中心,对所有元素点的计算,首先要把对元素属性进行归一化处理,即进行重新竞争,再次遍历数据集,所有元素都归入把元素的M个属性都转换成[0,1]区间的值。从而距离最近的有效类中心的类中,则聚类计算完毕。完成元素到空间立方体的映射。对于数值型属性对类有效性的判决,解决了类过于零碎的问题。重可以采取new_ value=(old_ value-min value)/(max_新竞争解决了各类之间的边界不明确的问题。另value-min_ value)的方法,但对于字符型的属性则需外,从算法的时间复杂度上看,随元素数量的增加,要根据行业特性进行特殊的处理。对于无锡网通时间开销与元素数量的关系呈明显的一阶线性增客户的字符型属性的处理,将在第3部分详细介绍。加。参考文献[3]中指定的实验环境下,时间开销1.1.2计算中心与立方体正交框架的距离(秒)与元素个数所拟和的函数为:F(x)=0.000计算出该空间立方体的中心,然后计算出该中2338X+5.333。随元素维数的增加,时间开销与元心与正交框架的M+1个点的距离D。由于在正素维数呈明显的二阶非线性增加,时间开销(秒)与交框架的元素属性中有大量0坐标存在,降低了实元素个数所拟和的函数为:F(x)=0.023X2+0际计算的时间开销。079X+10.933,分别如图1、图2所示。1.1.3遍历数据集计算每个元素到正交框架的距离,并与空间o实验观察值一阶函数拟和立方体中心到正交框架的距离D逐一进行比较判决,得到的判决结果组合成二进制数,再将该进制数转化成十进制数,即为该元素所属类的标识。经过以上三个步骤后,大部分元素都归入了相应的类别中,但还有两个问题需要解决:一个是由050000100000150000200000自变量:元素数量/个于现实聚类计算中数据分布的不对称性导致有的类包含较多元素,有的类只有2~3个元素,而这样图1元素数量与时间开销的函数关系的零碎类是没有实际意义的;另一个问题是边界性2算法流程1期常晓磊,等:基于空间定位的聚类算法在电信业客户划分中的应用具体流程如图3所示。22阶函数拟和离与立有效体中交《正上|第上行隔出区距离距离的/制类/有效聚类图3空间聚类算法流程自变量模型维数由此可以看出,定位法不需要事先指定聚类个图2元素维数与时间开销的函数关系数。而且定位法又提供惟一的参数Q来调节聚类有M个属性值,最小类阈值Q。个数,当需要分群个数较多时,只需将Q调小;反之(1)将M维数据表进行归一化处理,即将Z映需要分群个数较少时,将Q调大即可。射为空间立方体C,每个元素归一化后映射为空同2客户划分立方体内部某一空间点。2)计算所有元素对M维立方体的正交框架对一营销是指了解每一个客户,并同其建立所属的M+1个顶点的距离。(3)所有元素与正交框架所属M+1个点的各起持久的关系。这是一个很理想化的概念,大多数行业在实际操作中是无法做到的。但是,企业可以个距离D分别用空间立方体中心W与这M+1个将客户分类,为每类客户提供有针对性的产品或点的距离D,来判决:若D1≥Dn,则F=1,或F;=0其中,∈{1,2…,M+1,i∈R;F是第i位判次服务。客户划分,也称客户市场细分、客户市场分割,结果。就是把客户根据其性别、收入、交易行为特征等属4)将判决结果F=(F,F2,…,Fm+)按位组性细分为具有不同需求和交易习惯的群体同一群合成M+1位二进制数Rmm=F1,F2,…,Fm+1,转体中的客户对产品的需求以及交易心理等方面具换Rn成十进制数,即是初始聚类结果,写入每个有相似性,而不同群体间差异较大。客户群体细分元素的类别Fu(标识)字段。可以使企业在市场营销中制定正确的营销策略,通(5)统计初始聚类结果,得到各类包含的元素过对不同类别客户提供有针对性的产品和服务,提数判决初始类是否有效:若 CCount 2 NQ,则第i类高客户对企业和产品的满意度,以获取更大的利润。有效,或第i类所有元素的F字段清空。数据挖掘系统可以在客户群体细分的基础上(6)计算所有有效类的中心,设向量空间的维进行进一步的细分,直到所需要的粒度,并对此客数为M,空间立方体C内、某个初始类内有P个点,户却体进行各种分析。则该类的中心为E=(E1,E2,…,Em),式中,E=(E)/P,i∈{1,2M},t∈h3利用空间定位的聚类算法划分电信业客(7)对空间立方体C内所有N个元素点,计算户市场其与所有有效类的中心的距离。竞争聚类:若D=min(D),则Rm1=t,将R写入每个元素的Fu本节将利用以上介绍的空间定位聚类算法对字段。其中,D是该元素点与第i个有效类中心的部分无锡网通的客户进行分析,并验证了该算法的210科学技术与工程卷3.1数据预处理田、岛首先采用了无锡汇隆公司近两年的客户数、通USERID短信发送次数话、短信、充值,通过属性删减和不完整数据的删除,最终选取的客户属性为:年龄,收入,受教育程2753235度,职业,通话次数,短信发送量,联系人数目,充值3253次数,充值总额}九个属性。图4—图6分别是数据3254预处理前的各种客户数据情况截图。3258832812222m2993280阳大9图4用户基本信息3318田长国用33333330615:99000223039553303493351图6用户短信汇总信息对“受教育程度”,采用的处理方式是,首先对3选出来的所有数据进行统计分析,计算出各个学历层次的人数总和,最后除以总数据条数。这在数据取的时候就可以利用 oracle的函数进行运算。对于其余的数值型数据,我们采用是 new value(old_-value-min_value)/( max_value-min_value )B方法,其中 max value是该属性中的最大值,min图5用户通话汇总信息value是该属性的最小值,old_ value该属性处理前的1期常晓磊,等:基于空间定位的聚类算法在电信业客户划分中的应用211acle临时表中,最后导出为程序可处理的 excel表。每天在线的时间较长。为了方便客户充值,我们可3.2算法的应用以开通网上充值卡自动销售服务,同时对通话超过根据行业经验和相关实验的经验值设定类的定时给予短信奖励阈值为:4%。类4:这类客户从年龄段、职业、收入,联系人数第一编扫描数据数据库表,计算出数据元素组目等各个属性都有相关的值,且通话次数和短信发成立方体的中心,并计算出该中心与正交框架的距送量都较小。对于这类客户我们将其定位为潜在离,记为向量D。的真正客户。为此,我们需要从中区别出哪些是可第二次扫描数据库库,计算所有元素与正交框能给企业带来利益的客户,哪些是不能给企业带来架和立方体中心的距离,通过中心到框架的距离与利益,甚至是负面利益的客户。为此,我们需要做元素到框架的距离进行比较,判决出元素所属类别进一步的客户跟踪和引导。例如针对这类客户开进制数中的一位。通过与所有框架的距离的比展优惠活动和问卷调查等。较得出得出元素所属类别二进制序列,再将序列转为十进制数,记入该元素的类别属性中。4结束语第三遍扫描数据库,对于小于设定阈值的类或个别数据,按照上面的算法介绍的方法通过竞争聚空间定位概念的引人使得定位法避免了大量类划分到相应的有效类中。至此算法完成。的、任意两个元素的距离计算,从而大大节省了运3.3结果分析算时间;同时,算法不要求事先指定分群的个数,能方面,通过定位算法的分析,最终得到4个有较好地反映客户的实际聚集程度;参数只有一个需效类要调整,使数据挖掘操作员可以轻易调整类的规模类1:这类的特点的是年龄大多数低于25,职业(而不是个数),以解决聚类结果业务解释性不强的多为学生,学历为专科和本科,每月的短信数量一问题。在实验和实践中发现,使用定位法得到的聚般大于600,并且充值次数较多,但这类中的客户通类结果有所提升,业务解释性也有所优化,算法具话费用相对小。我们可以将这一类定位为学生群有较高的实用价值体。针对这类群体,我们可以开发出小面值的充值参考文献卡、通过短信奖励机制带动通话业务的提升等。类2:这类客户的特点是年龄一般大于45,通话1李益强,漆晨曦,基于数据挖掘的电信客户细分研究分析广东费用处于平均水平,充值次数较少,但充值金额较通信技术,2005;(5):12-15大。该类客户的最大特点是联系人数目最多,短信2江毅,朱顺泉数据挖掘技术在客户关系管理中的应用研究软科学,2003;17(12):46发送量高,月平均大于20000条。我们可以将这类erry M J A, Linoff G S. Data mining techniques-for marketing, sales客户定位为企业客户。他们通过短信方式定期向and customer relationship management.别荣贵,尹静,邓云爱联系人发送产品信息的广告。针对这类客户群体译.北京:机械工业出版社,2006我们可以开通短信定时发送功能,填加短信模版,4张舒博,牛琨基于定位的数据聚类新算法计算机技术与应更加方便客户,同时也可以增加短信发送量。用,2007;(4):118-120类3:这类客户职业一般是跟计算机相关的,学5段云峰,吴唯宁,李剑威,等.数据仓库及其在电信领域中的应用.北京:电子工业出版社,2003历为本科或硕士,且年龄一般小于30,通话次数较下转第228页)高,短信发送量介于平均值附近。这类客户可能是228科学技术与工程卷式识别标准的系统入侵检测模型,并且介绍了Linx参考文献高版本系统内核系统调用序列的提取方法,和用户1 Warrender C, Forrest s, Pearlmutter b. Detecting intrusions using行为模式库的创建方法。基本原理是通过加大对 system calls: alternative data models. Proceedings of the I99g获取了较高级别权限入侵手段的检测力度,为网络Symposium on Computer Security and Privacy. S.1.:[s. n. I1999:133-145这正好符合了橘皮书( TCSEC-Trusted Com20,mSystem Evaluation Criteria)的安全思想。本文提出的227—240入侵检测系统,只是系统级上的入侵检测。如果综3 Base r o入侵检测技术.陈明奇,等译北京:人民邮电出版合其他层次上的入侵检测,组成多层次的入侵检测土,2001系统,将会收到意想不到的效果。4宋立新,李善平,利用IKM实现Iinx系统的安全性,计算机应用研究,2002;8:103-10Application of"Immune System"Method on System-level IntrusionDetection TechnologyZHANG Han. YANG Wen-fei. Chen JinsL Abstract The"Immune System"method for computer system security is based on the fact that the short se-quences of system calls in running processes are concreted. The short system calls can be used to construct the da-tabase of normal behavior patterns for the processes. A system-level intrusion detection model is proposed, and dis-cussed the technology of system realization with Linux operating system[ Key words]“ Immune System” methodntrusion detectioshort system calls sequencesnormaland abnormal behavior patterns(上接第211页)Customer Demarcation Using Clustering MethodBased on Space locationCHANG Xiao-lei.yan Ren-wu".YANG Su-ningCollege of Electrics and Information, Jiangsu University of Science and Technology, Zhenjiang 212003, P. R. China)[Abstract] With the competitions among telecom industry prick up day by day, the traditional sell pattern hasbeen changing to the active and smart way, so customer demarcation become more important than before. Customersof telecom industry with the way of "Clustering"are compartmentalized, which are a usual technology of data min-ing. After compare with the time-complexity of common clustering methods, a method named "clustering based orspace location"is choosed to use. First the object of customer date into special space is mapped, then every dataelement using some special peaks of the cube space is located. At last, difference of distance between the date-ele-ments and the special peaks of the cube space to finish the process of clustering is used. To fit the particularity oftelecom customers, the way of customer date procession is improved. According to the result of experimentationusing the customers data, the time-complexity has fall to O( N)is found