Thuật Toán K-láng Giềng Gần Nhất K-Nearest Neighbor [8][9] - 123doc

1. Trang chủ >
2. Thể loại khác >
3. Tài liệu khác >

Thuật toán k-láng giềng gần nhất k-Nearest Neighbor [8][9]

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 (585.2 KB, 55 trang )

27Quá trình lọc cộng tác bao gồm 2 pha: dự đoán Prediction và khuyến cáo Recommendation− Dự đoán đánh giá của một khách hàng trên một sản phẩm. Các dự đoán này dựa trên cơ sở những đánh giá cũ của các khách hàng.− Giới thiệu danh sách các sản phẩm mà khách hàng ưa thích, danh sách này bao gồm những sản phẩm mà khách hàng chưa đánh giá.Trong luận văn này chúng tôi giới thiệu 3 phương pháp lọc cộng tác: − Lọc cộng tác dựa trên láng giềng gần nhất− Lọc cộng tác dựa trên mơ hình mật độ chung − Lọc cộng tác dựa trên mơ hình phân bố có điều kiệnPhương pháp lọc cộng tác sử dụng để xây dựng hệ thống khuyến cáo sản phẩm. Có thể sử dụng nhiều phương pháp trong cùng một hệ thống để thuđược kết quả tốt hơn.

2.2.1 Lọc cộng tác dựa trên láng giềng gần nhất

Phương pháp lọc cộng tác dựa trên láng giềng gần nhất sử dụng thuật toán k-láng giềng gần nhất.2.2.1.1 Thuật toán k-láng giềng gần nhất k-Nearest Neighbor [8][9]kNN là phương pháp truyền thống theo hướng tiếp cận thống kê đã được nghiên cứu trong nhiều năm qua. Thuật toán này được sử dụng trong cácbài toán cần đưa ra kết luận về một đối tượng trong khi không có hoặc có rất ít thơng tin về đối tượng đó.Ý tưởng của phương pháp là phân loại một đối tượng vào trong lớp tương đồng với nó nhất, sau đó đưa ra các kết luận cho đối tượng đó căn cứtheo thơng tin của các đối tượng khác cùng lớp với nó. Để phân lớp cho một đối tượng mới X, thuật tốn tính tốn độ tương đồng giữa X với tất cả các đốitượng khác trong tập dữ liệu. Qua đó tìm được tập NX, D, k gồm k đối tượng tương đồng với X nhất trong tập dữ liệu D. Để tính độ tương đồng giữa hai đốitượng người ta có thể sử dụng nhiều phương pháp đo khác nhau, phương pháp28thông dụng nhất là Euclid. Giả sử mỗi đối tượng là một điểm trong không gian N chiềuNR, với N thuộc tính. Độ tương đồng giữa 2 đối tượng có thể được coi như khoảng cách giữa 2 điểm trong không gianNR:2 ikjk 1, [x -x ]N ij kd X X==∑2 trong đó,i jd X Xlà khoảng cách giữa hai điểm trong không gian, X là một đối tượng vàikxlà thuộc tính k của đối tượngiX. Sau khi xác định được tập NX, D, k, có thể kết luận cho đối tương X bằng lớp chiếm đại đa số trong tậpNX, D, k.Khi phân lớp các đối tượng, chúng ta có thể sử dụng hàm tính trọng số cho mỗi lớp theo biểu thức:, ,| cos ,X Nc X D kScore c X X X∈=∑3 Trong đó NcX, D, k là tập con chỉ chứa các đối tượng thuộc lớp c của tậpNX, D, k. Khi đó đối tương X sẽ được phân vào lớpcnếu:| {| , }Score c X Max Score c X c C= ∈4 với C là tập tất cả các lớp trong D.2.2.1.2 Thuật toán k-láng giềng gần nhất với phương pháp lọc cộng tác [8] Thuật toán k-láng giềng gần nhất sử dụng để xếp nhóm các đối tượngvà đưa ra kết luận cho các đối tượng đó. Áp dụng trong phương pháp lọc cộng tác, các kết luận về đối tượng là thơng tin dự đốn cho một khách hàng, xácđịnh thơng tin dự đốn cho một khách hàng căn cứ trên nhóm khách hàng tương tự. Để dự đốn cho một khách hàng A bất kỳ, tìm những khách hàngtương tự như A trong cơ sở dữ liệu, sau đó dùng thơng tin sản phẩm của các khách hàng đó để thay thế cho thơng tin sản phẩm của A các sản phẩm nàykhách hàng A chưa mua hay đánh giá. Mục đích của phương pháp này là tìm những sản phẩm mà khách hàng có khả năng mua nhất trong hệ thống các sảnphẩm mà khách hàng chưa mua hay bình chọn giá trị sử dụng. Trong các29Website Thương mại điện tử số lượng mặt hàng rất lớn, do đó việc tích tốn các sản phẩm ưa thích nhất sẽ tạo thuận lợi cho khách hàng khi giao dịch.Q trình dự đốn cho một khách hàng: − Tìm các láng giềng gần nhất− Kết hợp các lá phiếu − Dự đoánGiả sử ta cần đưa dự đoán cho một User a. Đầu tiên chúng ta sẽ tìm các láng giềng gần nhất của a bằng cách tính trọng số của a với tất cả các lánggiềng của nó trong ma trận dữ liệu. Trọng số được tính tốn dựa trên sự tươngđồng của lá phiếu giữa 2 User. Chẳng hạn nếu User a bỏ phiếu cho một Item i nào đó, User b khác cũng bỏ phiếu cho Item i đó thì giữa a và b có sự tươngđồng. Trọng số giữa User a với User i được xác định như sau:, ,, 22 ,,wa j ai j ij a ia j ai j ij jv v vv vv vv −− =− −∑ ∑∑5trong đó,wa ilà trọng số giữa hai User, ,, i jvlà giá trị mà User i ước lượng cho Item j trong ma trận V,ivlà giá trị lá phiếu trung bình của User i.ivtính theo cơng thức:,1ii i jj iv v∈=∑ll6vớiillà tập các Item mà User i đã bỏ phiếu đánh giá, i jv0 khi j∈il,, i jv= 0 trong trường hợp ngược lại . Dễ thấy trọng số,wa icó giá trị nằm trong khoảng tử -1 đến 1.Với tất cả các User khác, ta tính tốn giá trị lá phiếu trung bình theo cơng thức 6, từ đó ta có lá phiếu điều chỉnh của ma trận:, ,i j i jiv vv =−730Dự đoán lá phiếu của User a trên Item j để a không phải bỏ phiếu cho nó. Từ các cơng thức 5,6,7 ta tính được giá trị dự đốn cho Item j theocơng thức:a,i ,1 ,a,i 1w |w |n i ji a ja niv vv= == +∑ ∑8, a jvcho thấy tỉ lệ User a mua Item j so với các Item khác trongl. Áp dụng phương trình dự đốn 8 cho tất cả Item trongl\\al. Các giá trị dự đoán cho mỗi Item được xếp hạng và thống kê những Item có hạng cao nhất cho User a.Cơng việc này chính là khuyến cáo sản phẩm cho một khách hàng căn cứ vào các sản phẩm mà khách hàng khác đã mua trước đó.Khi dự đốn giá trị các lá phiếu, nếu User a có tập lá phiếu lớn, có thể có rất nhiều User khác tương đồng với a nhưng độ tương đồng nhỏ. Việc gộptất cả các User tương đồng để tính tốn trong phương trình dự đốn có thể cho kết quả dự đốn kém chính xác hơn so với chỉ thực hiện trên một số User cóđộ tương đồng lớn. Để giải quyết vấn đề này chúng ta có thể giới hạn trọng số giữa các User, chỉ những User có trọng số lớn hơn giới hạn mới gộp vào trongphương trình dự đốn. Có thể chỉ dự đốn trong một tốp k User tương tự.Trong cơng thức 5 tập Item j là những Item mà cả hai User a và i cùng bỏ phiếu. Nếu khơng có Item chung trong tập lá phiếu của a và i thì,wa i= 0 theo mặc định. Như vậy phương pháp láng giềng gần nhất có một hạn chế tiềm tàng. Khi sự giao nhau của hai tậpalvàilnhỏ, trọng số tính tốn dựa trên số lượng ít Item, do vậy khi áp dụng vào phương trình dự đốnsẽ cung cấp dự đoán thiếu tin cậy. Để giải quyết vấn đề này chúng ta có thể mặc định những lá phiếu trên những Item đại chúng mà cả a và i đều không bỏphiếu. Việc mặc định những lá phiếu này bản chất là tự điền giá trị và trong dữ liệu còn thiếu.Một cơng thức tính trọng số khác cũng được đề xuất:31, ,a,i 22 ,,wa ia j i jj a ki k kkv vv v∈ ∈=∑ ∑∑l l9Theo công thức 9 dễ thấy giá trị trọng số,wa inằm trong khoảng từ 0 đến 1 0=,wa i=1. So với công thức trọng số 5, trong công thức này trọng số có xu hướng ít bị ảnh hưởng của hai tập lá phiếu của User a và i. Công thức nàycó thể dùng để tính tốn trọng số trong trường hợp hai User có ít điểm chung. Cụ thể nếu a chỉ bỏ phiếu trên 2 Item, một User i bỏ phiếu trên tất cả các Itemvà giá trị lá phiếu của a và i tương đồng nhau trên 2 Item kia thì trọng số giữa a và i được xem như 1 mặc dù a và i có rất ít điểm chung. Trên thực tế nếu ibỏ phiếu trên nhiều Item mà a khơng có thì trọng số của a và i cũng giảm dần theo số Item a khơng bỏ phiếu.

2.2.1.3 Xếp nhóm

Xem Thêm

Tài liệu liên quan

• Khai phá dữ liệu trong mô hình thương mại điện tử
  • 55
  • 1,070
  • 12

Tải bản đầy đủ (.pdf) (55 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(585.2 KB) - Khai phá dữ liệu trong mô hình thương mại điện tử-55 (trang) Tải bản đầy đủ ngay ×