Practical Algorithms for Knowledge Discovery from High-Dimensional Data based on Computational Geometry

点击翻译按钮获取中文摘要

In this project, we studied the problem of detecting geometric objects and that of region partition for 2-and 3-dimensional data. We developed algorithms for these problems whose running time is practically acceptable, based on the techniques of computational geometry. Our research results are summarized as follows.Algorithms for detecting basic geometric objects and for 2-d and k-d partitioning problem(a)We studied the problem of decomposing the rectangular region consisting of weighted pixels into k subrectangles such that each subregion contains exactly one specified point. For this problem, we developed an 0(n^2.5) time algorithm where n is the number of pixels.(b)Based on the existing exact algorithm for finding an optimal region such that the region to be detected is limited to either x-monotone, xy-monotone or rectangle region, and the one for constructing a pyramid from a terrain developed by the project leader, we have developed an algorithm for data partitioning for the use o … More f decision trees and decision rules.(c)We have developed an algorithm that enumerates efficient solutions for three-objective optimization problems, based on hand-proving method.Experiments from practical viewpoints(d)We have performed computational experiments of an algorithm developed in (a), aiming at the application to evacuation problem in urban areas.(e)We have developed the algorithm for recognizing glass openings on a building facade from architectural photographs, and another image recognition algorithm, based on an algorithm developed in (b).(f)We have developed a model predicting remaining strength of membrane materials for pavilions, based on an algorithm developed in (b), and examined its accuracy.(g)We have developed a model predicting the customer of condominiums from the questionnaire intended for visitors to model houses, based on an algorithm developed in (b), and examined its accuracy.(h)We have developed a model extracting the place where street crimes often happened from GIS data, based on an algorithm developed in (b), and examined its accuracy.(i)We have incorporated an algorithm developed in (c) to the evolutionally heuristics and applied it to the problem of assigning regions to evacuation centers against natural great disaster. Less