کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
468191 698196 2013 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Data complexity measured by principal graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Data complexity measured by principal graphs
چکیده انگلیسی

How to measure the complexity of a finite set of vectors embedded in a multidimensional space? This is a non-trivial question which can be approached in many different ways. Here we suggest a set of data complexity measures using universal approximators, principal cubic complexes. Principal cubic complexes generalize the notion of principal manifolds for datasets with non-trivial topologies. The type of the principal cubic complex is determined by its dimension and a grammar of elementary graph transformations. The simplest grammar produces principal trees.We introduce three natural types of data complexity: (1) geometric (deviation of the data’s approximator from some “idealized” configuration, such as deviation from harmonicity); (2) structural (how many elements of a principal graph are needed to approximate the data), and (3) construction complexity (how many applications of elementary graph transformations are needed to construct the principal object starting from the simplest one).We compute these measures for several simulated and real-life data distributions and show them in the “accuracy–complexity” plots, helping to optimize the accuracy/complexity ratio. We discuss various issues connected with measuring data complexity. Software for computing data complexity measures from principal cubic complexes is provided as well.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Mathematics with Applications - Volume 65, Issue 10, May 2013, Pages 1471–1482
نویسندگان
, ,