Approximation of Probabilistic Maximal Frequent Itemset Mining Over Uncertain Sensed Data

Event detection by discovering frequent itemsets is very popular in sensor network communities. However, the recorded data is often a probability rather than a determined value in a really productive environment as sensed data is often affected by noise. In this paper, we study to detect events by f...

Full description

Saved in:
Bibliographic Details
Published in:IEEE access 2020, Vol.8, p.97529-97539
Main Authors: Chen, Sheng, Nie, Lihai, Tao, Xiaoyi, Li, Zhiyang, Zhao, Laiping
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Approximation algorithms
Complexity
Data mining
event detection
Frequency measurement
Itemsets
Mathematical analysis
Probabilistic logic
probabilistic maximal frequent patterns
Semantics
Statistical analysis
Time complexity
Uncertain database
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Event detection by discovering frequent itemsets is very popular in sensor network communities. However, the recorded data is often a probability rather than a determined value in a really productive environment as sensed data is often affected by noise. In this paper, we study to detect events by finding frequent patterns over probabilistic sensor data under the Possible World Semantics . This is technically challenging as probabilistic records can generate an exponential number of possible worlds. Although several efficient algorithms are proposed in the literature, it is still difficult to mine probabilistic maximal frequent items (PMFIs) in large uncertain database due to the high time complexity. To address this issue, we employ approximate idea to further reduce the time complexity from O(nlogn) to O(n) and propose a two-step solution (Aproximation Probabilistic Frequent Itemset-MAX, APFI-MAX in short) including PMFI candidates generation and PMFIs confirmation. We also provide the necessary proofs of our approximation method to make APFI-MAX more solid and convincing. Finally, extensive experiments have been conducted on synthetic and real databases, demonstrating that the proposed APFI-MAX always running faster than state-of-art methods under different parameter settings.
ISSN:2169-3536
2169-3536
DOI:10.1109/ACCESS.2020.2997409