基于搜索引擎算法的双向收费客户排序研究

基于搜索引擎算法的双向收费客户排序研究

0电信用户细分近年来，移动通信公司经历了良好的快速发展，现在进入缓慢增长阶段。中国加入WTO后,电信市场将逐步对外开放,一些世界级的电信巨头将通过各种手段逐步渗透到中国电信市场。电信运营商们正面临一个更加激烈的市场竞争环境。因竞争加剧而导致利润下降,迫使国内各电信运营商不得不考虑寻求新的盈利模式,以及如何实施有针对性的营销策略。电信运营商逐渐意识到,客户才是企业生存和发展的根基,而保持客户、吸引客户和充分发掘客户的盈收潜力是企业提高核心竞争力的关键。如何提高客户的满意度及忠诚度,提升客户价值来扩大自身的收入及利润等问题,成为各电信运营商关注的焦点问题。然而客户天生具有区别,不同的客户对企业的价值不同。根据Pareto原理,企业80%的利润是由20%的客户提供的,这部分客户是企业最有价值的客户,通常称为大客户。目前,运营商对大客户采取多种主动营销策略,如上门服务、赠送手机、话费折扣以及积分等优惠,以此来提高大客户的忠诚度。因此,对客户进行区分,有效识别大客户,对提高企业盈利能力、增加客户满意度有重要的意义。传统上客户细分的依据是客户的统计学特征(年龄、性别、收入、购买产品等),这种细分方法存在着很大的误差。RFM分析方法是广泛应用于数据库营销的一种客户细分方法,它的分析过程复杂,细分后得到的客户群过多,比较耗费时间,而且存在购买次数与总购买额间的多重共线性,即一个给定客户每多一次购买,他的总购买额也相应增加。Marcus对传统的RFM分析进行了修正,提出客户价值矩阵,用平均购买额代替总购买额,在客户价值矩阵中剔除了第三个变量Recency,解决了传统RFM分析的以上问题。上述两种方法存在分析过程复杂,随着变量数的增加计算量急剧增加,不适合分析拥有大量数据、数据形式多样化的问题。而电信企业的运营数据库通常拥有海量数据,因此需要寻找新的方法来解决电信客户细分的问题。本文提出一种新的方法对客户按价值进行排序,称为Authority-hub客户排序算法。本算法不同于简单的客户价值排序,它考虑了客户之间的互相影响,可以作为客户按价值细分的预处理步骤。在排序的基础上对客户分类,得出对企业有价值大客户,同时根据企业的需求可以对大客户进行更细的划分。1与未开洞互通的观点随着因特网的迅猛发展,搜索引擎的应用非常普及。搜索引擎排序算法是搜索引擎的核心技术,PageRank算法和HITS算法都是其中较有影响力的算法。两个算法都是利用网页链接的互相加强作用,对网页的重要程度进行排序。PageRank算法基于这样一个理论:若B网页设置有连接A网页的链接(B为A的导入链接时),说明B认为A有链接价值,是一个“重要”的网页。当B网页级别(重要性)比较高时,则A网页可从B网页这个导入链接分得一定的级别(重要性),并平均分配给A网页上的导出链接。HITS算法中引入网页的两种权重,即hub和authority,两者互相增强:好的Hub网页指向许多好的authority网页;好的authority网页是有许多好的Hub网页指向的网页。这种Hub网页与Authority网页之间的相互加强关系,可用于authority网页的发现和WEB结构和资源的自动发现,这就是HITS算法的基本思想。电信移动通话与网页排序问题有相似之处,也是通过链接(通话)加强了通话双方的重要程度。电信企业的客户价值由互相通话发生费用而产生。通话过程中,号码与号码之间有相互加强的作用,一个号码被叫,则得到“authority权值”,如果是被一个hub权值高的号码呼叫,则得到的authority权制越大;若此号码主叫,则得到“hub权值”,同理它所呼叫号码的authority权值越大,它得到越高的hub权值。因此,可以采用HITS算法的基本思想来解决电信客户的排序问题。但是电信客户分析问题需要寻找“好”的客户,而不是单独的authority或者Hub,因此这种相似之处并不能直接解决客户排序问题,还需要解决如下如下几个方面的问题:1)网页的权重仅仅由超级链接结构确定,因为对一个特定的网页来说指向其他页面的每个链接的权重都相等,而移动通信的客户权重不仅仅决定于通话链接,还受通话所发生的费用影响。即在电信呼叫分析中客户的重要程度由所发生的费用和通话链接共同决定。2)在HITS算法中没有可引入呼叫费用的地方,而且该算法中最后收敛的值与初始值无关。因此,即使取所发生费用为初始值,HITS算法所得到的结果是一样的,因此需要对HITS算法作出相应的改进,使其符合上述的要求。3)再考虑通话费用和通话连接之后所得的值是否合理。本文首先介绍HITS算法,然后在该算法的基础上提出新的算法——Authority-hub客户排序算法,最后将通过计算实例以及实验证明Authority-hub客户排序算法的优点。2hub/位选择HITS(Hyperlink-InducedTopicSearch)算法是评价与主题相关的WEB网页的算法。对于给定的页面,HITS算法首先定义了一个与主题潜在相关网页的基本集,然后基于hubs和authorities相互加强的思想,HITS算法计算基本集中每一个页面的hub/authority权值:一个好的hub是链向许多好的authority的网页;而一个好的authority是被许多好的hub链接的网页。该算法中借助于迭代算法得到每个网页的hub/authority权值。具体如下:基本集中每个网页i都有一个非负的authority权值a(i)和一个非负的hub权值h(i)。当一个网页具有较大a(i)值和h(i)值时,则认为它是一个较好的网页。在迭代之前须满足规范化条件:∑pa(i)2=1和∑ph(i)2=1。算法的每一次迭代过程进行如下:a(i)等于基本集中所有链向网页i的网页j的hub权值之和,h(i)等于基本集中i所链向的所有页面的authority权值之和,即有如下公式:a(i)=∑j→ih(j)(1)h(i)=∑i→ja(j)(2)迭代过程一直继续到a(i)和h(i)值收敛于稳定值,其收敛值满足以下矩阵属性。假设基本集中有1,2,…,n个网页,则可以定义基本集对应有一个n×n的邻接矩阵B,其取值为0或1。若网页i有指向网页j的链接,则B=1;反之,则B=0。Hub权值和authority权值可由向量h=<h1,…,hn>和a=<a1,…,an>表示。由此可得出以下公式:h=B·a;a=BT·h进行一次迭代,得出:h=BBTh=(BBT)h;a=BTBa=(BTB)a经过k次迭代后,可以得到:由线形代数相关知识,其最终结果h(i)和a(i)分别为BBT和BTB的主特征向量,而且收敛值与初始值的选择无关。3基于号码的分析Authority-hub客户排序算法是受HITS算法中的hub-authority思想启发而得到的。电信移动通话中客户与客户有相互加强的关系,客户与客户之间的通话链接类似于web网的超级链接。基于一个客户可能拥有多个号码而一个号码只对应一个客户的情况,本算法中以号码为分析主体。正如上文分析,如何在本算法中合理地引入通话费用是本算法的一个难点与挑战。3.1节点与节点之间的关系如上文所述,每次通话记录可以认为是从主叫号码到被叫号码的链接,因此只要号码i有呼叫号码j的记录,就定义号码i有指向号码j的链接,用i→j表示。由于号码i呼叫号码j而发生的通话费用,视为链接的权重,记作cos(i→j)。这样整个电信企业的呼叫记录可以构成一个巨大的有向图,此种结构与Web链接结构非常相似。例如有表1所示的呼叫信息,以i、j、k、h表示呼叫号码,并将费用等级分成5个级别,1为最低级别,5为最高级别,级别越高,发生费用越多。表1对应的有向图如图1所示,图中结点即表示呼叫号码,有向边表示呼叫信息,链接权重则对应表中的费用级别。如图1中的有向边i→j表示号码i主叫号码j,对应表1中的第1行。正如上例所示,我们用图来表示链接关系,通话号码的集合V为一个有向图G=(V,E),图中的节点对应一组通话号码,有向边(i,j)∈E表示节点i呼叫节点j,节点i的出度(out-degree)指节点i呼出的通话次数,而节点i的入度(in-degree)则指的是节点i被呼叫的通话次数。如果集合W是V的一个子集,则用G[W]来表示由W组成的有向图,它的节点包含在W中,边对应于W中的所有链接。由此可以定义以下几点:cost(i→j):节点i呼叫节点j所发生的费用,所发生的费用越多,i与j对于企业来说越重要;Authority:如果存在从节点i到节点j的呼叫,且由此所发生的费用较多,即cost(i→j)较大,则认为j为一个好的authority;Hub:如果存在从节点i到节点j的呼叫,且由此所发生的费用较多,即cost(i→j)较大,则认为i为一个好的hub。Rank:包括主叫和被叫,节点i发生的费用较多,即节点i的Authority和Hub的权重之和较大时,则认为节点i的rank值较高。如节点i呼叫节点j所发生的费用越多,则i越重要;节点j接受节点i呼叫所发生的费用越多,则j也越重要。在目前中国移动通信双向收费的情况下,节点i的重要性由主叫和被叫所发生的费用共同决定。3.2节点的旋转信号由于每次呼叫所发生的费用并不相同,因此当i或j发生变化时,链接权重cost(i→j)也会发生变化,这是本文中模型与Web链接最大不同之处。因为在Web链接中所有链接同等重要,因此不用考虑权重问题。如果直接引用HITS算法,以通话所发生的费用作为初始值,由于HITS算法是一个与初始值无关的算法,最后得到的结果与初始值无关,因此还是无法与通话费用发生联系。本算法通过将通话费用考虑入链接来解决这个问题。给出如下公式:若节点i的a(i)权值越大,表明节点i的authority值越大,即号码i由于被叫而发生的费用越多;同理其h(i)权值越大,表明节点i的hub值越大,即号码i由于主叫而发生的费用越多。当节点i的a(i)权值与h(i)权值的和较大时,则r(i)值较大,表明号码i所发生的费用较多,对于移动电信企业比较重要。算法以一个相关矩阵来表示通话链接关系,记为B。若链接i→j存在,则bij=cost(i→j);若链接i→j不存在,则bij=0;当i=j时,bij=0。矩阵B称为呼叫费用矩阵:可以看出BBT是对称矩阵。同理可得,BTB也是对称矩阵。由线性代数的知识可知,两者的主特征向量分别为有向图中节点最终收敛的hub和authority值。由于双向收费的情况节点i的重要性由主叫与被叫共同决定,如公式5所示。当r(i)值越大,则节点i所发生的费用越多,这意味着节点i对于企业来说是越重要的。3.3算法的计算过程下面我们通过一个数值例子说明Authority-hub客户排序算法的过程。本例子使用表1的数据,构建的有向图如图1所示,有i,j,k,h四个节点,其中cost(i→j)=1,cost(i→k)=5,cost(k→i)=4,cost(j→k)=3,cost(h→k)=1。设节点i,j,k,h分别对应矩阵下标序号1,2,3,4,那么本算法计算过程如下:首先得到呼叫费用矩阵B如下:B=⎡⎣⎢⎢⎢⎢b11b21b31b41b12b22b32b42b13b23b33b43b14b24b34b44B=[b11b12b13b14b21b22b23b24b31b32b33b34b41b42b43b44=⎡⎣⎢⎢⎢⎢0040100053010000=[0150003040000010得到其转置矩阵BT如下:BT=⎡⎣⎢⎢⎢⎢0150003040000010BΤ=[0040100053010000那么可以得到:得到结果如表2所示。即节点i,j,k,h对于企业重要性的排列顺序为:k,i,j,h。分析图1,节点k所发生的费用最多,应为最