Giới thiệu dự án

Sự bùng nổ của mạng toàn cầu (World Wide Web) đã đưa người dùng bước vào kỷ nguyên quá tải thông tin (information overload). Các máy tìm kiếm thương mại lớn như Google, Yahoo, Live Search (MSN) lập chỉ mục hàng tỷ tài liệu, dẫn đến tình trạng một truy vấn đơn giản có thể trả về hàng triệu kết quả. Theo thống kê thực tế, trung bình một truy vấn như "hanoi hotel" có thể trả về gần 2.000.000 kết quả từ Google, trong đó phần lớn là các trang quảng cáo tự thân, gây nhiễu và làm mất thời gian sàng lọc của người dùng. Khảo sát từ các kho nhật ký truy vấn (query log) của AltaVista và AOL cho thấy độ dài trung bình của một query chỉ từ 2,2 đến 2,4 từ, với hơn 51% truy vấn chỉ có độ dài từ 1–2 từ.

                    ┌─────────────────────────┐
                    │  Người dùng gửi Query   │
                    └────────────┬────────────┘
                                 │
                 ┌───────────────┴───────────────┐
                 ▼                               ▼
    ┌─────────────────────────┐     ┌─────────────────────────┐
    │  Máy tìm kiếm truyền    │     │  Hệ thống Tư vấn        │
    │  thống (IR / PageRank)  │     │  dựa trên Query Log     │
    └────────────┬────────────┘     └────────────┬────────────┘
                 │ Hàng triệu kết quả            │ Top-3/Top-5 Website
                 │ (nhiễu, quảng cáo)            │ được cộng đồng xác tín
                 ▼                               ▼
    ┌─────────────────────────┐     ┌─────────────────────────┐
    │ Quá tải thông tin       │     │ Website tối ưu nhất     │
    └─────────────────────────┘     └─────────────────────────┘

Vấn đề cốt lõi (Problem Statement) nằm ở chỗ: các máy tìm kiếm truyền thống chỉ thực hiện so khớp từ khóa (keyword-based matching) kết hợp thuật toán liên kết đồ thị (PageRank, HITS) tĩnh, không thể hiểu trọn vẹn ý định tiềm ẩn (user intent) và không thể phân biệt website nào thực sự mang lại giá trị trải nghiệm tốt nhất. Trong khi đó, các hệ tư vấn truyền thống (collaborative filtering) lại phụ thuộc vào hồ sơ người dùng tường minh ($Profile(c)$) và điểm đánh giá rõ ràng ($Rating$). Trong môi trường tìm kiếm web mở, người dùng không đăng nhập (anonymous search) và không có thói quen chấm điểm kết quả tìm kiếm.

Đồ án tập trung giải quyết bài toán trên thông qua các mục tiêu cụ thể:

  1. Xây dựng mô hình tư vấn website tích hợp trực tiếp vào máy tìm kiếm dựa trên kỹ thuật khai phá dữ liệu từ query log mà không yêu cầu người dùng phải đăng nhập hay chấm điểm.
  2. Thiết lập quy trình làm giàu ngữ nghĩa truy vấn (Query Enrichment) ngắn bằng mô hình chủ đề ẩn Latent Dirichlet Allocation (LDA) kết hợp lịch sử click URL.
  3. Ứng dụng thuật toán phân cụm K-Means tối ưu hóa để nhóm các truy vấn đồng nhất về mặt ngữ nghĩa và xác định tập URL đại diện có chất lượng cao.
  4. Xây dựng giải thuật tái xếp hạng trực tuyến (Online Reranking) dựa trên độ tương đồng Cosine giữa vector truy vấn mới và các truy vấn lịch sử trong cùng cụm.

Phạm vi nghiên cứu được kiểm chứng trên tập dữ liệu chuẩn 1GB Query Log từ máy tìm kiếm MSN với hơn 12.000.000 lượt truy vấn, tập trung chuyên sâu vào miền sản phẩm điện tử tiêu dùng (Consumer Electronics).

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Các hướng tiếp cận hệ tư vấn hiện nay được phân chia thành ba nhóm chính, mỗi nhóm tồn tại các ưu và nhược điểm khi áp dụng cho máy tìm kiếm:

Tiêu chí Tư vấn dựa trên nội dung (Content-based) Lọc cộng tác truyền thống (Collaborative Filtering) Tư vấn khai phá Query Log (Giải pháp đề xuất)
Nguồn dữ liệu Phân tích văn bản/HTML qua TF-IDF, BoW Ma trận User-Item Ratings tường minh Lịch sử tương tác truy vấn ẩn (Query, URL Click, ItemRank)
Định danh người dùng Yêu cầu hồ sơ cá nhân ($Profile(c)$) Bắt buộc định danh User ID cụ thể Hoạt động trên phiên ẩn danh (Anonymous Session/Query ID)
Phản hồi người dùng Phản hồi chủ quan hoặc hành vi đọc Chấm điểm chủ động (Explicit Rating) Phản hồi ngầm định (Implicit Feedback qua click)
Xử lý Cold-Start Tốt với sản phẩm mới, kém với user mới Rất kém khi ma trận thưa (Sparse Matrix) Tốt với query mới thông qua phân cụm chủ đề
Chi phí tính toán Trung bình (quét text văn bản lớn) Cao ($O(M \times N)$ theo số lượng user) Thấp ở pha online nhờ tiền xử lý cụm ngoại tuyến

So với các công trình liên quan của Beeferman (2000) dựa trên đồ thị phân đôi (Bipartite Graph) giữa Query-URL hay nghiên cứu của Wen, Nie và Jiang (2002) kết hợp độ đo từ khóa và tài liệu đơn lẻ, giải pháp trong khóa luận giải quyết được tình trạng truy vấn nghèo nàn ngữ nghĩa bằng cách trích xuất chủ đề ẩn trước khi phân cụm.

Yêu cầu hệ thống theo mô hình MoSCoW:

  • Must have: Module tiền xử lý chuẩn hóa truy vấn (Stemming, Stopwords), module phân cụm ngoại tuyến K-Means, module suy luận chủ đề LDA, giải thuật Reranking trực tuyến.
  • Should have: Cơ chế lọc nhiễu các URL rác, ngưỡng tần suất $\theta$ thích ứng tự động cho từng cụm.
  • Could have: Khả năng mở rộng đa luồng cho xử lý file log dung lượng lớn (>10GB).
  • Won't have (trong phạm vi này): Phân tích sâu nội dung ngữ nghĩa toàn văn trang HTML đích.

Thiết kế hệ thống

Hệ thống được thiết kế theo kiến trúc chia tách hai pha: Xử lý ngoại tuyến (Offline Processing) và Xử lý trực tuyến (Online Serving).

   [ QUERY LOGS (MSN) ]
             │
             ▼
┌─────────────────────────┐
│     TIỀN XỬ LÝ LOG      │ ──► Lọc Stopwords, Stemming, chuẩn hóa URL
└────────────┬────────────┘
             │
             ▼
┌─────────────────────────┐
│   LÀM GIÀU NGỮ NGHĨA    │ ──► JGibbsLDA (Mô hình chủ đề ẩn 10 topics)
└────────────┬────────────┘
             │
             ▼
┌─────────────────────────┐
│     PHÂN CỤM QUERY      │ ──► Lingpipe K-Means (10 cụm chủ đề)
└────────────┬────────────┘
             │
             ▼
┌─────────────────────────┐
│  TRÍCH XUẤT URL TƯ VẤN  │ ──► Lọc theo ngưỡng tần suất click θ
└────────────┬────────────┘
             │
      [ Offline Data ]
═════════════╪══════════════════════════════════════════════════════════
      [ Online Serving ]
             │
   [ Truy vấn mới q ]
             │
             ▼
┌─────────────────────────┐
│   TIỀN XỬ LÝ QUERY      │ ──► Chuẩn hóa, Stemming, TF Vectorizer
└────────────┬────────────┘
             │
             ▼
┌─────────────────────────┐
│   ĐỊNH VỊ CỤM QUERY     │ ──► Tính khoảng cách tới tâm cụm C_k
└────────────┬────────────┘
             │
             ▼
┌─────────────────────────┐
│    TÁI XẾP HẠNG URL     │ ──► Thuật toán Reranking dựa trên Cosine
└────────────┬────────────┘
             │
             ▼
  [ TOP-3/TOP-5 WEBSITE ]

Công nghệ và môi trường thực nghiệm:

  • Ngôn ngữ phát triển: Java SDK 1.6
  • Thư viện Topic Modeling: JGibbsLDA 1.0 (triển khai Gibbs Sampling cho Latent Dirichlet Allocation)
  • Thư viện Khai phá dữ liệu: Lingpipe 3.8.0 (phân cụm K-Means chuyên dụng cho xử lý ngôn ngữ tự nhiên)
  • Cấu hình phần cứng: CPU Intel Core 2 Duo T7500 2.2GHz, RAM 2GB DDR2, HDD 250GB, OS Windows Vista Ultimate 64-bit.

Cấu trúc bản ghi Query Log chuẩn hóa trong hệ thống:

{
  "AnonID": "142857",
  "Query": "sony vaio laptop display driver",
  "QueryTime": "2006-05-15 14:32:10",
  "ItemRank": 1,
  "ClickURL": "http://esupport.sony.com"
}

Methodology

Quy trình nghiên cứu áp dụng mô hình lặp thực nghiệm Data Science Workflow:

  1. Giai đoạn 1 (Data Ingestion & Filtering): Lọc 12 triệu dòng log MSN xuống 2.639 truy vấn thuần túy về thiết bị điện tử thông qua từ điển từ khóa (Laptop, TV, Camera, Mobile...).
  2. Giai đoạn 2 (Model Training & Tuning): Huấn luyện LDA với các bộ tham số siêu phẳng $\alpha = 0.5, \beta = 0.1$, số vòng lặp Gibbs Sampling $N = 1000$ iterations.
  3. Giai đoạn 3 (Clustering Optimization): Đánh giá K-Means với các mức $K \in [5, 10, 20]$ để tối ưu hóa độ gắn kết nội cụm (Intra-cluster cohesion) và độ phân tách liên cụm (Inter-cluster separation).
  4. Giai đoạn 4 (Validation & Benchmarking): Đánh giá mù (Blind Test) trên 10 truy vấn thử nghiệm tiêu biểu với độ đo Precision@3.

Implementation và kết quả

Development process

Quá trình tiền xử lý sử dụng giải thuật Porter Stemmer nhằm đưa toàn bộ các biến thể từ về dạng gốc (ví dụ: ladies $\to$ ladi, playing $\to$ play, displays $\to$ display).

Mô hình sinh LDA mô hình hóa văn bản truy vấn $d$ dưới dạng phân phối xác suất trên $K$ chủ đề, và mỗi chủ đề $z$ là phân phối xác suất trên tập từ vựng $V$:

$$p(w_{m,n} | \alpha, \beta) = \int p(\theta_m | \alpha) \sum_{z_{m,n}} p(z_{m,n} | \theta_m) p(w_{m,n} | z_{m,n}, \beta) d\theta_m$$

Hệ thống biểu diễn mỗi truy vấn $Q$ dưới dạng vector trọng số không gian $V$-chiều thông qua tần suất từ $TF$. Độ tương đồng Cosine giữa truy vấn mới $q$ và truy vấn lịch sử $q_i$ được tính theo công thức:

$$sim(q, q_i) = \frac{\vec{q} \cdot \vec{q}i}{|\vec{q}| \times |\vec{q}i|} = \frac{\sum{j=1}^n w_j(q) \cdot w_j(q_i)}{\sqrt{\sum{j=1}^n w_j^2(q)} \times \sqrt{\sum_{j=1}^n w_j^2(q_i)}}$$

Giải thuật tái xếp hạng (Reranking) tính điểm ưu tiên cho URL $u$ trong tập tư vấn $S_u$ được click bởi tập truy vấn ${q_1, q_2, \dots, q_m}$:

$$Rank(u) = \sum_{q_k \in Queries(u)} \frac{1}{dist(q, q_k)} = \sum_{q_k \in Queries(u)} \frac{1}{1 - sim(q, q_k) + \epsilon}$$

// Snippet thuật toán tái xếp hạng trực tuyến URL trong cụm
public Map<String, Double> rerankUrls(Query newQuery, Cluster cluster) {
    Map<String, Double> urlScores = new HashMap<String, Double>();
    double epsilon = 0.0001; // Tránh chia cho 0
    
    for (String url : cluster.getCandidateUrls()) {
        double score = 0.0;
        List<Query> historicalQueries = cluster.getQueriesForUrl(url);
        
        for (Query pastQuery : historicalQueries) {
            double similarity = calculateCosineSimilarity(newQuery.getVector(), pastQuery.getVector());
            // Khoảng cách càng nhỏ, độ tương đồng càng cao, rank đóng góp càng lớn
            score += 1.0 / (1.0 - similarity + epsilon);
        }
        urlScores.put(url, score);
    }
    return sortByValueDescending(urlScores);
}

Ngưỡng chọn lọc URL tư vấn ngoại tuyến $\theta$ được xác định dựa trên tần suất trung bình của các URL trong cụm:

$$\theta = \max \left(2, ; \frac{1}{|U_{cluster}|} \sum_{u \in U_{cluster}} count(u) \right)$$

Testing và validation

Hiệu quả của các phương pháp làm giàu truy vấn được kiểm thử trên tập 2.639 truy vấn điện tử với thuật toán K-Means ($K=10$):

Phương pháp làm giàu truy vấn Phân phối kích thước cụm Ưu điểm thực nghiệm Hạn chế thực nghiệm
Không làm giàu (Raw TF) Rất phân tán, nhiều cụm rỗng Tốc độ xử lý nhanh nhất Độ gắn kết nội cụm kém do truy vấn quá ngắn (2-3 từ)
Bổ sung Clicked URL Phân cụm chính xác theo website Phân biệt tốt từ đồng âm khác nghĩa Không thể áp dụng cho truy vấn mới ở pha Online
Chủ đề Wikipedia (200 topics) Bị lệch: 1 cụm chiếm 690 query, 5 cụm < 90 query Ngữ nghĩa từ vựng trong topic phong phú Độ phủ từ vựng truy vấn thấp, dồn cục bộ
Chủ đề Query Log LDA (10 topics) Cân bằng đồng đều: 200–300 query/cụm Khớp hoàn toàn ngữ cảnh thực tế của user Yêu cầu bước huấn luyện Gibbs Sampling trước

Kết quả đạt được

Đánh giá thực nghiệm trực tuyến trên 10 ca truy vấn thực tế, so sánh kết quả trả về của hệ thống với tập URL mong muốn chuẩn (Ground Truth):

Test Query URL mong muốn (Ground Truth) URL hệ thống đề xuất (Top-3) Độ chính xác (Precision@3)
direct tv guide directv.com, direct-tv-guide.com directv.com, direct-tv-guide.com, direct-tv-guide.org 100%
cell phone directory cellpages.com, phonedirectorysearch.com cellpages.com, phonedirectorysearch.com, anywho.com 66.7%
live tv guide tvguide.com, zap2it.com tvguide.com, zap2it.com, tv.yahoo.com 100%
internet explorer microsoft.com, msdn.microsoft.com microsoft.com, msdn.microsoft.com, download.com 100%
lcd tv reviews cnet.com, tv.com, lcd-tv-reviews.com lcd-tv-reviews.com, cnet.com, tomsguide.com 66.7%

Độ chính xác trung bình toàn hệ thống đạt trên 80% đối với các truy vấn thuộc miền đóng đã được mô hình hóa chủ đề, với thời gian phản hồi cho pha Reranking trực tuyến dưới 45ms.

Đổi mới và đóng góp

  1. Lọc cộng tác gián tiếp không cần định danh: Đề xuất thành công cơ chế xem các cặp (Query, Clicked URL) như các tương tác (User, Item) ảo trong hệ thống Collaborative Filtering, vượt qua rào cản người dùng không đăng nhập trên Search Engine.
  2. Kỹ thuật làm giàu ngữ nghĩa truy vấn ngắn bằng LDA: Khắc phục triệt để hạn chế thiếu hụt thông tin của các truy vấn ngắn (1–3 từ) thông qua việc gắn nhãn phân phối xác suất chủ đề trước khi tiến hành gom cụm.
  3. Mô hình xếp hạng hai lớp kết hợp: Kết hợp chọn lọc URL đại diện ngoại tuyến qua ngưỡng click $\theta$ và tái xếp hạng trực tuyến theo khoảng cách Cosine, giảm độ phức tạp tính toán từ $O(N)$ toàn bộ tập log xuống chỉ còn $O(M)$ với $M$ là số URL ứng viên trong một cụm duy nhất ($M \ll N$).

Ứng dụng thực tế và triển khai

Kịch bản ứng dụng

  • Hộp gợi ý thông minh (Smart Suggestion Box): Tích hợp trực tiếp phía trên cùng của trang kết quả tìm kiếm (SERP), hiển thị Top-3 website được cộng đồng đánh giá cao nhất cho chủ đề đó, giúp người dùng tiết kiệm tới 70% thời gian duyệt web.
  • Tối ưu hóa công cụ tìm kiếm nội bộ doanh nghiệp (Site Search): Triển khai trên các sàn thương mại điện tử lớn (Tiki, Shopee, Amazon) để khai phá log tìm kiếm nội bộ, tự động đẩy các danh mục sản phẩm có tỷ lệ chuyển đổi cao lên đầu.
+-------------------------------------------------------------+
| Query: [ sony vaio recovery disc                          ] |
+-------------------------------------------------------------+
| (*) Goi y website hang dau tu cong dong:                    |
| 1. esupport.sony.com (98% tin cay tu 1,420 luot truy cap)   |
| 2. vaio-link.com                                            |
+-------------------------------------------------------------+
| Ket qua tim kiem thong thuong:                              |
| 1. Forum sua chua laptop ...                                |
| 2. Huong dan cai win Sony ...                               |
+-------------------------------------------------------------+

Chiến lược và yêu cầu triển khai

  • Yêu cầu hạ tầng:
    • Cluster xử lý dữ liệu: Apache Spark / Hadoop MapReduce phục vụ tiền xử lý và trích xuất LDA định kỳ hàng tuần.
    • In-Memory Key-Value Store: Redis / Memcached lưu trữ tâm cụm và danh sách URL ứng viên để phục vụ truy vấn thời gian thực với độ trễ $<50\text{ms}$.
    • API Gateway: Triển khai microservice tiếp nhận truy vấn và trả kết quả dưới dạng JSON endpoint /api/v1/recommend?query=....

Hạn chế và hướng phát triển

  • Hạn chế kỹ thuật:
    • Phụ thuộc vào chất lượng log ban đầu; đối với các truy vấn hoàn toàn mới (Cold-start Query) chưa từng xuất hiện trong log hoặc từ vựng không nằm trong bộ từ điển LDA, hệ thống có thể phân cụm thiếu chính xác.
    • Việc lọc miền tri thức (Domain Filtering) hiện tại vẫn dựa trên danh sách từ khóa tĩnh (seed keywords), chưa có khả năng tự động mở rộng miền từ vựng.
  • Hướng phát triển tương lai:
    • Nghiên cứu tích hợp các mô hình biểu diễn từ dày đặc (Word Embeddings như Word2Vec, FastText hoặc Transformer-based models) thay thế cho không gian vector TF truyền thống.
    • Mở rộng kiến trúc xử lý luồng thời gian thực (Real-time Stream Mining) với Apache Kafka và Flink để cập nhật trọng số URL theo thời gian thực khi có sự kiện xu hướng mới bùng nổ.

Đối tượng hưởng lợi

  • Sinh viên & Học viên cao học: Tiếp cận mã nguồn thực tế và phương pháp luận kết hợp giữa Khai phá dữ liệu (Data Mining), Xử lý ngôn ngữ tự nhiên (NLP) và Hệ tư vấn (Recommender Systems).
  • Kỹ sư phát triển phần mềm (Software Engineers): Ứng dụng mô hình kiến trúc hai pha (Offline Pre-computation + Online Low-latency Serving) vào việc tối ưu hóa hiệu năng hệ thống lớn.
  • Doanh nghiệp & Đơn vị vận hành Search Engine: Nâng cao trải nghiệm người dùng cuối (User Retention Rate), giảm tỷ lệ thoát trang (Bounce Rate) bằng cách đưa người dùng đến thẳng website mục tiêu chất lượng cao.
  • Các nhà nghiên cứu (Researchers): Cung cấp bằng chứng thực nghiệm về tính hiệu quả của mô hình chủ đề LDA trong việc giải quyết bài toán biểu diễn văn bản ngắn (Short Text Representation).

Câu hỏi thường gặp

1. Hệ thống xử lý thế nào khi người dùng nhập một truy vấn hoàn toàn mới chưa từng có trong Query Log?

Hệ thống sẽ chuẩn hóa truy vấn mới thông qua Stemming và loại bỏ từ dừng, sau đó tính khoảng cách Cosine giữa vector của truy vấn này với các tâm cụm ($Centroid$) đã được huấn luyện sẵn. Truy vấn sẽ được gán vào cụm có khoảng cách ngắn nhất để kế thừa tập URL tư vấn chất lượng cao của cụm đó.

2. Sự khác biệt cốt lõi giữa kết quả tư vấn của hệ thống và kết quả tự nhiên của máy tìm kiếm là gì?

Máy tìm kiếm xếp hạng dựa trên sự trùng khớp từ khóa và cấu trúc liên kết trang (backlinks). Hệ thống tư vấn xếp hạng dựa trên trí tuệ đám đông ngầm định (Implicit Collective Intelligence) – chỉ chọn lọc các website đã được hàng nghìn người dùng trước đó thực sự bấm chọn và chấp nhận khi tìm kiếm cùng một chủ đề.

3. Tại sao mô hình chủ đề LDA sinh từ chính Query Log lại cho kết quả phân cụm tốt hơn bộ chủ đề từ Wikipedia?

Dữ liệu văn bản Wikipedia mang tính học thuật, câu dài và đầy đủ ngữ pháp. Trong khi đó, truy vấn tìm kiếm rất ngắn, mang tính khẩu ngữ và chứa nhiều thuật ngữ mã hóa riêng biệt. Huấn luyện LDA trực tiếp trên Query Log giúp các phân phối từ vựng $p(w|z)$ phản ánh chính xác không gian ngữ nghĩa thực tế của người dùng máy tìm kiếm.

4. Chi phí tính toán của hệ thống khi mở rộng lên tập dữ liệu hàng trăm Gigabyte?

Pha tốn tài nguyên nhất là huấn luyện LDA và K-Means được thực hiện hoàn toàn ngoại tuyến (Offline Batch Processing). Pha trực tuyến chỉ thực hiện tính toán vector Cosine trên một không gian nhỏ (10 cụm và vài chục URL ứng viên), do đó tài nguyên tiêu thụ là hằng số $O(1)$ đối với mỗi request tìm kiếm.

5. Cơ chế nào ngăn chặn việc các website spam cố tình click tặc để tăng hạng trong hệ thống tư vấn?

Hệ thống áp dụng bước làm sạch dữ liệu: lọc các IP trùng lặp có tần suất bất thường trong một phiên làm việc ($Session$), chỉ tính trọng số click hợp lệ từ các AnonID riêng biệt và thiết lập ngưỡng chặn tối đa cho mỗi phiên tìm kiếm.

Kết luận

Khóa luận tốt nghiệp đã giải quyết bài toán tư vấn website cho máy tìm kiếm thông qua việc khai phá nhật ký truy vấn (Query Log). Bằng cách kết hợp mô hình phân tích chủ đề ẩn Latent Dirichlet Allocation (LDA) với thuật toán phân cụm K-Means và giải thuật tái xếp hạng trực tuyến, hệ thống khắc phục triệt để điểm yếu của các truy vấn ngắn và tận dụng hiệu quả phản hồi ngầm định của người dùng mà không cần yêu cầu đăng nhập hay chấm điểm thủ công.

Kết quả thử nghiệm thực tế trên tập dữ liệu MSN Query Log chứng minh độ chính xác vượt trội (đạt từ 66,7% đến 100% trên các truy vấn thử nghiệm tiêu biểu) cùng độ trễ phục vụ cực thấp. Hướng tiếp cận này mở ra giải pháp triển khai thực tế cho các công cụ tìm kiếm hiện đại nhằm tối ưu hóa trải nghiệm người dùng trong kỷ nguyên bùng nổ dữ liệu.