H-Mine — Frequent Pattern Mining

Đồ án môn học CSC14004 — Khai thác Dữ liệu (Data Mining), 2026

Cài đặt thuật toán H-mine bằng ngôn ngữ Julia để khai thác tập phổ biến (frequent pattern mining) trên cơ sở dữ liệu giao dịch. Dự án triển khai đầy đủ hai biến thể được mô tả trong bài báo gốc:

Biến thể	Mô tả
H-mine(Mem) — Algorithm 1	Khai thác toàn bộ CSDL trong bộ nhớ chính
H-mine — Algorithm 2	Khai thác theo phân hoạch (partition-based) cho CSDL lớn

Tham khảo: Pei et al. (2007) "H-Mine: Fast and space-preserving frequent pattern mining in large databases", IIE Transactions, 39, 593–605.

Yêu cầu hệ thống

Julia phiên bản ≥ 1.9 (Tải tại đây)
Hệ điều hành: Windows / macOS / Linux
Các package Julia (được cài tự động ở bước 3):
- DataStructures ≥ 0.18
- BenchmarkTools ≥ 1.3

Cài đặt

Bước 1 — Cài đặt Julia

Tải Julia tại: https://julialang.org/downloads/
Chạy installer. Quan trọng: Khi cài đặt, đánh dấu chọn "Add Julia to PATH" để có thể gọi julia từ terminal.

Nếu quên chọn "Add to PATH", thêm thủ công bằng cách mở PowerShell và chạy:
# Thay đổi đường dẫn nếu phiên bản Julia khác
[Environment]::SetEnvironmentVariable("Path", $env:Path + ";$env:LOCALAPPDATA\Programs\Julia-1.12.6\bin", "User")
Sau đó đóng và mở lại terminal.

Kiểm tra cài đặt thành công:

julia --version
# julia version 1.12.6

Bước 2 — Clone dự án

git clone https://github.com/Taylor3691/data-mining-project-2.git
cd data-mining-project-2

Bước 3 — Cài đặt dependency

julia --project=. -e "using Pkg; Pkg.instantiate()"

Lệnh trên sẽ tự động tải và cài đặt tất cả package được khai báo trong Project.toml. Chỉ cần chạy một lần duy nhất.

Cách sử dụng

julia --project=. src/main.jl <input_file> <min_sup> [options]

Tham số bắt buộc:

Tham số	Mô tả
`<input_file>`	Đường dẫn file dữ liệu đầu vào (định dạng SPMF)
`<min_sup>`	Ngưỡng support tối thiểu (số nguyên, absolute support)

Tham số tùy chọn:

Tùy chọn	Mô tả	Mặc định
`--output <file>`	Đường dẫn file kết quả đầu ra	In ra console
`--algorithm <1\|2>`	Chọn thuật toán: `1` = H-mine(Mem), `2` = H-mine	`1`
`--partitions <k>`	Số phần chia CSDL (chỉ dùng với Algorithm 2)	Tự động
`--memory <n>`	Bộ nhớ khả dụng tính theo số entry (chỉ dùng với Algorithm 2)	`100000`

Ví dụ

# Chạy cơ bản
julia --project=. src/main.jl data/toy/1-example.txt 2

# Xuất kết quả ra file
julia --project=. src/main.jl data/toy/4-paper.txt 2 --output results.txt

# Dùng Algorithm 2 cho dữ liệu lớn
julia --project=. src/main.jl data/benchmark/chess.txt 2000 --algorithm 2 --partitions 4

Kết quả đầu ra

Kết quả hiển thị trên console hoặc ghi ra file theo định dạng SPMF:

1 3 5 #SUP: 4
2 3 #SUP: 3
1 2 3 #SUP: 2

Mỗi dòng gồm: danh sách item (cách nhau bởi dấu cách) + #SUP: + giá trị support.

Định dạng dữ liệu

Dự án sử dụng định dạng SPMF — mỗi dòng là một giao dịch, các item (số nguyên) cách nhau bởi dấu cách:

Lưu ý: Các dataset benchmark (chess, mushroom, retail, accidents) có thể tải từ SPMF Data Repository hoặc FIMI Repository. Đặt file vào thư mục data/benchmark/.

Cấu trúc dự án

data-mining-project-2/
├── src/                          # Mã nguồn chính
│   ├── main.jl                   # Điểm vào — xử lý CLI và chạy thuật toán
│   ├── structures.jl             # Cấu trúc dữ liệu (HStruct, HeaderTable, ...)
│   ├── utils.jl                  # Tiện ích I/O, xây dựng H-struct, phân hoạch DB
│   └── algorithm/
│       ├── hmine_mem.jl          # Algorithm 1 — H-mine(Mem) Baseline
│       ├── hmine_mem_optimized.jl # Algorithm 1 — H-mine(Mem) Optimized
│       └── hmine.jl              # Algorithm 2 — H-mine (partition-based)
├── tests/                        # Bộ kiểm thử
│   ├── 3-1_test_basic.jl         # Chương 3: Cài đặt cơ bản, xuất patterns vs SPMF
│   ├── 3-2_test_unit.jl          # Chương 3: Unit test tự động 8 CSDL
│   ├── 3-3_test_optimization.jl  # Chương 3: So sánh Baseline vs Optimized
│   ├── 4-test_a_correctness.jl   # Chương 4: Tính đúng đắn vs SPMF
│   ├── 4-test_b_runtime.jl       # Chương 4: Thời gian chạy theo minsup
│   ├── 4-test_c_itemset_count.jl # Chương 4: Số pattern theo minsup
│   ├── 4-test_d_memory.jl        # Chương 4: Bộ nhớ
│   ├── 4-test_e_scalability.jl   # Chương 4: Scalability
│   └── 4-test_f_txn_length.jl    # Chương 4: Ảnh hưởng avg txn length
├── data/
│   ├── toy/                      # Dữ liệu nhỏ dùng cho test
│   │   ├── 1-example.txt
│   │   ├── 2-dense.txt
│   │   ├── 3-mixed.txt
│   │   ├── 4-paper.txt           # CSDL từ bài báo gốc (Table 1)
│   │   └── 5-sparse.txt
│   └── benchmark/                # Dữ liệu benchmark
│       ├── chess.txt
│       ├── mushroom.txt
│       ├── retail.txt
│       └── accidents.txt
├── spmf.jar                      # SPMF reference software
├── Project.toml                  # Cấu hình dự án Julia + dependency
└── README.md

Kiểm thử

Yêu cầu bổ sung: Các file test Chương 3 & 4 so sánh tự động với SPMF nên cần:

Java JDK (đã cài tại D:\Tools\JDK\bin\java.exe)

spmf.jar (đã có sẵn trong thư mục gốc dự án)

Tham số chung

Tất cả file test đều hỗ trợ:

Tham số	Mô tả
`<minsup>`	Absolute (vd: `2500`) hoặc relative (vd: `80%`)
`--output <file>`	Lưu kết quả ra file TXT thay vì in terminal
`--runs <n>`	Số lần chạy lấy median (mặc định: 3-5)

Chương 3 — Cài đặt & Tối ưu

3-1. Cài đặt cơ bản

Xuất toàn bộ frequent itemset + support, so sánh tự động với SPMF.

julia --project=. tests/3-1_test_basic.jl <input> <minsup> [--output <file>]

Ví dụ:

julia --project=. tests/3-1_test_basic.jl data/toy/1-example.txt 2
julia --project=. tests/3-1_test_basic.jl data/benchmark/chess.txt 80% --output results/3-1_chess.txt

Kết quả: Danh sách pattern (SPMF format), tỉ lệ khớp, pattern thiếu/thừa/sai support.

3-2. Tái tạo đúng kết quả (Unit Test)

Tự động chạy trên 8 CSDL (5 toy + 3 benchmark), ở nhiều minsup, so sánh với SPMF.

julia --project=. tests/3-2_test_unit.jl [--output <file>]

Không cần tham số — tự động quét datasets.

Kết quả:

Dataset                     minsup    #Ours     #SPMF     Khớp      Match%    Status
toy/1-example.txt           2         13        13        13        100.0%    PASS
benchmark/chess.txt         2600      6135      6135      6135      100.0%    PASS
...
PASS: 23/23   Tỉ lệ đúng: 100.0%

3-3. Tối ưu hóa bộ nhớ & tốc độ

So sánh Baseline (hmine_mem.jl) vs Optimized (hmine_mem_optimized.jl).

julia --project=. tests/3-3_test_optimization.jl <input> <minsup> [--output <file>] [--runs <n>]

Ví dụ:

julia --project=. tests/3-3_test_optimization.jl data/benchmark/chess.txt 80%
julia --project=. tests/3-3_test_optimization.jl data/benchmark/mushroom.txt 50% --output results/3-3_mushroom.txt

Kết quả:

Metric                   Baseline          Optimized         Cải thiện
Thời gian (ms)           120.5             42.3              64.9% (2.85x)
Bộ nhớ cấp phát          85.2 MB           52.1 MB           38.8%
#Patterns                6135              6135              ✓ khớp

Kỹ thuật tối ưu: @inbounds, BitSet, sizehint!, shared prefix buffer.

Chương 4 — Thực nghiệm so sánh với SPMF

4-a. Kiểm tra tính đúng đắn

julia --project=. tests/4-test_a_correctness.jl <input> <minsup> [--output <file>]

So sánh pattern-by-pattern với SPMF: tỉ lệ khớp, thiếu, thừa, sai support.

4-b. Thời gian chạy theo minsup

julia --project=. tests/4-test_b_runtime.jl <input> <minsup_list> [--output <file>] [--runs <n>]

<minsup_list>: danh sách phân cách bởi , (vd: 90%,85%,80%,75%,70% hoặc 2900,2700,2500).

Kết quả: Bảng minsup | #Patterns | Ours (ms) | SPMF (ms).

4-c. Số lượng frequent itemset theo minsup

julia --project=. tests/4-test_c_itemset_count.jl <input> <minsup_list> [--output <file>]

4-d. Sử dụng bộ nhớ

julia --project=. tests/4-test_d_memory.jl <input> <minsup> [--output <file>] [--runs <n>]

Kết quả: Bảng Metric | H-mine Opt | SPMF (patterns, time, memory).

4-e. Khả năng mở rộng (Scalability)

julia --project=. tests/4-test_e_scalability.jl <input> <minsup> [--output <file>] [--runs <n>]

Tạo tập con 10%/25%/50%/75%/100%, đo thời gian Ours vs SPMF.

4-f. Ảnh hưởng độ dài giao dịch

julia --project=. tests/4-test_f_txn_length.jl <n_trans> <n_items> <minsup> [--output <file>] [--runs <n>]

Sinh CSDL tổng hợp với avg_len tăng dần (5→30), so sánh Ours vs SPMF.

Ví dụ:

julia --project=. tests/4-test_f_txn_length.jl 2000 50 5%

Ví dụ minh họa

Chạy nhanh với dữ liệu mẫu

# Chạy H-mine(Mem) trên dữ liệu bài báo, min_sup = 2
julia --project=. src/main.jl data/toy/4-paper.txt 2

Kết quả mong đợi:

=======================================================
  H-MINE -- Frequent Pattern Mining
=======================================================
  Input file   : data/toy/4-paper.txt
  Min support  : 2
  Algorithm    : Algorithm 1
  Transactions : 4
  Items        : 9
=======================================================

Running H-mine(Mem)...

Done! Found ... frequent patterns
  Elapsed time: ... ms

Sử dụng trong Julia REPL

# Kích hoạt môi trường dự án
# julia --project=.

include("src/algorithm/hmine.jl")

# Đọc dữ liệu
tdb = load_transactions_spmf("data/toy/1-example.txt")

# Chạy H-mine(Mem) với min_sup = 2
patterns = run_hmine_mem(tdb, 2)

# In kết quả
print_patterns(patterns)

# Lưu kết quả ra file
save_patterns_spmf(patterns, "output.txt")

Kết quả kiểm thử mới nhất

================================================================================
  TÁI TẠO ĐÚNG KẾT QUẢ — Unit Test tự động (H-mine Optimized vs SPMF)
================================================================================

  Tổng test cases: 23

  Dataset                     minsup    #Ours     #SPMF     Khớp      Match%    Status
  --------------------------------------------------------------------------------------
  toy/1-example.txt           1         55        35        35        100.0%    PASS
  toy/1-example.txt           2         35        35        35        100.0%    PASS
  toy/1-example.txt           3         17        17        17        100.0%    PASS
  toy/4-paper.txt             1         147       147       147       100.0%    PASS
  toy/4-paper.txt             2         17        17        17        100.0%    PASS
  toy/4-paper.txt             3         7         7         7         100.0%    PASS
  toy/2-dense.txt             1         7         7         7         100.0%    PASS
  toy/2-dense.txt             2         7         7         7         100.0%    PASS
  toy/2-dense.txt             3         7         7         7         100.0%    PASS
  toy/5-sparse.txt            1         23        23        23        100.0%    PASS
  toy/5-sparse.txt            2         4         4         4         100.0%    PASS
  toy/3-mixed.txt             1         63        63        63        100.0%    PASS
  toy/3-mixed.txt             2         14        14        14        100.0%    PASS
  toy/3-mixed.txt             3         6         6         6         100.0%    PASS
  benchmark/chess.txt         2800      1350      1339      1339      100.0%    PASS
  benchmark/chess.txt         2600      6135      6135      6135      100.0%    PASS
  benchmark/chess.txt         2400      20582     20479     20479     100.0%    PASS
  benchmark/mushroom.txt      4000      191       191       191       100.0%    PASS
  benchmark/mushroom.txt      3000      1035      1035      1035      100.0%    PASS
  benchmark/mushroom.txt      2000      6961      6961      6961      100.0%    PASS
  benchmark/retail.txt        200       326       325       325       100.0%    PASS
  benchmark/retail.txt        100       1061      1061      1061      100.0%    PASS
  benchmark/retail.txt        50        3384      3294      3294      100.0%    PASS

================================================================================
  TỔNG KẾT
================================================================================
  Tổng test cases : 23
  PASS            : 23
  FAIL            : 0
  Tỉ lệ đúng     : 100.0% (41209 / 41209 patterns)

================================================================================

Xử lý sự cố

Lỗi	Nguyên nhân	Cách khắc phục
`julia is not recognized`	Julia chưa được thêm vào PATH	Thêm Julia vào PATH (xem phần Cài đặt)
`Package not found`	Chưa cài dependency	Chạy `julia --project=. -e "using Pkg; Pkg.instantiate()"`
`File not found`	Sai đường dẫn file dữ liệu	Kiểm tra file tồn tại, chạy từ thư mục gốc dự án
`MethodError` hoặc lỗi runtime	Phiên bản Julia quá cũ	Cập nhật Julia ≥ 1.9

Navigation Menu

Repository files navigation

H-Mine — Frequent Pattern Mining

Mục lục

Yêu cầu hệ thống

Cài đặt

Bước 1 — Cài đặt Julia

Bước 2 — Clone dự án

Bước 3 — Cài đặt dependency

Cách sử dụng

Ví dụ

Kết quả đầu ra

Định dạng dữ liệu

Cấu trúc dự án

Kiểm thử

Tham số chung

Chương 3 — Cài đặt & Tối ưu

3-1. Cài đặt cơ bản

3-2. Tái tạo đúng kết quả (Unit Test)

3-3. Tối ưu hóa bộ nhớ & tốc độ

Chương 4 — Thực nghiệm so sánh với SPMF

4-a. Kiểm tra tính đúng đắn

4-b. Thời gian chạy theo minsup

4-c. Số lượng frequent itemset theo minsup

4-d. Sử dụng bộ nhớ

4-e. Khả năng mở rộng (Scalability)

4-f. Ảnh hưởng độ dài giao dịch

Ví dụ minh họa

Chạy nhanh với dữ liệu mẫu

Sử dụng trong Julia REPL

Kết quả kiểm thử mới nhất

Xử lý sự cố

About

Releases

Packages

Contributors

Languages

Name		Name	Last commit message	Last commit date
data		data
notebooks		notebooks
results		results
src		src
tests		tests
.gitignore		.gitignore
README.md		README.md
benchmark_runtime.jl		benchmark_runtime.jl
project.toml		project.toml
spmf.jar		spmf.jar

Latest commit

History

Folders and files

Repository files navigation

H-Mine — Frequent Pattern Mining

Mục lục

Yêu cầu hệ thống

Cài đặt

Bước 1 — Cài đặt Julia

Bước 2 — Clone dự án

Bước 3 — Cài đặt dependency

Cách sử dụng

Ví dụ

Kết quả đầu ra

Định dạng dữ liệu

Cấu trúc dự án

Kiểm thử

Tham số chung

Chương 3 — Cài đặt & Tối ưu

3-1. Cài đặt cơ bản

3-2. Tái tạo đúng kết quả (Unit Test)

3-3. Tối ưu hóa bộ nhớ & tốc độ

Chương 4 — Thực nghiệm so sánh với SPMF

4-a. Kiểm tra tính đúng đắn

4-b. Thời gian chạy theo minsup

4-c. Số lượng frequent itemset theo minsup

4-d. Sử dụng bộ nhớ

4-e. Khả năng mở rộng (Scalability)

4-f. Ảnh hưởng độ dài giao dịch

Ví dụ minh họa

Chạy nhanh với dữ liệu mẫu

Sử dụng trong Julia REPL

Kết quả kiểm thử mới nhất

Xử lý sự cố

About

Topics

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages