Luận văn Nghiên cứu, xây dựng hệ thống lập kế hoạch du lịch dựa trên hệ gợi ý

c tính chứa đựng tập hợp hữu hạn những giá trị phần tử. Ví dụ cho lớp đặc tính này có thể thấy trong trường hợp khách sạn kể trên, khi “địa điểm” có thể thuộc {Hà Nội, Đà Nẵng, Sài Gòn}. Trong trường hợp những đặc tính với giá trị có dạng biểu tượng, khác với hai đặc tính trước đó, mối tương quan về giá trị không tồn tại. Để có thể tính toán khoảng cách giữa những đặc tính dạng biểu tượng, những đặc tính này có thể được chuyển đổi sang dạng những đặc tính dưới dạng số thực hay có hữu hạn những phần tử dạng số nguyên. Cách thứ hai để tính toán khoảng cách là áp dụng những hệ thức được thiết kế riêng cho những đặc tính dạng biểu tượng. Chi tiết về những hệ thức tính khoảng cách sẽ được trình bày trong mục 2.7. Cuối cùng, với mỗi không gian sản phẩm X = Xi , những khái niệm thành phần có thể được ký hiệu và mô tả như sau: - Tập CX ⊂ X : Tập hợp những danh mục sản phẩm cùng loại X. - x1, x2,., xm , (m = |CX|): Được coi như những sản phẩm phần tử thuộc tập danh mục CX. - xj = (x1j, , xnj): Là tập những giá trị đại diện cho những đặc tính của véc-tơ sản phẩm xj ∈ X. - Với điều kiện Xi là đặc tính có giá trị dạng số (hữu hạn nguyên hoặc thực), CX là danh mục sản phẩm cùng loại X, khoảng những giá trị khả dị cho đặc tính Xi trong danh mục sản phẩm CX có thể được ký hiệu như sau: rangeCX(Xi) = (max x∈ CX{ xi} - min x∈ CX{ xi}) (1.1) 2.2.1. Cấu trúc của một case Trong mục này, những khái niệm chính về cấu trúc của một tình huống tour sẽ được trình bày dưới dạng biểu diễn toán học và khai triển dưới dạng một văn bản XML. Dạng biểu diễn này sẽ được dùng để tính toán mức độ tương đồng giữa các case. 2.2.1.1. Biểu diễn toán học Tập hợp những tình huống tour có thể được hiểu theo khái niệm một không gian tình huống (case space) CB. Trong đó, một tình huống tour có thể được cấu tạo từ bốn thành phần riêng biệt: CB = TW x TB x U x R (1.2) Những thành phần này bao gồm: travelWish (TW), travelBag (TB), userPofile (U), và reward (R). Trong đó, từng thành phần lần lượt thuộc về một kiểu không gian nhất định. Ví dụ, với c = (tw, tb, u, r) ϵ CB, type (tw) = TW. Bên cạnh đó, từng thành phần của không gian CB có thể được tạo nên từ những thành phần nhỏ hơn. Điểm khác của một không gian tình huống là yếu tố chiều thời gian (temporal dimension). Yếu tố này tồn tại khi một tình huống tour được xây dựng thông qua quá trình tương tác giữa người dùng và hệ thống. Vì vậy, một tình huống trong không gian CB luôn luôn được coi như một “ảnh chụp” có cấu trúc về một quá trình tương tác người-máy trong một khoảng thời gian nhất định. Hình 2.2. Minh họa một case Nhìn vào hình 1.4, một tình huống tour được biểu thị dưới cấu trúc dạng cây. Gốc của cây đại diện cho tình huống tuor hiện tại. Các nhánh nhỏ hơn đại diện cho từng thành phần trong một tình huống tour. Từng thành phần này tiếp theo được cấu thành từ những phần nhỏ hơn được biểu diễn dưới dạng một véc-tơ đặc tính. Từng thành phần cấu thành một tình huống tuor được mô tả như sau. TB (TravelBag): Có thể được coi như một giỏ hàng ảo tập hợp những thành phần tour được người dùng chọn lựa trong quá trình tương tác với hệ thống. TB có cấu trúc dữ liệu phức tạp, được cấu thành từ những phần tử nối tiếp thuộc nhiểu không gian khác nhau. TB = B x Seq(X1) x x Seq(X3) (1.3) Trong biểu thức (1.3), B, X1, , X3 là những không gian véc-tơ, với X1,.., X3 là những không gian thành phần tuor tương ứng với điểm đến (location), điểm nghỉ chân (accomodation), và thắng cảnh (attractions). B là không gian mô tả những đặc điểm yêu cầu chung nhất của một TB từ phía người dùng. Những đặc tính này có thể là tổng chi phí của một tour TB (cost), loại hình nhà nghỉ (accomodation type), khoảng thời gian du lịch (travel duration) hay nhóm hành khách (travel party). Một trong những đặc điểm này có thể trùng với đặc điểm của một thành phần trong tour. Ví dụ về loại hình nhà nghỉ là một đặc tính xác định nơi nghỉ chân (accommodation) của du khách có thể là khách sạn hay căn hộ. Các thành phần Seq (X1), , Seq(X3) mô tả những chuỗi các đặc tính thuộc cùng một không gian. Vì vậy, một TravelBag có thể chứa nhiều thành phần thuộc cùng một kiểu. Ví dụ như một travelbag được diễn tả bằng hai thành phần tb1, tb2 như hình 1.4. Với mỗi thành phần trong một travelbag có thể được phân chia theo cấp thành phần nhỏ hơn, biểu thức biểu diễn một travelbag trở thành: tb = (b, [x1,1, , x1,j1], , [x3,1, , x3,j3]) với mỗi xi,j = (x11,1, , xni,j). Trong hình 1.4, ta có: tb = (1000, couple), [(Hanoi, historic), (New Sun, 120, 23 Hang Bai), ϕ,ϕ] Với những đặc điểm chung b = (1000, couple). Trong ví dụ này, những đặc điểm chung được giả định gồm có chi phí (budget) dành cho chuyến đi của du khách và loại hình du khách (travel party). Những đặc tính tiếp theo lần lượt mô tả điểm đến tb1 = (Hanoi, historic) (với giả định điểm đến được mô tả bởi hai đặc điểm chính là tên (location-name) và loại hình (location-type)), nơi nghỉ chân tb2 = (New Sun, 120, 23 Hang Bai) (với giả định các đặc điểm mô tả một địa điểm nghỉ chân gồm có tên, giá thuê/đêm, địa chỉ). Trong quá trình người dùng tương tác với hệ thống, người dùng có thể tiếp tục chọn và thêm một địa danh thắng cảnh sẽ tham quan vào trong túi du lịch ảo (travel bag) của mình. Thắng cảnh này có thể gồm những thông tin về tên, địa chỉ, giá vé, loại hình,.. Ví dụ tb3 = (Van Mieu, Quoc Tu Giam St, historic). Như vậy túi du lịch ảo đại diện cho các thành phần của một tour người dùng lựa chọn sẽ được mô tả như sau: tb = (1000, couple), [(Hanoi, historic), (New Sun, 120, 23 Hang Bai), (Van Mieu, Quoc Tu Giam St, historic), ϕ] TW (Travel Wish): Biểu thị mong muốn, yêu cầu về một tour du lịch từ phía người dùng. TW có cấu trúc dữ liệu phức tạp, được diễn tả như một tập hợp những truy vấn (queries) về các thành phần trong một tour, có cấu trúc giống với TravelBag. Một TW có thể được biểu diễn như sau: TW = Q(B) x Seq(Q(X1)) x x Seq(Q(X3)) (1.4) Trong đó, các thành phần trong một TW có cấu trúc tương tự với các thành phần tạo nên một TravelBag. Q (B): truy vấn chứa những đặc điểm chung của một tour. Seq (Q(Xi)): chuỗi những truy vấn về từng loại sản phẩm có trong tour, ví dụ, Seq(Q(X1)) là chuỗi truy vấn biểu thị mong muốn của người dùng về điểm đến (location) cho chuyến du lịch. Bên cạnh đó, một TB có thể có nhiều sản phẩm thuộc cùng loại, vì vậy, mỗi sự lựa chọn sẽ tương ứng với mỗi truy vấn khác nhau. Một ví dụ về biểu diễn chuỗi truy vấn TW có thể có dạng như sau với: Q (B) = (budget < 2000) ∧ (party = couple): Truy vấn với yêu cầu chung về tour với điều kiện chi phí cho phép nhỏ hơn 1000$, và dành cho một người đi du lịch. Seq(Q(X1)) = Seq(Q(accommodation)) = (location = Ha Noi) ∧ (cost < 150) ∧ (position = center): Truy vấn với yêu cầu về chỗ ở, điều kiện là địa điểm tại Hà Nội, vị trí trung tâm và giá thuê nhỏ hơn 150$/đêm. Seq(Q(X2)) = Seq(Q(attraction)) = (attraction-type = historic) ∧ (date = 10/02/2009), (attraction-type = entertainment): Tập hợp hai truy vấn về địa điểm thắng cảnh người dùng muốn đến. Truy vấn đầu tiên là yêu cầu về thắng cảnh mang tính lịch sử và ngày tham gia là 10/02/2009. Truy vấn thư hai là yêu cầu về thắng cảnh mang tính giải trí. Như vậy: TW = ((budget < 2000) ∧ (party = couple)) x ((location = Ha Noi) ∧ (cost < 150) ∧ (position = center)) x (attraction-type = historic) ∧ ((date = 10.02.2009), (attraction-type = entertainment)) U: Thông tin về người dùng hệ thống được biểu diễn dưới dạng một véc-tơ đặc tính trong không gian giống với không gian sản phẩm X có dạng U = ∏ni=1 Ui. Trong biểu đồ 3, một véc-tơ có thể được biểu diễn với ba đặc điểm của người dùng như tên, tuổi, giới tính: U = (name = Nam) ∧ (age = 20) ∧ (gender = male) (1.5) R: Đánh giá về một tour đã được xây dựng và tham gia từ phía người dùng. Cấu trúc đánh giá giống với cấu trúc của một travelbag đại diện cho một tour. Đánh giá bao gồm đánh giá chung cho toàn bộ tour du lịch, đồng thời với từng thành phần trong tour. Một đánh giá là một tập con hữu hạn các phần từ của tập số nguyên. Cấu trúc của một đánh giá có thể có dạng sau: R = RB x Seq(RX1) x x Seq(RX3) (1.6) Trong đó, RB = RX1 = .. = RX4 = {1, 2, 3, 4, 5}. Ví dụ, một tour du lịch có thể được đánh giá bởi điểm số như sau r = {4, [5], [4], ∅}. Các điểm số đánh giá lần lượt tương ứng với toàn bộ tour được đánh giá với điểm số 4/5. Từng thành phần được đánh giá lần lượt là điểm đến (5/5), nơi nghỉ chân (4/5), thắng cảnh (3/5). Điểm số 3/5 được coi như điểm đánh giá mặc định, được áp dụng cho những thành phần tour không được đánh giá bởi người dùng. Giả thiết này được áp dụng cho những trường hợp không có điểm đánh giá bởi vì điểm đánh giá 3/5 là trị số trung gian, nằm giữa những điểm đánh giá tích cực (4/5, 5/5) và điểm đánh giá tiêu cực (1/5, 2/5). 2.2.1.2. Đặc tả XML Đây là cấu trúc của một tình huống tour và được khai triển dưới dạng XML như sau: couple 0 2000 Ha Noi hotel 0 150 center 1000 couple Ha Noi historic New Sun 120 23 Hang Bai Nam 20 male Trong đặc tả XML trên, người dùng tên Nam, 20 tuổi, mong muốn được đi du lịch cùng người thân tại Hà Nội với chi phí tối đa cho phép là 2000$, muốn tìm kiếm một phòng đôi khách sạn ở vị trí trung tâm với giá thuê tối đa 150$/đêm. Nam đã thêm Hà Nội là điểm đến, với khách sạn New Sun ở địa chỉ 23 Hàng Bài vào tour du lịch của mình. 2.2.2. Độ tương đồng và xếp hạng các item Khái niệm “tương đồng” (similarity) [3] được sử dụng trong tính toán khoảng cách giữa hai đối tượng. Những đối tượng này có thể là cùng loại hoặc khác loại. Ví dụ, độ tương đồng biểu thị mức độ gần gũi giữa một người dùng tới một nhóm người dùng, hay một sản phẩm tới danh mục những sản phẩm. Trong trường hợp của hệ tư vấn, độ tương đồng mô tả khoảng cách giữa các thành phần tour cũng như các tình huống tour sẽ được tính toán thông qua các hệ thức tính khoảng cách. Các hệ thức này sẽ được dùng trong tính toán độ tương đồng cũng như xếp hạng sản phẩm dựa trên mức độ tương đồng. Các khái niệm về tìm kiếm sản phẩm tương tự cũng như sắp xếp sả phẩm sẽ được trình bày trong mục này. Các hệ thức khoảng cách sẽ được trình bày trong mục 1.2.7. 2.2.2.1. Thu thập và xếp hạng sản phẩm Với X = ∏ni=1 Xi là không gian các thành phần tour (sản phẩm), một hệ thức khoảng cách được định nghĩa là một hàm có giá trị dương ứng với từng cặp sản phẩm. Có nhiều loại hệ thức khoảng cách đã được nghiên cứu và sử dụng, trong khuôn khổ giải thuật CBR dùng trong hệ tư vấn, những hệ thức có dạng sau sẽ được sử dụng. d(x,y) = f(w1(x) * d1(x1, y1), , wn(x) * dn(xn, yn)) f : Rn à R+ (1.8) Với x, y ϵ X, 0 < wi(x) < 1 là trọng số của đặc điểm thứ i, f là hàm đơn điệu tăng (monotone increasing function), di(xi, yi) là hệ thức khoảng cách định nghĩa theo loại của đặc tính thứ i. Bên cạnh đó, những hệ thức di còn được gọi như những “phép đo độ tương đồng cục bộ (local similarity measures)” trong thuật ngữ CBR. Yếu tố cục bộ xảy ra trong trường hợp những trọng số trong hàm d (x, y) là những trị số thay đổi, phụ thuộc vào từng điểm đặc tính. Trong thực tế, di là những giá trị biểu thị độ bất tương đồng. Ví dụ, hai đặc tính có khoảng cách lớn sẽ dẫn đến giá trị tương đồng nhỏ giữa hai đặc tính. Từng giá trị khoảng cách cục bộ sẽ được kiểm soát bởi hàm tổ hợp tổng quát f, tổ hợp những giá trị khoảng cách cục bộ và đưa ra kết quả khoảng cách là một số thực dương R+. Ví dụ, một trong những hệ thức khoảng cách là hệ thức khoảng cách không đồng nhất Euclid – Overlap (Heterogeneous Euclid – Overlap Metric). heom x, y=1i=1nwii=1nwidi(xi, yi)2 (1.9) với: dxi, yi=1 nếu xi hay yi chưa biết overlapxi, yi nếu đặc tính thứ i có dạng ký tự (symbolic) |xi-yi|rangei nếu đặc tính thứ i có dạng số nguyên hoặc số thực hữu hạn (2.7) (1.10) Và hàm overlap(xi, yi) = 1 nếu xi ≠ yi và 0 với xi = yi. Hệ số chuẩn hóa i=1nwi được dùng để so sánh khoảng cách giữa những sản phẩm thuộc các không gian khác nhau. Độ tương đồng được định nghĩa là nghịch đảo của khoảng cách: Sim(x,y) = e(-d(x,y)) (1.11) Với hệ thức khoảng cách được định nghĩa như trên, các sản phẩm tương tự có thể được tìm kiếm và sắp xếp dựa trên mức độ tương đồng. 2.2.2.1.1. Tìm sản phẩm tương tự Với A ∈ X là một không gian con của tập không gian sản phẩm tour và p ∈ X là sản phẩm được xét tìm các sản phẩm tương tự, kNNd(p, A) là tập những láng giềng gần nhất (sản phẩm có độ tương đồng cao nhất với sản phẩm được xét) với p trong tập sản phẩm A, sử dụng hệ thức khoảng cách d. Tập láng giềng này được định nghĩa là một tập hợp con của A. Hằng số k xác định số lượng láng giềng gần nhất được xác định sử dụng khoảng cách d. Vì vậy, có thể nói việc tìm kiếm sản phẩm tương tự là quá trình chọn lọc những sản phẩm x1, x2, , xk tương đồng nhất với sản phẩm p trong một tập hợp không gian các sản phẩm cho trước. Các sản phẩm tương tự kNNd(p, A) cũng sẽ được sắp xếp dựa theo giảm dần mức độ tương đồng (tăng dần về khoảng cách d(p, xi)) sau quá trình tìm kiếm. Quá trình tìm kiếm tập những sản phẩm tương tự được thực hiện bởi thuật toán k Nearest Neighbor - kNNd(p,A,k) Tham số: Hệ thức khoảng cách d, sản phẩm xét tìm kiếm p, tập sản phẩm A Kết quả: Trả về tập k sản phẩm láng giềng gần nhất với p trong A, sắp xếp theo trình tự khoảng cách giảm dần 1 NN := danh sách có độ dài k từng cặp cùng loại (nil,∞) 2 for each a in A 3 d:= d(p,a) 4 if d < NN[1,2] 5 NN[1,1] := a, NN[1,2] = d, i := 1 6 while (i < k) AND (d < NN[i + 1, 2]) 7 NN[i,1] := NN[i + 1,1], NN[i,2] := NN[i + 1,2] 8 NN[i+1,1] := a, NN[i + 1,2] := d 9 i = i + 1 10 return NN Dựa vào thuật toán được trình bày ở trên, hàm tìm kiếm những sản phẩm tương tự có thể được thực hiện như sau: Giả thiết hệ thống đang gợi ý một điểm đến và người dùng mong muốn tìm kiếm những địa điểm giống với điểm đến đang được gợi ý, thỏa mãn truy vấn Q = C1∩ C2∩ ∩ Cm với Ci là những yêu cầu (constraints) về đặc tính cụ thể của một điểm đến. Với điều kiện truy vấn Q, A là tập hợp những điểm đến thỏa mãn Q, p là điểm đến đang được tư vấn, hàm tìm kiếm kNNd (p,A,5) sẽ tìm kiếm và đưa ra kết quả 5 điểm đến tương đồng nhất với điểm đến đang được tư vấn hiện tại. 2.2.2.1.2. Sắp xếp kết quả tìm kiếm Sau khi các sản phẩm tương tự được tìm kiếm, hệ thống sẽ sắp xếp kết quả tìm kiếm dựa trên điểm đánh giá độ tương đồng (similarity-based scores). Tại bước này, hai tập được xét là X S và R. Trong đó, S = {x1, x2, ..., xm} là tập những sản phẩm cần được sắp xếp và R là tập sản phẩm tham chiếu (reference set) được dùng để tính điểm tương đồng cho từng thành phần trong tập S. Tập sản phẩm tham khảo được trích chọn từ tập những tình huống tour giống với tình huống tour hiện tại. Việc tìm kiếm những tình huống tour tương đồng sẽ được trình bày trong mục 2.8 của chương. Tập sản phẩm được sắp xếp sử dụng khoảng cách d và tập tham khảo R được ký hiệu là: SS(R,d) = [xi1, , xim] với d(xij, R) ≥ d(xik, R) (i <k). Khoảng cách d(x, R) được định nghĩa là khoảng cách nhỏ nhất từ x đến các sản phẩm r ∈ R. d(x, R) = minr∈R { d(x, r) } (1.12) Với định nghĩa này, sản phẩm xi = xik được xếp hạng cao hơn nếu sản phẩm đó gần hơn (có khoảng cách nhỏ hơn) đối với những sản phẩm thuộc tập tham khảo. Để có thể sắp xếp kết quả tìm kiếm dựa trên khoảng cách giữa các sản phẩm (hàm Sort(d, S, R)), hệ thống khởi tạo một chuỗi bộ ba đối tượng gồm sản phẩm s thuộc S, khoảng cách từ s tới tập R, và phần tử thuộc R gần nhất với s. Tương ứng với mỗi sản phẩm s thuộc S, sản phẩm láng giềng gần nhất với s, r = NN[1,1] thuộc R và khoảng cách d = d(s,r) = NN[1,2] được tính toán. Tương tự với thuật toán kNN, danh sách SS những sản phẩm được sắp xếp và bộ ba đối tượng (s,d,r) được chuyển tiếp sau một bộ ba khác (s’,d’,r’) với d > d’. Ví dụ về thuật toán sắp xếp trong trường hợp sắp xếp điểm đến sau quá trình tìm kiếm, dựa vào tình huống tour hiện tại (bao gồm yêu cầu của người dùng, những sản phẩm khả dĩ trong travelbag, thông tin của người dùng), từ yêu cầu cụ thể về điểm đến, tập những điểm đến S = {loc1, loc2, loc3} được tìm kiếm và chọn lọc từ danh mục sản phẩm. Cuối cùng, các điểm đến sẽ được sắp xếp dựa trên mức độ tương đồng của từng điểm đến với điểm đến tương ứng trong tập tham khảo những tình huống tour tương tự R. Để trả về kết quả các điểm đến được sắp xếp, hàm Sortd(S, R) được gọi với d là khoảng cách giữa các điểm đến. Sort(d,S,R) Tham số: khoảng cách d, tập sản phẩm S cần được sắp xếp, tập sản phẩm tham khảo R Kết quả: chuỗi sản phẩm được sắp xếp SS[i,j] (j = 1,2,3) 1 SS := danh sách các phần tử s, d, r (đọ dài |S|, kiểu (nil, , nil)) = (SS[i,1], SS[i,2], SS[i,3]) 2 for each s in S 3 NN := kNN(p, R, 1) 4 SS[1,1] := s, SS[1,2] := NN[1,2] 5 SS[1,3] = NN[1,1], i := 1 6 while (i < |S|) AND d < SS[i+1,2] 7 SS[i,j] := SS[i+1,j] for all j = 1,2,3 8 SS[i+1,1] := s, SS[i+2,2] := d 9 SS[i+1,3] := NN[1,1], i := i + 1 10 return SS 2.2.2.2. Các hệ thức tính khoảng cách Độ chính xác của kết quả gợi ý phụ thuộc chủ yếu vào cách tính khoảng cách giữa các phần tử. Các hệ thức tính khoảng cách phổ biến nhất có thể thấy như khoảng Euclid hay còn gọi là Minkowsky dx,y= i=1n(di(xi,yi))1r (1.13) Trong đó dixi,yi=|xi- yi| là khoảng cách Euclid với r thường mang giá trị nguyên dương. Vời hệ thức này, yếu tố khoảng cách mô tả sự bất tương đồng giữa hai đối tượng, với khoảng cách càng lớn, độ tương đồng càng nhỏ. Vì vậy, hàm tương đồng là hàm nghịch đảo của hàm tính khoảng cách, ví dụ: Simx,y= 1d(x,y) hay Simx,y= e-d(x,y) (1.14) Bên cạnh đó, việc tính toán mức độ tương đồng cũng có thể được tiến hành bằng cách sử dụng các phương pháp thống kê. Trong đó, phương pháp nổi tiếng nhất là phương sai Pearson (Pearson Corelation) Simx,y= i=1nxi- λiyi- λii=1nxi- λi2i=1nyi- λi2 (2.12) Với λi là giá trị trung bình của đặc tính thứ i trong cơ sở dữ liệu tình huống (case base). Trong trường hợp này, phương sai Pearson trực tiếp đưa ra kết quả mô tả mức độ tương đồng, như vậy Simx,y=d(x,y). Tuy nhiện, phương sai Pearson hay khoảng cách Euclid chỉ đúng trong trường hợp các đặc tính của phần tử sản phẩm được biểu diễn dưới dạng giá trị số (numeric features). Trong trường hợp sản phẩm được biểu diễn dưới dạng biểu tượng ký tự (symbolic features), khoảng cách chéo (overlap distance) được sử dụng như phương pháp để tính toán khoảng cách giữa các đặc tính dạng biểu tượng. overlapxi,yi= 0 if xi= yi1 otherwise (1.15) Bên cạnh phương pháp khoảng cách chéo, một phương pháp khác được sử dụng rộng rãi là phương pháp VDM (Value Difference Metric). VDM là một phương pháp thống kê cho phép tính toán khoảng cách giữa những đối tượng có đặc tính chỉ có thể được biểu diễn dưới dạng biểu tượng ký tự. Một phiên bản đã được đơn giản hóa của VDM (không có trọng số) có dạng sau: vdmx,y= 1n[c=1C|pcxi- p(c|yi)|2] (1.16) Với: - C là tổng số lớp kết quả trong miền bài toán. - pcxi là xác suất điều kiện để lớp kết quả là C với giá trị thuộc tính i là xi được cho trước. pcxi=# số lần xuất hiện của xi trong lớp c# số lần xuất hiện của xi trong toàn bộ cơ sở dữ liệu tình huống (1.17) Giống như những phương pháp thống kê khác, phương pháp VDM được dùng để giải quyết các bài toàn phân loại (classification problem). Vì vậy, trong trường hợp hệ tư vấn, VDM có thể được dùng trong việc phân tách nhóm đặc trưng thích/không thích của người dùng. Tuy nhiên, VDM không phù hợp với tính toán mức độ tương đồng như đã trình bày, mặc dù trong trường hợp c = 1, tính chất phân loại đã được loại bỏ. 2.2.3. Hệ thức khoảng cách không đồng nhất Trong hệ tư vấn, hệ thức khoảng cách không đồng nhất được định nghĩa là tổ hợp những hệ thức khoảng cách áp dụng cho những đặc tính được biểu diễn dưới dạng số và ký tự. dix,y= 1 nếu xi và yi không biết dsxi,yinếu đặc tính thứ i dưới dạng ký tựdnxi,yi nếu đặc tính thứ i dưới dạng số (1.18) Với ds và dn lần lượt là hệ thức khoảng cách áp dụng cho đặc tính dạng ký tự và dạng số. Trong trường hợp đặc tính được xét có giá trị null, khoảng cách được mặc định có giá trị là 1 với giả sử hai đặc tính không có mối liên hệ khi không tồn tại giá trị. Từ định nghĩa khoảng cách như trên, với sự lựa chọn khác nhau của ds và dn sẽ dẫn đến các hệ thức không đồng nhất khác nhau. Trong đó, hệ thức nổi tiếng nhất là hệ thức HEOM (Heterogeneous Euclidean-Overlap Metric) [2] sử dụng heomxi,yi= 1 nếu xi và yi không biết overlapxi,yi nếu đặc tính thứ i dưới dạng ký tự|xi- yi|rangei nếu đặc tính thứ i dưới dạng số (1.19) Một ví dụ khác là hệ thức HVDM (Heterogeneous Value Difference Metric) [3] sử dụng hvdmxi,yi= 1 nếu xi và yi không biết vdmxi,yi nếu đặc tính thứ i dưới dạng ký tự|xi- yi|rangei nếu đặc tính thứ i dưới dạng số (1.20) Hai hệ thức HEOM và HVDM [3] có thể tiếp tục được tùy biến bằng cách sử dụng những kỹ thuật chuẩn hóa hay rời rạc hóa khác nhau. Như vậy, bằng cách tùy biến các tổ hợp những hệ thức khoảng cách với các kỹ thuật chuẩn hóa hay rời rạc hóa, ta có thể có được những hệ thức khoảng cách không đồng nhất khác nhau. Trong phạm vi hệ tư vấn, những hệ thức khoảng cách không đồng nhất được phân tích là những hệ thức sau: HEOM(x,y) = i=1n(heom(xi.yi))21/2 (1.21) HVDM(x,y) = i=1n(hvdm(xi.yi))21/2 (1.22) Hệ thức tương đồng phương sai Pearson [3] CORR(x,y) = i=1n(xi- λi)(yi- λi)i=1n(xi- λi)2i=1n(yi- λi)2 (1.23) Với xi= xi nếu đặc tính thứ i có dạng số pxi nếu đặc tính thứ i có dạng ký tự pxi=# số lần xuất hiện của xi trong lớp c# số lần xuất hiện của xi trong toàn bộ cơ sở dữ liệu tình huống là xác suất đặc tính thứ i có giá trị xi. Xác suất pxi được dùng để chuyển đổi những giá trị đặc tính dạng ký tự sang dạng số dùng trong phương sai Pearson. Bên cạnh sử dụng giá trị xác suất, các kỹ thuật khác như gán những giá trị dạng ký tự tương ứng với những giá trị dạng số đã được áp dụng. Tuy nhiên, cách làm này không giải quyết được vấn đề về thứ tự. Ngược lại, vấn đề này có thể được giải quyết khi sử dụng giá trị xác suất. Ví dụ, nếu là một đặc tính chỉ nhận giá trị đúng (true) hoặc sai (false), và người dùng nhận được nhiều giá trị đúng hơn giá trị sai về đặc tính này. Điều này dẫn đến p(true) > p(false). Dựa vào kết quả định tính này, ta có thể kết luận true > false, thay vì false > true. Các hệ thức khoảng cách đã trình bày đều không sử dụng trọng số như đã đề cập. Các giá trị trọng số, phụ thuộc vào thông tin người dùng, yêu cầu truy vấn, sẽ được đề cập sâu hơn ở các mục sau. 2.2.4. Độ tương đồng giữa hai case Độ tương đồng giữa các tình huống tour là chủ đề trung tâm có vai trò quan trọng trong hệ tư vấn. Yếu tố tương đồng này có vai trò tiên quyết trong việc tìm kiếm những tình huống tour tương tự và cũng là bước đầu tiên trong bất kì một hệ thống lập luận tình huống CBR nào. Trong điều kiện của hệt tư vấn, việc tìm kiếm những tình huống tương tự gặp nhiều khó khăn hơn vì cầu trúc phức tạp của một tình huống tour (mục 1.2.5). Một tình huống tour được tạo nên từ những thành phần đơn vị (TW, TB, U, R ) và những thành phần này tiếp tục bao gồm những thành phần nhỏ hơn. Những thành phần này hợp thành cấu trúc dạng cây (tree-based model structure) của một tình huống tour. Dựa trên cấu trúc được mô tả ở trên, hai tình huống tour được xem là tương đồng nếu những thành phần cấu thành nên tình huống tour đó cũng tương đồng với nhau. Điều này có nghĩa với c = (tw,tb,u,r) và c’ = (tw’,tb’,u’,r’) là hai tình huống tour, độ tương đồng Sim(c,c’) sẽ được tính toán dựa trên các độ tương đồng thành phần Sim(tw,tw’),,Sim(r,r’). Áp dụng cách tính này theo phương pháp hồi qui, ta có thể nhận thấy những độ tương đồng thành phần có thể tiếp tục được tính toán dựa trên độ tương đồng của những thành phần nhỏ hơn. Với cấu trúc dạng cây của một tình huống tour, độ tương đồng sẽ được tính dựa trên độ tương đồng của lá. Lá trong cấu trúc dạng cây của tình huống tour được xem như những sản phẩm tách biệt, là những phần tử trong những không gian véc-tơ đã được định nghĩa sẵn (mục 1.2.4). Với những thành phần tour có cùng kiểu, độ tương đồng mang giá trị khác rỗng với tw tương đồng với tw’. Áp dụng khái niệm độ tương đồng giữa các tình huống, ta có thể giải quyết bài toán gợi ý dựa trên nguyên lý sau: “Nếu hai tình huống là tương đồng, thành phần trong tình huống trước có thể được tái sử dụng làm lời giải cho tình huống sau”. Trong các bài toán lập luận tình huống truyền thống, khái niệm thành phần có thể được hiểu là thành phần trong qui trình lập luận như mô tả vấn đề. Trong khuôn khổ hệ tư vấn, các thành phần được khái quát lên đối với tất cả những thành phần trong một tình huống tour. Như vậy, ta có thể đoán biết được những sản phẩm cần gợi ý dựa trên TB của những tình huống tour tương tự đã xảy ra. Những tình huống tour tương tự đã được đề cập ở phần trước dưới tên “tập tham khảo”. Giả sử c ∈ CB là một tình huống có dạng đồ thị (graph) Gc(Vc,Ec) (một cây), ta ký hiệu Vc là những đỉnh (vertices) bao gồm những thành phần của tình huống c, và Ec là những cạnh (edges). Một cạnh (p,q) tồn tại trong trường hợp thành phần q là thành phần con của p. Như vậy, ta có thể thấy trong trường hợp một tình huống tour c = (tw,tb,u,r), ta có (c,tw) ∈ Ec. Tương tự, với tw = (q1,[q11,,q1k1],, [q31,,q3k1]) ta có