Outlier Detection under Interval Uncertainty: Algorithmic Solvability and Computational Complexity View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Vladik Kreinovich , Luc Longpré , Praveen Patangay , Scott Ferson , Lev Ginzburg

ABSTRACT

In many application areas, it is important to detect outliers. Traditional engineering approach to outlier detection is that we start with some ”normal” values x1,...,xn, compute the sample average E, the sample standard variation σ, and then mark a value x as an outlier if x is outside the k0-sigma interval [E − k0·σ,E + k0·σ] (for some pre-selected parameter k0). In real life, we often have only interval ranges \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$[{\underline x}_i,{\overline x}_i]$\end{document} for the normal values x1,...,xn. In this case, we only have intervals of possible values for the bounds E-k0·σ and E+k0·σ. We can therefore identify outliers as values that are outside all k0-sigma intervals. In this paper, we analyze the computational complexity of these outlier detection problems, and provide efficient algorithms that solve some of these problems (under reasonable conditions). More... »

PAGES

238-245

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24588-9_26

DOI

http://dx.doi.org/10.1007/978-3-540-24588-9_26

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1005640002


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computer Science Department, University of Texas at El Paso, 79968, El Paso, TX, USA", 
          "id": "http://www.grid.ac/institutes/grid.267324.6", 
          "name": [
            "Computer Science Department, University of Texas at El Paso, 79968, El Paso, TX, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kreinovich", 
        "givenName": "Vladik", 
        "id": "sg:person.012602771355.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012602771355.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, University of Texas at El Paso, 79968, El Paso, TX, USA", 
          "id": "http://www.grid.ac/institutes/grid.267324.6", 
          "name": [
            "Computer Science Department, University of Texas at El Paso, 79968, El Paso, TX, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Longpr\u00e9", 
        "givenName": "Luc", 
        "id": "sg:person.010474226755.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010474226755.58"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, University of Texas at El Paso, 79968, El Paso, TX, USA", 
          "id": "http://www.grid.ac/institutes/grid.267324.6", 
          "name": [
            "Computer Science Department, University of Texas at El Paso, 79968, El Paso, TX, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Patangay", 
        "givenName": "Praveen", 
        "id": "sg:person.016401717555.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016401717555.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Applied Biomathematics, 100 North Country Road, 11733, Setauket, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.422751.7", 
          "name": [
            "Applied Biomathematics, 100 North Country Road, 11733, Setauket, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ferson", 
        "givenName": "Scott", 
        "id": "sg:person.012115026643.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012115026643.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Applied Biomathematics, 100 North Country Road, 11733, Setauket, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.422751.7", 
          "name": [
            "Applied Biomathematics, 100 North Country Road, 11733, Setauket, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ginzburg", 
        "givenName": "Lev", 
        "id": "sg:person.015102730643.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015102730643.26"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "In many application areas, it is important to detect outliers. Traditional engineering approach to outlier detection is that we start with some \u201dnormal\u201d values x1,...,xn, compute the sample average E, the sample standard variation \u03c3, and then mark a value x as an outlier if x is outside the k0-sigma interval [E\u2009\u2212\u2009k0\u00b7\u03c3,E\u2009+\u2009k0\u00b7\u03c3] (for some pre-selected parameter k0). In real life, we often have only interval ranges \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$[{\\underline x}_i,{\\overline x}_i]$\\end{document} for the normal values x1,...,xn. In this case, we only have intervals of possible values for the bounds E-k0\u00b7\u03c3 and E+k0\u00b7\u03c3. We can therefore identify outliers as values that are outside all k0-sigma intervals. In this paper, we analyze the computational complexity of these outlier detection problems, and provide efficient algorithms that solve some of these problems (under reasonable conditions).", 
    "editor": [
      {
        "familyName": "Lirkov", 
        "givenName": "Ivan", 
        "type": "Person"
      }, 
      {
        "familyName": "Margenov", 
        "givenName": "Svetozar", 
        "type": "Person"
      }, 
      {
        "familyName": "Wa\u015bniewski", 
        "givenName": "Jerzy", 
        "type": "Person"
      }, 
      {
        "familyName": "Yalamov", 
        "givenName": "Plamen", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24588-9_26", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-21090-0", 
        "978-3-540-24588-9"
      ], 
      "name": "Large-Scale Scientific Computing", 
      "type": "Book"
    }, 
    "keywords": [
      "computational complexity", 
      "outlier detection", 
      "outlier detection problem", 
      "values x1", 
      "efficient algorithm", 
      "detection problem", 
      "algorithmic solvability", 
      "application areas", 
      "traditional engineering approaches", 
      "engineering approach", 
      "outliers", 
      "interval uncertainty", 
      "real life", 
      "complexity", 
      "algorithm", 
      "detection", 
      "possible values", 
      "value x", 
      "interval range", 
      "uncertainty", 
      "area", 
      "solvability", 
      "values", 
      "Xn", 
      "intervals", 
      "cases", 
      "X1", 
      "life", 
      "range", 
      "samples", 
      "problem", 
      "paper", 
      "approach", 
      "sample standard variation \u03c3", 
      "standard variation \u03c3", 
      "variation \u03c3", 
      "k0-sigma interval", 
      "normal values x1", 
      "bounds E"
    ], 
    "name": "Outlier Detection under Interval Uncertainty: Algorithmic Solvability and Computational Complexity", 
    "pagination": "238-245", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005640002"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24588-9_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24588-9_26", 
      "https://app.dimensions.ai/details/publication/pub.1005640002"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T19:03", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_8.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-24588-9_26"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24588-9_26'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24588-9_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24588-9_26'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24588-9_26'


 

This table displays all metadata directly associated to this object as RDF triples.

145 TRIPLES      23 PREDICATES      65 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24588-9_26 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N3e634b603a6b444693e718dce9a71f83
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description In many application areas, it is important to detect outliers. Traditional engineering approach to outlier detection is that we start with some ”normal” values x1,...,xn, compute the sample average E, the sample standard variation σ, and then mark a value x as an outlier if x is outside the k0-sigma interval [E − k0·σ,E + k0·σ] (for some pre-selected parameter k0). In real life, we often have only interval ranges \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$[{\underline x}_i,{\overline x}_i]$\end{document} for the normal values x1,...,xn. In this case, we only have intervals of possible values for the bounds E-k0·σ and E+k0·σ. We can therefore identify outliers as values that are outside all k0-sigma intervals. In this paper, we analyze the computational complexity of these outlier detection problems, and provide efficient algorithms that solve some of these problems (under reasonable conditions).
7 schema:editor Nba62e1d3db2545b3b976c40efc7a299c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3faa0bb706684df9981799e35ef414c0
12 schema:keywords X1
13 Xn
14 algorithm
15 algorithmic solvability
16 application areas
17 approach
18 area
19 bounds E
20 cases
21 complexity
22 computational complexity
23 detection
24 detection problem
25 efficient algorithm
26 engineering approach
27 interval range
28 interval uncertainty
29 intervals
30 k0-sigma interval
31 life
32 normal values x1
33 outlier detection
34 outlier detection problem
35 outliers
36 paper
37 possible values
38 problem
39 range
40 real life
41 sample standard variation σ
42 samples
43 solvability
44 standard variation σ
45 traditional engineering approaches
46 uncertainty
47 value x
48 values
49 values x1
50 variation σ
51 schema:name Outlier Detection under Interval Uncertainty: Algorithmic Solvability and Computational Complexity
52 schema:pagination 238-245
53 schema:productId N37445b50b4164334a2744bf3d20c1146
54 N9832f2dabf3b4a25ae9f3172d5d49fa4
55 schema:publisher Nb427bf380be244878e01f757e8127c6d
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005640002
57 https://doi.org/10.1007/978-3-540-24588-9_26
58 schema:sdDatePublished 2021-11-01T19:03
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher Na8eba5f70c6e4ddcb0b1f8df99166950
61 schema:url https://doi.org/10.1007/978-3-540-24588-9_26
62 sgo:license sg:explorer/license/
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N03b1fcee06b64d76a0cbfd33bbd294b3 rdf:first sg:person.015102730643.26
66 rdf:rest rdf:nil
67 N059f2898b2764eb7ac35b9b892d7d6a8 rdf:first Ncc414f24c500401daa5d349253440ac2
68 rdf:rest N904b8b4993e4498c9696b7628628639a
69 N2a8e80205c624044b14a21c97e066589 rdf:first sg:person.012115026643.10
70 rdf:rest N03b1fcee06b64d76a0cbfd33bbd294b3
71 N311c5097b9cd48e5a9fcb8753ecdd3b3 rdf:first sg:person.010474226755.58
72 rdf:rest Nbc4e10a3e56442cba59c46865febd44a
73 N37445b50b4164334a2744bf3d20c1146 schema:name doi
74 schema:value 10.1007/978-3-540-24588-9_26
75 rdf:type schema:PropertyValue
76 N3e634b603a6b444693e718dce9a71f83 rdf:first sg:person.012602771355.27
77 rdf:rest N311c5097b9cd48e5a9fcb8753ecdd3b3
78 N3faa0bb706684df9981799e35ef414c0 schema:isbn 978-3-540-21090-0
79 978-3-540-24588-9
80 schema:name Large-Scale Scientific Computing
81 rdf:type schema:Book
82 N4aea7989dc104105bd8eb30684baa046 schema:familyName Waśniewski
83 schema:givenName Jerzy
84 rdf:type schema:Person
85 N904b8b4993e4498c9696b7628628639a rdf:first N4aea7989dc104105bd8eb30684baa046
86 rdf:rest Nbc38315dd59d4c58af75ad91dcf06380
87 N9832f2dabf3b4a25ae9f3172d5d49fa4 schema:name dimensions_id
88 schema:value pub.1005640002
89 rdf:type schema:PropertyValue
90 N9aa773befc1f46a58b7c5debe072a36b schema:familyName Yalamov
91 schema:givenName Plamen
92 rdf:type schema:Person
93 Na8eba5f70c6e4ddcb0b1f8df99166950 schema:name Springer Nature - SN SciGraph project
94 rdf:type schema:Organization
95 Nb427bf380be244878e01f757e8127c6d schema:name Springer Nature
96 rdf:type schema:Organisation
97 Nba62e1d3db2545b3b976c40efc7a299c rdf:first Nfd900ab63a394588aa46bcfb858a08f5
98 rdf:rest N059f2898b2764eb7ac35b9b892d7d6a8
99 Nbc38315dd59d4c58af75ad91dcf06380 rdf:first N9aa773befc1f46a58b7c5debe072a36b
100 rdf:rest rdf:nil
101 Nbc4e10a3e56442cba59c46865febd44a rdf:first sg:person.016401717555.50
102 rdf:rest N2a8e80205c624044b14a21c97e066589
103 Ncc414f24c500401daa5d349253440ac2 schema:familyName Margenov
104 schema:givenName Svetozar
105 rdf:type schema:Person
106 Nfd900ab63a394588aa46bcfb858a08f5 schema:familyName Lirkov
107 schema:givenName Ivan
108 rdf:type schema:Person
109 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
110 schema:name Information and Computing Sciences
111 rdf:type schema:DefinedTerm
112 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
113 schema:name Computation Theory and Mathematics
114 rdf:type schema:DefinedTerm
115 sg:person.010474226755.58 schema:affiliation grid-institutes:grid.267324.6
116 schema:familyName Longpré
117 schema:givenName Luc
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010474226755.58
119 rdf:type schema:Person
120 sg:person.012115026643.10 schema:affiliation grid-institutes:grid.422751.7
121 schema:familyName Ferson
122 schema:givenName Scott
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012115026643.10
124 rdf:type schema:Person
125 sg:person.012602771355.27 schema:affiliation grid-institutes:grid.267324.6
126 schema:familyName Kreinovich
127 schema:givenName Vladik
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012602771355.27
129 rdf:type schema:Person
130 sg:person.015102730643.26 schema:affiliation grid-institutes:grid.422751.7
131 schema:familyName Ginzburg
132 schema:givenName Lev
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015102730643.26
134 rdf:type schema:Person
135 sg:person.016401717555.50 schema:affiliation grid-institutes:grid.267324.6
136 schema:familyName Patangay
137 schema:givenName Praveen
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016401717555.50
139 rdf:type schema:Person
140 grid-institutes:grid.267324.6 schema:alternateName Computer Science Department, University of Texas at El Paso, 79968, El Paso, TX, USA
141 schema:name Computer Science Department, University of Texas at El Paso, 79968, El Paso, TX, USA
142 rdf:type schema:Organization
143 grid-institutes:grid.422751.7 schema:alternateName Applied Biomathematics, 100 North Country Road, 11733, Setauket, NY, USA
144 schema:name Applied Biomathematics, 100 North Country Road, 11733, Setauket, NY, USA
145 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...