文章快速检索     高级检索
  重庆邮电大学学报(自然科学版)  2018, Vol. 30 Issue (6): 848-854  DOI: 10.3979/j.issn.1673-825X.2018.06.017
0

引用本文 

于晓飞, 葛洪伟. 噪声环境下复杂流形数据的势能层次聚类算法[J]. 重庆邮电大学学报(自然科学版), 2018, 30(6): 848-854. DOI: 10.3979/j.issn.1673-825X.2018.06.017.
YU Xiaofei, GE Hongwei. Hierarchical clustering algorithm based on potentialin complex flow data sets with noise[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2018, 30(6): 848-854. DOI: 10.3979/j.issn.1673-825X.2018.06.017.

基金项目

江苏省普通高校研究生科研创新计划项目(KYLX16_0781);江苏省普通高校研究生科研创新计划项目(KYLX16_0782);江苏省高校优势学科建设工程项目

通信作者

葛洪伟 ghw8601@163.com

作者简介

于晓飞(1992—),女,吉林吉林人,硕士研究生,主要研究方向为模式识别与人工智能。E-mail: 850254450@qq.com; 葛洪伟(1967—),男,江苏无锡人,教授,博士,主要研究方向为人工智能、模式识别和图像处理等。E-mail:ghw8601@163.com

文章历史

收稿日期: 2017-11-15
修订日期: 2018-10-19
噪声环境下复杂流形数据的势能层次聚类算法
于晓飞1,2, 葛洪伟1,2     
1. 江南大学 轻工过程先进控制教育部重点实验室,江苏 无锡 214122;
2. 江南大学 物联网工程学院,江苏 无锡 214122
摘要: 基于势能的快速凝聚层次聚类算法使用一种全新的相似性度量准则,可以更高效地得到聚类结果。针对该算法无法有效处理含噪声的复杂流形数据的缺陷,提出噪声环境下复杂流形数据的势能层次聚类算法。通过势能递增曲线识别噪声点,在新定义的势能最大、最小2层数据上进行自动聚类,以确定类簇的大体框架,并在此基础上对整个数据集进行层次聚类。人工数据集上的实验表明,新算法可以有效处理噪声环境下复杂流形数据;真实数据集上的实验表明,新算法具有更优的聚类效果。
关键词: 聚类    PHA    势能分层    层次聚类    噪声识别    
Hierarchical clustering algorithm based on potentialin complex flow data sets with noise
YU Xiaofei1,2 , GE Hongwei1,2     
1. Key Laboratory of Advanced Process Control for Light Industry, Ministry of Education, Jiangnan University, Wuxi 214122, P. R. China;
2. School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, P. R. China
Foundation Items: The Research Innovation Program for College Graduate of Jiangsu Province(KYLX16_0781);The Research Innovation Program for College Graduate of Jiangsu Province(KYLX16_0782);The Foundation of Priority Academic Program Development of Jiangsu Higher Education Institutions
Abstract: Potential-based hierarchical agglomerative (PHA) clustering uses a new similarity metric to get clustering results more efficiently. Aiming at the problem that PHA can not effectively deal with the complex structure data sets with noise, we proposed a hierarchical clustering algorithm based on potential in complex flow data sets with noise. Firstly, the noise points were identified by means of the potential increase curve; Secondly, the maximum and minimum layers of the data set based on potential were defined, and these two data layers were made to cluster automatically to determine the general framework of the clusters; Finally, clustering of the entire data set was hierarchied based on the precious clustering results. The experiments on artificial data sets show that the new algorithm can deal with the complex flow data sets with noise effectively. The experiments on real data sets show that the new algorithm can get the better clustering results.
Keywords: clustering    potential-based hierarchical agglomerative (PHA)    potential hierarchy    hierarchical agglomerative clustering    noise recognition    
0 引言

聚类分析作为一种无监督的学习方法,是数据挖掘中的一项重要任务,它按照一定的规则将数据划分成若干类,使相同类数据尽可能相似,不同类数据尽可能相异[1]。聚类分析既可以作为独立的数据挖掘工具来对数据进行分析,也可以作为其他数据挖掘算法的预处理过程,其在生物信息、信息检索、机器学习、人工智能等领域有着重要作用[2-3]

目前聚类分析已经吸引了大量的研究目光,有许多经典的聚类算法被提出,如基于划分方法的K-means[4-5],K-mediods[6]等,这些算法虽然简单快速,但聚类结果对初始类簇中心的选取有一定的依赖;基于层次的聚类方法如Cure[7],Chameleon[8]等,这些算法虽可检测非球形簇,但算法过程相对复杂,在具体应用中都存在一定的局限性;基于密度的聚类方法如DBSCAN[9],OPTICS[10]等,这些算法虽然可以发现任意形状的簇,但对于参数十分敏感;基于网格的聚类方法如STING[11],WAVECLUSTER[12]等,这些聚类算法虽有较好的聚类效果,但处理时间与空间所划分单元数有关,一定程度上降低了聚类的质量和准确度。

Yonggang Lu等[13]提出一种基于势能的聚类(clustering by sorting potential values,CSPV)算法,该算法虽提出了基于势能的相似性度量准则,但聚类效果完全依赖于对参数B的选取。针对这一问题,Yonggang Lu等[14]于2013年在《Pattern Recognition》上提出了一种基于势能的快速凝聚层次聚类(potential-based hierarchical agglomerative clustering,PHA)算法。该算法十分便捷高效,首先依据各点的势能和与父节点的距离构造边缘加权树,然后依据树中权值大小使用层次聚类得到最终的聚类结果。PHA算法使用全新的相似性度量准则,并与凝聚层次聚类相结合,在时间上更快速,在精度上可以得到更好的聚类效果。

PHA算法虽然具有上述优点,但该算法只能处理一些结构简单的、簇内势能大小分布明显不同的球形簇,无法处理一些复杂的流形结构簇,而且聚类结果易受到噪声数据的影响。针对这一缺陷,本文提出了噪声环境下复杂流形数据的势能层次聚类算法(hierarchical clustering based on potential in complex flow data with noise,HCPC)。首先,根据势能递增曲线确定势能阈值,找到数据集中的噪声点;其次,在非噪声数据点上,定义出势能最大、最小2层数据,并基于势能的分布特点,提出分层聚类的方法,以确定类簇的大体框架;最后,在分层聚类结果的基础上,对正常点使用层次聚类,同时将噪声点聚到距离自身最近的类簇中去。实验表明,HCPC算法不仅可以识别噪声点,而且能有效地处理复杂的流形数据集,同时在真实数据集上具有更优的聚类效果。

1 PHA算法及其缺陷分析 1.1 PHA算法

PHA算法[14]认为,数据点的势能大小与其概率密度分布是密切相关的。该算法首先根据重力势能的物理意义来计算每个数据的势能。其中,每2点之间的势能Φij定义为

$ {\mathit{\Phi }_{ij}}({r_{ij}}) = \left\{ \begin{array}{l} - \frac{1}{{{r_{ij}}}}, \;\;\;\;\;{\rm{若}}{r_{ij}} \ge \delta \\ - \frac{1}{\delta }, \;\;\;\;\;{\rm{若}}{r_{ij}} < \delta \end{array} \right. $ (1)

(1) 式中:rij是点i与点j之间的欧式距离;δ用来避免分母为零的情况出现。δ的计算方式为

$ Min{D_i} = \mathop {{\rm{min}}}\limits_{{r_{ij}} \ne 0, j = 1, \ldots , N} ({r_{ij}}) $ (2)
$ \delta = mean\left( {Min{D_i}} \right)/S $ (3)

(2)—(3)式中:MinDi是点i到其他各点的最短距离;N是数据点的个数;S是一个尺度因子[14],一般设为10。

计算了每2点之间的势能Φij后,每个点的势能Φi定义为

$ {\mathit{\Phi }_i} = \sum\limits_{j = 1}^N {{\mathit{\Phi }_{ij}}({r_{ij}})} $ (4)

文献[14]中使用Parzen窗口函数[15]这一非参数估计方法来证明势能和概率密度分布的关系。在Parzen窗口函数中概率密度的定义为

$ {\hat p_N}(i) = \frac{1}{N}\sum\limits_{j = 1}^N {{\mathit{\Phi }_{ij}}({r_{ij}})} $ (5)

(5) 式中,N表示数据点总数。

文献[14]经过证明得到

$ {\mathit{\Phi }_{ij}} = \left( { - N/\alpha } \right){{\hat p}_N}(i) $ (6)

即势能和概率密度函数成反比,其中,α是归一化因子,它的主要作用是确保窗口函数在所有特征空间上的积分为1。因此,势能可以反映数据点的分布情况,如势能越小的点的周围数据点分布越密集。

将势能从小到大排序,并以势能最小的点作为根节点,构造边缘加权树,其他数据点寻找自身的父节点。其中,父节点定义为

$ parent\left[ i \right] = \mathop {{\rm{argmin}}}\limits_k ({r_{k, i}}|{\mathit{\Phi }_k} \le {\mathit{\Phi }_i}\;AND\;k \ne i) $ (7)

即势能小于点i且与i距离最近的点为其父节点。

i到父节点parent[i]的距离ρi

$ {\rho _i} = {r_{i, parent\left[ i \right]}} $ (8)

在边缘加权树中,每个数据点与父节点之间的权值为两者的距离。在树构造完成后,使用凝聚层次聚类算法进行聚类,得到聚类结果。

1.2 PHA算法缺陷分析

PHA算法虽然十分便捷快速,但其只能处理一些簇内势能分布明显不均匀的数据集如图 1所示。然而,针对一些复杂的流形数据集,PHA算法无法得到理想的聚类结果。

图 1 DS1数据集 Figure 1 DS1 data set

其原因在于一些复杂的数据集簇内势能分布较均匀,无明显差异,缺陷分析示例如图 2所示。图 2a中,该数据集中2个环形簇的簇内势能分布相对均匀,且中间的团状簇势能整体偏小。PHA算法在构建树的过程中,环形簇上的点会错误地选取中间的团簇上的点作为父节点;图 2b中,以点abc为例:Φ(a)<Φ(b),Φ(a)<Φ(c),但由于r(a, b)<r(a, c),因此,点a错误地选择点b为父节点。PHA算法的上述缺陷导致其只能得到如图 2b错误的聚类结果。

图 2 缺陷分析示例 Figure 2 Defect example analysis

同时,针对含噪声的数据集,由于PHA算法在聚类过程中没有对噪声数据进行处理,导致其聚类结果易受到噪声数据的影响,无法得到正确的聚类结果。

2 含噪声的复杂流形数据的势能层次聚类 2.1 识别噪声点

HCPC算法采用构造势能递增曲线的方法识别噪声点。一般情况下,由于各数据集中噪声点的数量远少于正常数据点,且噪声点的分布相对稀疏,因此其势能较大。噪声点判定如图 3所示,在势能递增曲线上,噪声点与正常点之间存在一个拐点,图 3a中的点C即为图 3b中数据集的拐点,拐点之前的点为正常点,拐点之后的点为噪声点,图 3b中的星型点为该数据集被识别的噪声点。

图 3 噪声点判定 Figure 3 Determination of noise points
2.2 势能的分层

基于对重力势能物理意义的分析发现,势能可以反映数据点的分布情况[14]。势能分布图如图 4所示,势能大小由内向外逐层递增,边缘点的势能最大,中心点的势能最小。与此同时,受文献[16]中分层聚类的启发,提出依据势能将数据点分层聚类的方法。

图 4 势能分布图 Figure 4 Graph ofpotential field

定义1  势能最大层数据集Smax定义为

$ {S_{\max }} = \left\{ {i|{\mathit{\Phi }_i} \ge {\mathit{\Phi }_n}} \right\} $ (9)

定义2  势能最小层数据集Smin定义为

$ {S_{\min }} = \left\{ {i|{\mathit{\Phi }_i} \le {\mathit{\Phi }_p}} \right\} $ (10)

(9)—(10)式中:Φn为去除噪声点后,势能从大到小排序后,第$ \left\lfloor {N' \times 0.25} \right\rfloor $个数据[16]Φp为势能从小到大排序后,第$ \left\lfloor {N' \times 0.25} \right\rfloor $个数据[16]

假设通过势能递增曲线确定的噪声点总数为n,正常点总数为N

$ N' = N - n $ (11)

图 1图 2a所示的2个数据集为例,分别取势能最大、最小2层数据,如图 5图 6中星形点所示。由图 5图 6可见,势能最大层的数据一般处于类边缘位置,或某类数据的势能整体较大;而势能最小层的数据一般处于中心位置,或某类数据的势能整体较小。

图 5 DS1分层 Figure 5 Layer of DS1
图 6 DS2分层 Figure 6 Layer of DS2

基于上述分析,分别将最大、最小层数据进行单独聚类,可以确定类簇的大致轮廓。因此,依据文献[17]中介绍的方法,通过势能和与父节点距离的乘积γi来自动聚类,其中,γi定义[17]

$ {\gamma _i} = |{\mathit{\Phi }_i}|\cdot{\rho _i} = - {\mathit{\Phi }_i}\cdot\rho $ (12)

2层数据的聚类结果如图 7所示,图 7中黑色圆点为未聚类数据点。

图 7 分层聚类结果 Figure 7 Clustering result of hierarchy clustering

最后使用最小类间距离测度将得到的子簇与剩余数据进行层次聚类,得到如图 8所示的聚类结果。

图 8 DS1与DS2聚类结果 Figure 8 Clustering results of DS1 and DS2

综上所述,HCPC算法通过依据势能分层聚类,不仅可以自适应地识别噪声点,而且能够有效处理复杂的流形数据集。

2.3 HCPC算法步骤

HCPC算法流程简单描述如下。

步骤1  由(1)—(4)式计算出每个数据点的势能Φi,并排序;

步骤2  根据势能大小构造势能递增曲线,找到拐点,识别噪声点;

步骤3  由定义1、定义2确定最大、最小层数据;

步骤4  分别在最大、最小2层数据内依据(7)式确定每个数据点的父节点parent[i],并由(8)式计算各层中的数据点到自身父节点的距离ρi

步骤5  分别在2层数据集内由(12)式计算各点的γi值,使用文献[17]中介绍的算法分别对2层数据进行自动聚类;

步骤6  在步骤5的聚类结果基础上,对整个数据集采用最小类间距离测度进行层次聚类,直到所有正常数据点的类别都确定为止;

步骤7  最后,将步骤2确定的噪声数据分别聚到离其最近的类别中去。

2.4 算法复杂度分析

HCPC算法的时间复杂度主要由3部分组成:计算势能和距离;在最大、最小层数据上对γi值分类;使用最小类间距离进行层次聚类。假设数据点个数为n,则计算势能和距离的时间复杂度为O(n2),在最大、最小2层数据上对γi值分类的时间复杂度为O(n),最后层次聚类的时间复杂度为O(n2),因此,HCPC算法的时间复杂度为O(n2)。文献[14]中介绍PHA算法的时间复杂度为O(n2),可见,HCPC算法在没有增加算法时间复杂度的同时,提高了算法的聚类效果。

3 实验分析

为了验证HCPC算法的性能,分别在人工数据集和UCI[18]数据集上与PHA算法[14],CSPV(基于排序势能的聚类算法)[13]进行对比实验。

3.1 人工数据集的实验结果分析

表 1中,DS为Data Set的缩写,其中,DS1由3组服从标准正态分布的随机数构成,各组的中心数据点分别为(0, 0),(3, 5)和(6, 0),每组有300个数据,如1.2节中图 1;DS2由2个环状簇和1个团状簇构成,如1.2节中图 2a;DS3由1个流形簇和2个团状簇构成,如图 9a;DS4为2个流形簇相互缠绕所构成,如图 9b(为证实HCPC算法能够处理噪声环境的复杂流形数据,特在DS3,DS4数据集上添加噪声点)。

表 1 4个人工数据集信息 Table 1 Four synthetic data sets
图 9 DS3,DS4数据集 Figure 9 DS1 and DS2 data sets

基于欧氏距离测度,分别使用PHA,HCPC,CSPV 3种算法对表 1中的4个数据集进行实验。其中,图 10图 11分别为PHA和CSPV算法得到的聚类结果,由图 10图 11可知,PHA和CSPV算法只能在类似DS1的球形数据集上得到正确的聚类结果,而无法处理复杂的流形数据集,且针对含噪声的数据集,聚类结果易受噪声点的影响。

图 10 PHA在人工数据集的聚类结果 Figure 10 Clustering results onsynthetic datasets by PHA
图 11 CSPV在人工数据集的聚类结果 Figure 11 Clustering results on synthetic datasets by CSPV

图 12为HCPC算法得到的聚类结果,该算法首先识别噪声数据,然后根据势能分层聚类,确定了类簇的边缘与中心部分,最后在不受噪声数据的影响下得到正确的聚类结果。由图 12a可见,针对类内势能分布明显不均匀的团簇结构,3种算法都可以得到正确的聚类结果;而针对PHA算法与CSPV算法无法处理的类内势能分布均匀、类间势能分布差异明显的DS2数据集,HCPC算法亦能得到正确的聚类结果。

图 12 HCPC在人工数据集的聚类结果 Figure 12 Clustering results on synthetic datasets by HCPC

针对含噪声的复杂数据集DS3,DS4,PHA算法与CSPV算法无法识别噪声点,而且受噪声点的影响,最终没有得到正确的聚类结果(见图 10图 11);但通过HCPC算法可以识别噪声点并有效处理这一类数据集。

由此可见,HCPC算法不仅保留了PHA算法快速高效的优点,还解决了该算法无法有效处理噪声环境下复杂流形数据的缺陷。

3.2 真实数据集的实验结果分析

为了进一步验证HCPC算法的性能,选取了5个UCI[18]数据集与PHA算法、CSPV算法进行实验对比,如表 2所示。

表 2 5个真实数据集信息 Table 2 Five real data sets

同时,使用FMIndex[19],F1-measure[20]和ARI[21]3种聚类评价指标来衡量种算法的聚类效果。3种指标值的取值均为[0, 1],数值越大,表示聚类效果越好。实验结果如表 3表 5所示(各指标的最大值用下横线标出)。

表 3 PHA算法在真实数据集上的聚类指标值 Table 3 Index values of PHA on real data sets
表 4 HCPC算法在真实数据集上的聚类指标值 Table 4 Index values of HCPC on real data sets
表 5 CSPV算法在真实数据集上的聚类指标值 Table 5 Index values of CSPV on real data sets

表 3表 4中的数据可见,与PHA算法相比,在iris数据集上,2种算法的各聚类指标值相等;在letter数据集上,虽然PHA算法的ARI聚类指标值高于HCPC算法,但在其余2种聚类指标值上均为HCPC算法更高;除此之外,在剩余的3个数据集上,HCPC的3种聚类指标值均高于PHA算法。产生上述结果的原因:一方面,HCPC算法对噪声数据进行了识别,聚类结果不受噪声数据的影响;另一方面,HCPC算法采用势能分层的思想,可以得到更优的聚类效果。

表 4表 5中的数据可见,与CSPV算法相比,在iris数据集上,2种算法的各聚类指标值相等;在letter数据集上,虽然CSPV算法的3种聚类指标值最高,但该算法是在选取了最优参数B值的前提下得到上述聚类结果,且聚类数目远远高于HCPC算法;在vowel数据集上,虽然CSPV算法的ARI指标值高于HCPC算法,但另外2种指标值上均为HCPC算法更高;除此之外,在剩余的glass与wine数据集上,HCPC算法的3种聚类指标值均为最高。

整体而言,HCPC算法能够得到更优的聚类结果,具有更高的准确度。

4 结束语

针对PHA算法无法有效处理流形数据集且对噪声数据敏感的缺陷,本文提出了HCPC算法。与PHA算法相比,HCPC算法在保留原算法快速高效的优势的前提下,不仅弥补了PHA算法的不足,而且可以得到更优的聚类效果。然而,由于HCPC算法采用了欧氏距离的距离测度方法,不利于其处理一些维度较高的数据集。因此,如何使HCPC算法可以在高维数据集上得到更好的聚类结果,将是下一步的研究工作。

参考文献
[1]
WILLIAMSON B, GUYON I. Clustering: science or art?[J]. Mach Learn Res, 2012, 27(2): 65-80.
[2]
张勇, 王庆, 夏长红, 等. 离散多目标量子微粒群聚类算法[J]. 模式识别与人工智能, 2017, 30(3): 204-213.
ZHANG Yong, WANG Qing, XIA Changhong, et al. Discrete Multi-objective Quantum Particle Swarm Optimization Clustering Algorithm[J]. Pattern Recognition and Artificial Intelligence, 2017, 30(3): 204-213.
[3]
朱杰, 陈黎飞. 核密度估计的聚类算法[J]. 模式识别与人工智能, 2017, 30(5): 439-447.
ZHU Jie, CHEN Lifei. Clustering Algorithm with Kernel Density Estimation[J]. Pattern Recognition and Artificial Intelligence, 2017, 30(5): 439-447.
[4]
JAINA K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition, 2010, 31(8): 651-666. DOI:10.1016/j.patrec.2009.09.011
[5]
VELMURUGAN T. Performance based analysis between k-Means and Fuzzy C-Means clustering algorithms for connection oriented telecommunication data[J]. APPLIED SOFT COMPUTING, 2014, 19(46): 134-146.
[6]
PARK H S, JUN C H. A simple and fast algorithm for K-medoids clustering[J]. Expert Systems with Applications, 2009, 36(2): 3336-3341.
[7]
GUHAS. Cure: an efficient clustering algorithm for large databases[C]//Proceeding of the ACM SIGMOD International Conference on Management of Data.New York: Information Systems, 1998: 73-84.
[8]
WILCOX H, NICHOL R C, ZHAO G B. Simulation tests of galaxy cluster constraints on chameleon gravity[J]. Monthly Notices of the Royal Astronomical Society, 2016, 452(2): 715-725.
[9]
VISWANATH P, BABU S V. Rough-DBSCAN:A fast hybrid density based clustering method for large data sets[J]. Pattern Recognition Letters, 2009, 30(16): 1477-1488. DOI:10.1016/j.patrec.2009.08.008
[10]
KALITA H K. A New Algorithm for Ordering of Points to Identify Clustering Structure Based on Perimeter of Triangle: OPTICS(BOPT)[C]//ladcom. IEEE Computer Society.New York: IEEE Press, 2007: 523-528.
[11]
ANSARI S, CHETLUR S, PRABHU S, et al. An Overview of Clustering Analysis Techniques used in Data Miniing[J]. International Journal of Emerging Technology and Advanced Engineering, 2013, 3(12): 284-286.
[12]
AMINI A, WAH T Y, SAYBANI M R, et al. A study of density-grid based clustering algorithms on data streams[C]//Fuzzy Systems and Knowledge Discovery (FSKD), 2011 Eighth International Conference on.New York: IEEE Press, 2011, 3: 1652-1656.
[13]
YONGGANG Lu, YI Wan. Clustering by Sorting Potential Values(CSPV):A novel potential-based clustering method[J]. Pattern Recognition, 2012, 45(9): 3512-3522. DOI:10.1016/j.patcog.2012.02.035
[14]
YONGGANG Lu, YI Wan. PHA: A fast potential-based hierarchical agglomerative clustering method[J]. Pattern Recognition, 2013, 46(5): 1227-1239. DOI:10.1016/j.patcog.2012.11.017
[15]
PARZEN E. On estimation of a probability density function and mode[J]. Annals of Mathematical Statistic, 1962, 33(07): 1065-1076.
[16]
LI Caiyun, WAN Yi. Research on Improved Hierarchical Clustering Algorithm Based on Density[D]. Lanzhou: Lanzhou University, 2016.
[17]
于晓飞, 葛洪伟. 自动确定聚类中心的势能聚类算法[J]. 计算机科学与探索, 2017, 12(6): 1004-1012.
YU Xiaofei, GE Hongwei. Potential clustering by Automatic Determination of Cluster Center[J]. Journal of Frontiers of Computer Science and Technology, 2017, 12(6): 1004-1012.
[18]
LICHMAN M.UCI machine learning repository[EB/OL].(2013-12-23)[2017-10-10].http://archive.ics.uci.edu/ml.
[19]
FOWLKES E B. A method for comparing two hierarchical clusterings[J]. Journal of the American Statistical Association, 1983, 78(383): 553-569. DOI:10.1080/01621459.1983.10478008
[20]
YANG Y, JIN F, MOHAMED K. Survey of clustering validity evaluation[J]. Application Research of Computers, 2008, 25(6): 1630-1632.
[21]
VINH N X, EPPS J, BAILEYJ.Information theoretic measures for clusterings comparison: is a correction for chance necessary?[C]//Proceeding ICML'09. Proceedings of the 26th Annual International Conference on Machine Learning. Montreal, Quebec, Canada: ACM, 2009: 1073-1080.