Ứng dụng thuật toán efim để khai phá tập mục hữu ích cao từ cơ sở dữ liệu bán hàng tại siêu thị co.opmart quảng ngãi

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

PHẠM THỊ KIM PHƯỢNG

ỨNG DỤNG THUẬT TOÁN EFIM

ĐỂ KHAI PHÁ TẬP MỤC HỮU ÍCH CAO TỪ

CƠ SỞ DỮ LIỆU BÁN HÀNG TẠI SIÊU THỊ

CO.OPMART QUẢNG NGÃI

Chuyên ngành: Hệ thống thông tin

Mã số: 61.49.01.04

TÓM TẮT

LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN

Đà Nẵng – Năm 2017

Công trình được hoàn thành tại

TRƯỜNG ĐẠI HỌC SƯ PHẠM - ĐHĐN

Người hướng dẫn khoa học: PGS.TSKH. Trần Quốc Chiến

Phản biện 1: TS. Vũ Thị Thanh Trà

Phản biện 2: TS. Nguyễn Quang Thanh

Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn tốt

nghiệp thạc sĩ Hệ thống thông tin họp tại Đại học sư phạm – Đại học

Đà Nẵng vào ngày 30 tháng 07 năm 2017

Có thể tìm hiểu luận văn tại:

Thư viện Trường Đại học Sư phạm Đà Nẵng, Đại học Đà Nẵng.

1

MỞ ĐẦU

1. Lý do chọn đề tài

Trong những năm gần đây, khai phá dữ liệu (Data mining) đã

trở thành một trong những hướng nghiên cứu lớn nhất của lĩnh vực

khoa học máy tính và công nghệ thông tin. Khai phá dữ liệu là quá

trình khai phá, trích xuất, khai thác và sử dụng những dữ liệu có giá

trị tiềm ẩn từ bên trong lượng lớn dữ liệu được lưu trữ trong các Cơ

Sở Dữ Liệu (CSDL), kho dữ liệu, trung tâm dữ liệu… dựa trên kĩ

thuật như mạng nơ ron, lý thuyết tập thô, tập mờ, biểu diễn tri thức…

Khai phá dữ liệu đang được áp dụng một cách rộng rãi trong nhiều

lĩnh vực kinh doanh và đời sống khác nhau: Marketing, tài chính,

ngân hàng, bảo hiểm, khoa học, y tế, giáo dục, an ninh...

Khai phá tập mục phổ biến thông thường tập trung chủ yếu vào

việc tìm kiếm và phát hiện các tập mục thường xuyên trong CSDL

giao tác. Mô hình khai phá tập mục phổ biến cơ bản có nhiều ứng

dụng trong thực tế nhưng có những hạn chế, không đáp ứng đầy đủ

yêu cầu của người sử. Chính vì vậy mà một khái niệm mới ra đời, đó

là khai phá tập mục hữu ích cao (High Utility Itemsets Mining) tức là

mỗi một mục có xét đến yếu tố hữu ích của nó (ví dụ: Nhà kinh

doanh họ chỉ quan tâm đến số lượng, lợi nhuận, doanh thu của mỗi

mặt hàng là bao nhiêu trong mỗi lần giao dịch). Như vậy, khai phá

tập mục hữu ích cao là tìm kiếm trong CSDL giao tác các tập mục có

giá trị lớn hơn một ngưỡng hữu ích tối thiểu cho trước.

Khai phá tập mục hữu ích cao là một mở rộng của bài toán

khai phá tập mục phổ biến, đã được nhiều tác giả quan tâm với mục

2

đích đánh giá ý nghĩa của các tập mục trong khai phá luật kết hợp.

Thuật toán EFIM là một trong các thuật toán khai phá tập mục hữu

ích cao, đây là thuật toán mới có khả năng khắc phục các hạn chế của

các thuật toán được đề xuất trước đó.

Siêu thị Co.opMart Quảng Ngãi là một hệ thống siêu thị bán lẻ

của Việt Nam trực thuộc Liên hiệp các Hợp tác xã Thương mại thành

phố Hồ Chí Minh. Co.opMart trở thành nơi mua sắm đáng tin cậy

của người tiêu dùng Quảng Ngãi. Siêu thị cung cấp nhiều mặt hàng

đảm bảo chất lượng và số lượng. Tuy nhiên trong siêu thị có những

mặt hàng tuy số lượng bán nhiều nhưng lợi nhuận mang lại khá thấp

và ngược lại có những mặt hàng tuy số lượng bán ít nhưng mang lại

lợi nhuận cao mà siêu thị chưa xác định được nên chưa có chiến lược

kinh doanh dẫn đến doanh thu bán hàng thấp. Ví dụ: Một ngày siêu

thị bán được 100 bịch khăn giấy nhưng lợi nhuận không cao bằng

bán 1 cái tivi.

Từ đó ta có thể áp dụng kỹ thuật khai phá tập mục hữu ích cao

để rút ra thông tin các mặt hàng bán kèm với nhau mang lại giá trị lợi

nhuận cao cho siêu thị. Coi mỗi mặt hàng là một mục, mỗi hóa đơn

bán hàng là một giao tác. Ứng với mỗi giao tác, mỗi mục có một giá

trị hữu ích nội, chính là số lượng bán ra của mỗi mặt hàng trong từng

hóa đơn, mỗi mặt hàng có giá trị lợi nhuận và được coi là giá trị hữu

ích ngoại của mục.

Từ những lý do trên, với sự hướng dẫn của thầy PGS.TSKH.

Trần Quốc Chiến. Tôi chọn hướng nghiên cứu và thực hiện đề tài:

“Ứng dụng thuật toán EFIM để khai phá tập mục hữu ích cao từ

3

cơ sở dữ liệu bán hàng tại siêu thị Co.opMart Quảng Ngãi”.

2. Mục tiêu và nhiệm vụ

2.1. Mục tiêu

- Thu thập dữ liệu bán hàng tại siêu thị Co.opMart Quảng Ngãi.

- Tìm hiểu thuật toán EFIM để khai phá tập mục hữu ích cao từ

CSDL giao tác.

- Ứng dụng thuật toán EFIM để tìm các tập mục hữu ích cao từ

CSDL bán hàng tại siêu thị Co.opMart Quảng Ngãi.

2.2. Nhiệm vụ

- Tìm hiểu các khái niệm cơ bản về khai phá dữ liệu và khai

phá luật kết hợp.

- Tìm hiểu các thuật toán khai phá tập mục hữu ích cao trước đây.

- Tìm hiểu thuật toán EFIM.

- Thu nhập dữ liệu từ thực tế, tổng hợp phân tích dữ liệu.

- Cài đặt thuật toán EFIM trên CSDL giao tác và rút ra những tập

mục hữu ích cao của mặt hàng thường bán kèm với nhau mang lại lợi

nhuận cao cho siêu thị.

- So sánh thuật toán EFIM so với thuật toán khác.

3. Đối tượng và phạm vi nghiên cứu

3.1. Đối tượng

- Thuật toán EFIM để khai phá tập mục hữu ích cao.

- Thông tin dữ liệu bán hàng tại siêu thị.

3.2. Phạm vi nghiên cứu

- Nghiên cứu thuật toán EFIM để khai phá tập mục hữu ích cao

từ CSDL giao tác.

4

- Số liệu kinh doanh của siêu thị Co.opMart tại Quảng Ngãi

trong thời gian năm 2016.

4. Phương pháp nghiên cứu

4.1. Phương pháp nghiên cứu tài liệu

- Tiến hành thu thập và nghiên cứu các tài liệu có liên quan

đến đề tài.

- Nghiên cứu giải pháp xây dựng và cài đặt thuật toán EFIM.

4.2. Phương pháp thực nghiệm

- Xây dựng cơ sở dữ liệu.

- Cài đặt thuật toán và chạy thử nghiệm trên bộ dữ liệu giao tác.

- Nhận xét và đánh giá kết quả thuật toán EFIM với thuật toán khác.

5. Ý nghĩa của đề tài

5.1. Ý nghĩa khoa học

- Cài đặt thuật toán EFIM để rút ra các mặt hàng bán kèm có

giá trị lợi nhuận cao làm cơ sở để áp dụng thuật toán khai phá luật kết

hợp từ tập mục hữu ích cao.

- Rút ra các ưu điểm so với các thuật toán khác.

5.2. Ý nghĩa thực tiễn

Từ CSDL bán hàng rút ra các mặt hàng bán kèm mang lại lợi

nhuận cao, từ đó định hướng kinh doanh cho siêu thị.

6. Kết quả dự kiến

6.1. Kết quả của đề tài

- Nắm được lý thuyết khai phá tập mục hữu ích cao bằng thuật

toán EFIM.

- Ứng dụng trên CSDL giao tác bán hàng tại siêu thị

5

Co.opMart Quảng Ngãi.

6.2. Hướng phát triển của đề tài.

- Nghiên cứu các thuật toán khai phá tập mục hữu ích cao khác.

- Nghiên cứu thuật toán khai phá luật kết hợp từ tập mục hữu

ích cao.

7. Bố cục luận văn

Chương 1: Cơ sở lý thuyết về khai phá dữ liệu

Chương này trình bày các cơ sở lý thuyết bao gồm: Tổng quan

về khai phá dữ liệu, kỹ thuật khai phá tập mục phổ biến và luật kết

hợp trong CSDL giao tác.

Chương 2: Khai phá tập mục hữu ích cao từ cơ sở dữ liệu

giao tác

Trong chương 2 trình bày các khái niệm liên quan đến khai

phá tập mục hữu ích cao và thuật toán EFIM trong CSDL giao tác.

Chương 3: Cài đặt thuật toán EFIM và ứng dụng khai phá

dữ liệu bán hàng

Chương này tập trung vào thuật toán EFIM, thu thập và xử lý

dữ liệu bán hàng tại siêu thị Co.opMart Quảng Ngãi, cài đặt và thực

nghiệm chương trình. So sánh thuật toán EFIM với thuật toán khác.

Cuối cùng, những đánh giá, kết luận và hướng phát triển của

đề tài trong tương lai.

6

CHƯƠNG 1

CƠ SỞ LÝ THUYẾT VỀ KHAI PHÁ DỮ LIỆU

1.1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU

1.1.1. Sơ lượt về khai phá dữ liệu

Khai phá dữ liệu đã thu hút rất nhiều sự chú ý trong ngành

công nghiệp thông tin và toàn xã hội trong những năm gần đây, do sự

sẵn có một lượng lớn dữ liệu và cần phải sắp xếp chuyển dữ liệu đó

thành thông tin và kiến thức bổ ích. Các thông tin và kiến thức thu

được có thể được sử dụng cho các ứng dụng khác nhau, từ phân tích

thị trường, phát hiện gian lận, và duy trì khách hàng, để kiểm soát sản

xuất, v.v. Khai Phá Dữ Liệu (KPDL) là một khái niệm xuất hiện vào

những năm cuối của thập niên 80. Nó bao hàm các kỹ thuật nhằm

phát hiện ra các thông tin có giá trị tiềm ẩn trong các CSDL. KPDL

có một tiềm năng to lớn trong việc tạo ra những lợi nhuận đáng kể

trong nền kinh tế.

Nói cách khác KPDL là quá trình khai phá, trích xuất và sử

dụng những dữ liệu có giá trị tiềm ẩn từ bên trong một lượng lớn dữ

liệu được lưu trữ trong các CSDL, kho dữ liệu…

1.1.2. Quá trình khám phá tri thức từ cơ sở dữ liệu

1.1.3. Các dạng dữ liệu có thể khai phá

- Cơ sở dữ liệu quan hệ (Relational Database): Một hệ thống

cơ sở dữ liệu, cũng được gọi là một hệ thống quản lý CSDL, bao gồm

một bộ sưu tập các dữ liệu liên quan với nhau, được biết đến như là

một CSDL và một tập hợp các chương trình phần mềm để quản lý và

7

truy cập dữ liệu. Các chương trình phần mềm cung cấp cơ chế để xác

định cấu trúc CSDL và lưu trữ dữ liệu, để xác định và quản lý đồng

thời, chia sẻ, hoặc truy cập dữ liệu phân tán, đảm bảo tính thống nhất

và an ninh thông tin lưu trữ bất chấp sự cố hệ thống hoặc các nỗ lực

truy cập trái phép.

- Cơ sở dữ liệu giao tác (Transaction Database): Là tập hợp

những bản ghi giao dịch. Khai phá dữ liệu trên CSDL giao tác tập

trung vào khai phá luật kết hợp, tìm mối tương quan giữa những mục

dữ liệu trong các bản ghi giao dịch. Dạng dữ liệu này thường phổ

biến trong lĩnh vực thương mại, ngân hàng, bán hàng,…

- Cơ sở dữ liệu đa chiều (Multidimention Structures, Data

Warehouses, Data Mart): Các kho dữ liệu được tập hợp và chọn lọc

từ nhiều nguồn dữ liệu khác nhau. Dạng dữ liệu này chủ yếu phục vụ

cho quá trình phân tích cũng như khai phá tri thức và hỗ trợ quá trình

ra quyết định.

- Cơ sở dữ liệu quan hệ - hướng đối tượng (Object Relational

Databases): Dạng dữ liệu kết hợp giữa hai mô hình quan hệ và hướng

đối tượng. Dữ liệu này được ứng dụng trong viễn thông,…

- Dữ liệu không gian và thời gian (Spatial, Temporal, and

Time-series data): Dạng dữ liệu có tích hợp thuộc tính về không gian

như dữ liệu bản đồ, mạng cáp điện thoại hoặc thời gian như dữ liệu

cước điện thoại, phát hành báo chí.

- Cơ sở dữ liệu đa phương tiện (Multimedia Databases): Dạng

dữ liệu âm thanh (Audio), hình ảnh (Video)… Dữ liệu này rất phổ

biến trên internet.