基于层次分裂算法的价格指数序列聚类
褚洪洋, 柴跃廷 , 刘义    
清华大学自动化系, 电子商务交易技术国家工程实验室, 北京 100084
摘要:目前,中国国家统计局发布的消费者价格指数不包含网购部分。随着电子商务的快速发展,网购价格指数的发布已经成为亟待解决的问题。互联网环境下,网购交易数据能够实时获取,因此网购价格指数应当更为准确可靠。然而,由于企业对商品分类标准不同,分类价格指数的计算需要首先解决基本价格指数的分类问题。该文提出一种基于层次分裂算法的价格指数序列聚类方法,选择基于相关系数的距离和Manhattan距离作为距离度量,分两步对价格指数序列进行聚类。算法通过设置不同的终止条件停止分裂,不需要事先设置簇数。引用实例对算法进行验证,有效划分了226组价格指数序列中的219组,取得了较好的聚类效果。
关键词价格指数序列    层次分裂算法    基于相关系数的距离    Manhattan距离    
Cluster analysis of a price index series based on the hierarchical division algorithm
CHU Hongyang, CHAI Yueting , LIU Yi    
National Engineering Laboratory for E-Commerce Technology, Department of Automation, Tsinghua University, Beijing 100084, China
Abstract: At present, e-commerce trade is not included in the consumer price index published by the National Bureau of Statistics of China. With the rapid development of e-commerce, the development of an online consumer price index(CPI) has become an urgent problem. Online transaction data supports real-time access and corresponds to actual transactions. Therefore, an online CPI should be more real-time and more accurate than the traditional CPI. However, the calculation of a classification price index requires classification of elementary price indexes, because there are differences in the classification standards used by different enterprises. This paper describes a hierarchical division algorithm for cluster analyses of price index series, which uses a correlation coefficient based distance and the Manhattan distance to measure the distances between price index series and then divides the series by two steps. The method uses ending conditions to stop the divisions, so that the cluster count need not be preset. Finally, the method is applied to practical cases with 219 of 226 price index series effectively divided, which indicates a good clustering result.
Key words: price index series    divisive hierarchical clustering method    correlation coefficient based distance    Manhattan distance    

价格指数是反映一定时期内,相同的产品或服务价格总水平变动趋势和程度的相对数,它是用某一时期(报告期)的价格水平与另一时期(基期)的价格水平相比,来说明价格变动趋势[1]。价格指数可以及时度量一般物价水平,并且在一定程度的通缩下测算实际收入和支出[2]。目前,中国国家统计局计算和发布的价格指数不包含网购商品价格,导致网购的价格变动趋势缺乏可靠的统计指数。

传统环境下,通过抽样调查的方法获取代表商品的价格数据,经过简单综合得到基本价格指数,也即某一地区某一类商品的价格指数。接着,根据基本价格指数计算分类价格指数,也即某一地区的价格指数或某一类商品的价格指数。

网购环境下,交易数据来源于电子商务企业自行存储的交易数据,或者是集中管理的电子发票[3]。因此,统计部门更易于获取代表商品的价格数据,进而通过简单综合得到的基本价格指数,也即某一企业某一类商品的价格指数。然而,在进一步加总过程中,由于电子商务企业采用的分类标准不同,同一类商品在不同企业的称呼存在差异,导致在计算分类价格指数时,难以找到同一类商品的基本价格指数。所以,在计算网购分类价格指数时,首先需要将基本价格指数进行划分,为分类价格指数的计算提供依据。考虑到单一时期的价格指数不足以区分其商品类别,研究对象应当是多个连续时期的价格指数也即价格指数序列。

本文提出一种基于层次分裂算法的价格指数序列聚类方法,选择剔除整体趋势后的相关系数和Manhattan距离作为距离度量,分2步对价格指数序列进行聚类,达到有效划分对不同企业基本价格指数序列的效果。

1 价格指数序列聚类问题描述

本文解决的实际问题是:根据不同企业的不同商品类别在多个连续时期的基本价格指数,对基本价格指数进行分类,找到属于同类商品或相似类别商品的基本价格指数。

价格指数有多种编制方式,常见的包括定基价格指数和环比价格指数。前者用于观察物价变动的长期趋势及其规律,后者用于观察物价的逐期变动趋势和程度。同类商品的价格指数的相似性易于在长期趋势中体现,因此选用定基价格指数作为聚类对象。

假设数据集D是不同企业的不同商品的价格指数序列的集合,且共有n组价格指数序列。每组价格指数序列是连续T个周期的定基价格指数,并且各组价格指数序列的起始和终止时间相同,记作(xi,1,xi,2,…,xi,T),1≤in

本文解决的抽象问题是,通过一种聚类算法将数据集D中的n组价格指数序列分配到k个簇中,使得簇内对象相似而簇间对象相异,也即簇内的价格指数序列属于同类商品或相似类别,而不同簇的价格指数序列属于不同类商品。

由于D中价格指数序列的商品类别数目未知,因此无法事先确定聚类的簇数k,需要通过算法获取适当的簇数。同时,算法不会对每个簇包含的价格指数序列个数进行限制,对某一商品类别可能只有一个价格指数序列,也可能有多个。

价格指数序列是一种时序数据,因此在聚类分析时可以采用一般时序数据的处理方法。时序数据是一类重要的时空数据对象,并且易于从实际生活中获取[4]。时序数据的聚类方法是当前的数据挖掘热点问题之一[5],已经涉及金融[6 ,7]、 自然语言处理[8]、 气象[9]、 交通费用[10]和地理[11]等多方面。目前,层次聚集算法、 K-means算法、模糊C-means算法和自组织映射等方法已被应用到时序数据聚类中[12]。在聚类分析中,距离度量常常作为分类的主要依据,而常见的距离度量包含Euclid距离、 Minkowski距离、相关系数和相对熵等[13]。本文结合价格指数序列的性质,选择层次分裂算法,并采用基于相关系数的距离和Manhattan距离作为距离度量。

2 距离选取

两组价格指数序列的距离用于衡量其相似程度,距离应不小于零,且距离越接近于零的价格指数序列越相似。距离选取是聚类分析中的关键问题之一。

2.1 基于相关系数的距离

相关系数是反映变量间相关关系密切程度的统计指标,在时序数据的聚类问题中常用作距离度量。相关系数的取值范围为[-1,1],越接近1意味着变量间的相关性越高。在本问题中,相关系数也可以说明价格指数序列间的相似程度,2组价格指数序列(xi,1,xi,2,…,xi,T)和(xj,1,xj,2,…,xj,T)的相关系数为

$ {\rm{cc}}\left( {i,j} \right) = \frac{{\sum\limits_{t = 1}^T {\left( {{x_{i,t}} - {{\bar x}_i}} \right)\left( {{x_{j,t}} - {{\bar x}_j}} \right)} }}{{\sqrt {\sum\limits_{t = 1}^T {{{\left( {{x_{i,t}} - {{\bar x}_i}} \right)}^2}} \sum\limits_{t = 1}^T {{{\left( {{x_{j,t}} - {{\bar x}_j}} \right)}^2}} } }}. $

其中${{\bar x}_i} = \frac{1}{T}\sum\limits_{t = 1}^T {{x_{i,t}}} $。

大部分情况下,相关系数能够说明价格指数序列间的关系。然而,在一些特殊情况下,相关系数呈现出不足。

图1为2组服装类和2组耐久商品的价格指数序列,数据来源于美国劳工统计局发布的城市居民消费者价格指数,分别为15个不同地区的服装类和耐久商品在2004年1月至2013年12月的月度定基价格指数中具有代表性的2个地区,基期选为2004年1月。服装类和耐久商品各自的2组价格指数序列有明显的相似,然而部分价格指数序列间的相关系数却无法说明这种相似。分别计算服装类和耐久商品的15组价格指数序列的相关系数,可知:对于服装类,相关系数的最小值为0.628,平均值为0.803;对于耐久商品,相关系数的最小值为0.317,平均值为0.770。存在多组同类商品价格指数序列的相关系数数值过低的情况,如果直接使用相关系数作为距离度量,将影响聚类结果。

图 1 服装类和耐久商品价格指数序列

事实上,同类商品的价格指数序列有着各自的整体变化趋势,导致其序列虽然形状相似,但是相关系数不高。为解决这个问题,应当剔除价格指数序列中整体变化趋势部分,分析剩余部分的相关系数。本文中,为减少整体变化趋势部分的计算工作,将其视为与时间呈线性关系,在实例验证中这种简化起到了较好的效果。假设价格指数序列分为整体变化趋势部分(zi,1,zi,2,…,zi,T)和剩余部分(xi,1,xi,2,…,xi,T),即:

$ {x_{i,t}} = {z_{i,t}} + x{'_{i,t}}. $ (1)

其中zi,t=ait+bi代表与原价格指数序列间距离最小的直线,即aibi使$\sum\limits_{t = 1}^T {\left| {{x_{i,t}} - {a_i}t - {b_i}} \right|} $取最小值。

通过(1)式获取整体趋势部分的直线参数,并计算原价格指数序列与该直线的差值作为剩余部分,即(xi,0-bi,xi,1-ai-bi,xi,2-2ai-bi,…,xi,T-Tai-bi)。

图2为2组服装类和2组耐久商品的价格指数序列剩余部分,仍然能够直观地反映出指数序列之间的相似关系。

图 2 服装类和耐久商品剩余部分价格指数序列

计算后可知:对于服装类剩余部分,相关系数的最小值为0.740,平均值为0.848。对于耐久商品剩余部分,相关系数的最小值为0.593,平均值为0.794。剩余部分的相关系数要整体大于原序列相关系数,可以更有效提高同类商品距离度量的准确度。

因此,本文使用剩余部分说明价格指数序列之间的距离关系。2组价格指数序列剩余部分的相关系数为

$ {\rm{cc'}}\left( {i,j} \right) = \frac{{\sum\limits_{t = 1}^T {\left( {x{'_{i,t}} - \bar x{'_i}} \right)\left( {x{'_{j,t}} - \bar x{'_j}} \right)} }}{{\sqrt {\sum\limits_{t = 1}^T {{{\left( {x{'_{i,t}} - \bar x{'_i}} \right)}^2}} \sum\limits_{t = 1}^T {{{\left( {x{'_{j,t}} - \bar x{'_j}} \right)}^2}} } }}. $

其中$\bar x{'_i} = \frac{1}{T}\sum\limits_{t = 1}^T {x{'_{i,t}}} $。

相关系数的取值范围为[-1,1],且越接近1则二者相关程度越高。距离度量则要求取值大于0并且越接近0二者相似性越高。因此,对剩余部分的相关系数进行适当转换,得到基于相关系数的距离为

$ dis{t_1}\left( {i,j} \right) = {\left( {\frac{{1 - {\rm{cc'}}\left( {i,j} \right)}}{{1 + {\rm{cc'}}\left( {i,j} \right)}}} \right)^2}. $
2.2 Manhattan距离

一些情况下,基于相关系数的距离仍然难以说明价格指数序列间的关系。例如图3中包含2组价格指数序列,分别是美国劳工统计局发布的1组公共交通和1组能源的城市居民消费者价格指数,它们的变化趋势相同但是变化幅度有明显差异,基于相关系数的距离难以对其进行区分。

图 3 相关性度量中无法区分的类别

由于同一类价格指数序列间各点距离较小,而不同类序列各点距离较大,本文使用Manhattan距离作为第2种距离度量,即:

$ dis{t_2}\left( {i,j} \right) = \sum\limits_{t = 1}^T {\left| {{x_{i,t}} - {x_{j,t}}} \right|} . $

同类商品的价格指数,在部分时期可能存在较大的差异。此时,Euclid距离和其他Minkowski距离由于指数项较大,会扩大这些特殊点带来的不利影响,得到的距离度量效果不佳。因此,Manhattan距离在本算法中优于其他的点距离度量方法。

在实际的聚类划分时,同时使用基于相关系数的距离和Manhattan距离作为不同价格指数序列相似度或相异度的度量方式。基于相关系数的距离能在更多情况下有效说明价格指数序列的相似关系,是价格指数序列聚类的主要距离度量。无法用基于相关系数的距离区分的价格指数序列(见图3)需要使用Manhattan距离作为聚类的次要距离度量。

3 层次分裂算法

目前,划分和层次聚类是时间序列聚类中最常用的两种算法。划分算法(如K-means等)要求事先给出簇数。然而对不同来源的价格指数序列进行聚类前,无法预先知道价格指数序列的类数。同时,划分算法也不适合于发现有一定大小差异的簇,这种情况在价格指数序列中经常出现。相比之下,层次聚类算法可以设置适当的终止条件,以替代预先指定的簇数,并且能够处理有大小差异的簇[14]。因此,本文选用层次聚类算法对价格指数序列进行聚类。

在聚类过程中,基于相关系数的距离是区分价格指数序列的主要指标,而Manhattan距离则用于处理相关系数无法区分的部分。在这种情况下,分裂的层次聚类方法优于凝聚的层次聚类方法,因为凝聚的方法无法判断使用何种距离度量,而分裂的方法则依次使用基于相关系数的距离和Manhattan距离。层次分裂算法的简要步骤如下:首先将所有价格指数序列置于1个簇中;接着根据基于相关系数的距离将该簇分裂成2个子簇,并且递归地将这些簇分裂成更小的子簇,当子簇达到终止条件时停止分裂;然后对各子簇根据Manhattan距离分裂成2个子簇,并且递归地进行分裂,直至达到终止条件。

无论是以基于相关系数的距离还是以Manhattan距离作为距离度量,在分裂过程中,都应使得分裂出的2个子簇的簇内距离小,而簇间距离大。

针对基于相关系数的距离,本文采用基于最大割的分裂方式,即在分裂过程中找到使子簇间距离和最小的2个簇。子簇间距离和定义为$\sum\limits_{i \in {C_1},j \in {C_2}} {{\rm{dis}}{{\rm{t}}_1}\left( {i,j} \right)} $。其中,C1C2为2个子簇。

最大割问题是一个NP难问题,采用枚举法会使算法复杂度呈指数增长,因此需要采取启发式算法获取近似的最优解。本文采用蚁群算法[15],比其他方法更容易取得最优值,但是算法运行时间较长。考虑到价格指数序列的数量往往从几十到几千,蚁群算法的时间代价可以接受。

最大割找到子簇间距离和最小的2个簇,而在元素间距离差异不明显时,最大割更容易找到割边数较大的2个簇,也即2个子簇的对象数目会更接近。

采用基于相关系数的距离时,由于同类价格指数序列要明显区分于不同类,上述问题不会影响正常分裂。而采用Manhattan距离时,基于最大割的分裂方法往往会找到2个对象数目相近的簇,导致错误的分裂发生。

为避免该情况发生,针对Manhattan距离分裂时考虑加权子簇间距离和${\left( {\frac{1}{{\left| {{C_1}} \right|\left| {{C_2}} \right|}}} \right)^\gamma }\sum\limits_{i \in {C_1},j \in {C_2}} {{\rm{dis}}{{\rm{t}}_2}\left( {i,j} \right)} $,其中γ∈[0,1]。特别地,当γ为0时即为子簇间距离和,γ为1时即为子簇间平均距离和。

分别使用蚁群算法,计算γ=0,0.1,…,1时上述加权子簇间距离和取最小值时的分裂结果。对得到的11组分裂结果进行比较,取其中簇间平均距离与簇内平均距离较大值之比最大的一组,也即令$\frac{1}{{\left| {{C_1}} \right|\left| {{C_2}} \right|}}\sum\limits_{i \in {C_1},j \in {C_2}} {{\rm{dis}}{{\rm{t}}_2}\left( {i,j} \right)} /\mathop {max}\limits_{t = 1,2} \left( {\frac{2}{{\left| {{C_l}} \right|\left( {\left| {{C_l}} \right| - 1} \right)}} \cdot \sum\limits_{i,j \in {C_l}} {{\rm{dis}}{{\rm{t}}_2}\left( {i,j} \right)} } \right)$取最大值的一组分裂结果为最终分裂结果。

分裂完成后,需要使用终止条件对分裂进行验证。如果分裂满足终止条件,则原簇由2个子簇替代,继续迭代分裂2个子簇;如果分裂不满足终止条件,则取消该次分裂,并对原簇进行标记。终止条件是对簇分裂结果的一种判断,考虑到簇间平均距离总会大于簇内平均距离,并且二者差距越明显则分裂结果越好。在本算法中,采取下式进行判断:

$ \begin{array}{*{20}{c}} {\frac{1}{{\left| {{C_1}} \right|\left| {{C_2}} \right|}}\sum\limits_{i \in {C_1},j \in {C_2}} {{\rm{dis}}{{\rm{t}}_k}\left( {i,j} \right)} > }\\ {{\alpha _k}\mathop {max}\limits_{t = 1,2} \left( {\frac{2}{{\left| {{C_l}} \right|\left( {\left| {{C_l}} \right| - 1} \right)}} \cdot \sum\limits_{i,j \in {C_l}} {{\rm{dis}}{{\rm{t}}_k}\left( {i,j} \right)} } \right),} \end{array} $

其中k=1,2。也即当分裂后子簇的簇间平均距离大于2个子簇簇内平均距离αk倍时,视为成功的分裂,不满足终止条件;而当子簇的簇间平均距离小于两个子簇任何一个的簇内平均距离的αk倍时,满足终止条件,不进行分裂。其中,αk的选取根据实际情况选取。一般来讲,αk>1,并且α2α1

同时还需要注意到,使用基于相关系数的距离时,一个簇的簇内平均距离过小的情况下,因为这簇内价格指数序列的相似程度很高,不应再进行分裂,本文设该距离小于0.01时不再分裂。

价格指数序列的层次分裂算法细节如图4所示。

图 4 价格指数序列层次分裂算法细节
4 实例验证

本文使用美国劳工统计局发布的城市居民的消费者价格指数数据,作为聚类对象的226个价格指数序列覆盖食品、服装、耐用品、能源、医疗产品和交通等,且来源于美国不同城市或地区。价格指数序列选取2004年1月至2013年12月共计120个月的月度定基价格指数,基期选为2004年1月。

采用本文所述方法,对价格指数序列进行聚类,终止条件参数选择为α1=2,α2=2.5。两步分裂完成后,聚类结果如表1所示,其中“2-1”表示该价格指数序列第一步被分裂到由原始集合分裂出第2个子簇,第二步被分裂到由上述子簇分裂出的第1个子簇。可以看到:二手汽车、医疗产品、汽油和食品分别被划分成一个簇;新汽车属于耐用品的一种,因此与耐用品划分到一个簇。

表 1 各簇包含的价格指数序列
簇编号包含的价格指数序列
1服装(15),教育交流(1)
2-1新汽车(9),耐用品(15)
2-2二手汽车(3)
2-3医疗产品(3)
3-1公共交通(28)
3-2公共交通(2)
3-3汽油(78)
4教育交流(13)
5食品(15)
6教育交流(1)
7家用能源(40),住房租金(3)

公共交通的价格指数序列中,有2组价格指数序列与其他序列有明显区别,因此在分裂过程中被单独分出。教育交流和住房租金则由于地域性较强,难以有效进行聚类。可以看出:虽然有少量难以处理的价格指数序列,但是算法仍然能够有效对不同类别的价格指数序列进行区分。

5 结 论

本文提出一种价格指数序列的层次分裂算法,使用基于相关系数的距离和Manhattan距离作为距离度量,分两步对价格指数序列进行聚类。在编制网购价格指数时,算法能够有效划分价格指数序列,找到同类商品的基本价格指数,为分类价格指数的编制提供依据。与其他时序数据的聚类算法相比,本算法有如下特点:

1) 不直接采用相关系数作为距离度量,而是采用剔除整体趋势后的相关系数,能够更准确地反映价格指数序列间的关系;

2) 结合价格指数序列的实际情况,分别采用两种不同的距离度量对价格指数序列进行分裂聚类,有效地对价格指数序列进行划分;

3) 不需要事先设置簇数,通过分裂终止条件控制簇分裂的停止,算法根据价格指数序列数据和终止条件参数自动获取簇数。

参考文献
[1] 陈娟, 余灼萍. 我国居民消费价格指数的短期预测[J]. 统计与决策, 2005, 2(2):40-41.CHEN Juan, Yu Zhuoping. Short-term forecasting of China consumer pricing index[J]. Statistics and Decision, 2005:2(2) 40-41. (in Chinese)
[2] Nordhaus WD. Quality changes in price indexes[J]. Journal of Economic Perspectives, 1998, 12(1):59-68.
[3] Koch B. E-Invoicing/EBilling:International market overview & forecast[R]. Deutsch:Billentis, 2014.
[4] Fu T. A review on time series data mining[J]. Engineering Application of Artificial Intelligence, 2011, 24(1):164-181.
[5] Plant C, Wohlschlager AM, Zherdin A. Interaction-based clustering of multivariate time series[C]//Ninth IEEE international conference on data mining. Miami, FL, USA:IEEE Press, 2009, 914-909.
[6] De Luca G, Zuccolotto P, A tail dependence-based dissimilarity measure for financial time series clustering[J]. Advances in Data Analysis and Classification, 2011(5):323-340.
[7] D'Urso P, Cappelli C, Di Lallo D, et al. Clustering of financial time series[J]. Physica A:Statistical Mechanics and its Applications, 2013, 392(9):2114-2129.
[8] Fong S. Using hierarchical time series clustering algorithm and wavelet classifier for biometric voice classification[J/OL].[2014-10-18]. http://www.hindawi.com/journals/bmri/2012/215019/.
[9] Ji M, Xie F, Ping Y. A dynamic fuzzy cluster algorithm for time series[J]. Abstract & Applied Analysis, 2013, 51(2):1781-1801.
[10] Duru O, Bulut E. A non-linear clustering method for fuzzy time series:Histogram damping partition under the optimized cluster paradox[J]. Applied Soft Computing, 2014, 24:742-748.
[11] Scotto M, Alonso A, Barbosa S. Clustering time series of sea levels:Extreme value approach[J]. Journal of Waterway, Port, Coastal, and Ocean Engineering, 2014, 136(4):215-225.
[12] Liao W. Clustering of time series data:A survey[J]. Pattern Recognization, 2005, 38:1857-1874.
[13] Han J, Kamber M, Pei J. 数据挖掘:概念与技术[M]. 3版. 范明, 孟晓峰, 译. 北京:机械工业出版社, 2012. Han J, Kamber M, Pei J. Data Mining:Concepts and Techniques[M]. 3rd ED. FAN Ming, MENG Xiaofeng, translate. Beijing:China Machine Press, 2012. (in Chinese)
[14] Rodrigues PP, Gama J, Pedroso JP. Hierarchical clustering of time series data streams[J]. IEEE Transaction on Knowledge and Data Engineering, 2008, 20(5):615-627.
[15] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[C]//Proceedings of the first European conference on artificial life. Paris, France:MIT Press, 1991, 134-142.