基于相邻关系的地理标识语言空间线对象离群检测算法*

南京大学学报(自然科学版) ›› 2012, Vol. 48 ›› Issue (1): 84–90.

基于相邻关系的地理标识语言空间线对象离群检测算法*

朱娟1^.2**，吉根林^1.2

出版日期:2015-05-19 发布日期:2015-05-19
作者简介: (1.南京师范大学计算机科学与技术学院，南京，210097; 2.江苏省信息安全保密技术工程研究中心，南京，210097)
基金资助:
国家自然科学基金(40871176)

Algorithms for detecting outlier spatial lines
based on adjacent relationship for geography mark-up language data

Zhu .Juan1’2，Ji Gen一Lin1.2

Online:2015-05-19 Published:2015-05-19
About author: (1. School of Computer Science and Technology, Nanjing Normal University, Nanjing, 210097，China
2. Jiangsu Research Center of Information Security and Privacy (hechnology, Nanjing, 210097，China)

摘要/Abstract

摘要： 提出了两种基于相邻关系的地理标识语言空间线对象离群检测算法:DOL一ARl和DOL AR2，定义了基于相邻关系的空间线对象之间的相异度，DOL-ARl将基于相邻关系的相异度作为空间
线对象之I司的距离度量准则，利用Density-based Spatial Clustering of Applications with Noise算法检测出离群的空间线对象.算法DOL一AR2以基于相邻关系的相异度为准则对空间线对象进行聚类，根据每
个簇的离群因子，检测该簇是否离群.实验结果表明，算法DOL ARl和算法DOL AR2都能有效地检测出离群的线对象，本文对提出的两种离群检测算法的性能讲行了比较，发现算法DOL AR2的效率要
高于算法DOL AR1的效率.

Abstract: Outlier detection is an important problem for data mining. Outlier detection is intended to discover unexpected，interesting and useful patterns of further analysis. Spatial outlicr detection is aimed at detection of
spatial objects different from other spatial objects in their spatial attributes or topological relationships. Now, only point objects without line or polygon objects arc considered in the existing spatial outlier detection algorithms in
which different degrees on topological relationships are not included. Algorithms DOL一AR1 and DOL一AR2 are presented here for detecting outlicr lines based on adjacent relationship for GML data. Adjacent relations between
each spatial line and other spatial objects are computed firstly.The difference degree between different lines that have the same type as the previous line on adjacent relationship is defined. In algorithm DOL一AR1，the difference
degree is used as the standard of the distance between different lines. Density-based spatial clustering of applications with noise is used in algorithm DOL一ARl in order to detect outlicr spatial lines. In algorithm DOL一AR2，firstly,
cluster spatial lines by the difference degree on adjacent relationship, then define the outlicr factor of each cluster, the outlicr factor of the cluster determines whether the cluster is‘outlier’or not.The experimental results show
that algorithms DOL一AR1 and DOL一AR2 both can detect outlier lines based on adjacent relationship accurately and effectively. However, algorithm DOL一AR2 can run more effectively.

朱娟1^.2**，吉根林^1.2. 基于相邻关系的地理标识语言空间线对象离群检测算法*[J]. 南京大学学报(自然科学版), 2012, 48(1): 84–90.

Zhu .Juan1’2，Ji Gen一Lin1.2
. Algorithms for detecting outlier spatial lines
based on adjacent relationship for geography mark-up language data
[J]. Journal of Nanjing University(Natural Sciences), 2012, 48(1): 84–90.

参考文献

[1]Barnett V , Lewis T.Outlicrs in statistical data New York; John Wiley and Sons，1994.
[2]Knorr E, Ng R. Finding intensional knowledge of distance-based outliers. Proceedings of the 25^th Very Large Databases Conference Edin- burgh; Morgan Kaufman Publishers，1999,211~222
[3]Breunig M M，Kriegel H P，Ng RT，et al. Op- tics of identifying density-based local outlicrs. Proceedings of the 3rd European Conference on Principles and Practice of Knowledge Discovery
in Databases, Lecture Notes in Computer Sci- ence 1704. Prague:Springcr,1999,262一270.
[4]Prcarata F, Shamos M. Computational geome try; An introduction. Berlin; Springer- Verlag, 1988.
[5]Jagadish H V, Koudas N, Muthukrishnan S. Mining deviants in a time series databases. Pro ceedings of the 25^thVery Large Databases Con ference Edinburgh, Edinburgh:Morgan Kauf- man Publishers, 1999，102一113.
[6]Zheng J G,Jiao L C. Using deviation detection for data mining. Computer Engineering, 2011，27(8) :33-35.(郑建国，焦李成.偏差检测挖掘方法研究.计算机工程,2001,27(8): 33-35).
[7]Sheng Y J，Qing B A. Clustering-based outlier detection method. The 5^th International Confer- ence on Fuzzy Systems and Knowledge Discov- ery. Piscataway; IEEE Computer Society, 2008.429一433.
[8]Yu S Y，Shang L. An entropy-based algorithm to detect relative outlicrs; ENBROD. Journal of Nanjing University(Natural Sciences)，2008，44 (2);212-218.(于绍越，商琳.基于信息墒的
相对离群点的检测为一法:ENBROD.南京大学学报(自然科学),2008,44(2);212 -218).
[9]Xue A R,Ju S G. Outlier mining based on spa- tial constraint. Computer Science, 2007，34(6): 207-230.(薛安荣，鞠时光.基于空间约束的离群点挖掘.计算机科学，2007,34(6):207一230)
[10]Jia R Y，Qian G C, Zhang R，et al. A spatial outlier detection algorithm. Computer Science and Development, 2008，18(5):28一30.(贾瑞玉，钱光超，张然等.空间离群点的检测算法.计算机科学与发展，2008,18(5);28-30).
[11]Lu C T，Chen D C，Kou Y F. Algorithms for spatial outlicr detection. The 3^rd IEEE lnterna- tional Conference on Data Mining. Piscataway: IEEE Press,2003，19一22.
[12]Zhang S L, Yan G N，Uong J Y，et al. Geogra- phy mark-up language-Geo Web basis. Bei- jing;Science Publishing,2008,3~4.(张书亮，阎国年，龚健雅等.地理标示语言—Geo Web 基础.北京:科学出版社,2008,3一4).
[13]Chen J C，Ji G L. A space adjacent relations based GMI. point outlicr detection algorithm. Journal of Nanjing Normal University(Fngi- neering and Technology)，2009，9(1):61一63.
(陈佳春，吉根林.基于空间相邻关系的CML 点对象离群检测算法.南京师范大学学报(工程技术),2009,9(1):61-63).
[14]Li N G, Bao P M, Sha L. An algorithm for de tecting outlier region in UMI. data based on re- gion spatial inclusion relationship. Journal of Guangxi Normal University(Natural Sciences)，
2009,27(3):118-121.(李尼格，鲍培明，沙露.一种基于面包含关系的C}MI.空间离群面检测算法.广西师范大学学报(自然科学)，2009 .27(3).118-121).
[15]Ester M, Kriegel H P，Jorg S,et al. A density- based algorithm for discovering clustering in large spatial databases with noise. Proceedings of the 2^nd Conference on Knowledge Discovery in Databases. Piscataway; IEEE Press, 1996，226一231.
[16]Yang N,Ji G L. A spatial lines clustering algo- rithm based on adjacent relation for GML data. Proceedings of 2009 international Conference on information Engineering and Computer Science, 2009，3593一3596.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed