A High-performance Classifier from K-dimensional Tree-based Dual-kNN

Swe Swe Aung,Itaru Nagayama,Shiro Tamaki 대한전자공학회 2018 IEIE Transactions on Smart Processing & Computing Vol.7 No.3

The k-nearest neighbors (kNN) method is highly effective in many application areas. Conceptually, its other good properties are simplicity and ease of understanding. However, according to measurements of the performance of algorithms based on three considerations (simplicity, processing time, and prediction power), the classic kNN algorithm lacks high-speed computation as well as maintenance of high accuracy for different values of k. The k-nearest neighbors algorithm is still influenced by varying k values and high variance in the training data set. Prediction accuracy diminishes when k approaches larger values. To overcome these issues, this paper introduces a k-dimensional (kd)-tree–based dual-kNN approach that concentrates on two properties to maintain classification accuracy at different k values and that also upgrades processing time performance. By conducting experiments on real data sets and comparing this algorithm with two other algorithms (dual-kNN and classic kNN), it was experimentally confirmed that the kdtree–based dual-kNN is a more effective and robust approach for classification than pure dual-kNN and classic kNN.

Stacking Based Ensemble with Instance Selection in Random KNN

Kyupil Yeon 한국자료분석학회 2020 Journal of the Korean Data Analysis Society Vol.22 No.4

Nearest neighbor classification is a simple and quite effective method. But it has some drawbacks in that it suffers from both so called the curse of dimensionality and computational burden when there are lots of examples. A lot of features in high dimensional data degrade the performance of KNN due to the noisy and redundant variables. Hence some kinds of feature selection mechanism is essential to KNN. Random KNN simplifies the feature selection problem by utilizing an ensemble of KNNs constructed with randomly selected subsets of features. Two kinds of enhancements of the random KNN methodology are proposed in this paper. One is to add an instance selection procedure and the other is to determine the weights by training another combining model instead of simple voting in the random KNN. These two additional procedures applied to the random KNN can improve the classification performance of the original random KNN, which is verified by some data analyses with a real data set.

위치 측위 향상을 위한 KNN과 Local Map Classification 및 Bayes Filter를 사용한 실내 위치 인식 시스템

오승훈(Seung-Hoon Oh),맹주현(Ju-Hyun Maeng) 한국컴퓨터정보학회 2021 韓國컴퓨터情報學會論文誌 Vol.26 No.6

본 논문에서는 위치 측위의 정확도를 높일 수 있는 방안으로 KNN(K-Nearest Neighbor)과 Local Map Classification 및 Bayes Filter를 융합한 기법을 제안한다. 먼저 이 기법은 Local Map Classification이 실제 지도를 여러 개의 Cluster로 나누고, 다음으로 KNN으로 Cluster들을 분류한다. 그리고 Bayes Filter가 획득한 각 Cluster의 확률을 통하여 Posterior Probability을 계산한다. 이 Posterior Probability으로 로봇이 위치한 Cluster를 검색한다. 성능 평가를 위하여 KNN과 Local Map Classification 및 Bayes Filter을 적용하여서 얻은 위치 측위의 결과를 분석하였다. 분석 결과로 RSSI 신호가 변하더라도 위치 정보는 한 Cluster에 고정되면서 위치 측위의 정확도가 높아진다는 사실을 확인하였다. In this paper, we propose a method that combines KNN(K-Nearest Neighbor), Local Map Classification and Bayes Filter as a way to increase the accuracy of location positioning. First, in this technique, Local Map Classification divides the actual map into several clusters, and then classifies the clusters by KNN. And posterior probability is calculated through the probability of each cluster acquired by Bayes Filter. With this posterior probability, the cluster where the robot is located is searched. For performance evaluation, the results of location positioning obtained by applying KNN, Local Map Classification, and Bayes Filter were analyzed. As a result of the analysis, it was confirmed that even if the RSSI signal changes, the location information is fixed to one cluster, and the accuracy of location positioning increases.

WiFi 핑거프린트 위치추정 방식의 적응형 KNN에서 평균 범위 설정에 관한 연구

오종택,Oh, Jongtaek 한국인터넷방송통신학회 2018 한국인터넷방송통신학회 논문지 Vol.18 No.1

실내에서의 위치를 추정하기 위한 기술 연구가 활발하게 진행되고 있다. 특히 추가적인 기반 시설을 필요로 하지 않는 WiFi fingerprint 방식은 경제성이 높아서 부분적으로 실용화되고 있다. 사전에 여러 지점에서 측정된 무선랜 수신 신호의 세기 정보와 추후에 특정 지점에서 측정된 세기 정보를 비교하여 유사한 지점을 해당 지점으로 추정하는 KNN 방식은 간단하지만 성능이 좋다. 그러나 기존의 KNN 방식은 평균하는 후보 위치들의 개수 K가 일정하므로, 특정 지점에 따라 위치 추정 오차가 최적화되지 못하는 문제가 있다. 본 논문에서는 특정 지점마다 K 값을 적응적으로 변화시키는 KNN 방식에서 평균 범위를 설정하는 알고리즘을 제안하고 실험 데이터에 적용하여 그 성능을 평가하였다. Research on the technique for estimating the indoor position has been actively carried out. In particular, the WiFi fingerprint method, which does not require any additional infrastructure, is being partially used because of its high economic efficiency. The KNN method which estimates similar points to the corresponding points by comparing intensity information of the WLAN reception signal measured at various points in advance with intensity information measured at a specific point in the future is simple but has a good performance. However, in the conventional KNN scheme, since the number K of average candidate positions is constant, there is a problem that the position estimation error is not optimized according to a specific point. In this paper, we proposed an algorithm that adaptively changes the K value for each point and applied it to experimental data and evaluated its performance.

다중 무선 방송채널에서 kNN 질의 처리를 위한 R-tree 인덱스 스케줄링 기법

정의준(Euijun Jung),정성원(Sungwon Jung) 한국정보과학회 2010 정보과학회논문지 : 데이타베이스 Vol.37 No.2

본 논문은 다중 무선 방송채널환경에서 R-tree를 이용하여 kNN 질의처리의 효과적인 인덱스 스케줄링 기법에 관한 논문이다. 기존 방식은 kNN질의처리 시 노드를 여러 개 얻어야 할 때 child들이 다중 채널 방송스케줄 상 같은 타임 슬롯에 위치하고 있어 원하는 데이터를 얻기 위해서 다음 사이클로 넘어가 데이터를 얻는 시간이 길어지는 단점이 존재하였다. 제안하는 방법은 방송채널에 인덱스 스케줄링을 하기 전에 kNN을 수행하여 R-tree의 각 노드의 child의 접근빈도를 구한 후 구해진 접근 빈도를 기반으로 인덱스 스케줄링 시 방문이 많이 되어 접근빈도가 높은 child들을 다중채널 상에 직렬로 할당하고 접근이 적게 되는 노드는 병렬로 할당하여 질의처리 시 각 노드의 child들을 탐색할 때 겹치는 부분을 줄여 사용자가 원하는 데이터를 빠르게 얻을 수 있는 인덱스 스케줄링 기법이다. This paper proposes an efficient index scheduling technique for kNN query processing in multiple wireless broadcast channel environment. Previous works have to wait for the next cycle if the required child nodes of the same parent node are allocated in the same time slot on multiple channel. Our proposed method computes the access frequencies of each node of R tree at the server before the generation of the R-tree index broadcast schedule. If they have high frequencies, we allocate them serially on the single channel. If they have low frequencies, we allocate them in parallel on the multiple channels. As a result, we can reduce the index node access conflicts and the long broadcast cycle. The performance evaluation shows that our scheme gives the better performance than the existing schemes.

유사 질의어 처리를 위한 데이터 독립적인 빈티지 포인트 선택 방법

조범준,김상근,정성원 한국정보과학회 2015 데이타베이스 연구 Vol.31 No.3

Distance based space transformation by using vantages point allows efficient similarity query(ex: range query, kNN query) processing without complex distance computation. However, most of these methods are not able to handle frequently updated dynamic databases, since the existing works of space transformation methods need to search databases to find a set of vantage points from data points, In the transformed space, range query processing is very effective whereas the existing kNN query processing methods are not directly applicable. This is because space transformation methods do not preserve the distance order of data points. To handle these problems, we first propose a method of selecting vantage points among the corner points in the closed space using dynamic programming. We then propose a kNN algorithm which computes the exact kNN in the transformed space. Experimental results show that our distance-based space transformation method gives better space for range queries than the existing distance-based space transformation methods. 빈티지 포인트에 의한 거리 기반의 공간 변환은 데이터 객체간의 복잡한 거리 계산이 필요 없는 효율적인 유사 질의어 (예: 범위 질의, kNN 질의) 처리를 가능하게 한다. 그런데 기존에 제안된 공간 변환 기법들은 데이터 포인트 중에서 빈티지 포인트를 선택하기 때문에 업데이트가 빈번한 데이터베이스에는 적용하기 어렵다는 문제점이 있었다. 또한 이와 같은 방법으로 생성된 변환 공간은 범위질의에는 적합하지만 특정 질의 점에 대한 데이터 포인트들의 거리 순서가 보장되지 않기 때문에 기존의 kNN질의 처리 기법 적용이 불가능하다는 단점도 있다. 이와 같은 문제를 해결하기 위하여 본 논문에서는 먼저 다이나믹 프로그래밍 기법을 사용하여 닫힌 공간의 코너 포인트 중에서 데이터 독립적인 빈티지 포인트를 선택하는 기법을 제안하고, 변환된 공간에서의 kNN 탐색 알고리즘을 개발하였다. 실험 결과는 제안된 기법이 다른 거리기반 공간 변환 기법들에 비해 범위질위에 더 효과적인 변환공간을 생성함을 보여준다.

KNN을 이용한 융합기술 특허문서의 자동 IPC 분류

박찬정,김기용,성동수 한국정보기술학회 2014 한국정보기술학회논문지 Vol. No.

Convergence technology is actively being studied globally. Recently, IPC(International Patent Classification) used for analyze convergence technologies, in particular, multiple IPC classified patent documents are used. Thus, using the IPC for the convergence technology to retrieve, to analyze the IPC classified patent documents should be made fast and accurate. In this paper, automatic classification of patent documents included multiple classification of IPC using KNN classifiers, and the methods of selecting the appropriate features and comparing rates are tested. Feature selection methods Chi square statistics, Information gain, Mutual information and Dominant information that is proposed method in this paper were used. As a result, most of the feature selection methods are available feature selection ratio within 10%, performance is good. Especially, the rate of around 4% in the case of Dominant information when used as better than the other feature selection methods were compared with other feature selection method showed that KNN classified speed is faster. 국내외적으로 융합기술에 대한 연구가 활발히 진행되고 있다. 최근에는 융합기술을 분석하기 위하여 국제 특허분류체계인 IPC가 사용되고 있으며, 특히 IPC가 다중 분류된 특허 문서를 이용하고 있다. 이와 같이 IPC를 이용하여 융합기술을 검색, 분석하기 위하여 특허문서에 대한 빠르고 정확한 IPC 분류가 이루어져야 한다. 본 논문에서는 다중 IPC 분류가 포함된 특허문서의 IPC 자동분류를 위하여 KNN 분류기를 사용하고, 이에 적합한 특징선택 방법과 비율을 비교 실험하였다. 특징선택 방법은 카이제곱 통계량, 정보이득, 상호정보량 및 본 논문에서 제안한 방법인 우세정보량을 사용하였다. 실험 결과, 특징선택 비율은 10% 이내로 사용할 경우 다수의 특징선택 방법에서 분류성능이 좋았으며, 특히 우세정보량의 경우 4% 내외의 비율로 사용할 때 다른 특징선택 방법에 비해 우수하였고, 다른 특징선택 방법에 비해 KNN 분류 속도도 빠른 것으로 나타났다.

Manufacture and Surface Structure Characteristics of Mn-Doped (K,Na)NbO₃ Films

Yeon Jung Kim,Jaeduk Byun,June Won Hyun 한국표면공학회 2021 한국표면공학회지 Vol.54 No.1

KNN is widely used in the electronic industry such as memory devices, sensors, and capacitors due to various structural, electrical, and eco-friendly properties. In this study, Mn-doped KNN was prepared by adopting a sol-gel method with advantages of low cost and large area thin film fabrication. The Mn-doped KNN thin films were deposited by annealing in air for 1 hour and 700° C. The surface morphology characteristics and grain size of the heat-treated KNN were observed by SEM and AFM, and we used the X-ray diffraction for measuring the crystal phase of KNN. The XRD analysis results show that the fabrication of (K0.5Na0.5)(Nb1-xMnx)O₃ thin films by sol-gel method in the thin film process of this experiment was stable in the perovskite phase of c-axis orientation. The SEM and AFM results show that the cracks were not confirmed from the fracture surface data of KNN thin films and were densely deposited with thin films with uniform thickness.

KNN 알고리즘을 기반으로 하는 질병 예측 및 건강기능식품 추천 알고리즘에 관한 연구

추용주(Young-Ju Chu) 한국스마트미디어학회 2024 스마트미디어저널 Vol.13 No.8

본 논문에서는 최근 고령화 사회로 진입하면서 건강기능식품에 높은 관심과 머신러닝의 발달로 질병을 고려한 맞춤형 건강기능식품을 추천할 수 있는 알고리즘을 제시하였다. KNN 알고리즘을 적용하여 질환에 대한 분석과 공개된 건강기능식품 정보, 국가 공공데이터의 매칭 기법을 적용하여, 맞춤형 건강기능식품 추천에 대한 플랫폼의 기초 워크프레임을 제시하였다. 신뢰성 높은 질환 대비 건강기능식품 사이의 매칭을 위해서, 상관관계를 분석하고, KNN알고리즘의 고도화를 위한 변수의 적절성과 정확도를 분석하고, 향후 공개되는 정보와 학습 모델의 개선을 통해 제안하는 시스템의 개선 방향에 대해서 도출하였다. In this paper, we propose an algorithm that can recommend personalized health functional foods considering diseases due to the high interest in health functional foods and the development of machine learning as society enters an aging phase. By applying the KNN algorithm, we presented a foundational framework for a platform for personalized health functional food recommendations through disease analysis, matching techniques of publicly available health functional food information, and national public data. To ensure reliable matching between diseases and health functional foods, we analyzed correlations, assessed the appropriateness and accuracy of variables for enhancing the KNN algorithm, and derived improvement directions for the proposed system through the improvement of learning models and information to be disclosed in the future.

KNN과 DEA 방법을 활용한 IT 서비스 기업의 효율성 분석

박민규,여얼,신민수 한국경영정보학회 2017 한국경영정보학회 학술대회논문집 Vol.2017 No.12

최근 기업이나 공공기관에서는 DEA 분석을 통하여 다양한 DMU(Decision Making Unit)의 효율성을 분석하고자 노력하고 있다. 하지만 기존의 DEA분석 방법을 이용하여 분석을 수행하였을 때, 분석의 목적인 바람직한 참조 DMU가 우리가 목적으로 하는 DMU(Target DMU)의 개선을 통해서 도달하기가 힘들다는 한계점을 가지고 있다. 따라서 본 연구에서는 KNN(K-nearest neighbor)과 DEA(Data Envelopment Analysis를 이용하여 IT 서비스 기업의 효율성을 분석하고자 한다. 이를 위해서 산출 기준 CCR, 산출 기준 BCC모형을 이용하여 모델을 구축하고 본 연구에서 제안하는 방법인 KNN을 이용한 참조 그룹 생성하고자 한다. 연구 결과 전체 데이터를 이용한 DEA 분석 결과 보다 본 연구에서 제안한 KNN을 이용한 DEA분석 방법이 목적 DMU에 대하여 보다 실현 가능성이 높은 대안을 제시 해 줄 수 있을 것으로 기대한다.