基于LCS算法实现会话分组数据与列表的推荐集合生成函数

Got it, let's walk through building the recommenSet function you described, which leverages the LCS algorithm from the qualv package to generate recommendations based on similar page sequences.

First, Prep the Required Package #

First off, make sure you have the qualv package installed—it's the tool we'll use for computing the Longest Common Subsequence (LCS):

install.packages("qualv")
library(qualv)

The recommenSet Function Code #

Here's the full function, with comments explaining each step to match your requirements:

recommenSet <- function(mylist, pages) {
  # Sort the input pages (as shown in your session_id=877 example)
  sorted_pages <- sort(pages)
  
  # Convert the igraph.vs vertex sequence into a list of page sequences
  # Update 'page_sequence' here to match the attribute name storing page IDs in your igraph vertices
  mylist_sequences <- lapply(mylist, function(vertex) vertex$page_sequence)
  
  # Calculate LCS length between sorted input pages and each sequence in mylist
  lcs_lengths <- sapply(mylist_sequences, function(seq) {
    # Optional: Sort the mylist sequence too if you want consistent ordering
    sorted_seq <- sort(seq)
    # Get the number of rows in the LCS result (this is the LCS length)
    nrow(LCS(sorted_pages, sorted_seq)$LCS)
  })
  
  # Find the sequence with the maximum LCS length (pick first if there's a tie)
  best_seq_index <- which.max(lcs_lengths)
  best_sequence <- mylist_sequences[[best_seq_index]]
  
  # Compute the set difference: elements in the best sequence not present in input pages
  recommendation <- setdiff(best_sequence, pages)
  
  # Return the recommendation set
  return(recommendation)
}

Example Walkthrough #

Let's test this with your sample scenario where session_id=877 has pages c(11,8):

# First, simulate an igraph.vs object (adjust this to match your actual data)
library(igraph)
# Create a dummy graph with 3 vertices, each having a page_sequence attribute
dummy_graph <- make_empty_graph(3)
V(dummy_graph)$page_sequence <- list(c(8,11,5), c(3,8), c(11,9))
mylist <- V(dummy_graph) # This is your igraph.vs type input

# Test the function with the sample pages
sample_pages <- c(11,8)
recommenSet(mylist, sample_pages)
# Output should be: 5 (since the first sequence has the longest LCS with the sorted sample pages)

Important Notes to Customize for Your Data #

• igraph Attribute Name: The function assumes your igraph vertices store the page sequence in an attribute called page_sequence. If your data uses a different name (like pages or user_sequence), replace vertex$page_sequence with the correct attribute.
• Sorting: We sorted the input pages as per your example. If you need to sort the sequences in mylist too, the code already includes that step (feel free to remove sorting if it's not needed for your use case).
• Tie Breaking: If multiple sequences have the same maximum LCS length, the function picks the first one. You can modify this logic (e.g., pick the longest sequence, or return all top sequences) if required.
• Set Direction: The function returns elements from the best sequence that aren't in the input pages. If you want the reverse (pages not in the best sequence), swap the arguments in setdiff() to setdiff(pages, best_sequence).

内容的提问来源于stack exchange，提问作者SumitArya