클러스터 중심 결정 방법을 개선한 K-Means 알고리즘의 구현

이신원,오형진,안동언,정성종,Lee Shin-Won,Oh HyungJin,An Dong-Un,Jeong Seong-Jong 한국정보처리학회 2004 정보처리학회논문지B Vol.11 No.7

K-Means algorithm is a non-hierarchical (plat) and reassignment techniques and iterates algorithm steps on the basis of K cluster centroids until the clustering results converge into K clusters. In its nature, K-Means algorithm has characteristics which make different results depending on the initial and new centroids. In this paper, we propose the modified K-Means algorithm which improves the initial and new centroids decision methodologies. By evaluating the performance of two algorithms using the 16 weighting scheme of SMART system, the modified algorithm showed $20{\%}$ better results on recall and F-measure than those of K-Means algorithm, and the document clustering results are quite improved. K-Means 알고리즘은 재배치 기법의 일종으로 K개의 초기 센트로이드를 중심으로 K개의 클러스터가 될 때까지 클러스터링을 반복하는 것이다. 알고리즘의 특성상 K-Means 알고리즘은 초기 클러스터 센트로이드(중심) 및 클러스터 중심을 결정하는 방법에 따라 다른 클러스터링 결과를 얻을 수 있다. 본 논문에서는 K-Means 알고리즘을 이용한 초기 클러스터 중심 및 클러스터 중심을 결정하는 방법을 개선한 변형 K-Means 알고리즘을 제안한다. 제안한 알고리즘의 평가를 위하여 SMART 시스템의 16가지 가중치 계산 방식을 이용하여 성능을 평가한 결과 변형 K-Means알고리즘이 K-Means 알고리즘보다 재현률과 F-Measure에서 $20{\%}$이상 향상된 결과를 얻을 수 있었으며 특정 주제 아래 관련 문서가 할당되는 클러스터링 성능이 우수함을 알 수 있었다.

맵리듀스를 이용한 다중 중심점 집합 기반의 효율적인 클러스터링 방법

강성민(Sungmin Kang),이석주(Seokjoo Lee),민준기(Jun-ki Min) 한국정보과학회 2015 정보과학회 컴퓨팅의 실제 논문지 Vol.21 No.7

데이터 사이즈가 증가함에 따라서 대용량 데이터를 분석하여 데이터의 특성을 파악하는 것이 매우 중요해졌다. 본 논문에서는 분산 병렬 처리 프레임워크인 맵리듀스를 활용한 k-Means 클러스터링 기반의 효과적인 클러스터링 기법인 MCSK-Means (Multi centroid set k-Means)알고리즘을 제안한다. k-Means 알고리즘은 임의로 정해지는 k개의 초기 중심점들의 위치에 따라서 클러스터링 결과의 정확도가 많은 영향을 받는 문제점을 가지고 있다. 이러한 문제를 해결하기 위하여, 본 논문에서 제안하는 MCSK-Means 알고리즘은 k개의 중심점들로 이루어진 m개의 중심점 집합을 사용하여 임의로 생성되는 초기 중심점의 의존도를 줄였다. 또한, 클러스터링 단계를 거친 m개의 중심점 집합들에 속한 중심점들에 대하여 직접 계층 클러스터링 알고리즘을 적용하여 k개의 클러스터 중심점들을 생성하였다. 본 논문에서는 MCSK-Means 알고리즘을 맵리듀스 프레임워크 환경에서 개발하여 대용량 데이터를 효율적으로 처리할 수 있도록 하였다. As the size of data increases, it becomes important to identify properties by analyzing big data. In this paper, we propose a k-Means based efficient clustering technique, called MCSKMeans (Multi centroid set k-Means), using distributed parallel processing framework MapReduce. A problem with the k-Means algorithm is that the accuracy of clustering depends on initial centroids created randomly. To alleviate this problem, the MCSK-Means algorithm reduces the dependency of initial centroids using sets consisting of k centroids. In addition, we apply the agglomerative hierarchical clustering technique for creating k centroids from centroids in m centroid sets which are the results of the clustering phase. In this paper, we implemented our MCSK-Means based on the MapReduce framework for processing big data efficiently.

다목적 유전자 알고리즘을 이용한문서 클러스터링

이정송(Jung Song Lee),박순철(Soon Cheol Park) 한국산업정보학회 2012 한국산업정보학회논문지 Vol.17 No.2

본 논문에서는 텍스트 마이닝 분야에서 중요한 부분을 차지하고 있는 문서 클러스터링을 위하여 다목적 유전자 알고리즘을 제안한다. 문서 클러스터링에 있어 중요한 요소 중 하나는 유사한 문서를 그룹화 하는 클러스터링 알고리즘이다. 지금까지 문서 클러스터링에는 k-means 클러스터링, 유전자 알고리즘 등을 사용한 연구가 많이 진행되고 있다. 하지만 k-means 클러스터링은 초기 클러스터 중심에 따라 성능 차이가 크며 유전자 알고리즘은 목적 함수에 따라 지역 최적해에 쉽게 빠지는 단점을 갖고 있다. 본 논문에서는 이러한 단점을 보완하기 위하여 다목적 유전자 알고리즘을 문서 클러스터링에 적용해 보고, 기존의 알고리즘과 정확성을 비교 및 분석한다. 성능 시험을 통해 k-means 클러스터링(약 20%)과 기존의 유전자 알고리즘(약 17%)을 비교할 때 본 논문에서 제안한 다목적 유전자 알고리즘의 성능이 월등하게 향상됨을 보인다. In this paper, the multi-objective genetic algorithm is proposed for the document clustering which is important in the text mining field. The most important function in the document clustering algorithm is to group the similar documents in a corpus. So far, the k-means clustering and genetic algorithms are much in progress in this field. However, the k-means clustering depends too much on the initial centroid, the genetic algorithm has the disadvantage of coming off in the local optimal value easily according to the fitness function. In this paper, the multi-objective genetic algorithm is applied to the document clustering in order to complement these disadvantages while its accuracy is analyzed and compared to the existing algorithms. In our experimental results, the multi-objective genetic algorithm introduced in this paper shows the accuracy improvement which is superior to the k-means clustering(about 20 %) and the general genetic algorithm (about 17 %) for the document clustering.

내비게이션 데이터를 활용한 시간대 그룹별 통행량 집중률 분포 패턴 분석

송용욱,김익기,남호현,박상준 대한교통학회 2021 대한교통학회지 Vol.39 No.3

This study was intended to verify the hypothesis that there is a difference in the choice of start time by travel distance and the behavioral hypothesis that such difference in departure time results in differences in vehicle trip distribution patterns by time range using actual measurement data of navigation. In the current, when estimating traffic demand, use AAWDT (Annual Average WeekDay Traffic) estimated from household traffic survey sample data to estimate traffic pattern by applying the ratio of peak and non-peak vehicle trip. However, it is thought that estimating the concentration ratio of roads with uniform rate of peak and non-peak regardless of travel distance (travel time) to analyze the network path will differ significantly from the actual traffic patterns. This study proposes a more realistic method of estimating by reflecting the traffic patterns which difference in peak and non-peak time due to differences in departure time by distance using actual measurement data of navigation. in the network analysis. This study use SK T-map data, which has the highest share of navigation service in Korea, of 261 day on weekdays during one year. SAS (statistical package program) and RapidMiner (data mining platform) were used as analysis tools to construct k-means clustering. Based on actual navigation data, interregional travel distance was divided into seven groups to have similar characteristics, and the average traffic rate was calculated by the distance groups. By grouping and simplifying similar traffic patterns such as peak, non-peak and night using 24-hours traffic concentration rate data from derived seven distance group, a study was conducted on how to most realistically express traffic patterns. In other word, using the 24-hour traffic concentration rate of seven distance groups, through the k-means clustering analysis from k=2 to k=5, the time zone with similar traffic pattern of concentration was divided into one group. The results of BIC, Elbow, Silhouette, correlation coefficient analysis by k-means clustering result, slope, and value of non-segmented simple regression model were compared according to k value. As a result of this study, it was found that it is best to classified traffic pattern by time into three groups. In addition, it proposed a method of building OD data to enable network analysis that reflected the classification of travel distance and traffic concentration ratio patterns obtained from the research results. It is expected that a more realistic analysis of the traffic patterns of time bands on roads where short, medium and long distance traffic is mixed when performing a traffic assignment based on OD data which reflecting differences in departure time by travel distance. 이 연구는 내비게이션의 실측 데이터를 이용하여 지역 간 통행에 있어 통행거리별로 출발시각 선택에 차이가 있다는 가설과 이와 같은 출발시각 차이는 통행거리별로 시간대별 교통량 분포패턴의 차이를 야기한다는 행태적 가설을 검증하고자 하였다. 현재 교통수요추정 시 가구통행실태조사 표본자료를 전수화하여 추정된 AAWDT(Annual Average WeekDay Traffic)를 이용하여 첨두 ‧ 비첨두의 집중률을 적용하여 교통패턴을 추정 분석하고 있다. 하지만 이와 같이 통행거리(통행시간)에 상관없이 획일적 첨두 및 비첨두 집중률을 적용하여 네트워크 노선배정분석을 하여 각 도로구간의 첨두시, 비첨두시의 교통량을 추정하는 것은 현실적 통행패턴과는 차이가 클 것으로 고려된다. 그래서 본 연구에서는 현실에서 실측 조사된 내비게이션 자료로부터 통행거리별 출발시각의 차이로 인한 첨두시간대의 차이를 네트워크 분석에 반영함으로써 출발시각 시점을 기준으로 첨두시와 비첨두시의 집중률 패턴을 좀 더 현실적으로 추정하는 방법을 제안한다. 본 연구에서 사용한 자료는 현재 국내 내비게이션 서비스 중 가장 높은 점유율을 확보하고 있는 SK T-map 자료이며, 2016년의 평일 261일의 자료를 사용하였다. 적용한 분석도구는 통계 패키지 프로그램인 SAS와 데이터 마이닝 플랫폼인 RapidMiner를 이용하여 k-means 클러스터링을 실시하였다. 내비게이션 실측자료를 기반으로 지역 간 통행의 통행거리를 통행특성이 유사하도록 거리별 7개의 그룹으로 구분하였으며, 구분한 거리별 그룹에 대해 시간대별 평균 교통량 비율을 산출하였다. 위에서 구한 통행거리별 7개 그룹의 출발시간 기준 24시간 교통량 집중률 자료를 활용하여 그룹별 시간대를 첨두, 비첨두 및 심야로 구분하는 것과 같이 유사 교통패턴을 그룹화 및 단순화하여 시간대별 분포패턴을 가장 현실적으로 표현 하는 방법에 대한 연구를 수행하였다. 즉, 7개의 그룹의 하루 24시간의 시간대별 교통량 집중률을 k=2부터 k=5까지 k-means 클러스터링 분석을 통해 집중률 패턴이 유사한 시간대를 하나의 그룹으로 구분하였다. k값에 따라 k-means 클러스터링 결과별 BIC, Elbow Method, 실루엣 계수, 상관계수 분석과 절편이 없는 단순회귀모형의 기울기와 값을 평가 분석결과 시간대별 교통 패턴을 3개로 구분하는 것이 최적의 결과로 도출되었다. 또한 네트워크 분석이 가능하도록 연구결과로 얻어진 통행거리 구분과 시간대별 교통량 집중률 패턴 구분이 반영된 OD 자료를 구축하는 방법도 제안하였다. 이와 같이 통행거리별 출발시각의 차이를 반영한 하루의 시간대 그룹별 OD 자료에 의한 네트워크의 노선배정(traffic assignment)을 수행할 경우 단거리, 중거리 및 장거리 통행이 혼재한 도로구간(링크) 상의 시간대 구간 그룹의 교통량 패턴을 더욱 현실적 분석을 가능하게 할 수 있을 것으로 기대된다.

K-means 클러스터링을 이용한 압축 기반 이상탐지

안종하,김대원 한국정보과학회 2012 정보과학회논문지 : 소프트웨어 및 응용 Vol.39 No.8

본 연구는 대규모 로그데이터의 보관문제와 이상 탐지를 병행적으로 해결하기 위한 압축 기반 클러스터링 기법을 제안한다. 이상 탐지를 위해 K-means 클러스터링 알고리즘을 활용하였으며, 대규모 로그 데이터의 처리를 위해 개선된 Logpack 압축 알고리즘에 기반한 거리 척도를 사용하였다. 추가적으로, 유전 알고리즘을 이용하여 데이터의 이상 특징을 나타내는 필드를 탐사하였고, 제안한 방법에 기초한 실험 결과가 기존 연구보다 우수한 결과를 도출함을 확인하였다. This study presents a new method for storing large log data, and simultaneously, detecting anomaly data. To achieve this, the well-known K-means clustering algorithm is used for the anomaly detection. In K-means algorithm, the dissimilarity between data is calculated on the space transformed by the Logpack compression algorithm. We also performed a feature selection using genetic algorithms to obtain an informative subset of features relevant to anomaly events. Through various tests, it is observed that the proposed method is superior to conventional algorithms.

고차원 대규모 데이터 처리를 위한 K-means 클러스터링

윤태식(Taesik Yoon),심규석(Kyuseok Shim) 한국정보과학회 2012 정보과학회 컴퓨팅의 실제 논문지 Vol.18 No.1

클러스터링은 유사한 데이터 포인트들을 그룹으로 묶어 데이터를 분석하는데 유용하다. 본 논문에서는 기존의 K-means 알고리즘과 비교해 고차원 대규모 데이터에 대해서 효율적으로 동작하는 K-means 알고리즘을 제안한다. 제안된 알고리즘들은 점간 거리 정보와 휴면 군집을 이용해 불필요한 거리계산을 줄인다. 제안된 알고리즘은 기존의 연구의 제안된 알고리즘에 비해 공간을 적게 쓰면서 동시에 빠르다. 실제 고차원 데이터 실험을 통해서 제안된 알고리즘의 효율성을 보였다. Clustering is the one of the most popular data mining algorithms, which groups similar points in the same cluster while putting dissimilar points in different clusters. In this paper we propose efficient k-means clustering algorithms for high-dimensional large data. The proposed method utilizes the precomputed distances between points and dormant clusters to reduce distance computations. As the result of experiments, our methods outperform the existing work with respect to the total running time. Moreover, the proposed method uses less space compared to the previous works.

K-Means 군집모형과 계층적 군집(교차효율성 메트릭스에 의한 평균연결법, Ward법)모형 및 혼합모형을 이용한 컨테이너항만의 클러스터링 측정에 대한 실증적 비교 및 검증에 관한 연구

박노경(Park, Ro-Kyung) 한국항만경제학회 2018 韓國港灣經濟學會誌 Vol.34 No.3

본 논문에서는 K-Means 군집모형과 계층적 군집모형, 혼합모형으로, 아시아 38개 컨테이너항만들의 2006년부터 2015년까지의 자료와 선석길이, 수심, 총면적, 크레인 수를 투입물, 컨테이너화물처리량을 산출물로 하여 국내대표 컨테이너항만 들(부산, 인천, 광양항)이 클러스터링 해야만 하는 항만들을 적출해 내는 측정방법을 보여 주고 비교, 분석, 검증하였다. 실증분석의 주요한 결과는 다음과 같다. 첫째, 10년간의 자료를 이용한 분석에서 클러스터링 후의 효율성 증가폭이 큰 순서대로 살펴보면 평균연결법[average linkage(AL)]은 42.04% 상승, Mixed Ward는 35.01% 상승, 경험법칙[rule of thumb(RT)]&Elbow는 30.47% 상승, Ward는23.65% 상승, Mixed AL는 23.25% 상승의 순서였다. 둘째, RT와 Elbow모형에 의한 국내항만들의 클러스터링을 살펴보면 ➀부산항은 두바이, 홍콩, 광저우, 칭타오, 포트 클랑, 싱가포르, 림찬방 ➁인천항은 하이파, 포트슐탄 카부스, 담만, 크호르 파칸, 탄중프리옥, 탄중퍼락, 동경, 나고야, 오사카, 카라치, 오아심, 마닐라, 다바오, 콜롬보, 킬롱, 방콕, ➂광양항은 아카바, 크호르 파칸, 광정우, 닝보, 칭타오, 포트 클랑, 카오슝, 림찬방 항과 클러스터링 해야만 하는 것으로 나타났다. 셋째, 최적 군집 수를 살펴보면 AL(6개), Mixed Ward(5개), RT&ELBOW (4개), Ward(5개), Mixed AL(6개)가 최적 군집 수인 것으로 나타났다. 넷째, 전문가 그룹에 의해서 선호되는 항만들과 본 실증분석결과에 의해서 도출된 국내항만들의 클러스터링 되는 항만들과의 일치성 여부는 부산항은 80%, 인천항은 17%, 광양항은 50%수준에서 일치하는 것으로 검증되었다. 본 논문이 제안하고 있는 정책적인 측면의 의미는 첫째, 항만정책입안자, 항만운영관리자들이 본 연구에서 사용한 모형들을 항만의 클러스터링에 도입하여 벤치마킹항만들을 선정해야만 한다. 둘째, 실증분석의 결과로서 도출된, 국내항만들의 참조항만, 클러스터링항만들에 대하여, 그들 항만들의 항만개발, 운영방안 등에 대한 내용을 비교⋅분석하고 벤치마킹이 필요한 부분은 신속하게 도입하여 실시하는 것이 필요하다는 점이다. The purpose of this paper is to measure the clustering change and analyze empirical results. Additionally, by using k-means, hierarchical, and mixed models on Asian container ports over the period 2006-2015, the study aims to form a cluster comprising Busan, Incheon, and Gwangyang ports. The models consider the number of cranes, depth, birth length, and total area as inputs and container twenty-foot equivalent units(TEU) as output. Following are the main empirical results. First, ranking order according to the increasing ratio during the 10 years analysis shows that the value for average linkage(AL), mixed ward, rule of thumb(RT)& elbow, ward, and mixed AL are 42.04% up, 35.01% up, 30.47%up, and 23.65% up, respectively. Second, according to the RT and elbow models, the three Korean ports can be clustered with Asian ports in the following manner: Busan Port(Hong Kong, Guangzhou, Qingdao, and Singapore), Incheon Port(Tokyo, Nagoya, Osaka, Manila, and Bangkok), and Gwangyang Port(Gungzhou, Ningbo, Qingdao, and Kasiung). Third, optimal clustering numbers are as follows: AL(6), Mixed Ward(5), RT&elbow(4), Ward(5), and Mixed AL(6). Fourth, empirical clustering results match with those of questionnaire-Busan Port(80%), Incheon Port(17%), and Gwangyang Port(50%). The policy implication is that related parties of Korean seaports should introduce port improvement plans like the benchmarking of clustered seaports.

마이크로 어레이 데이터에 적용된 2단계 K-means 클러스터링의 소개

박대훈(Daehoon Park),김연태(Yountae Kim),김성신(Sungshin Kim),이춘환(Choon-Hwan Lee) 한국지능시스템학회 2007 한국지능시스템학회논문지 Vol.17 No.2

많은 유전자 정보와 그 부산물은 많은 방법을 통해 연구되어 왔다. DNA 마이크로어레이 기술의 사용은 많은 데이터를 가져왔으며, 이렇게 얻은 데이터는 기존의 연구 방법으로는 분석하기 힘들다. 본 눈문에서는 많은 양의 데이터를 처리할 수 있게 하기 위하여 K-means 클러스터링 알고리즘을 이용한 분할 클러스터링을 제안하였다. 제안한 방법을 쌀 유전자로부터 나온 마이크로어레이 데이터에 적용함으로써 제안된 클러스터링 방법의 유용성을 검증하였으며, 기존의 K-means 클러 스터링 알고리즘을 적용한 결과와 비교함으로써 제안된 알고리즘의 우수성을 확인할 수 있었다. Long gene sequences and their products have been studied by many methods. The use of DNA(Deoxyribonucleic acid) microarray technology has resulted in an enormous amount of data, which has been difficult to analyze using typical research methods. This paper proposes that mass data be analyzed using division clustering with the K-means clustering algorithm. To demonstrate the superiority of the proposed method, it was used to analyze the microarray data from rice DNA. The results were compared to those of the existing K-meansmethod establishing that the proposed method is more useful in spite of the effective reduction of performance time.

K-Means 클러스터링 성능 향상을 위한 최대평균거리 기반 초기값 설정

이신원 ( Shin-won Lee ),이원휘 ( Won-hee Lee ) 한국인터넷정보학회 2011 인터넷정보학회논문지 Vol.12 No.2

대규모 데이터에 대한 특성에 따라 몇 개의 클러스터로 군집화하는 클러스터링 기법은 계층적 클러스터링이나 분할 클러스터링 등 다양한 기법이 있는데 그 중에서 K-Means 알고리즘은 구현이 쉬우나 할당-재계산에 소요되는 시간이 증가하게 된다. 본 논문에서는 초기 클러스터 중심들 간의 거리가 최대가 되도록 하여 초기 클러스터 중심들이 고르게 분포되도록 함으로써 할당-재계산 횟수를 줄이고 전체 클러스터링 시간을 감소시키고자 한다. Clustering methods is divided into hierarchical clustering, partitioning clustering, and more. If the amount of documents is huge, it takes too much time to cluster them in hierarchical clustering. In this paper we deal with K-Means algorithm that is one of partitioning clustering and is adequate to cluster so many documents rapidly and easily . We propose the new method of selecting initial seeds in K-Means algorithm. In this method, the initial seeds have been selected that are positioned as far away from each other as possible.

K-Means 클러스터링에서 초기 중심 선정 방법 비교

이신원 ( Shinwon Lee ) 한국인터넷정보학회 2012 인터넷정보학회논문지 Vol.13 No.6

클러스터링 기법은 데이터에 대한 특성에 따라 몇 개의 클러스터로 군집화 하는 계층적 클러스터링이나 분할 클러스터링 등 다양한 기법이 있는데 그 중에서 K-Means 알고리즘은 구현이 쉬우나 할당-재계산에 소요되는 시간이 증가하게 된다. 또한 초기 클러스터중심이 임의로 설정되기 때문에 클러스터링 결과가 편차가 심하다. 본 논문에서는 클러스터링에 소요되는 시간을 줄이고 안정적인 클러스터링을 하기 위해 초기 클러스터 중심 선정 방법을 삼각형 높이를 이용하는 방법을 제안하고 비교 실험해 봄으로서 할당-재계산 횟수를 줄이고 전체 클러스터링 시간을 감소시키고자 한다. 실험결과로 평균 총소요시간을 보면 최대평균거리를 이용하는 방법은 기존 방법에 비해서 17.9% 감소하였고, 제안한 방법은 38.4% 감소하였다. Clustering method is divided into hierarchical clustering, partitioning clustering, and more. K-Means algorithm is one of partitioning clustering and is adequate to cluster so many documents rapidly and easily. It has disadvantage that the random initial centers cause different result. So, the better choice is to place them as far away as possible from each other. We propose a new method of selecting initial centers in K-Means clustering. This method uses triangle height for initial centers of clusters. After that, the centers are distributed evenly and that result is more accurate than initial cluster centers selected random. It is time-consuming, but can reduce total clustering time by minimizing the number of allocation and recalculation. We can reduce the time spent on total clustering. Compared with the standard algorithm, average consuming time is reduced 38.4%