순차 패턴 마이닝

Sequential pattern mining

순차 패턴 마이닝은 데이터 마이닝의 주제로서, 데이터 예시들 사이에서 통계적으로 관련되는 패턴을 찾는 것과 관련이 있다.[1]일반적으로 값은 별개의 것으로 추정되며, 따라서 시계열 채굴은 밀접하게 관련되어 있지만, 보통은 다른 활동으로 간주된다.순차 패턴 마이닝은 구조화된 데이터 마이닝의 특별한 경우다.null

이 분야에서는 몇 가지 주요 전통적인 계산 문제가 다루어져 있다.여기에는 시퀀스 정보를 위한 효율적인 데이터베이스 및 인덱스 구축, 자주 발생하는 패턴 추출, 유사성에 대한 시퀀스 비교, 누락된 시퀀스 멤버 복구 등이 포함된다.일반적으로 시퀀스 마이닝 문제는 일반적으로 문자열 처리 알고리즘과 연결 규칙 학습에 기반한 항목 집합 마이닝에 기반한 문자열 마이닝으로 분류될 수 있다.로컬 프로세스 모델은 순차적 패턴 마이닝을 순차적 주문 구조 외에도 선택, 루프 및 동시성 구조를 포함할 수 있는 더 복잡한 패턴으로 확장한다.null

스트링 마이닝

스트링 마이닝은 일반적으로 순서에 따라 나타나는 항목에 대해 제한된 알파벳을 다루지만, 순서 자체는 일반적으로 매우 길 수도 있다.알파벳의 예로는 자연어 텍스트에 사용되는 ASCII 문자 집합, DNA 서열에서 뉴클레오티드 베이스 'A', 'G', 'C', 'T' 또는 단백질 서열을 위한 아미노산이 있을 수 있다.생물학적 응용에서 문자열의 알파벳 배열 분석을 사용하여 유전자와 단백질 서열을 검사하여 그 특성을 결정할 수 있다.DNA나 단백질의 문자 순서를 아는 것 자체가 궁극적인 목표는 아니다.오히려 그 구조와 생물학적 기능 측면에서 그 순서를 이해하는 것이 주요 과제다.이는 일반적으로 각 시퀀스 내에서 개별 영역 또는 구조 단위를 식별한 후 각 구조 단위에 함수를 할당함으로써 먼저 달성된다.많은 경우에 이것은 주어진 순서와 이전에 연구된 순서를 비교해야 한다.문자열에서 삽입, 삭제, 돌연변이가 발생하면 문자열의 비교가 복잡해진다.null

생물정보학을 위한 시퀀스 비교를 위한 핵심 알고리즘의 조사와 분류법은 Abouelhoda & Ghanem(2010)에 의해 제시되며,[3] 여기에는 다음이 포함된다.

  • 반복 관련 문제: 단일 시퀀스에 대한 작업을 처리하며 분산된 고정 길이 및 최대 길이 반복을 찾기 위한 정확한 문자열 일치 또는 대략적인 문자열 일치 방법을 기반으로 할 수 있으며, 탠덤 반복을 찾고, 고유 반복 및 누락(속도가 없는) 반복을 찾는 데 사용할 수 있다.
  • 정렬 문제: 하나 이상의 시퀀스를 먼저 정렬하여 문자열 간의 비교를 처리하는 방법. 일반적인 방법의 예로는 데이터베이스의 단일 시퀀스를 여러 시퀀스와 비교하는 VLAST와 다중 얼라인먼트에 대한 ClustalW가 있다.정렬 알고리즘은 정확하거나 근사적인 방법에 기초할 수 있으며, 전역 정렬, 반 전역 정렬 및 로컬 정렬로도 분류할 수 있다.시퀀스 정렬을 참조하십시오.

아이템셋 마이닝

시퀀스 마이닝의 몇 가지 문제점은 자주 발생하는 항목 집합과 나타나는 순서를 스스로 발견하는 데 빌려주는데, 예를 들어 '{고객이 차를 사면 1주일 이내에 {보험}을 사게 된다'는 형식의 규칙을 구하거나, 주가의 맥락에서 '{노키아 업과 에릭슨 업'이라고 하면 {모토롤라 업과 삼성 u.2일 이내에 p}".전통적으로 품목셋 마이닝은 대규모 거래에서 자주 발생하는 품목들 사이의 규칙성을 발견하기 위한 마케팅 어플리케이션에 사용된다.예를 들어 슈퍼마켓에서 고객 쇼핑 바구니 거래를 분석해 보면 '고객이 양파와 감자를 함께 사면 햄버거 고기도 같은 거래로 살 가능성이 높다'는 규칙을 만들 수 있다.null

아이템 세트 마이닝의 핵심 알고리즘에 대한 조사와 분류법은 Han et al.에 의해 제시된다.(2007).[4]null

빈번한 항목 집합 채굴을 위한 시퀀스 데이터베이스에 적용되는 두 가지 일반적인 기법은 영향력 있는 애프리오리 알고리즘과 보다 최신의 FP-성장 기법이다.null

적용들

제품 및 사용자 구매 행태의 변화가 큰 상황에서 제품을 전시하고 있는 선반들은 소매 환경에서 가장 중요한 자원 중 하나이다.유통업체는 수익 증대뿐 아니라 쉘프 공간 할당과 제품 디스플레이를 적절히 관리해 비용을 절감할 수 있다.이 문제를 해결하기 위해 조지·비누(2013년)는 접두사스팬 알고리즘을 이용해 사용자 구매 패턴을 채굴하고 채굴된 구매 패턴의 순서를 기준으로 제품을 선반 위에 놓는 방식을 제안했다.[5]null

알고리즘

일반적으로 사용되는 알고리즘은 다음과 같다.

  • GSP 알고리즘
  • SPADE(등가 등급)를 사용한 순차 패턴 검색
  • 자유 스판
  • 접두사 스판
  • MAPres[6]
  • Seq2Pat(제약 기반 순차 패턴 마이닝용)[7][8]

참고 항목

참조

  1. ^ Mabroukeh, N. R.; Ezeife, C. I. (2010). "A taxonomy of sequential pattern mining algorithms". ACM Computing Surveys. 43: 1–41. CiteSeerX 10.1.1.332.4745. doi:10.1145/1824795.1824798. S2CID 207180619.
  2. ^ Tax, N.; Sidorova, N.; Haakma, R.; van der Aalst, Wil M. P. (2016). "Mining Local Process Models". Journal of Innovation in Digital Ecosystems. 3 (2): 183–196. arXiv:1606.06066. doi:10.1016/j.jides.2016.11.001. S2CID 10872379.
  3. ^ Abouelhoda, M.; Ghanem, M. (2010). "String Mining in Bioinformatics". In Gaber, M. M. (ed.). Scientific Data Mining and Knowledge Discovery. Springer. doi:10.1007/978-3-642-02788-8_9. ISBN 978-3-642-02787-1.
  4. ^ Han, J.; Cheng, H.; Xin, D.; Yan, X. (2007). "Frequent pattern mining: current status and future directions". Data Mining and Knowledge Discovery. 15 (1): 55–86. doi:10.1007/s10618-006-0059-1.
  5. ^ George, A.; Binu, D. (2013). "An Approach to Products Placement in Supermarkets Using PrefixSpan Algorithm". Journal of King Saud University-Computer and Information Sciences. 25 (1): 77–87. doi:10.1016/j.jksuci.2012.07.001.
  6. ^ Ahmad, Ishtiaq; Qazi, Wajahat M.; Khurshid, Ahmed; Ahmad, Munir; Hoessli, Daniel C.; Khawaja, Iffat; Choudhary, M. Iqbal; Shakoori, Abdul R.; Nasir-ud-Din (1 May 2008). "MAPRes: Mining association patterns among preferred amino acid residues in the vicinity of amino acids targeted for post-translational modifications". Proteomics. 8 (10): 1954–1958. doi:10.1002/pmic.200700657. PMID 18491291. S2CID 22362167.
  7. ^ Hosseininasab A, van Hoeve WJ, Cire AA (2019). "Constraint-Based Sequential Pattern Mining with Decision Diagrams". Proceedings of the AAAI Conference on Artificial Intelligence. 33: 1495–1502. doi:10.1609/aaai.v33i01.33011495. S2CID 53427299.
  8. ^ https://github.com/fidelity/seq2pat

외부 링크

  • SPMF는 GSP, PrefixSpan, SPADE, SPAME 등의 오픈 소스 구현을 포함한다.