ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.95 MB, 62 trang )
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Phiếu Giao Nhiệm Vụ Đồ Án Tốt Nghiệp
1. Thông tin về sinh viên
Họ và tên sinh viên: Lê Minh Nghĩa
Điện thoại liên lạc: 0936 073 986 Email: bem2vnn@gmail.com
Lớp: Công Nghệ Phần Mềm K51 Hệ đào tạo: Đại học
Đồ án tốt nghiệp được thực hiện tại bộ môn CNPM, viện Công Nghệ Thông Tin và Truyền
Thông, Đại Học Bách Khoa Hà Nội.
Thời gian làm ĐATN: Từ ngày 1/ 1 /2011 đến 28 / 5 /2011
2. Mục đích nội dung của ĐATN
Nghiên cứu luật kết hợp ứng dụng để khai phá dữ liệu trong mạng xã hội chia sẻ đồ vật MiGi
3. Các nhiệm vụ cụ thể của ĐATN
– Nghiên cứu nắm vững lý thuyết và các thuật toán cơ bản về luật kết hợp
– Xây dựng mạng xã hội chia sẻ đồ vật MiGi
– Xây dựng mô hình khai phá dữ liệu cho mạng xã hội chia sẻ đồ vật MiGi
4. Lời cam đoan của sinh viên:
Tôi – Lê Minh Nghĩa – cam kết ĐATN là công trình nghiên cứu của bản thân tôi dưới sự hướng
dẫn của kĩ sư Hoàng Anh Việt.
Các kết quả nêu trong ĐATN là trung thực, không phải là sao chép toàn văn của bất kỳ công
trình nào khác.
Hà Nội, ngà 28 tháng 5 năm 2011
Tác giả ĐATN
Lê Minh Nghĩa
5. Xác nhận của giáo viên hướng dẫn về mức độ hoàn thành của ĐATN và cho phép bảo vệ
Hà Nội, ngày 28 tháng 5 năm 2011
Giáo viên hướng dẫn
Thạc Sỹ Hoàng Anh Việt
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 1
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Lời cảm ơn
Em xin gửi lời cảm ơn chân thành tới các thầy cô trong viện công nghệ thông tin và
truyền thông cũng như các thầy cô trong trường đại học Bách Khoa Hà Nội, nhưng người
đã truyền thụ cho em những kiến thức quý báu trong quá trình học tập và nghiên cứu tại
trường. Đó là những điều kiện vô cùng quan trọng giúp em trưởng thành và vững vàng
trong lĩnh vực chuyên môn mình đã chọn.
Đặc biệt, em xin gửi lời cảm ơn tới thạc sĩ Hoàng Anh Việt- giáo viên trực tiếp
hướng dẫn của em. Thầy đã luôn giành sự quan tâm chỉ bảo tận tình, luôn động viên
khích lệ em vươn lên trong học tập và trong cuộc sống. “Mọi ước mơ đều có thể trở
thành hiện thực”, đó là lời nói của thầy, và đó cũng điều em luôn khắc ghi để không
ngừng nỗ lực vươn tới những ước mơ, những khát khao xa hơn, lớn hơn trong cuộc sống!
Tinh cảm yêu mến của gia đình và bạn bè luôn là một nguồn động lực tinh thần to
lớn giúp em vững vàng trong cuộc sống. Có thể lúc nào đó, trên chặng đường em đi sẽ
không bằng phẳng, sẽ đầy gian nan thử thách và tranh đấu. Nhưng em biết trong trái tim
những người yêu thương, sẽ luôn cho em những bình yên để nghỉ ngơi và để rồi tiếp tục
tiến về phía trước.
Hà Nội ngày 28 tháng 5 năm 2011
Sinh viên
Lê Minh Nghĩa
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 2
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Tóm Tắt Nội Dung Đồ Án Tốt Nghiệp
Mạng xã hội đang dần trở thành một phần không thể thiếu trong cuộc sống
hiện đại. Nó mang đến cho con người cơ hội được kết nối một cách dễ
dàng, để chia sẻ sở thích, thói quen và suy nghĩ. Mạng xã hội đã trở thành
một kho dữ liệu số ghi lại nhiều khía cạnh khác nhau của cuộc sống của
mỗi người. Và đó cũng là cơ hội to lớn để các công cụ phân tích dữ liệu
phân tích tìm ra những thông tin hữu ích từ người dùng. Nhờ đó giúp cho
các website trở nên thông minh hơn, mang lại cho người dùng nhiều trải
nghiệm tốt hơn, cũng như những thông kê và phân tích hữu ích cho quản lý
và kinh doanh. Trong đồ án tốt nghiệp này, người viết luận văn tập trung
nghiên cứu luât kết hợp- một trong những lĩnh vực được ứng dụng rộng rãi
nhất của Data Mining. Đề từ đó góp phần tìm ra các thói quen chia sẻ đồ
vật của người dùng trong mạng chia sẻ đồ vật-MiGi. Nhằm làm cho hệ
thống có thể gợi ý thông minh hơn, giúp người chia sẻ dễ dàng tìm được
người thực sự cần những đồ vật mình cho đi.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 3
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Abtract Thesis
Social Network becomes gradually the indispensable thing in the modern
life. It brings the opportunity for people to connect easily, to share their
interests, habits, and thoughts… Social Network has become a huge digital
database to record many different aspects of each users s’ life. It is also the
great chance for data analytic tools to discover useful information of users.
It makes website more intelligent, give better experience for users, and also
useful analytic and statistic for business and management. In this thesis,
author concentrates on Association Rules- one of the most important areas
in Data Mining. With purpose is to find sharing habits in the object sharing
network-MiGi. It makes system more intelligent in suggestion functions,
supports offering people find easily the person that really need the object
they shared.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 4
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Mục Lục
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 5
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Danh mục các kí hiệu và chữ viết tắt.
STT Từ Viết Tắt Giải nghĩa
1 NVLV Người viết luận văn
2 CSDL Cơ sở dữ liệu
3 DB Database
4 DHP Direct Hashsing and Pruning
5 PHP Perfect Hashing and Pruning
6 FP Tree Frequent Pattern Tree
7 Association Rules Luật kết hợp
8 Item Mục
9 ItemSet Tập mục
10 K Item Set Tập K mục
11 Support Count Độ hộ trợ
12 Min Sup Độ hộ trợ tối thiểu
13 Confidence Độ tin cậy
14 Min Conf Độ tin cậy tối thiểu
15 Frequent Itemset Tập mục thường xuyên
16 Transaction Giao dịch
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 6
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Danh mục các bảng.
Bảng3.2.Thông tin đăng ký
Bảng3.3. Mô tả tính năng đăng nhập
Bảng3.4. Mô tả thông tin đăng nhập
Bảng3.4. Mô tả tính năng hiển thị danh sách đồ vật chia sẻ
Bảng3.5. Mô tả tính năng tạo một offer
Bảng3.6. Mô tả thông tin tạo đồ vật
Bảng3.7. Mô tả tính năng xem thông tin đồ vật
Bảng3.8. Mô tả tính năng hiển thị danh sách request của cộng đồng
Bảng 3.9. Mô tả tính năng tạo request
Bảng3.10. Mô tả tính năng tạo request
Bảng 3.11 Bảng mô tả bảng dữ liệu tbl_Account
Bảng 3.12 Bảng mô tả bảng dữ liệu tbl_Offer
Bảng 3.13 Bảng mô tả bảng dữ liệu tbl_Request
Bảng 3.14 Bảng mô tả bảng dữ liệu tbl_RequestGiftTransaction
Bảng 3.15 Bảng mô tả bảng dữ liệu tbl_GiftRequestTransaction
Bảng 3.16 Bảng mô tả bảng dữ liệu tbl_Category
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 7
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Danh mục các hình vẽ và đồ thị.
Hình 2.1 Bảng dữ liệu mẫu cho ví dụ
Hình 2.2. Ví dụ về tìm tập mục thường xuyên
Hình 2.3: Code mẫu thuật toán Apriori
Hình 2.4 Ví dụ minh hoạt xây dựng cây FP Tree
Hình 3.1 Sơ đồ Use Case cho người dùng thông thường
Hình 3.2. Sơ đồ use case cho nhóm người tổ chức từ thiện
Hình 3.3. Sơ đồ use case cho nhóm người dùng admin
Hình 3.4. Kiến trúc tổng thể của hệ thống
Hình 3.5. Sơ đồ phụ thuộc của các package chính của hệ thống/
Hình 3.6: Sơ đồ các liên kết các lớp chính của hệ thống
Hình 3.7 Biều đồ diễn tiến chức năng đăng ký
Hình 3.8. Biểu đồ diễn tiến chức năng đăng nhập
Hình 3.9 Biểu đồ diễn tiến chức năng Offer
Hình 3.10 Biểu đồ diễn tiến chức năng tạo mới request đồ vật
Hình 3.11 Biểu đồ diễn tiến cho chức năng hiển thị danh sách offer đồ vật
Hình 3.12 Biểu đồ diễn tiến cho chức năng hiển thị danh sách các request đồ vật
Hình 3.13 Biểu đồ diễn tiến cho chức năng request tới một đồ vật được chia sẻ
Hình 3.14 Biểu đồ diễn tiến cho chức năng offer đồ vật cho một request
Hình 3.15 Sơ đồ thiết kế database
Hình 3.16: Sơ đồ Database phân tích
Hình 3.17: Quy trình xử lý dữ liệu để phân tích
Hình 3.17:Sơ đồ lớp của module phân tịch luật Apriori
Hình 3.18:Sơ đồ lớp của module phân tích luật PHP
Hình 5.19:Sơ đồ lớp của module phân tích luật FP Tree
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 8
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Mở đầu
Quản lý hiệu quả các dữ liệu đã là mục tiêu khởi nguồn quan trọng cho sự ra đời và
phát triển của các hệ thống thông tin quản lý. Các hệ thống thông tin quản lý ngày một
được sử dụng rộng rãi hơn trong mọi hoạt động của cuộc sống. Từ các hệ thống lớn cho
các ngân hàng, siêu thị, cho tới các hệ thống quản lý cho các nhà hàng, cửa hiệu… Và dữ
liệu cũng bùng nổ cùng với sự phát triển và phổ biến của các hệ thống thông tin quản lý.
Giờ đây quản lý hiệu quả dữ liệu không còn là mục tiêu duy nhất mà hơn thế cần phải
biết khai thác hiệu quả dữ liệu lưu trữ. Đó chính là nguyên nhân cho sự phát triển mạnh
mẽ của lĩnh vực nghiên cứu data mining trong các thập niên gần đây.
Luật kết hợp là một trong những lĩnh vực data mining được áp dụng rộng rãi trong
rất nhiều lĩnh vực khác nhau. Nó được phát triển xuất phát từ yêu cầu thực tế khi người ta
cần tìm các quy luật về mối quan hệ giữa các sản phẩm được mua bán cùng nhau trong
các siêu thị. Các quy luật đó rất có ý nghĩa đối việc marketing giới thiệu sản phẩm cho
khách hàng, hay đơn giản là bố trị vị trí các gian hàng gần nhau sao cho hợp lý nhất. Một
người mua máy tính thường mua kèm phần mềm diệt virus, vậy thì thay vì để cách xa
nhau, họ có thể xếp hai gian hàng ở gần nhau. Như vậy cơ hội cho khách mua đồng thời
hai sản phẩm sẽ cao hơn rất nhiều.
Trong đồ án tốt nghiệp này, NVLV áp dụng các thuật toán luật kết hợp vào hệ thống
mạng chia sẻ đồ vật do người viết luật văn xây dưng với mong muốn tìm ra các quy luật
cho trong hoạt động chia sẻ đồ vật. Từ đó sẽ có những gợi ý thông minh cho người dùng,
giúp quá trình tìm kiếm đồ vật được dễ dàng.
Mạng chia sẻ đồ vật là một web site cho phép người dùng đưa các thông tin về các
đồ vật mà người dùng không còn cần dùng nữa. Và những người đang cần tới chúng có
thể sử dụng mạng chia sẻ để dễ dàng liên lạc với người cho. Đó là dự án do người viết
luật văn xây dựng để tham gia cuộc thi Imagine Cup 2011 do Microsoft tổ chức. Với mục
tiêu tạo ra một cộng đồng giúp đỡ lẫn nhau phục vụ cho các mục tiêu thiên niên kỉ là xóa
đói giảm nghèo và bảo vệ môi trường.
Bố cục đề tài tốt nghiệp của NVLV gồm các phần chính sau:
• Chương 1: Trình bày về vai trò của các mạng xã hội với bài toán khai phá dữ liệu.
Lợi ích từ việc khai thác dữ liệu mạng chia sẻ đồ vật MiGi. Đồng thời trình bày
các lý thuyết cơ bản về luật kết hợp.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 9
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
• Chương 2: Trình bày về các giải thuật cơ bản của luật kết hợp, cùng một kỹ thuật
cài đặt và xử lý.
• Chương 3: Thiết kế và cài đặt mạng chia sẻ đồ vật phục vụ việc phân tích dữ liệu.
• Chương 4: Các kết quả đạt được
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 10
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Chương 1: Bài toán khai phá
dữ liệu từ mạng xã hội
Trong chương này sẽ trình bày về:
• Sự phát triển của các mạng xã hội
• Mạng xã hội và bài toán data mining
• Mạng xã hội chia sẻ đồ vật
Mạng xã hội đáng phát triển một cách bùng nổ. Nó trở thành một trào lưu mạnh mẽ,
thu hút hàng triệu người tham gia. Nó mang tới cơ hội cho người dùng có thể dễ dàng kết
nối với nhau, chia sẻ thông tin. Các mạng xã hội trở thành những kho lưu trữ số thông tin
của người dùng.
1.1. Mạng xã hội
Ngày nay, các mạng xã hội đang có sự phát triển bùng nổ, với số lượng người dùng
lên đến hàng trăm triệu. Các mạng xã hội đang dần trở thành một môi trường mạng
không thể thiếu với hàng triệu người dùng. Nơi mang lại cho người dùng một cơ hội to
lớn để kết nối và chia sẻ thông tin dễ dàng. Nó cũng phản ánh nhu cầu tâm lý tất yếu của
con người là chia sẻ và trao đổi thông tin. Khi mà xã hội càng hiện đại thì áp lực cuộc
sống, sự thiếu thốn về thời gian càng tăng… Điều đó làm cho các mạng xã hội trở thành
một môi trường tiện dụng để người dùng có thể chia sẻ nhanh chóng những thông tin
mình có với bạn bè.
1.1.1. Mạng xã hội Facebook
Facebook là mạng xã hội lớn nhất thế giới, được thành lập vào tháng 2 năm 2004,
Facebook ban đầu có tên là Facemash. Đây là một phiên bản Hot or Not của trường đại
học Harvard. Sau đó, MarkZuckerberg thành lập “The Facebook” đặt trên domain
thefacebook.com. Dịch vụ mạng xã hội này ban đầu chỉ dành riêng cho các sinh viên của
Đại học Harvard. Chỉ sau một tháng, hơn nửa số sinh viên Đại học Harvard đã đăng ký
sử dụng dịch vụ này.
Tháng 9 năm 2004, Mark Zuckerberg đã chuyển trụ sở của thefacebbook.com về
Palo, Alto, California và bỏ chữ “the” trong tên miền thefacebook.com, chuyển thành
facebook.com.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 11
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Facebook nhanh chóng trở thành cái tên quen thuộc đối với người sử dụng các dịch
vụ mạng xã hội. Đến tháng 12 năm 2004, tức chỉ 10 tháng sau khi thành lập, Facebook đã
gần chạm mốc 1 triệu người dùng.
Một năm sau đó, số người dùng đã tăng vọt lên tới 5.5 triệu người. Facebook dần
dần mở rộng hoạt động ra phạm vi bên ngoài các trường đại học. Các trường trung học tại
Hoa Kỳ bắt đầu được thêm vào hệ thống.
Tháng 4 năm 2008, Facebook chính thức có mặt trên nhiều quốc gia và vùng lãnh thổ
với 21 ngôn ngữ khác nhau. Số thành viên của mạng xã hội này đã lên tới 100 triệu
người.
Thành công đến với Facebook nhanh hơn mong đợi khi số lượng thành viên của
mạng xã hội này lần lượt chạm mốc 200 triệu vào tháng 4, 300 triệu vào tháng 9 năm
2009, 400 triệu vào tháng 2 năm 2010. Mới đây nhất, Facebook đã vượt mốc 500 triệu
người dùng.
1.1.2. Mạng xã hội Twitter
Twitter cũng là một trong những mạng xã hội lớn nhất thế giới. Nó còn được biết đến
như một mạng “tiểu” blog khi mà mỗi người dùng chỉ được phép đăng một tin (tweet) có
đồ dài không vượt quá 104 kí tự. Mặc dù vậy, nhưng Twitter đáp ứng đúng yêu cầu của
người dùng trong một xã hội ngày càng “vội vã”.
Ngày 21/3 vừa qua Twitter kỉ niệm sinh nhật lần thứ 5 của mình. Đó một dấu mốc
quan trọng trong sự phát triển nhiều thăng trầm mạng tiểu blog này. Đã có thời Twitter
phải chật vật để níu giữ người dùng. Nhưng ngày nay witter đã trở nên trưởng thành hơn
và giữ một vai trò quan trọng trong xã hội, chính trị, truyền thông, thể thao và nhiều lĩnh
vực khác.
Người dùng Twitter hiện nay gửi đi 140 triệu đoạn tweet mỗi ngày. Trước đây,
Twitter đã mất 3 năm, 2 tháng và 1 ngày để đạt được 1 tỷ tweet đầu tiên, nhưng giờ đây,
cứ 8 ngày thì có 1 tỷ tweet được gửi đi.
Tương tự, Twitter đã mất 18 tháng để có 500 ngàn người dùng, nhưng giờ đây, mỗi
ngày lại có thêm 500 ngàn tài khoản mới được đăng ký.
1.1.3. Mạng xã hội Zing Me
Đáp ứng xu thế mạng xã hội, tại Việt Nam đã có hàng loạt mạng xã hội ra đời. Tiêu
biểu trong số đố là mạng xã hội Zing Me do tập VNG làm chủ. Đây có thể nói là mạng xã
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 12
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
hội lớn nhất Việt Nam. Chỉ sau hơn một năm phát triển Zing Me đã có hơn 5 triệu người
dùng.
Với giao diện được việt hóa thân thiện, cùng sự tích hợp nhiều ứng dụng và dịch vụ
khác nhau, Zing Me đã nhanh chóng thu hút được một lượng lớn người dùng. Đặc biệt là
nhóm những người dùng trẻ tuổi. Zing Me cung cấp một môi trường chia sẻ và kết nối dễ
dàng. Đồng thời Zing Me cũng cung cấp nhiều công cụ khác nhau để các doanh nghiệp tổ
chức các sự kiện, thực hiện các điều tra thăm dò. Zing Me cũng mở các API để các bên
thứ ba phát triển các ứng dụng dựa trên nền tảng Zing Me. Zing Me ngày càng chiếm
được cảm tình của người dùng, đặc biệt là nhóm người dùng trẻ tuổi. Đó là cơ sở cho sự
phát triển bền vững tại thị trường Việt Nam sau này.
Trên đây là một số mạng xã hội phổ biến ở trên thế giới và ở Việt Nam. Nó cho thấy
mạng xã hội đã trở thành một xu hướng chi phối đời sống xã hội, nó chiếm được cảm tính
và sự quan tâm của tất cả mọi lứa tuổi, tầng lớp và trên phạm vi toàn cầu rộng lớn. Xu
hướng đó tạo ra sự phát triển bùng nổ của mạng xã hội. Đồng thời nó cũng biến mạng xã
hội trở thành một kho chứa thông tin khổng lồ. Bởi mạng xã hội gần như trở thành một
môi trường xã hội ảo. Nó ghi nhận một cách đa dạng các hoạt động khác nhau của người
dùng. Nó nắm giữ từ các thông tin cá nhân, cho tới các thông tin về các mối quan hệ, về
sở thích, về thói quen của người dùng. Mạng xã hội trở thành một kho dữ liệu khổng lồ
mà nếu khai thác hiệu quả người ta có thể tìm được rất nhiều thông tin hữu ích. Có thể
đoán nhận được sở thích của một người, phân tích các xu hướng về nhu cầu của người
dùng, hay mối quan hệ giữa những người dùng
Nhưng chính sự đa dạng về dữ liệu lại chính là một trong những rào cản để phục vụ
các bài toán phân tích và khai thác dữ liệu. Chính vì thế mà không có một mô hình phân
tích thống kê chung nhất cho tất cả các mạng xã hội, mà nó thay đổi tùy theo từng mục
đích khác nhau của bài toán. Đối với một mạng như Amazon thì thông tin về sở thích
người dùng luôn được quan tâm hàng đầu. Từ đó có thể biết được mối quan tâm giữa
những loại sách mà người dùng tìm kiếm.
MiGi là một mạng chia sẻ đồ vật. Trong hoạt động chia sẻ đồ vật, luôn xuất hiện
yêu cầu đồ vật được chia sẻ tìm được đến đúng người có nhu cầu phù hợp với loại đồ vật
được chia sẻ. Điều đó giúp quá trình chia sẻ hiệu quả hơn, và cũng giúp người dụng thuật
tiện hơn trong quá trình tìm kiếm và sử dụng.
Xuất phát từ yêu cầu đó, hệ thống cần phải xác định được các quy luật xem người
dùng thường chia sẻ những đồ vật gì cùng nhau, cũng như thường có nhu cầu về những
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 13
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
loại đồ vật nào. Ví dụ người X cho vật B thì thường sẽ cho thêm vật C, hoặc người lại
người Y khi xin một đồ vật D thì thường sẽ có nhu cầu đối với vật E. Những luật đó gọi
là các luật kết hợp.
Để tìm được các luật kết hợp đó, đòi hỏi phải tìm được tập các đồ vật mà người
dùng thường chia sẻ cùng nhau, hoặc tập các đồ vật mà người dùng thường yêu cầu. Đó
là trọng tâm của tất cả các thuật toán tìm luật kết hợp.
1.2. Các lợi ích từ việc khai thác dữ liệu mạng chia sẻ đồ vật MiGi
Việc khai thác dữ liều từ mạng chia sẻ đồ vật mang lại nhiều thông tin hữu ích cho
nhiều lính vực khác nhau. Có thể kể ra một số hướng có thể khai thác được từ dữ liệu
người dùng của mạng MiGi là:
• Xác định được thói quen chia sẻ đồ vật của người dùng: biết được những món
đồ mà người dùng thường cho đi, các nhu cầu thường đi cùng với nhau. Để từ
đó xây dựng các hệ gợi ý thông minh. Ví dụ: người A cho một cái điện thoại cũ,
người B cần chiếc đoạn thoại đó, thì có thể sẽ cần một chiếc xác điện thoại của
một người X nào đó cũng cho đi.
• Phân tích sở thích của người dùng để phục vụ mục đích quảng cáo. Qua các
đồ vật người đó cho đi có thể biết phần nào là sở thích người dùng là gì. Ví dụ
nhãn hiệu quần áo mà người ta quan tâm. Đó là cơ sở để quảng cáo các sản
phẩm phù hợp.
• Điều tra thị trường: Qua những đồ vật mà cộng đồng cho đi có thể xác định
nhu cầu tiêu thụ của một khu vực nào đó. Thông thường, nếu mặt hàng nào đó
càng bán chạy thì càng có nhiều đồ được “thải” ra. Dựa trên MiGi cũng có thể
lập được một bản đồ số phân bố theo nhu cầu
1.3. Tổng quan về khai phá dữ liệu
Data Mining là một lĩnh vực rộng lớn, nó được chia thành nhiều lĩnh vực nhỏ để giải
quyết nhiều bài toán khác nhau. Trong phạm vi đề tài, người viết luận văn chỉ cố gắng
tìm hiểu để nắm bắt những ý tưởng chính để phục vụ cho bài toán đề xuất. Chính vì thế,
để tập trung cho phần trình bày, trong chường này chỉ xin trình bày về những lý thuyết cơ
bản về luật kết hợp. Lĩnh vực luật kết hợp là một trong những lĩnh vực được quan tâm
nhiều nhất trong data mining. Bởi nó được ứng dụng một cách rộng rãi nhằm phân tích
các mối quan hệ, tìm ra các quy luật giữa các thuộc tính khác nhau… Ví dụ như trong các
siêu thị khi tìm kiếm quy luật về các mặt hàng mà người dùng cùng mua với nhau, hay
trong y học khi tìm mối quan hệ giữa các triệu chứng dẫn đến một loại bệnh nào đó…
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 14
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
1.3.1. Các khái niệm cơ bản.
a. Tập mục.
• I1,I2,…In là các mục-mặt hàng (items). I={I1,I2,…In} là tập tất cả các mục.
• Một tập con X I được gọi là tập mục (itemset). Một k-tập mục (k-itemset) là môt
tập mục chứa k mục (item).
b. Độ hỗ trợ tập mục.
• Cho một cơ sở dữ liệu D ={T1,T2,…Tn} là một tập giao dịch, trong đó mỗi giao
dịch Ti,i{1,…n} là một tập mục. Một giao dịch T chứa một tập mục X nếu XT.
Một giao dịch Ti được đi kèm với một chỉ số TID.
• Chỉ số hỗ trợ đối với tập mục X (support count ) được định nghĩa là số giao dịch
trong cơ sở dữ liệu D chứa tập mục X:
(1)
• Độ hỗ trợ được định nghĩa như là tỉ lệ số giao dịch trong cơ sở dữ liệu D chứa tập
mục X, tức là:
(2)
• Chỉ số support count còn được gọi là độ hộ trợ tuyệt đối (absolute support). Chỉ
số hỗ trợ còn được gọi là độ hỗ trợ tương đối (relative support).
c. Luật kết hợp.
• Một luật kết hợp (association rule) là một luật có dạng, trong đó và. X được gọi
là tiền nghiệm, X được gọi là kết quả suy ra.
• Luật có độ tin cậy c (confidency) trong tập giao dịch D nếu c% các giao dịch
trong D khi đã chứa X thì cũng chứa Y:
(3)
• Luât có độ tin cậy c (confidency) trong tập giao dịch D nếu c% các giao dịch
trong D khi đã chứa X thì cũng chứa Y:
hay (4)
• Một ngưỡng s min được sử dụng để loại bỏ các luật mà tập mục có độ hỗ trợ nhỏ
hơn s min, và một ngưỡng c min dùng để loại bỏ các luật không có đủ độ chắc
chắn c min.
d. Tập mục thường xuyên.
Các tập mục với độ hỗ trợ lớn hơn độ hỗ trợ tối thiểu được gọi là các tập mục
thường xuyên (frequent itemset) hay các tập mục lớn (large itemsets). Tập các k-itemset
thường được ký hiệu là Lk.
Ví dụ: Cơ sở dữ liệu giao dịch
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 15
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
TID Items
1 Bread, Milk
2 Bread, Diaper, Beer, Eggs
3 Milk, Diaper, Beer, Coke
4 Bread, Milk, Diaper, Beer
5 Bread, Milk, Diaper, Coke
Tập {Milk, Bread, Diaper} là tập 3-items, có:
• Độ hỗ trợ tuyệt đối:
• Độ hỗ trợ tương đối:
• Luật kết hợp {Milk, Diaper}=> {Beer}
e. Tập mục đóng, tập mục thường xuyên cực đại
• Tập mục X được gọi là đóng (closed itemset) nếu không tồn tại tập mục Y, sao
cho và. Một tập mục thường xuyên và đóng được gọi là tập mục thường xuyên
đóng (closed frequent itemset).
• Một tập mục X được gọi là tập mục thường xuyên cực đại (maximal frequent
itemset) nếu X thường xuyên và không tồn tại tập mục Y, và Y là thường xuyên.
1.3.2. Bài toán phát hiện luật kết hợp.
Cho một tập mục I, một cơ sở dữ liệu các tập mục D, một ngưỡng hỗ trợ s
min
và một
ngưỡng tin cậy c
min
, cần phải tìm ra các luật kết hợp trong D với độ hỗ trợ và độ tin cậy .
Một cách tổng quát, phát hiện luật kết hợp được chia làm hai bước:
• Bước 1: Tìm tất cả các tập mục thường xuyên.
• Bước 2: Sinh ra các luật tin cậy từ các tập mục thường xuyên.
Từ công thức (4), độ tin cậy của có thể được tính thông qua độ hỗ trợ của X và .
Điều này có nghĩa là khi đã tính được độ hỗ trợ của X, Y và thì có thể trực tiếp sinh ra
các luật dạng và và kiểm tra xem chúng có phải là các luật tin cậy hay không. Vì chi phí
tính toán của bước hai là nhỏ hơn rất nhiều so với bước, hiệu năng của toàn quá trình
phát hiện luật kết hợp phụ thuộc vào hiệu năng của bước 1, từ đó bài toán phát hiện luật
kết hợp được đơn giản thành bài toán phát hiện các tập mục thường xuyên.
1.3.3. Khó khăn trong phát hiện luật kết hợp.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 16
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Mặc dù có những độ đo khác nhau được đề xuất trong phát hiện luật kết hợp, nhưng
2 độ đo chính vẫn được sử dụng phổ biến là độ đo hỗ trợ (support) và độ đo tin cậy
(confidency). Khi giống nhau về giá trị ngưỡng của độ đo hỗ trợ và tin cậy, các cách tiếp
cận khác nhau phải cho cùng một tập luật kết hợp. Khi đó, để so sánh các phương pháp
với nhau, người ta sẽ so sánh về hiệu năng của thuật toán (chi phí tính toán, chi phí bộ
nhớ), các cấu trúc dữ liệu được sử dụng, chiến lược tìm kiếm và cách cắt giảm tập mục
không thường xuyên…
a. Khó khăn trong giảm độ phức tạp của thuật toán.
Khó khăn đặt ra chủ yếu trong phát hiện luật kết hợp đối với CSDL kích thước lớn
là thường sinh ra rất nhiều tập mục thường xuyên, đặc biệt trong trường hợp ngưỡng
minsup nhỏ. Điều này là bởi vì một tập mục là thường xuyên thì các tập mục bộ phận của
nó (sub-itemset) cũng là thường xuyên. Chẳng hạn như một tập mục thường xuyên có
-kích thước 100 {a
0
, a
1
, …, a
100
} sẽ chứa tập 1-mục, tập 2-mục thường xuyên… Điều
này dẫn đến số tập mục thường xuyên được chứa trong tập mục thường xuyên kích thước
100 là:
Là quá lớn cho máy tính tính toán và lưu trữ.
Zaki[2] đã chứng minh bài toán phát hiện tất cả các tập mục thường xuyên là bài toán
NP-khó. Bởi vì với CSDL có d tập mục, số ứng viên phải là c
d
là hàm mũ.
Đã có nhiều thuật toán và kĩ thuật khác nhau được đề xuất để làm tăng hiệu năng
của hệ thống, trong đó tập trung vào việc cắt tỉa các transaction không phục vụ quá trình
tìm luật kết hợp, cắt bỏ các mục không có ý nghĩa, sử dụng các cấu trúc dữ liệu bảng băm
để lưu trữ nhằm giảm số lần duyệt cơ sở dữ liệu.
b. Khó khăn trong phát hiện luật kết hợp có giá trị
Bên cạnh vấn đề về việc phải tính toán trên quá trình tập mục thường xuyên, một
vấn đề khác trong phát hiện luật kết hợp là có thể bỏ sót những luật có ý nghĩa. Lấy ví dụ
như với cách tiếp cận thông thường, các tập mục có cùng một ngưỡng hỗ trợ. Khi đó, nếu
đặt ngưỡng này đủ lớn để loại đi được nhiều tập mục không thường xuyên, thì có những
tập mục có bản chất ít xuất hiện trong giao dịch sẽ không được phát hiện trong luật. Tuy
nhiên, nhiều khi những luật liên quan tới các mặt hàng ít xuất hiện này lại có giá trị. Cụ
thể như trong CSDL giao dịch, những tập mục liên quan tới các mặt hàng tiêu dùng như
bánh mỳ, sữa… có lợi nhuận thấp, tính phổ biến hơn rất nhiều so với những tập mục liên
quan đến các mặt hàng như tivi, tủ lạnh, điều hòa… vốn là những mắt hàng ít mua nhưng
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 17
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
lại có lợi nhuận cao. Nếu ngưỡng hỗ trợ cao, thì chỉ phát hiện được các luật liên quan đến
mặt hàng tiêu dùng, mà bỏ đi một mảng liên quan đến các mặt hàng cho lợi nhuận cao.
Cách tiếp cận ở đây là đưa ra với mỗi một mục khác nhau một giá trị ngưỡng hỗ trợ khác
nhau. Giá trị ngưỡng hỗ trợ cho tập mục sẽ được xác định dựa trên giá trị hỗ trợ của các
mục thành viên. Ngoài ra, với các mục khác nhau người ta có thể đưa vào trọng số chỉ
mức độ quan trọng khác nhau.
Hơn nữa, trong trường hợp các tập mục ở các mức khác nhau, một cách đương
nhiên, các mục ở mức trừu tượng cao hơn sẽ có giá trị hỗ trợ cao hơn các mục ở mức trừu
tượng thấp. Nếu đặt ngưỡng hỗ trợ quá thấp, thì sinh ra quá nhiều luật, ngược lại với
ngưỡng hỗ trợ cao thì chỉ sinh ra được các luật ở mức trừu tượng cao, mà bỏ xót các luật
quan trọng ở mức trừu tượng thấp. Cách tiếp cận ở đây là đưa ra cơ chế điều chỉnh giá trị
ngưỡng hỗ trợ cho phù hợp với từng mức khác nhau.
Kết chương một:
Qua trường này NVLV đã trình bày tổng quan về các mạng xã hội, và tiềm năng cho
việc khai thác dữ liệu từ các mạng xã hội. Đồng thời NVLV trình bày các kiến thức cơ
bản khai phá dữ liệu trong lĩnh vực luật kết hợp. Qua đây NVLV định ra các mục tiêu của
đồ án tốt nghiệp là:
• Xây dưng phát triển hoàn thiện MiGi để khai thác thông tin và hỗ trợ
giao dịch
• Tìm hiểu các thuật toán về luật kết hợp
• Cài đặt và so sánh đánh giá các thuật toán trên bộ dữ liệu thực
• Định hướng phát triển mở rộng.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 18
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Chương 2: Luật kết hợp
và các kĩ thuật xử lý
Trong chương này sẽ trình bày:
• Thuật toán Apriori
• Thuật toán PHP
• Thuật toán FP Tree
Như đã trình bày ở trên, khó khăn của bài toán tìm luật kết hợp nằm ở việc tìm được
các tập mục thường xuyên. Nó là bước chiếm nhiều hiệu năng nhất của hệ thống. Tất cả
các thuật toán tìm luật kết hợp đều xoay quanh viên tìm kiếm các tập mục thường xuyên
sao cho nhanh nhất và hiệu quả nhất có thể.
Trong phân tích luật kết hợp, có hai loại cơ sở dữ liệu là cơ sở dữ liệu đơn chiều và
cơ sở dữ liệu đa chiều. CSDL đơn chiều chỉ có một chiều. Ví dú như cơ sở dữ liệu giao
dịch, chỉ có chiều “mặt hàng”, trong đó mỗi bản ghi là một giao dịch, ghi nhận các mặt
hàng được mua bởi người dùng trong giao dịch đó. CSDL đa chiều có nhiều chiều, như
bên cạnh chiều mặt hàng thì còn có thêm các chiều thuộc tính khác của mặt hàng. Ví dụ:
màu sắc, nhãn hiệu, giá cả… Dưới là trình bày vắn tắt các giải thuật cơ bản để tìm các tập
mục thường xuyên trong cơ sở dữ liệu đơn chiều.
2.1. Thuật toán Apriori
Giải thuật Apriori là một giải thuật được R.Agrawal và R.Srikant được ra vào năm
1994. Đên nay nó vẫn được coi là một giải thuật nổi tiếng nhất trong việc tìm luật kết
hợp. Tên của giải thuật dựa trên thực tế giải thuật sử dụng kiến thức tiên nghiệm các tập
mục thường xuyên để xác định các tập mục thường xuyên có kích cỡ lớn hơn. Apriori sử
dụng phương pháp search mở rộng theo mức, trong đó tập k-muc (k-itemset) được sử
dụng để tìm các tập mục k+1. Đầu tiên các tập 1 mục (1-itemsets) được tìm thấy bằng
việc quét toàn bộ database, đồng thời xác định độ hỗ trợ tương ứng. Kết quá ta được tập
L1. L1 được sử dụng để tìm tập L2 là các tập 2 mục (2-itemsets), rồi từ L2 tìm được
L3… Quá trình tiếp diễn cho tới khi không tìm được thêm tập mục nào nữa.
Để tăng tính hiệu quả của quá trình search theo cấp độ (wise level search) giải thuật
Priori sử dụng thuộc tính tiên nghiệm, nhằm loại bỏ các tập sinh ra, giúp giảm không gian
search. Thuộc tính tiên nghiệm được định nghĩa như sau:
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 19
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Thuộc tính tiên nghiệm(Apriori):Tất cả các tập con không rỗng của một tập mục
thường xuyên phải là một tập mục thường xuyên.
Dựa trên thuộc tính này, thì tại bước sinh các tập L
k+1
từ L
k
nếu bất kỳ một tập mục
nào thuộc L
k+1
mà không thuộc L
k
nghĩa là không phải tập mục thường xuyên, thì sẽ loại
bỏ L
k+1
tương ứng. Giải thuật Apriori gồm hai bước chính:
• Bước Join: để tìm lập mục thường xuyên K, một tập các ứng viên k mục sẽ
được sinh ra bằng cách join các tập L
k-1
với chính nó. Tập hợp sinh ra gọi là
tập C
k
. Từ tập này chúng ta sẽ sử dụng để tìm L
k
.
• Bước tỉa: Sau khi join tập L
k-1
với chính nó ta được tập C
k
là tập lớn chứa tập
L
k
. Trong đó chứa các các tập k-mục thường xuyên, và cả các tập không phải
thường xuyên. Để xác định, thì phải tiến hành quét database. Nhưng số lượng
tập mục thuộc C
k
là rất lớn. Chi phí quét cho toàn bộ là rất tốn kém. Để giảm
không gian search thì lúc này thuộc tính tiên nghiệm được sử dụng. Bất cứ
tập hợp nào thuộc C
k
mà có tập con k-1 không phải tập mục thường xuyên
đều bị loại bỏ. Từ đó mà không gian search sẽ giảm xuống.
Ví dụ:
Cơ sở dữ liệu gốc:
Hình 2.1 Bảng dữ liệu mẫu cho ví dụ
Quá trình tìm kiếm các tập mục thường xuyên với ngưỡng độ hỗ trợ là 2.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 20
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Hình 2.2. Ví dụ về tìm tập mục thường xuyên
Dưới đây là code mô tả thuật toán:
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 21
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Hình 2.3: Code mẫu thuật toán Apriori
2.2. Thuật toán PHP- Perfect Hashing and Prunning
Giải thuật PHP(Perfect Hashing and Prunning) là giải thuật được phát triển lên từ
giải thuật Apriori nhằm cải thiện hiệu năng. Giải thuật PHP sử dụng các kĩ thuật bảng
băm, tận dụng nhiều tri thức tiền nghiệm để loại giảm số lượt quét database và giảm kích
cỡ của cơ sở dữ liệu giao dịch. Giải thuật PHP gồm ba phần:
Phần 1: Quét toàn bộ Database, đếm số lần xuất hiện của các mục (item), đồng thời xây
dựng bảng băm cho các tập 2 mục, chọn lựa các item thỏa mãn độ hỗ trợ tối thiểu để đưa
vào L1
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 22
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Phần 2: Từ bảng băm chúng ta sẽ xác định được tập các ứng viên. Các ứng viên đó sẽ
được kiểm tra để tạo ra L
k
. Khi chúng ta kết thúc L
k
, database sẽ được cắt giảm, loại bỏ
các mục không cần thiệt, các giao dịch không có ý nghĩa.
Phần 3: Tương tự như phần hai nhưng trừ việc phải xây dựng lại bảng băm.
Cắt tỉa Trong giải thuật PHP một phần quan trọng là thao tác cắt tỉa database. Thao tác
cắt tỉa database dựa trên hai nhận xét sau:
• Một giao dịch có thể chứa k+1 tập k-mục (k-itemsets) khi nó có ít nhất k+1 tập k-
mục (k+1 itemsets). Điều đó có nghĩa là chúng ta có thể loại bỏ các giao dịch mà
không có đủ k+1 tập k-mục
• Nếu một item thuộc một k+1 tập mục thường xuyên, thì nó phải nằm ít nhất k lần
trong k tập mục. Do đó chúng ta sẽ loại bỏ những mục nào có số lần xuất hiện
trong tập L
k
nhỏ hơn k lần.
Thực chất còn tồn tại một giải thuật khác trước giải thuật PHP là DHP (Direct Hashing
and Prunning). PHP cơ bản là giống DHP, chỉ khác nhau ở hàm băm. Hàm băm của PHP
là hàm băm hoàn chỉnh đảm bảo không có sự trùng lặp key.
2.3. Thuật toán FP Tree
Như đã trình bày ở trên, việc phát hiện các tập mục thường xuyên có ý nghĩa quyết
định đối với việc sinh ra các tập luật kết hợp. Đối với giải thuật Apriori thì việc tìm các
tập mục thường xuyên đòi hỏi phải sinh ra các tập ứng viên. Nhưng ngay cả khi đã áp
dụng các kĩ thuật cải tiến thì số tập ứng viên sinh ra vẫn quá lớn. Đó chính là nguyên
nhân chính ảnh hưởng tới hiệu năng của thuật toán.
Nhóm nghiên cứu của Han đã đề xuất sử dụng cấu trúc cây trên ba khía canh sau:
• Thứ nhất: Sử dụng cấu trúc dữ liệu nén truyền thống được gọi là cây mẫu
thường xuyên FP-Tree (Frequent pattern tree) được xây dưng. Nó là sự mở
rộng của cây tiền tố để lưu trữ các thông tin chủ yếu về cây mẫu thường
xuyên. Chỉ những mục thường xuyên mới có các nút trong cây, và nút của
cây được sắp xếp theo ý tưởng nút nào xuất hiện thường xuyên hơn sẽ có
cơ hội hơn để chia sẻ nút đó.
• Thứ hai: Quá trnnh phát hiện tập mục thường xuyên dựa trên FP-Tree
được phát triển bắt đầu từ mẫu thường xuyên kích thước 1 (như một mẫu
hậu tổ khởi đầu), chỉ kiểm tra cơ sở mẫu điều kiện(một cơ sở dữ liệu con
chứa tập các mục thường xuyên cùng xuất hiện với mẫu hậu tổ), xây dựng
FP-Tree điều kiện và thực hiện khai phá đệ quy với cây. Tăng trưởng mẫu
đạt được thông qua thao tác kết nối mẫu hậu tố với mẫu hậu tố mới được
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 23
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
sinh ra từ cây FP-Tree điều kiện. Thao tác chính ở đây là đếm bộ tích lũy và
điều chính bộ đếm tiền tố, do đó sẽ ít tốn kém hơn so với việc sinh ra các
ứng viên và so khớp mẫu được thực hiện trong thuật toán Apriori.
• Thứ ba: Kỹ thuật tìm kiếm thực hiện dựa trên phân đoạn, chia và trị chứ
không phải là kết hợp sinh ra các tập mục thường xuyên từ dưới lên theo
kiểu Apriori, do đó giảm kích thước cơ sở mẫu điều kiện sinh ra ở mức tiếp
sau của việc tìm kiếm.
2.3.1 Cây mẫu thường xuyên
Định nghĩa: FP-Tree là một cây mẫu thường xuyên có cấu trúc như sau:
• Cây mẫu bao gồm một nút gốc gán nhãn “null”, một tập các cây con tiền tố như là
các con của nút gốc và một bảng header mục thường xuyên.
• Mỗi nút trong cây con tiền tố bao gồm có ba trường: tên mục(item name), bộ
đếm(count) và con trỏ nút (nút -link). Tên mục cho biết mục mà nút biểu diễn, bộ
đếm cho biết số giao dịch được biểu diễn một phần tử nút gốc cho tới nút này và
con trỏ nút chỉ tới nút tiếp theo trong cây mà nó có cùng tên hoặc con trỏ nút sẽ là
“null” nếu không có nút cùng tên nào khác.
• Mỗi giá trị entry trong bảng header mục thường xuyên có hai trường: tên mục và
con trỏ head trỏ tới một nút trên FP-Tree
2.3.2 Thuật toán xây dựng FP Tree
B1: Duyệt cơ sở dữ liệu lần đầu, tìm tất cả các mục thường xuyên chỉ có một mục và sắp
xếp chúng vào một danh sách L theo thứ tự giảm dần của tần xuất.
B2: Duyệt cơ sở dữ liệu lần hai, với mỗi giao dịch, sắp xếp các mục thường xuyên của nó
theo thứ tự trong L và đưa nó vào cây FP-Tree.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 24
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Hình 2.4 Ví dụ minh hoạt xây dựng cây FP Tree
Kết chương hai:
Chương này NVLV đã trình bày và làm rõ các được các vấn đề sau:
• Thuật toán Apriori và các nhược điểm của thuật toán
• Thuật toán PHP và các kĩ thuật cải tiến so với thuật toán Apriori
• Thuật toán Apriori và các ưu điểm so với các thuật toán cổ điển như
Apriori
Đây là các cơ sở để thiết kế cài đặt hệ thống để phân tích dữ liệu. Chương tiếp theo,
NVLV sẽ trình bày về thiết kế cài đặt của mạng xã hội chia sẻ đồ vật – MiGi.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 25
Lời cảm ơnEm xin gửi lời cảm ơn chân thành tới những thầy cô trong viện công nghệ thông tin vàtruyền thông cũng như những thầy cô trong trường ĐH Bách Khoa TP. Hà Nội, nhưng ngườiđã truyền thụ cho em những kỹ năng và kiến thức quý báu trong quy trình học tập và điều tra và nghiên cứu tạitrường. Đó là những điều kiện kèm theo vô cùng quan trọng giúp em trưởng thành và vững vàngtrong nghành nghề dịch vụ trình độ mình đã chọn. Đặc biệt, em xin gửi lời cảm ơn tới thạc sĩ Hoàng Anh Việt – giáo viên trực tiếphướng dẫn của em. Thầy đã luôn giành sự chăm sóc chỉ bảo tận tình, luôn động viênkhích lệ em vươn lên trong học tập và trong đời sống. “ Mọi tham vọng đều hoàn toàn có thể trởthành hiện thực ”, đó là lời nói của thầy, và đó cũng điều em luôn khắc ghi để khôngngừng nỗ lực vươn tới những tham vọng, những khát khao xa hơn, lớn hơn trong đời sống ! Tinh cảm thương mến của mái ấm gia đình và bạn hữu luôn là một nguồn động lực ý thức tolớn giúp em vững vàng trong đời sống. Có thể khi nào đó, trên chặng đường em đi sẽkhông phẳng phiu, sẽ đầy nguy hiểm thử thách và tranh đấu. Nhưng em biết trong trái timnhững người yêu thương, sẽ luôn cho em những bình yên để nghỉ ngơi và để rồi tiếp tụctiến về phía trước. TP.HN ngày 28 tháng 5 năm 2011S inh viênLê Minh NghĩaLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 2 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Tóm Tắt Nội Dung Đồ Án Tốt NghiệpMạng xã hội đang dần trở thành một phần không hề thiếu trong cuộc sốnghiện đại. Nó mang đến cho con người thời cơ được liên kết một cách dễdàng, để san sẻ sở trường thích nghi, thói quen và tâm lý. Mạng xã hội đã trở thànhmột kho tài liệu số ghi lại nhiều góc nhìn khác nhau của đời sống củamỗi người. Và đó cũng là thời cơ to lớn để những công cụ nghiên cứu và phân tích dữ liệuphân tích tìm ra những thông tin hữu dụng từ người dùng. Nhờ đó giúp chocác website trở nên mưu trí hơn, mang lại cho người dùng nhiều trảinghiệm tốt hơn, cũng như những thông kê và nghiên cứu và phân tích hữu dụng cho quản lývà kinh doanh thương mại. Trong đồ án tốt nghiệp này, người viết luận văn tập trungnghiên cứu luât kết hợp – một trong những nghành nghề dịch vụ được ứng dụng rộng rãinhất của Data Mining. Đề từ đó góp thêm phần tìm ra những thói quen san sẻ đồvật của người dùng trong mạng san sẻ đồ vật-MiGi. Nhằm làm cho hệthống hoàn toàn có thể gợi ý mưu trí hơn, giúp người san sẻ thuận tiện tìm đượcngười thực sự cần những đồ vật mình cho đi. Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 3 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Abtract Thes isSocial Network becomes gradually the indispensable thing in the modernlife. It brings the opportunity for people to connect easily, to share theirinterests, habits, and thoughts … Social Network has become a huge digitaldatabase to record many different aspects of each users s ’ life. It is also thegreat chance for data analytic tools to discover useful information of users. It makes website more intelligent, give better experience for users, and alsouseful analytic and statistic for business and management. In this thesis, author concentrates on Association Rules – one of the most important areasin Data Mining. With purpose is to find sharing habits in the object sharingnetwork-MiGi. It makes system more intelligent in suggestion functions, supports offering people find easily the person that really need the objectthey shared. Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 4 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Mục LụcLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 5 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Danh mục những kí hiệu và chữ viết tắt. STT Từ Viết Tắt Giải nghĩa1 NVLV Người viết luận văn2 CSDL Cơ sở dữ liệu3 DB Database4 DHP Direct Hashsing and Pruning5 PHP Perfect Hashing and Pruning6 FP Tree Frequent Pattern Tree7 Association Rules Luật kết hợp8 Item Mục9 ItemSet Tập mục10 K Item Set Tập K mục11 Support Count Độ hộ trợ12 Min Sup Độ hộ trợ tối thiểu13 Confidence Độ tin cậy14 Min Conf Độ an toàn và đáng tin cậy tối thiểu15 Frequent Itemset Tập mục thường xuyên16 Transaction Giao dịchLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 6 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Danh mục những bảng. Bảng3. 2. tin tức đăng kýBảng3. 3. Mô tả tính năng đăng nhậpBảng3. 4. Mô tả thông tin đăng nhậpBảng3. 4. Mô tả tính năng hiển thị list vật phẩm chia sẻBảng3. 5. Mô tả tính năng tạo một offerBảng3. 6. Mô tả thông tin tạo đồ vậtBảng3. 7. Mô tả tính năng xem thông tin đồ vậtBảng3. 8. Mô tả tính năng hiển thị list request của cộng đồngBảng 3.9. Mô tả tính năng tạo requestBảng3. 10. Mô tả tính năng tạo requestBảng 3.11 Bảng miêu tả bảng tài liệu tbl_AccountBảng 3.12 Bảng diễn đạt bảng tài liệu tbl_OfferBảng 3.13 Bảng diễn đạt bảng tài liệu tbl_RequestBảng 3.14 Bảng diễn đạt bảng tài liệu tbl_RequestGiftTransactionBảng 3.15 Bảng miêu tả bảng tài liệu tbl_GiftRequestTransactionBảng 3.16 Bảng diễn đạt bảng tài liệu tbl_CategoryLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 7 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Danh mục những hình vẽ và đồ thị. Hình 2.1 Bảng dữ liệu mẫu cho ví dụHình 2.2. Ví dụ về tìm tập mục thường xuyênHình 2.3 : Code mẫu thuật toán AprioriHình 2.4 Ví dụ minh hoạt thiết kế xây dựng cây FP TreeHình 3.1 Sơ đồ Use Case cho người dùng thông thườngHình 3.2. Sơ đồ use case cho nhóm người tổ chức triển khai từ thiệnHình 3.3. Sơ đồ use case cho nhóm người dùng adminHình 3.4. Kiến trúc toàn diện và tổng thể của hệ thốngHình 3.5. Sơ đồ phụ thuộc vào của những package chính của mạng lưới hệ thống / Hình 3.6 : Sơ đồ những link những lớp chính của hệ thốngHình 3.7 Biều đồ diễn tiến tính năng đăng kýHình 3.8. Biểu đồ diễn tiến tính năng đăng nhậpHình 3.9 Biểu đồ diễn tiến tính năng OfferHình 3.10 Biểu đồ diễn tiến tính năng tạo mới request đồ vậtHình 3.11 Biểu đồ diễn tiến cho công dụng hiển thị list offer đồ vậtHình 3.12 Biểu đồ diễn tiến cho tính năng hiển thị list những request đồ vậtHình 3.13 Biểu đồ diễn tiến cho tính năng request tới một vật phẩm được chia sẻHình 3.14 Biểu đồ diễn tiến cho công dụng offer vật phẩm cho một requestHình 3.15 Sơ đồ phong cách thiết kế databaseHình 3.16 : Sơ đồ Database phân tíchHình 3.17 : Quy trình giải quyết và xử lý tài liệu để phân tíchHình 3.17 : Sơ đồ lớp của module phân tịch luật AprioriHình 3.18 : Sơ đồ lớp của module nghiên cứu và phân tích luật PHPHình 5.19 : Sơ đồ lớp của module nghiên cứu và phân tích luật FP TreeLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 8 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Mở đầuQuản lý hiệu suất cao những tài liệu đã là tiềm năng khởi xướng quan trọng cho sự sinh ra vàphát triển của những mạng lưới hệ thống thông tin quản trị. Các mạng lưới hệ thống thông tin quản trị ngày mộtđược sử dụng thoáng đãng hơn trong mọi hoạt động giải trí của đời sống. Từ những mạng lưới hệ thống lớn chocác ngân hàng nhà nước, nhà hàng siêu thị, cho tới những mạng lưới hệ thống quản trị cho những nhà hàng quán ăn, cửa hiệu … Và dữliệu cũng bùng nổ cùng với sự tăng trưởng và phổ cập của những mạng lưới hệ thống thông tin quản trị. Giờ đây quản trị hiệu suất cao tài liệu không còn là tiềm năng duy nhất mà hơn thế cần phảibiết khai thác hiệu suất cao tài liệu tàng trữ. Đó chính là nguyên do cho sự tăng trưởng mạnhmẽ của nghành nghiên cứu và điều tra data mining trong những thập niên gần đây. Luật kết hợp là một trong những nghành nghề dịch vụ data mining được vận dụng thoáng rộng trongrất nhiều nghành khác nhau. Nó được tăng trưởng xuất phát từ nhu yếu trong thực tiễn khi người tacần tìm những quy luật về mối quan hệ giữa những loại sản phẩm được mua và bán cùng nhau trongcác ẩm thực ăn uống. Các quy luật đó rất có ý nghĩa đối việc marketing ra mắt mẫu sản phẩm chokhách hàng, hay đơn thuần là bố trị vị trí những quầy bán hàng gần nhau sao cho hài hòa và hợp lý nhất. Mộtngười mua máy tính thường mua kèm ứng dụng diệt virus, vậy thì thay vì để cách xanhau, họ hoàn toàn có thể xếp hai quầy bán hàng ở gần nhau. Như vậy thời cơ cho khách mua đồng thờihai mẫu sản phẩm sẽ cao hơn rất nhiều. Trong đồ án tốt nghiệp này, NVLV vận dụng những thuật toán luật kết hợp vào hệ thốngmạng san sẻ vật phẩm do người viết luật văn xây dưng với mong ước tìm ra những quy luậtcho trong hoạt động giải trí san sẻ vật phẩm. Từ đó sẽ có những gợi ý mưu trí cho người dùng, giúp quy trình tìm kiếm vật phẩm được thuận tiện. Mạng san sẻ vật phẩm là một web site được cho phép người dùng đưa những thông tin về cácđồ vật mà người dùng không còn cần dùng nữa. Và những người đang cần tới chúng cóthể sử dụng mạng san sẻ để thuận tiện liên lạc với người cho. Đó là dự án Bất Động Sản do người viếtluật văn thiết kế xây dựng để tham gia cuộc thi Imagine Cup 2011 do Microsoft tổ chức triển khai. Với mụctiêu tạo ra một hội đồng trợ giúp lẫn nhau Giao hàng cho những tiềm năng thiên niên kỉ là xóađói giảm nghèo và bảo vệ môi trường tự nhiên. Bố cục đề tài tốt nghiệp của NVLV gồm những phần chính sau : • Chương 1 : Trình bày về vai trò của những mạng xã hội với bài toán khám phá tài liệu. Lợi ích từ việc khai thác tài liệu mạng san sẻ vật phẩm MiGi. Đồng thời trình bàycác kim chỉ nan cơ bản về luật kết hợp. Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 9 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. • Chương 2 : Trình bày về những giải thuật cơ bản của luật kết hợp, cùng một kỹ thuậtcài đặt và giải quyết và xử lý. • Chương 3 : Thiết kế và setup mạng san sẻ vật phẩm phục vụ việc nghiên cứu và phân tích tài liệu. • Chương 4 : Các hiệu quả đạt đượcLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 10 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Chương 1 : Bài toán khai phádữ liệu từ mạng xã hộiTrong chương này sẽ trình diễn về : • Sự tăng trưởng của những mạng xã hội • Mạng xã hội và bài toán data mining • Mạng xã hội san sẻ đồ vậtMạng xã hội đáng tăng trưởng một cách bùng nổ. Nó trở thành một trào lưu can đảm và mạnh mẽ, lôi cuốn hàng triệu người tham gia. Nó mang tới thời cơ cho người dùng hoàn toàn có thể thuận tiện kếtnối với nhau, san sẻ thông tin. Các mạng xã hội trở thành những kho tàng trữ số thông tincủa người dùng. 1.1. Mạng xã hộiNgày nay, những mạng xã hội đang có sự tăng trưởng bùng nổ, với số lượng người dùnglên đến hàng trăm triệu. Các mạng xã hội đang dần trở thành một thiên nhiên và môi trường mạngkhông thể thiếu với hàng triệu người dùng. Nơi mang lại cho người dùng một thời cơ tolớn để liên kết và san sẻ thông tin thuận tiện. Nó cũng phản ánh nhu yếu tâm ý tất yếu củacon người là san sẻ và trao đổi thông tin. Khi mà xã hội càng tân tiến thì áp lực đè nén cuộcsống, sự thiếu thốn về thời hạn càng tăng … Điều đó làm cho những mạng xã hội trở thànhmột môi trường tự nhiên tiện lợi để người dùng hoàn toàn có thể san sẻ nhanh gọn những thông tinmình có với bè bạn. 1.1.1. Mạng xã hội FacebookFacebook là mạng xã hội lớn nhất quốc tế, được xây dựng vào tháng 2 năm 2004, Facebook khởi đầu có tên là Facemash. Đây là một phiên bản Hot or Not của trường đạihọc Harvard. Sau đó, MarkZuckerberg xây dựng “ The Facebook ” đặt trên domainthefacebook.com. Dịch Vụ Thương Mại mạng xã hội này bắt đầu chỉ dành riêng cho những sinh viên củaĐại học Harvard. Chỉ sau một tháng, hơn nửa số sinh viên Đại học Harvard đã đăng kýsử dụng dịch vụ này. Tháng 9 năm 2004, Mark Zuckerberg đã chuyển trụ sở của thefacebbook.com vềPalo, Alto, California và bỏ chữ “ the ” trong tên miền thefacebook.com, chuyển thànhfacebook. com. Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 11 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Facebook nhanh gọn trở thành cái tên quen thuộc so với người sử dụng những dịchvụ mạng xã hội. Đến tháng 12 năm 2004, tức chỉ 10 tháng sau khi xây dựng, Facebook đãgần chạm mốc 1 triệu người dùng. Một năm sau đó, số người dùng đã tăng vọt lên tới 5.5 triệu người. Facebook dầndần lan rộng ra hoạt động giải trí ra khoanh vùng phạm vi bên ngoài những trường ĐH. Các trường trung học tạiHoa Kỳ khởi đầu được thêm vào mạng lưới hệ thống. Tháng 4 năm 2008, Facebook chính thức xuất hiện trên nhiều vương quốc và vùng lãnh thổvới 21 ngôn từ khác nhau. Số thành viên của mạng xã hội này đã lên tới 100 triệungười. Thành công đến với Facebook nhanh hơn mong đợi khi số lượng thành viên củamạng xã hội này lần lượt chạm mốc 200 triệu vào tháng 4, 300 triệu vào tháng 9 năm2009, 400 triệu vào tháng 2 năm 2010. Mới đây nhất, Facebook đã vượt mốc 500 triệungười dùng. 1.1.2. Mạng xã hội TwitterTwitter cũng là một trong những mạng xã hội lớn nhất quốc tế. Nó còn được biết đếnnhư một mạng “ tiểu ” blog khi mà mỗi người dùng chỉ được phép đăng một tin ( tweet ) cóđồ dài không vượt quá 104 kí tự. Mặc dù vậy, nhưng Twitter cung ứng đúng nhu yếu củangười dùng trong một xã hội ngày càng “ vội vã ”. Ngày 21/3 vừa mới qua Twitter kỉ niệm sinh nhật lần thứ 5 của mình. Đó một dấu mốcquan trọng trong sự tăng trưởng nhiều thăng trầm mạng tiểu blog này. Đã có thời Twitterphải chật vật để níu giữ người dùng. Nhưng thời nay witter đã trở nên trưởng thành hơnvà giữ một vai trò quan trọng trong xã hội, chính trị, tiếp thị quảng cáo, thể thao và nhiều lĩnhvực khác. Người dùng Twitter lúc bấy giờ gửi đi 140 triệu đoạn tweet mỗi ngày. Trước đây, Twitter đã mất 3 năm, 2 tháng và 1 ngày để đạt được 1 tỷ tweet tiên phong, nhưng giờ đây, cứ 8 ngày thì có 1 tỷ tweet được gửi đi. Tương tự, Twitter đã mất 18 tháng để có 500 ngàn người dùng, nhưng giờ đây, mỗingày lại có thêm 500 ngàn thông tin tài khoản mới được ĐK. 1.1.3. Mạng xã hội Zing MeĐáp ứng xu thế mạng xã hội, tại Nước Ta đã có hàng loạt mạng xã hội sinh ra. Tiêubiểu trong số đố là mạng xã hội Zing Me do tập VNG làm chủ. Đây hoàn toàn có thể nói là mạng xãLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 12 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. hội lớn nhất Nước Ta. Chỉ sau hơn một năm tăng trưởng Zing Me đã có hơn 5 triệu ngườidùng. Với giao diện được việt hóa thân thiện, cùng sự tích hợp nhiều ứng dụng và dịch vụkhác nhau, Zing Me đã nhanh gọn lôi cuốn được một lượng lớn người dùng. Đặc biệt lànhóm những người dùng trẻ tuổi. Zing Me phân phối một môi trường tự nhiên san sẻ và liên kết dễdàng. Đồng thời Zing Me cũng cung ứng nhiều công cụ khác nhau để những doanh nghiệp tổchức những sự kiện, triển khai những tìm hiểu thăm dò. Zing Me cũng mở những API để những bênthứ ba tăng trưởng những ứng dụng dựa trên nền tảng Zing Me. Zing Me ngày càng chiếmđược tình cảm của người dùng, đặc biệt quan trọng là nhóm người dùng trẻ tuổi. Đó là cơ sở cho sựphát triển vững chắc tại thị trường Nước Ta sau này. Trên đây là một số ít mạng xã hội thông dụng ở trên quốc tế và ở Nước Ta. Nó cho thấymạng xã hội đã trở thành một khuynh hướng chi phối đời sống xã hội, nó chiếm được cảm tínhvà sự chăm sóc của tổng thể mọi lứa tuổi, những tầng lớp và trên khoanh vùng phạm vi toàn thế giới to lớn. Xuhướng đó tạo ra sự tăng trưởng bùng nổ của mạng xã hội. Đồng thời nó cũng biến mạng xãhội trở thành một kho chứa thông tin khổng lồ. Bởi mạng xã hội gần như trở thành mộtmôi trường xã hội ảo. Nó ghi nhận một cách phong phú những hoạt động giải trí khác nhau của ngườidùng. Nó nắm giữ từ những thông tin cá thể, cho tới những thông tin về những mối quan hệ, vềsở thích, về thói quen của người dùng. Mạng xã hội trở thành một kho tài liệu khổng lồmà nếu khai thác hiệu suất cao người ta hoàn toàn có thể tìm được rất nhiều thông tin hữu dụng. Có thểđoán nhận được sở trường thích nghi của một người, nghiên cứu và phân tích những khuynh hướng về nhu yếu của ngườidùng, hay mối quan hệ giữa những người dùngNhưng chính sự phong phú về tài liệu lại chính là một trong những rào cản để phục vụcác bài toán nghiên cứu và phân tích và khai thác tài liệu. Chính cho nên vì thế mà không có một quy mô phântích thống kê chung nhất cho tổng thể những mạng xã hội, mà nó đổi khác tùy theo từng mụcđích khác nhau của bài toán. Đối với một mạng như Amazon thì thông tin về sở thíchngười dùng luôn được chăm sóc số 1. Từ đó hoàn toàn có thể biết được mối chăm sóc giữanhững loại sách mà người dùng tìm kiếm. MiGi là một mạng san sẻ vật phẩm. Trong hoạt động giải trí san sẻ vật phẩm, luôn xuất hiệnyêu cầu vật phẩm được san sẻ tìm được đến đúng người có nhu yếu tương thích với loại đồ vậtđược san sẻ. Điều đó giúp quy trình san sẻ hiệu suất cao hơn, và cũng giúp người dụng thuậttiện hơn trong quy trình tìm kiếm và sử dụng. Xuất phát từ nhu yếu đó, mạng lưới hệ thống cần phải xác lập được những quy luật xem ngườidùng thường san sẻ những vật phẩm gì cùng nhau, cũng như thường có nhu yếu về nhữngLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 13 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. loại vật phẩm nào. Ví dụ người X cho vật B thì thường sẽ cho thêm vật C, hoặc người lạingười Y khi xin một vật phẩm D thì thường sẽ có nhu yếu so với vật E. Những luật đó gọilà những luật kết hợp. Để tìm được những luật kết hợp đó, yên cầu phải tìm được tập những vật phẩm mà ngườidùng thường san sẻ cùng nhau, hoặc tập những vật phẩm mà người dùng thường nhu yếu. Đólà trọng tâm của tổng thể những thuật toán tìm luật kết hợp. 1.2. Các quyền lợi từ việc khai thác tài liệu mạng san sẻ vật phẩm MiGiViệc khai thác dữ liều từ mạng san sẻ vật phẩm mang lại nhiều thông tin có ích chonhiều lính vực khác nhau. Có thể kể ra một số ít hướng hoàn toàn có thể khai thác được từ dữ liệungười dùng của mạng MiGi là : • Xác định được thói quen san sẻ vật phẩm của người dùng : biết được những mónđồ mà người dùng thường cho đi, những nhu yếu thường đi cùng với nhau. Để từđó kiến thiết xây dựng những hệ gợi ý mưu trí. Ví dụ : người A cho một cái điện thoại cảm ứng cũ, người B cần chiếc đoạn thoại đó, thì hoàn toàn có thể sẽ cần một chiếc xác điện thoại cảm ứng củamột người X nào đó cũng cho đi. • Phân tích sở trường thích nghi của người dùng để Giao hàng mục tiêu quảng cáo. Qua cácđồ vật người đó cho đi hoàn toàn có thể biết phần nào là sở trường thích nghi người dùng là gì. Ví dụnhãn hiệu quần áo mà người ta chăm sóc. Đó là cơ sở để quảng cáo những sảnphẩm tương thích. • Điều tra thị trường : Qua những vật phẩm mà hội đồng cho đi hoàn toàn có thể xác địnhnhu cầu tiêu thụ của một khu vực nào đó. Thông thường, nếu loại sản phẩm nào đócàng hút khách thì càng có nhiều đồ được “ thải ” ra. Dựa trên MiGi cũng có thểlập được một map số phân bổ theo nhu cầu1. 3. Tổng quan về tìm hiểu và khám phá dữ liệuData Mining là một nghành to lớn, nó được chia thành nhiều nghành nhỏ để giảiquyết nhiều bài toán khác nhau. Trong khoanh vùng phạm vi đề tài, người viết luận văn chỉ cố gắngtìm hiểu để chớp lấy những ý tưởng sáng tạo chính để Giao hàng cho bài toán yêu cầu. Chính vì vậy, để tập trung chuyên sâu cho phần trình diễn, trong chường này chỉ xin trình diễn về những triết lý cơbản về luật kết hợp. Lĩnh vực luật kết hợp là một trong những nghành được quan tâmnhiều nhất trong data mining. Bởi nó được ứng dụng một cách thoáng rộng nhằm mục đích phân tíchcác mối quan hệ, tìm ra những quy luật giữa những thuộc tính khác nhau … Ví dụ như trong cácsiêu thị khi tìm kiếm quy luật về những loại sản phẩm mà người dùng cùng mua với nhau, haytrong y học khi tìm mối quan hệ giữa những triệu chứng dẫn đến một loại bệnh nào đó … Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 14 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. 1.3.1. Các khái niệm cơ bản. a. Tập mục. • I1, I2, … In là những mục-mặt hàng ( items ). I = { I1, I2, … In } là tập toàn bộ những mục. • Một tập con X I được gọi là tập mục ( itemset ). Một k-tập mục ( k-itemset ) là môttập mục chứa k mục ( item ). b. Độ tương hỗ tập mục. • Cho một cơ sở tài liệu D = { T1, T2, … Tn } là một tập thanh toán giao dịch, trong đó mỗi giaodịch Ti, i { 1, … n } là một tập mục. Một thanh toán giao dịch T chứa một tập mục X nếu XT.Một thanh toán giao dịch Ti được đi kèm với một chỉ số TID. • Chỉ số tương hỗ so với tập mục X ( tư vấn count ) được định nghĩa là số giao dịchtrong cơ sở tài liệu D chứa tập mục X : ( 1 ) • Độ tương hỗ được định nghĩa như thể tỉ lệ số thanh toán giao dịch trong cơ sở tài liệu D chứa tậpmục X, tức là : ( 2 ) • Chỉ số tư vấn count còn được gọi là độ hộ trợ tuyệt đối ( absolute tư vấn ). Chỉsố tương hỗ còn được gọi là độ tương hỗ tương đối ( relative tư vấn ). c. Luật kết hợp. • Một luật kết hợp ( association rule ) là một luật có dạng, trong đó và. X được gọilà tiền nghiệm, X được gọi là hiệu quả suy ra. • Luật có độ đáng tin cậy c ( confidency ) trong tập thanh toán giao dịch D nếu c % những giao dịchtrong D khi đã chứa X thì cũng chứa Y : ( 3 ) • Luât có độ an toàn và đáng tin cậy c ( confidency ) trong tập thanh toán giao dịch D nếu c % những giao dịchtrong D khi đã chứa X thì cũng chứa Y : hay ( 4 ) • Một ngưỡng s min được sử dụng để vô hiệu những luật mà tập mục có độ tương hỗ nhỏhơn s min, và một ngưỡng c min dùng để vô hiệu những luật không có đủ độ chắcchắn c min. d. Tập mục tiếp tục. Các tập mục với độ tương hỗ lớn hơn độ tương hỗ tối thiểu được gọi là những tập mụcthường xuyên ( frequent itemset ) hay những tập mục lớn ( large itemsets ). Tập những k-itemsetthường được ký hiệu là Lk. Ví dụ : Cơ sở tài liệu giao dịchLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 15 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. TID Items1 Bread, Milk2 Bread, Diaper, Beer, Eggs3 Milk, Diaper, Beer, Coke4 Bread, Milk, Diaper, Beer5 Bread, Milk, Diaper, CokeTập { Milk, Bread, Diaper } là tập 3 – items, có : • Độ tương hỗ tuyệt đối : • Độ tương hỗ tương đối : • Luật kết hợp { Milk, Diaper } => { Beer } e. Tập mục đóng, tập mục tiếp tục cực lớn • Tập mục X được gọi là đóng ( closed itemset ) nếu không sống sót tập mục Y, saocho và. Một tập mục tiếp tục và đóng được gọi là tập mục thường xuyênđóng ( closed frequent itemset ). • Một tập mục X được gọi là tập mục tiếp tục cực lớn ( maximal frequentitemset ) nếu X liên tục và không sống sót tập mục Y, và Y là tiếp tục. 1.3.2. Bài toán phát hiện luật kết hợp. Cho một tập mục I, một cơ sở tài liệu những tập mục D, một ngưỡng tương hỗ sminvà mộtngưỡng đáng tin cậy cmin, cần phải tìm ra những luật kết hợp trong D với độ tương hỗ và độ an toàn và đáng tin cậy. Một cách tổng quát, phát hiện luật kết hợp được chia làm hai bước : • Bước 1 : Tìm toàn bộ những tập mục tiếp tục. • Bước 2 : Sinh ra những luật an toàn và đáng tin cậy từ những tập mục liên tục. Từ công thức ( 4 ), độ an toàn và đáng tin cậy của hoàn toàn có thể được tính trải qua độ tương hỗ của X và. Điều này có nghĩa là khi đã tính được độ tương hỗ của X, Y và thì hoàn toàn có thể trực tiếp sinh racác luật dạng và và kiểm tra xem chúng có phải là những luật an toàn và đáng tin cậy hay không. Vì chi phítính toán của bước hai là nhỏ hơn rất nhiều so với bước, hiệu năng của toàn quá trìnhphát hiện luật kết hợp phụ thuộc vào vào hiệu năng của bước 1, từ đó bài toán phát hiện luậtkết hợp được đơn thuần thành bài toán phát hiện những tập mục liên tục. 1.3.3. Khó khăn trong phát hiện luật kết hợp. Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 16 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Mặc dù có những độ đo khác nhau được đề xuất kiến nghị trong phát hiện luật kết hợp, nhưng2 độ đo chính vẫn được sử dụng thông dụng là độ đo tương hỗ ( tư vấn ) và độ đo an toàn và đáng tin cậy ( confidency ). Khi giống nhau về giá trị ngưỡng của độ đo tương hỗ và an toàn và đáng tin cậy, những cách tiếpcận khác nhau phải cho cùng một tập luật kết hợp. Khi đó, để so sánh những phương phápvới nhau, người ta sẽ so sánh về hiệu năng của thuật toán ( ngân sách thống kê giám sát, ngân sách bộnhớ ), những cấu trúc tài liệu được sử dụng, kế hoạch tìm kiếm và cách cắt giảm tập mụckhông tiếp tục … a. Khó khăn trong giảm độ phức tạp của thuật toán. Khó khăn đặt ra hầu hết trong phát hiện luật kết hợp so với CSDL kích cỡ lớnlà thường sinh ra rất nhiều tập mục liên tục, đặc biệt quan trọng trong trường hợp ngưỡngminsup nhỏ. Điều này là chính bới một tập mục là liên tục thì những tập mục bộ phận củanó ( sub-itemset ) cũng là liên tục. Chẳng hạn như một tập mục tiếp tục có-kích thước 100 { a, a, …, a100 } sẽ chứa tập 1 – mục, tập 2 – mục tiếp tục … Điềunày dẫn đến số tập mục liên tục được chứa trong tập mục tiếp tục kích thước100 là : Là quá lớn cho máy tính giám sát và tàng trữ. Zaki [ 2 ] đã chứng tỏ bài toán phát hiện toàn bộ những tập mục tiếp tục là bài toánNP-khó. Bởi vì với CSDL có d tập mục, số ứng viên phải là clà hàm mũ. Đã có nhiều thuật toán và kĩ thuật khác nhau được yêu cầu để làm tăng hiệu năngcủa mạng lưới hệ thống, trong đó tập trung chuyên sâu vào việc cắt tỉa những transaction không Giao hàng quá trìnhtìm luật kết hợp, cắt bỏ những mục không có ý nghĩa, sử dụng những cấu trúc tài liệu bảng bămđể tàng trữ nhằm mục đích giảm số lần duyệt cơ sở tài liệu. b. Khó khăn trong phát hiện luật kết hợp có giá trịBên cạnh yếu tố về việc phải thống kê giám sát trên quy trình tập mục tiếp tục, mộtvấn đề khác trong phát hiện luật kết hợp là hoàn toàn có thể bỏ sót những luật có ý nghĩa. Lấy ví dụnhư với cách tiếp cận thường thì, những tập mục có cùng một ngưỡng tương hỗ. Khi đó, nếuđặt ngưỡng này đủ lớn để loại đi được nhiều tập mục không liên tục, thì có nhữngtập mục có thực chất ít Open trong thanh toán giao dịch sẽ không được phát hiện trong luật. Tuynhiên, nhiều khi những luật tương quan tới những loại sản phẩm ít Open này lại có giá trị. Cụthể như trong CSDL thanh toán giao dịch, những tập mục tương quan tới những mẫu sản phẩm tiêu dùng nhưbánh mỳ, sữa … có doanh thu thấp, tính thông dụng hơn rất nhiều so với những tập mục liênquan đến những mẫu sản phẩm như tivi, tủ lạnh, điều hòa … vốn là những mắt hàng ít mua nhưngLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 17 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. lại có doanh thu cao. Nếu ngưỡng tương hỗ cao, thì chỉ phát hiện được những luật tương quan đếnmặt hàng tiêu dùng, mà bỏ đi một mảng tương quan đến những mẫu sản phẩm cho doanh thu cao. Cách tiếp cận ở đây là đưa ra với mỗi một mục khác nhau một giá trị ngưỡng tương hỗ khácnhau. Giá trị ngưỡng tương hỗ cho tập mục sẽ được xác lập dựa trên giá trị tương hỗ của cácmục thành viên. Ngoài ra, với những mục khác nhau người ta hoàn toàn có thể đưa vào trọng số chỉmức độ quan trọng khác nhau. Hơn nữa, trong trường hợp những tập mục ở những mức khác nhau, một cách đươngnhiên, những mục ở mức trừu tượng cao hơn sẽ có giá trị tương hỗ cao hơn những mục ở mức trừutượng thấp. Nếu đặt ngưỡng tương hỗ quá thấp, thì sinh ra quá nhiều luật, ngược lại vớingưỡng tương hỗ cao thì chỉ sinh ra được những luật ở mức trừu tượng cao, mà bỏ xót những luậtquan trọng ở mức trừu tượng thấp. Cách tiếp cận ở đây là đưa ra chính sách kiểm soát và điều chỉnh giá trịngưỡng tương hỗ cho tương thích với từng mức khác nhau. Kết chương một : Qua trường này NVLV đã trình diễn tổng quan về những mạng xã hội, và tiềm năng choviệc khai thác tài liệu từ những mạng xã hội. Đồng thời NVLV trình diễn những kỹ năng và kiến thức cơbản tìm hiểu và khám phá tài liệu trong nghành nghề dịch vụ luật kết hợp. Qua đây NVLV định ra những tiềm năng củađồ án tốt nghiệp là : • Xây dưng tăng trưởng hoàn thành xong MiGi để khai thác thông tin và hỗ trợgiao dịch • Tìm hiểu những thuật toán về luật kết hợp • Cài đặt và so sánh nhìn nhận những thuật toán trên bộ tài liệu thực • Định hướng tăng trưởng lan rộng ra. Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 18 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Chương 2 : Luật kết hợpvà những kĩ thuật xử lýTrong chương này sẽ trình diễn : • Thuật toán Apriori • Thuật toán PHP • Thuật toán FP TreeNhư đã trình diễn ở trên, khó khăn vất vả của bài toán tìm luật kết hợp nằm ở việc tìm đượccác tập mục tiếp tục. Nó là bước chiếm nhiều hiệu năng nhất của mạng lưới hệ thống. Tất cảcác thuật toán tìm luật kết hợp đều xoay quanh viên tìm kiếm những tập mục thường xuyênsao cho nhanh nhất và hiệu suất cao nhất hoàn toàn có thể. Trong nghiên cứu và phân tích luật kết hợp, có hai loại cơ sở tài liệu là cơ sở tài liệu đơn chiều vàcơ sở dữ liệu đa chiều. CSDL đơn chiều chỉ có một chiều. Ví dú như cơ sở tài liệu giaodịch, chỉ có chiều “ loại sản phẩm ”, trong đó mỗi bản ghi là một thanh toán giao dịch, ghi nhận những mặthàng được mua bởi người dùng trong thanh toán giao dịch đó. CSDL đa chiều có nhiều chiều, nhưbên cạnh chiều loại sản phẩm thì còn có thêm những chiều thuộc tính khác của mẫu sản phẩm. Ví dụ : sắc tố, thương hiệu, Chi tiêu … Dưới là trình diễn vắn tắt những giải thuật cơ bản để tìm những tậpmục liên tục trong cơ sở tài liệu đơn chiều. 2.1. Thuật toán AprioriGiải thuật Apriori là một giải thuật được R.Agrawal và R.Srikant được ra vào năm1994. Đên nay nó vẫn được coi là một giải thuật nổi tiếng nhất trong việc tìm luật kếthợp. Tên của giải thuật dựa trên thực tiễn giải thuật sử dụng kỹ năng và kiến thức tiên nghiệm những tậpmục liên tục để xác lập những tập mục liên tục có kích cỡ lớn hơn. Apriori sửdụng chiêu thức search lan rộng ra theo mức, trong đó tập k-muc ( k-itemset ) được sửdụng để tìm những tập mục k + 1. Đầu tiên những tập 1 mục ( 1 – itemsets ) được tìm thấy bằngviệc quét hàng loạt database, đồng thời xác lập độ tương hỗ tương ứng. Kết quá ta được tậpL1. L1 được sử dụng để tìm tập L2 là những tập 2 mục ( 2 – itemsets ), rồi từ L2 tìm đượcL3 … Quá trình tiếp nối cho tới khi không tìm được thêm tập mục nào nữa. Để tăng tính hiệu suất cao của quy trình search theo Lever ( wise level search ) giải thuậtPriori sử dụng thuộc tính tiên nghiệm, nhằm mục đích vô hiệu những tập sinh ra, giúp giảm không giansearch. Thuộc tính tiên nghiệm được định nghĩa như sau : Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 19 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Thuộc tính tiên nghiệm ( Apriori ) : Tất cả những tập con không rỗng của một tập mụcthường xuyên phải là một tập mục tiếp tục. Dựa trên thuộc tính này, thì tại bước sinh những tập Lk + 1 từ Lnếu bất kể một tập mụcnào thuộc Lk + 1 mà không thuộc Lnghĩa là không phải tập mục liên tục, thì sẽ loạibỏ Lk + 1 tương ứng. Giải thuật Apriori gồm hai bước chính : • Bước Join : để tìm lập mục tiếp tục K, một tập những ứng viên k mục sẽđược sinh ra bằng cách join những tập Lk-1với chính nó. Tập hợp sinh ra gọi làtập C. Từ tập này tất cả chúng ta sẽ sử dụng để tìm L • Bước tỉa : Sau khi join tập Lk-1với chính nó ta được tập Clà tập lớn chứa tập. Trong đó chứa những những tập k-mục liên tục, và cả những tập không phảithường xuyên. Để xác lập, thì phải triển khai quét database. Nhưng số lượngtập mục thuộc Clà rất lớn. Ngân sách chi tiêu quét cho hàng loạt là rất tốn kém. Để giảmkhông gian search thì lúc này thuộc tính tiên nghiệm được sử dụng. Bất cứtập hợp nào thuộc Cmà có tập con k-1 không phải tập mục thường xuyênđều bị vô hiệu. Từ đó mà khoảng trống search sẽ giảm xuống. Ví dụ : Cơ sở tài liệu gốc : Hình 2.1 Bảng dữ liệu mẫu cho ví dụQuá trình tìm kiếm những tập mục liên tục với ngưỡng độ tương hỗ là 2. Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 20 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Hình 2.2. Ví dụ về tìm tập mục thường xuyênDưới đây là code diễn đạt thuật toán : Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 21 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Hình 2.3 : Code mẫu thuật toán Apriori2. 2. Thuật toán PHP – Perfect Hashing and PrunningGiải thuật PHP ( Perfect Hashing and Prunning ) là giải thuật được tăng trưởng lên từgiải thuật Apriori nhằm mục đích cải tổ hiệu năng. Giải thuật PHP sử dụng những kĩ thuật bảngbăm, tận dụng nhiều tri thức tiền nghiệm để loại giảm số lượt quét database và giảm kíchcỡ của cơ sở tài liệu thanh toán giao dịch. Giải thuật PHP gồm ba phần : Phần 1 : Quét hàng loạt Database, đếm số lần Open của những mục ( item ), đồng thời xâydựng bảng băm cho những tập 2 mục, lựa chọn những item thỏa mãn nhu cầu độ tương hỗ tối thiểu để đưavào L1Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 22 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Phần 2 : Từ bảng băm tất cả chúng ta sẽ xác lập được tập những ứng viên. Các ứng viên đó sẽđược kiểm tra để tạo ra L. Khi tất cả chúng ta kết thúc L, database sẽ được cắt giảm, loại bỏcác mục không cần thiệt, những thanh toán giao dịch không có ý nghĩa. Phần 3 : Tương tự như phần hai nhưng trừ việc phải thiết kế xây dựng lại bảng băm. Cắt tỉa Trong giải thuật PHP một phần quan trọng là thao tác cắt tỉa database. Thao táccắt tỉa database dựa trên hai nhận xét sau : • Một thanh toán giao dịch hoàn toàn có thể chứa k + 1 tập k-mục ( k-itemsets ) khi nó có tối thiểu k + 1 tập k-mục ( k + 1 itemsets ). Điều đó có nghĩa là tất cả chúng ta hoàn toàn có thể vô hiệu những thanh toán giao dịch màkhông có đủ k + 1 tập k-mục • Nếu một item thuộc một k + 1 tập mục liên tục, thì nó phải nằm tối thiểu k lầntrong k tập mục. Do đó tất cả chúng ta sẽ vô hiệu những mục nào có số lần xuất hiệntrong tập Lnhỏ hơn k lần. Thực chất còn sống sót một giải thuật khác trước giải thuật PHP là DHP ( Direct Hashingand Prunning ). PHP cơ bản là giống DHP, chỉ khác nhau ở hàm băm. Hàm băm của PHPlà hàm băm hoàn hảo bảo vệ không có sự trùng lặp key. 2.3. Thuật toán FP TreeNhư đã trình diễn ở trên, việc phát hiện những tập mục liên tục có ý nghĩa quyếtđịnh so với việc sinh ra những tập luật kết hợp. Đối với giải thuật Apriori thì việc tìm cáctập mục liên tục yên cầu phải sinh ra những tập ứng viên. Nhưng ngay cả khi đã ápdụng những kĩ thuật nâng cấp cải tiến thì số tập ứng viên sinh ra vẫn quá lớn. Đó chính là nguyênnhân chính tác động ảnh hưởng tới hiệu năng của thuật toán. Nhóm nghiên cứu và điều tra của Han đã đề xuất kiến nghị sử dụng cấu trúc cây trên ba khía canh sau : • Thứ nhất : Sử dụng cấu trúc tài liệu nén truyền thống cuội nguồn được gọi là cây mẫuthường xuyên FP-Tree ( Frequent pattern tree ) được xây dưng. Nó là sự mởrộng của cây tiền tố để tàng trữ những thông tin hầu hết về cây mẫu thườngxuyên. Chỉ những mục tiếp tục mới có những nút trong cây, và nút củacây được sắp xếp theo ý tưởng sáng tạo nút nào Open liên tục hơn sẽ cócơ hội hơn để san sẻ nút đó. • Thứ hai : Quá trnnh phát hiện tập mục liên tục dựa trên FP-Treeđược tăng trưởng mở màn từ mẫu liên tục kích cỡ 1 ( như một mẫuhậu tổ khởi đầu ), chỉ kiểm tra cơ sở mẫu điều kiện kèm theo ( một cơ sở tài liệu conchứa tập những mục tiếp tục cùng Open với mẫu hậu tổ ), xây dựngFP-Tree điều kiện kèm theo và thực thi tìm hiểu và khám phá đệ quy với cây. Tăng trưởng mẫuđạt được trải qua thao tác liên kết mẫu hậu tố với mẫu hậu tố mới đượcLê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 23 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. sinh ra từ cây FP-Tree điều kiện kèm theo. Thao tác chính ở đây là đếm bộ tích góp vàđiều chính bộ đếm tiền tố, do đó sẽ ít tốn kém hơn so với việc sinh ra cácứng viên và so khớp mẫu được triển khai trong thuật toán Apriori. • Thứ ba : Kỹ thuật tìm kiếm triển khai dựa trên phân đoạn, chia và trị chứkhông phải là kết hợp sinh ra những tập mục liên tục từ dưới lên theokiểu Apriori, do đó giảm size cơ sở mẫu điều kiện kèm theo sinh ra ở mức tiếpsau của việc tìm kiếm. 2.3.1 Cây mẫu thường xuyênĐịnh nghĩa : FP-Tree là một cây mẫu liên tục có cấu trúc như sau : • Cây mẫu gồm có một nút gốc gán nhãn “ null ”, một tập những cây con tiền tố như làcác con của nút gốc và một bảng header mục tiếp tục. • Mỗi nút trong cây con tiền tố gồm có có ba trường : tên mục ( item name ), bộđếm ( count ) và con trỏ nút ( nút – link ). Tên mục cho biết mục mà nút trình diễn, bộđếm cho biết số thanh toán giao dịch được màn biểu diễn một thành phần nút gốc cho tới nút này vàcon trỏ nút chỉ tới nút tiếp theo trong cây mà nó có cùng tên hoặc con trỏ nút sẽ là “ null ” nếu không có nút cùng tên nào khác. • Mỗi giá trị entry trong bảng header mục tiếp tục có hai trường : tên mục vàcon trỏ head trỏ tới một nút trên FP-Tree2. 3.2 Thuật toán kiến thiết xây dựng FP TreeB1 : Duyệt cơ sở tài liệu lần đầu, tìm toàn bộ những mục liên tục chỉ có một mục và sắpxếp chúng vào một list L theo thứ tự giảm dần của tần xuất. B2 : Duyệt cơ sở tài liệu lần hai, với mỗi thanh toán giao dịch, sắp xếp những mục tiếp tục của nótheo thứ tự trong L và đưa nó vào cây FP-Tree. Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 24 Đồ án tốt nghiệp K51Ứng dụng luật kết hợp trong nghiên cứu và phân tích tài liệu của mạng xã hội. Hình 2.4 Ví dụ minh hoạt kiến thiết xây dựng cây FP TreeKết chương hai : Chương này NVLV đã trình diễn và làm rõ những được những yếu tố sau : • Thuật toán Apriori và những điểm yếu kém của thuật toán • Thuật toán PHP và những kĩ thuật nâng cấp cải tiến so với thuật toán Apriori • Thuật toán Apriori và những ưu điểm so với những thuật toán cổ xưa nhưAprioriĐây là những cơ sở để phong cách thiết kế setup mạng lưới hệ thống để nghiên cứu và phân tích tài liệu. Chương tiếp theo, NVLV sẽ trình diễn về phong cách thiết kế setup của mạng xã hội san sẻ vật phẩm – MiGi. Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 25
