TY - JOUR AU - Wan, Renxia AU - Chen, Jingchao AU - Wang, Lixin AU - Su, Xiaoke PY - 2009/12/15 Y2 - 2024/03/29 TI - PNMBG: Point Neighborhood Merging with Border Grids JF - Journal of Information and Organizational Sciences JA - J. inf. organ. sci. (Online) VL - 33 IS - 2 SE - Articles DO - UR - //jios.foi.hr/index.php/jios/article/view/118 SP - AB - <span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-bidi-font-weight: bold;" lang="EN-US">The special clustering algorithm is attractive for the task of grouping arbitrary shaped database into several proper classes. Up to now, a wide variety of clustering algorithms designed for this task have been proposed, the majority of these algorithms is density-based. But the effectivity and efficiency still is the great challenges for these algorithms as far as the clustering quality of such task is concerned. </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA; mso-bidi-font-weight: bold;" lang="EN-US">In this paper, we</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-bidi-font-weight: bold;" lang="EN-US"> propose an arbitrary shaped clustering method with border grids (PNMBG),</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA; mso-bidi-font-weight: bold;" lang="EN-US"> </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-bidi-font-weight: bold;" lang="EN-US">PNMBG</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US"> is a crisp partition method. It groups objects </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US">to point neighborhoods</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US"> first</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US">ly</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US">, and then</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US"> </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US">iterati</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US">vely</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US"> merges</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US"> these </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US">point neighborhoods</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US"> into </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US">clusters</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US"> </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US">via</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US"> grids</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US">, only bordering grids are considered during the merging stage. </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US">Experiments show that </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-bidi-font-weight: bold;" lang="EN-US">PNMBG</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US"> has a good efficiency </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US">especially</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US"> on the database with high dimension. In general, </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-bidi-font-weight: bold;" lang="EN-US">PNMBG</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US"> outperforms DBSCAN in the term of efficiency</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US"> and has an almost same </span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: EN-US; mso-bidi-language: AR-SA;" lang="EN-US">effectivity</span><span style="font-size: 11pt; font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 10.5pt; mso-fareast-font-family: 宋体; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA;" lang="EN-US"> with the later.</span> ER -