The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] nearest neighbor(44hit)

1-20hit(44hit)

  • A Personalised Session-Based Recommender System with Sequential Updating Based on Aggregation of Item Embeddings Open Access

    Yuma NAGI  Kazushi OKAMOTO  

     
    PAPER

      Pubricized:
    2024/01/09
      Vol:
    E107-D No:5
      Page(s):
    638-649

    The study proposes a personalised session-based recommender system that embeds items by using Word2Vec and sequentially updates the session and user embeddings with the hierarchicalization and aggregation of item embeddings. To process a recommendation request, the system constructs a real-time user embedding that considers users’ general preferences and sequential behaviour to handle short-term changes in user preferences with a low computational cost. The system performance was experimentally evaluated in terms of the accuracy, diversity, and novelty of the ranking of recommended items and the training and prediction times of the system for three different datasets. The results of these evaluations were then compared with those of the five baseline systems. According to the evaluation experiment, the proposed system achieved a relatively high recommendation accuracy compared with baseline systems and the diversity and novelty scores of the proposed system did not fall below 90% for any dataset. Furthermore, the training times of the Word2Vec-based systems, including the proposed system, were shorter than those of FPMC and GRU4Rec. The evaluation results suggest that the proposed recommender system succeeds in keeping the computational cost for training low while maintaining high-level recommendation accuracy, diversity, and novelty.

  • Packer Identification Method for Multi-Layer Executables Using Entropy Analysis with k-Nearest Neighbor Algorithm

    Ryoto OMACHI  Yasuyuki MURAKAMI  

     
    LETTER

      Pubricized:
    2022/08/16
      Vol:
    E106-A No:3
      Page(s):
    355-357

    The damage cost caused by malware has been increasing in the world. Usually, malwares are packed so that it is not detected. It is a hard task even for professional malware analysts to identify the packers especially when the malwares are multi-layer packed. In this letter, we propose a method to identify the packers for multi-layer packed malwares by using k-nearest neighbor algorithm with entropy-analysis for the malwares.

  • An Efficient Method to Decompose and Map MPMCT Gates That Accounts for Qubit Placement

    Atsushi MATSUO  Wakaki HATTORI  Shigeru YAMASHITA  

     
    PAPER-Algorithms and Data Structures

      Pubricized:
    2022/08/10
      Vol:
    E106-A No:2
      Page(s):
    124-132

    Mixed-Polarity Multiple-Control Toffoli (MPMCT) gates are generally used to implement large control logic functions for quantum computation. A logic circuit consisting of MPMCT gates needs to be mapped to a quantum computing device that invariably has a physical limitation, which means we need to (1) decompose the MPMCT gates into one- or two-qubit gates, and then (2) insert SWAP gates so that all the gates can be performed on Nearest Neighbor Architectures (NNAs). Up to date, the above two processes have only been studied independently. In this work, we investigate that the total number of gates in a circuit can be decreased if the above two processes are considered simultaneously as a single step. We developed a method that inserts SWAP gates while decomposing MPMCT gates unlike most of the existing methods. Also, we consider the effect on the latter part of a circuit carefully by considering the qubit placement when decomposing an MPMCT gate. Experimental results demonstrate the effectiveness of our method.

  • Machine-Learning Approach for Solving Inverse Problems in Magnetic-Field-Based Positioning Open Access

    Ai-ichiro SASAKI  Ken FUKUSHIMA  

     
    PAPER-General Fundamentals and Boundaries

      Pubricized:
    2021/12/13
      Vol:
    E105-A No:6
      Page(s):
    994-1005

    Magnetic fields are often utilized for position sensing of mobile devices. In typical sensing systems, multiple sensors are used to detect magnetic fields generated by target devices. To determine the positions of the devices, magnetic-field data detected by the sensors must be converted to device-position data. The data conversion is not trivial because it is a nonlinear inverse problem. In this study, we propose a machine-learning approach suitable for data conversion required in the magnetic-field-based position sensing of target devices. In our approach, two different sets of training data are used. One of the training datasets is composed of raw data of magnetic fields to be detected by sensors. The other set is composed of logarithmically represented data of the fields. We can obtain two different predictor functions by learning with these training datasets. Results show that the prediction accuracy of the target position improves when the two different predictor functions are used. Based on our simulation, the error of the target position estimated with the predictor functions is within 10cm in a 2m × 2m × 2m cubic space for 87% of all the cases of the target device states. The computational time required for predicting the positions of the target device is 4ms. As the prediction method is accurate and rapid, it can be utilized for the real-time tracking of moving objects and people.

  • SimpleZSL: Extremely Simple and Fast Zero-Shot Learning with Nearest Neighbor Classifiers

    Masayuki HIROMOTO  Hisanao AKIMA  Teruo ISHIHARA  Takuji YAMAMOTO  

     
    PAPER-Pattern Recognition

      Pubricized:
    2021/10/29
      Vol:
    E105-D No:2
      Page(s):
    396-405

    Zero-shot learning (ZSL) aims to classify images of unseen classes by learning relationship between visual and semantic features. Existing works have been improving recognition accuracy from various approaches, but they employ computationally intensive algorithms that require iterative optimization. In this work, we revisit the primary approach of the pattern recognition, ı.e., nearest neighbor classifiers, to solve the ZSL task by an extremely simple and fast way, called SimpleZSL. Our algorithm consists of the following three simple techniques: (1) just averaging feature vectors to obtain visual prototypes of seen classes, (2) calculating a pseudo-inverse matrix via singular value decomposition to generate visual features of unseen classes, and (3) inferring unseen classes by a nearest neighbor classifier in which cosine similarity is used to measure distance between feature vectors. Through the experiments on common datasets, the proposed method achieves good recognition accuracy with drastically small computational costs. The execution time of the proposed method on a single CPU is more than 100 times faster than those of the GPU implementations of the existing methods with comparable accuracies.

  • Individuality-Preserving Silhouette Extraction for Gait Recognition and Its Speedup

    Masakazu IWAMURA  Shunsuke MORI  Koichiro NAKAMURA  Takuya TANOUE  Yuzuko UTSUMI  Yasushi MAKIHARA  Daigo MURAMATSU  Koichi KISE  Yasushi YAGI  

     
    PAPER-Pattern Recognition

      Pubricized:
    2021/03/24
      Vol:
    E104-D No:7
      Page(s):
    992-1001

    Most gait recognition approaches rely on silhouette-based representations due to high recognition accuracy and computational efficiency. A fundamental problem for those approaches is how to extract individuality-preserved silhouettes from real scenes accurately. Foreground colors may be similar to background colors, and the background is cluttered. Therefore, we propose a method of individuality-preserving silhouette extraction for gait recognition using standard gait models (SGMs) composed of clean silhouette sequences of various training subjects as shape priors. The SGMs are smoothly introduced into a well-established graph-cut segmentation framework. Experiments showed that the proposed method achieved better silhouette extraction accuracy by more than 2.3% than representative methods and better identification rate of gait recognition (improved by more than 11.0% at rank 20). Besides, to reduce the computation cost, we introduced approximation in the calculation of dynamic programming. As a result, without reducing the segmentation accuracy, we reduced 85.0% of the computational cost.

  • Revisiting a Nearest Neighbor Method for Shape Classification

    Kazunori IWATA  

     
    PAPER-Pattern Recognition

      Pubricized:
    2020/09/23
      Vol:
    E103-D No:12
      Page(s):
    2649-2658

    The nearest neighbor method is a simple and flexible scheme for the classification of data points in a vector space. It predicts a class label of an unseen data point using a majority rule for the labels of known data points inside a neighborhood of the unseen data point. Because it sometimes achieves good performance even for complicated problems, several derivatives of it have been studied. Among them, the discriminant adaptive nearest neighbor method is particularly worth revisiting to demonstrate its application. The main idea of this method is to adjust the neighbor metric of an unseen data point to the set of known data points before label prediction. It often improves the prediction, provided the neighbor metric is adjusted well. For statistical shape analysis, shape classification attracts attention because it is a vital topic in shape analysis. However, because a shape is generally expressed as a matrix, it is non-trivial to apply the discriminant adaptive nearest neighbor method to shape classification. Thus, in this study, we develop the discriminant adaptive nearest neighbor method to make it slightly more useful in shape classification. To achieve this development, a mixture model and optimization algorithm for shape clustering are incorporated into the method. Furthermore, we describe several helpful techniques for the initial guess of the model parameters in the optimization algorithm. Using several shape datasets, we demonstrated that our method is successful for shape classification.

  • Mapping a Quantum Circuit to 2D Nearest Neighbor Architecture by Changing the Gate Order Open Access

    Wakaki HATTORI  Shigeru YAMASHITA  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2019/07/25
      Vol:
    E102-D No:11
      Page(s):
    2127-2134

    This paper proposes a new approach to optimize the number of necessary SWAP gates when we perform a quantum circuit on a two-dimensional (2D) NNA. Our new idea is to change the order of quantum gates (if possible) so that each sub-circuit has only gates performing on adjacent qubits. For each sub-circuit, we utilize a SAT solver to find the best qubit placement such that the sub-circuit has only gates on adjacent qubits. Each sub-circuit may have a different qubit placement such that we do not need SWAP gates for the sub-circuit. Thus, we insert SWAP gates between two sub-circuits to change the qubit placement which is desirable for the following sub-circuit. To reduce the number of such SWAP gates between two sub-circuits, we utilize A* algorithm.

  • Recursive Nearest Neighbor Graph Partitioning for Extreme Multi-Label Learning

    Yukihiro TAGAMI  

     
    PAPER-Artificial Intelligence, Data Mining

      Pubricized:
    2018/11/30
      Vol:
    E102-D No:3
      Page(s):
    579-587

    As the data size of Web-related multi-label classification problems continues to increase, the label space has also grown extremely large. For example, the number of labels appearing in Web page tagging and E-commerce recommendation tasks reaches hundreds of thousands or even millions. In this paper, we propose a graph partitioning tree (GPT), which is a novel approach for extreme multi-label learning. At an internal node of the tree, the GPT learns a linear separator to partition a feature space, considering approximate k-nearest neighbor graph of the label vectors. We also developed a simple sequential optimization procedure for learning the linear binary classifiers. Extensive experiments on large-scale real-world data sets showed that our method achieves better prediction accuracy than state-of-the-art tree-based methods, while maintaining fast prediction.

  • Development of License Plate Recognition on Complex Scene with Plate-Style Classification and Confidence Scoring Based on KNN

    Vince Jebryl MONTERO  Yong-Jin JEONG  

     
    PAPER-Image Recognition, Computer Vision

      Pubricized:
    2018/08/24
      Vol:
    E101-D No:12
      Page(s):
    3181-3189

    This paper presents an approach for developing an algorithm for automatic license plate recognition system (ALPR) on complex scenes. A plate-style classification method is also proposed in this paper to address the inherent challenges for ALPR in a system that uses multiple plate-styles (e.g., different fonts, multiple plate lay-out, variations in character sequences) which is the case in the current Philippine license plate system. Methods are proposed for each ALPR module: plate detection, character segmentation, and character recognition. K-nearest neighbor (KNN) is used as a classifier for character recognition together with a proposed confidence scoring to rate the decision made by the classifier. A small dataset of Philippine license plates but with relevant features of complex scenarios for ALPR is prepared. Using the proposed system on the prepared dataset, the performance of the system is evaluated on different categories of complex scenes. The proposed algorithm structure shows promising results and yielded an overall accuracy higher than the existing ALPR systems on the dataset consisting mostly of complex scenes.

  • Speeding up Extreme Multi-Label Classifier by Approximate Nearest Neighbor Search

    Yukihiro TAGAMI  

     
    PAPER-Artificial Intelligence, Data Mining

      Pubricized:
    2018/08/06
      Vol:
    E101-D No:11
      Page(s):
    2784-2794

    Extreme multi-label classification methods have been widely used in Web-scale classification tasks such as Web page tagging and product recommendation. In this paper, we present a novel graph embedding method called “AnnexML”. At the training step, AnnexML constructs a k-nearest neighbor graph of label vectors and attempts to reproduce the graph structure in the embedding space. The prediction is efficiently performed by using an approximate nearest neighbor search method that efficiently explores the learned k-nearest neighbor graph in the embedding space. We conducted evaluations on several large-scale real-world data sets and compared our method with recent state-of-the-art methods. Experimental results show that our AnnexML can significantly improve prediction accuracy, especially on data sets that have a larger label space. In addition, AnnexML improves the trade-off between prediction time and accuracy. At the same level of accuracy, the prediction time of AnnexML was up to 58 times faster than that of SLEEC, a state-of-the-art embedding-based method.

  • Scalable and Parameterized Architecture for Efficient Stream Mining

    Li ZHANG  Dawei LI  Xuecheng ZOU  Yu HU  Xiaowei XU  

     
    PAPER-Systems and Control

      Vol:
    E101-A No:1
      Page(s):
    219-231

    With an annual growth of billions of sensor-based devices, it is an urgent need to do stream mining for the massive data streams produced by these devices. Cloud computing is a competitive choice for this, with powerful computational capabilities. However, it sacrifices real-time feature and energy efficiency. Application-specific integrated circuit (ASIC) is with high performance and efficiency, which is not cost-effective for diverse applications. The general-purpose microcontroller is of low performance. Therefore, it is a challenge to do stream mining on these low-cost devices with scalability and efficiency. In this paper, we introduce an FPGA-based scalable and parameterized architecture for stream mining.Particularly, Dynamic Time Warping (DTW) based k-Nearest Neighbor (kNN) is adopted in the architecture. Two processing element (PE) rings for DTW and kNN are designed to achieve parameterization and scalability with high performance. We implement the proposed architecture on an FPGA and perform a comprehensive performance evaluation. The experimental results indicate thatcompared to the multi-core CPU-based implementation, our approach demonstrates over one order of magnitude on speedup and three orders of magnitude on energy-efficiency.

  • Multiple k-Nearest Neighbor Classifier and Its Application to Tissue Characterization of Coronary Plaque

    Eiji UCHINO  Ryosuke KUBOTA  Takanori KOGA  Hideaki MISAWA  Noriaki SUETAKE  

     
    PAPER-Biological Engineering

      Pubricized:
    2016/04/15
      Vol:
    E99-D No:7
      Page(s):
    1920-1927

    In this paper we propose a novel classification method for the multiple k-nearest neighbor (MkNN) classifier and show its practical application to medical image processing. The proposed method performs fine classification when a pair of the spatial coordinate of the observation data in the observation space and its corresponding feature vector in the feature space is provided. The proposed MkNN classifier uses the continuity of the distribution of features of the same class not only in the feature space but also in the observation space. In order to validate the performance of the present method, it is applied to the tissue characterization problem of coronary plaque. The quantitative and qualitative validity of the proposed MkNN classifier have been confirmed by actual experiments.

  • Protein Fold Classification Using Large Margin Combination of Distance Metrics

    Chendra Hadi SURYANTO  Kazuhiro FUKUI  Hideitsu HINO  

     
    PAPER-Pattern Recognition

      Pubricized:
    2015/12/14
      Vol:
    E99-D No:3
      Page(s):
    714-723

    Many methods have been proposed for measuring the structural similarity between two protein folds. However, it is difficult to select one best method from them for the classification task, as each method has its own strength and weakness. Intuitively, combining multiple methods is one solution to get the optimal classification results. In this paper, by generalizing the concept of the large margin nearest neighbor (LMNN), a method for combining multiple distance metrics from different types of protein structure comparison methods for protein fold classification task is proposed. While LMNN is limited to Mahalanobis-based distance metric learning from a set of feature vectors of training data, the proposed method learns an optimal combination of metrics from a set of distance metrics by minimizing the distances between intra-class data and enlarging the distances of different classes' data. The main advantage of the proposed method is the capability in finding an optimal weight coefficient for combination of many metrics, possibly including poor metrics, avoiding the difficulties in selecting which metrics to be included for the combination. The effectiveness of the proposed method is demonstrated on classification experiments using two public protein datasets, namely, Ding Dubchak dataset and ENZYMES dataset.

  • k Nearest Neighbor Classification Coprocessor with Weighted Clock-Mapping-Based Searching

    Fengwei AN  Lei CHEN  Toshinobu AKAZAWA  Shogo YAMASAKI  Hans Jürgen MATTAUSCH  

     
    PAPER-Electronic Circuits

      Vol:
    E99-C No:3
      Page(s):
    397-403

    Nearest-neighbor-search classifiers are attractive but they have high intrinsic computational demands which limit their practical application. In this paper, we propose a coprocessor for k (k with k≥1) nearest neighbor (kNN) classification in which squared Euclidean distances (SEDs) are mapped into the clock domain for realizing high search speed and energy efficiency. The minimal SED searching is carried out by weighted frequency dividers that drastically reduce the normally exponential increase of the worst-case search-clock number with the bit width of vector components to only a linear increase. This also results in low power dissipation and high area-efficiency in comparison to the traditional method using large numbers of adders and comparators. The kNN classifier determines the class of an unknown input sample with a majority decision among the k nearest reference samples. The required majority-decision circuit is integrated with the clock-mapping-based minimal-SED searching architecture and proceeds with the classification immediately after identification of each of the k nearest references. A test chip in 180 nm CMOS technology, which can process 8 dimensions of 32 reference vectors in parallel, achieves low power dissipation of 40.32 mW (at 51.21 MHz clock frequency and 1.8 V supply voltage). Significantly, the distance search circuit consumes only 5.99 mW. Feature vectors with different dimensionality up to 2048 dimensions can be handled by the designed coprocessor due to a dimension extension circuit, enabling large flexibility for usage in different application.

  • Efficient Anchor Graph Hashing with Data-Dependent Anchor Selection

    Hiroaki TAKEBE  Yusuke UEHARA  Seiichi UCHIDA  

     
    LETTER-Image Recognition, Computer Vision

      Pubricized:
    2015/08/17
      Vol:
    E98-D No:11
      Page(s):
    2030-2033

    Anchor graph hashing (AGH) is a promising hashing method for nearest neighbor (NN) search. AGH realizes efficient search by generating and utilizing a small number of points that are called anchors. In this paper, we propose a method for improving AGH, which considers data distribution in a similarity space and selects suitable anchors by performing principal component analysis (PCA) in the similarity space.

  • Multiple Binary Codes for Fast Approximate Similarity Search

    Shinichi SHIRAKAWA  

     
    PAPER-Pattern Recognition

      Pubricized:
    2014/12/11
      Vol:
    E98-D No:3
      Page(s):
    671-680

    One of the fast approximate similarity search techniques is a binary hashing method that transforms a real-valued vector into a binary code. The similarity between two binary codes is measured by their Hamming distance. In this method, a hash table is often used when undertaking a constant-time similarity search. The number of accesses to the hash table, however, increases when the number of bits lengthens. In this paper, we consider a method that does not access data with a long Hamming radius by using multiple binary codes. Further, we attempt to integrate the proposed approach and the existing multi-index hashing (MIH) method to accelerate the performance of the similarity search in the Hamming space. Then, we propose a learning method of the binary hash functions for multiple binary codes. We conduct an experiment on similarity search utilizing a dataset of up to 50 million items and show that our proposed method achieves a faster similarity search than that possible with the conventional linear scan and hash table search.

  • Infrared Target Tracking Using Naïve-Bayes-Nearest-Neighbor

    Shujuan GAO  Insuk KIM  Seong Tae JHANG  

     
    LETTER-Image Recognition, Computer Vision

      Pubricized:
    2014/11/18
      Vol:
    E98-D No:2
      Page(s):
    471-474

    Robust yet efficient techniques for detecting and tracking targets in infrared (IR) images are a significant component of automatic target recognition (ATR) systems. In our previous works, we have proposed infrared target detection and tracking systems based on sparse representation method. The proposed infrared target detection and tracking algorithms are based on sparse representation and Bayesian probabilistic techniques, respectively. In this paper, we adopt Naïve Bayes Nearest Neighbor (NBNN) that is an extremely simple, efficient algorithm that requires no training phase. State-of-the-art image classification techniques need a comprehensive learning and training step (e.g., using Boosting, SVM, etc.) In contrast, non-parametric Nearest Neighbor based image classifiers need no training time and they also have other more advantageous properties. Results of tracking in infrared sequences demonstrated that our algorithm is robust to illumination changes, and the tracking algorithm is found to be suitable for real-time tracking of a moving target in infrared sequences and its performance was quite good.

  • Nearest Neighbor Search with the Revised TLAESA

    Dong WANG  Hiroyuki MITSUHARA  Masami SHISHIBORI  

     
    PAPER

      Vol:
    E98-D No:1
      Page(s):
    65-77

    It is significant to develop better search methods to handle the rapidly increasing volume of multimedia data. For NN (Nearest Neighbor) search in metric spaces, the TLAESA (Tree Linear Approximating and Eliminating Search Algorithm) is a state of art fast search method. In this paper a method is proposed to improve the TLAESA by revising the tree structure with an optimal number of selected global pivots in the higher levels as representatives and employing the best-first search strategy. Based on an improved version of the TLAESA that succeeds in using the best-first search strategy to greatly reduce the distance calculations, this method improves the drawback that calculating less at the price of the lower pruning rate of branches. The lower pruning rate further can lead to lower search efficiency, because the priority queue used in the adopted best-first search strategy stores the information of the visited but unpruned nodes, and need be frequently accessed and sorted. In order to enhance the pruning rate of branches, the improved method tries to make more selected global pivots locate in the higher levels of the search tree as representatives. As more real distances instead of lower bound estimations of the node-representatives are used for approximating the closet node and for “branch and bound”, not only which nodes are close to the query object can be evaluated more effectively, but also the pruning rate of branches can be enhanced. Experiments show that for k-NN queries in Euclidean space, in a proper pivot selection strategy the proposed method can reach the same fewest distance calculations as the LAESA (Linear Approximating and Eliminating Search Algorithm) which saves more calculations than the TLAESA, and can achieve a higher search efficiency than the TLAESA.

  • Efficient K-Nearest Neighbor Graph Construction Using MapReduce for Large-Scale Data Sets

    Tomohiro WARASHINA  Kazuo AOYAMA  Hiroshi SAWADA  Takashi HATTORI  

     
    PAPER-Data Engineering, Web Information Systems

      Vol:
    E97-D No:12
      Page(s):
    3142-3154

    This paper presents an efficient method using Hadoop MapReduce for constructing a K-nearest neighbor graph (K-NNG) from a large-scale data set. K-NNG has been utilized as a data structure for data analysis techniques in various applications. If we are to apply the techniques to a large-scale data set, it is desirable that we develop an efficient K-NNG construction method. We focus on NN-Descent, which is a recently proposed method that efficiently constructs an approximate K-NNG. NN-Descent is implemented on a shared-memory system with OpenMP-based parallelization, and its extension for the Hadoop MapReduce framework is implied for a larger data set such that the shared-memory system is difficult to deal with. However, a simple extension for the Hadoop MapReduce framework is impractical since it requires extremely high system performance because of the high memory consumption and the low data transmission efficiency of MapReduce jobs. The proposed method relaxes the requirement by improving the MapReduce jobs, which employs an appropriate key-value pair format and an efficient sampling strategy. Experiments on large-scale data sets demonstrate that the proposed method both works efficiently and is scalable in terms of a data size, the number of machine nodes, and the graph structural parameter K.

1-20hit(44hit)