PaperlayerView exact revision on arXiv

Source-linked AI summary

Distance-based clustering of sparsely observed stochastic processes, with applications to online auctions

Jie Peng, Hans-Georg Müller

arXiv:0805.0463v2stat.APstat.ME

TL;DR

A suitable distance for clustering is difficult to choose when trajectories are observed only through sparse, irregularly timed, noisy measurements. The paper defines a functional distance conditional on observed trajectory snapshots, then applies standard distance-based methods such as clustering and multidimensional scaling. Six bidding-strategy clusters in the studied eBay auctions differ in their chances of winning and the final prices paid; late, moderate bids in the “L” cluster best combine a reasonable chance of winning with a relatively low price.

  • Problem

    A suitable distance for clustering is difficult to choose when trajectories are observed only through sparse, irregularly timed, noisy measurements.

    Source: §1 · pp. 1, 4, 5

  • Method

    The paper defines a functional distance conditional on observed trajectory snapshots, then applies standard distance-based methods such as clustering and multidimensional scaling.

    Source: §1 · p. 5, §4 · p. 17

  • Results

    Six bidding-strategy clusters in the studied eBay auctions differ in their chances of winning and the final prices paid; late, moderate bids in the “L” cluster best combine a reasonable chance of winning with a relatively low price.

    Source: §4 · pp. 17–18

  • Takeaways & Limitations

    For the second-price closed-ended eBay auctions studied, late bids at moderate levels are most effective when seeking both a reasonable chance of winning and a relatively low price.

    Source: §4 · p. 18

    The setup assumes sparse measurements at randomly sampled time points, with measurements corrupted by additive i.i.d. random noise.

    Source: §1 · p. 5

Abstract

from arXiv · show

We propose a distance between two realizations of a random process where for each realization only sparse and irregularly spaced measurements with additional measurement errors are available. Such data occur commonly in longitudinal studies and online trading data. A distance measure then makes it possible to apply distance-based analysis such as classification, clustering and multidimensional scaling for irregularly sampled longitudinal data. Once a suitable distance measure for sparsely sampled longitudinal trajectories has been found, we apply distance-based clustering methods to eBay online auction data. We identify six distinct clusters of bidding patterns. Each of these bidding patterns is found to be associated with a specific chance to obtain the auctioned item at a reasonable price.

1. Introduction.

Clustering irregularly observed trajectories requires a distance that can work with sparse, noisy measurements, where the usual L2 distance is not readily calculable. The paper develops this problem from individual eBay bidders’ sparse bid histories and motivates distance-based analysis of their bidding patterns.

1. Introduction.

  • The paper uses traditional clustering, in which each subject belongs to exactly one cluster, while noting alternatives that allow partial membership.The introduction names soft clustering and mixed-membership clustering as alternatives.Source: §1 · p. 2
  • In the seven-day second-price auctions studied, bidders submit maximum willingness-to-pay amounts through proxy bidding, and bid times are sparse and irregular.A bidder may submit only one or two bids; consecutive willingness-to-pay amounts can decrease.Source: §1 · p. 2
  • The study clusters individual bidder trajectories to distinguish strategies, unlike prior work that clusters auction-level price trajectories formed from all bidders’ bids.The observed bids are snapshots of an underlying continuous trajectory representing bidding behavior.Source: §1 · pp. 2–4
  • The proposed distance treats each realization as noisy measurements of an underlying stochastic process, enabling distance-based clustering or multidimensional scaling.The approach assumes observation times are randomly sampled from a possibly unknown distribution, with typically few observations per realization.Source: §1 · pp. 4–5
  • Analysis of 158 seven-day Palm M515 auctions identifies six bidding-pattern clusters associated with different chances of winning at a reasonable price.The introduction reports that the strategies differ in how well they achieve the goal of winning at a reasonable price.Source: §1 · p. 4
  • The L2 distance is not readily calculable from noisy, sparse, irregularly sampled measurements, motivating a distance designed for such observations.The setup treats observations as noisy measurements at randomly located points of a stochastic process.Source: §1 · pp. 1, 4, 5

2. A distance for sparse and irregular data.

The section defines a distance for sparsely observed trajectories using the conditional expectation of their squared L2 distance given the observed data. It establishes metric and prediction properties, describes estimation, and uses estimated distances for multidimensional scaling.

2.1. Definition and basic properties.

  • The proposed distance is the square root of the conditional expected squared L2 distance between two curves, given their observed data.The analysis conditions on measurement times and their counts.Source: §2.1 · p. 6, §2 · p. 6
  • The proposed distance is nonnegative, symmetric, zero for identical curves, positive for distinct curves almost surely, and satisfies the triangle inequality.It can therefore be viewed as a metric on the subject space of random process realizations.Source: §2.1 · p. 6
  • The conditional expectations are unbiased predictors of the corresponding squared L2 distances, including for truncated distances.The expected truncated squared distance equals the sum of the first K component contributions.Source: §2.1 · p. 7

2.2. Estimation.

  • With the stated assumptions, the estimated truncated distance converges in probability to the proposed distance.The result provides assurance when enough components are included and the number of observed curves is large enough; estimation plugs in estimates of the mean, covariance, eigenvalues, eigenfunctions, and error variance.Source: §2.2 · pp. 8–9

2.3. Distance-based scaling.

  • Metric MDS with the s-stress criterion visualizes sparse, irregularly observed trajectories using the estimated proposed distances as input.MDS projects objects into a low-dimensional Euclidean space so projected distances match the original dissimilarities according to a target criterion.Source: §2.3 · pp. 9–10

3. Clustering bidders in online auctions.

The analysis clusters sparsely observed eBay bidder trajectories into six patterns using a conditional functional distance and MDS. Winning chances and prices vary by cluster: H favors winning, while L offers a lower-priced win with a reasonable chance.

3. Clustering bidders in online auctions.

  • The analysis covered 1,801 trajectories from 157 seven-day auctions after removing 47 bids outside three standard deviations of the mean curve.The analyzed trajectories contained 3,596 bids.Source: §3 · pp. 10–11, Figure 2 · p. 12
  • Five components accounted for about 95% of trajectory variation in the conditional L2 distance, and the MDS projection used two dimensions.The first five eigenvalues explained 78.6%, 12.6%, 2.21%, 1.72%, and 0.87% of the first 100 eigenvalues' sum.Source: §3 · pp. 11–12
  • K-means on the two-dimensional metricsstress MDS projection of the conditional functional distance identified six clusters: L, H, S, F, A, and E.Only metricsstress converged among the three MDS criteria tried.Source: §3 · p. 12, Figure 3 · p. 13
  • 24.3% was the winning rate for H, versus 9.1% for A and 7.5% for L; H had the highest cluster winning rate.S and E had only 2 and 1 winners, respectively, and F had none.Source: Table 1 · p. 13, §3 · p. 15
  • L and H bid near auction end, E bids early, and S, F, and A bid throughout, with distinct bid-amount trajectories.S raises bids faster toward the end; F starts high and increases cautiously, while A raises bids more aggressively.Source: §3 · p. 14, Figure 5 · p. 15, Figure 6 · p. 16
  • H bidders paid an average of $237 when winning, compared with $245 for A and $208 for L; H best served securing the item, while L offered a low price with a reasonable chance.L and H both involved fewer bids, also limiting bidder effort.Source: §3 · pp. 15–16

4. Discussion.

The proposed distance supports analysis of sparse, irregular trajectories, and its application identifies six eBay bidding strategies distinguished by bid timing, amounts, and their interaction. In the considered auctions, late moderate bids in the “L” cluster best combine a reasonable chance of winning with a relatively low price.

4. Discussion.

  • Bid timing and amounts interact to characterize strategies: ignoring amounts would leave the similarly timed “L” and “H” bidders indistinguishable.The functional viewpoint also describes these interactions in the “S”, “A” and “F” clusters.Source: §4 · pp. 16–17
  • The proposed functional distance is conditioned on observed trajectory snapshots, addresses sparse and irregular measurements, and supports standard MDS and clustering methods.The authors report that estimated distances converge to target values under suitable assumptions.Source: §4 · p. 17
  • For the considered second-price closed-ended eBay auctions, six strategies differ in bid timing and amounts; late moderate bids (“L”) best combine a reasonable chance of winning with a relatively low price.The bid-amount histograms show the distributions for each cluster.Source: §4 · pp. 16–18, Figure 7 · p. 17

APPENDIX

The appendix gives technical support for the distance construction and its estimation, including model-fitting procedures and convergence results.

APPENDIX

  • The proof notes that the proposed distance satisfies the triangle inequality, supporting its characterization as a metric on the subject space.The appendix invokes the Cauchy–Schwarz inequality in proving a proposition property.Source: APPENDIX · p. 18
  • Model fitting uses pooled-data local linear smoothers for the mean and covariance, with bandwidths selected by leave-one-curve-out cross-validation.The covariance fit uses off-diagonal empirical covariance entries to avoid the measurement-error variance contribution.Source: APPENDIX · pp. 18–19
  • The appendix states that the estimated truncated distance converges in probability to the target distance under its stated assumptions.It also states that the truncated distance converges in probability to the full distance.Source: APPENDIX · pp. 20–21

SUPPLEMENTARY MATERIAL

The supplementary material lists eBay codes and R functions used for FPCA and conditional distance analysis.

SUPPLEMENTARY MATERIAL

Loading 0805.0463v2…