Data-driven segmentation has become standard practice in strategic marketing. Typically, however, respondents are grouped only once, implicitly assuming deterministic nature of the segmentation methods applied. Once the segments are derived, background variables are used to test the significance of the difference between clusters indicating external validity of the market segments. High external validity implies a high level of trustworthiness of the solution and thus managerially useful market segments to choose from. However, single runs of explorative analysis remain only a weak basis for good long-term managerial decisions. In this study a different approach is suggested to improve the quality of the market structure insight for decision-making: two data-driven segmentation solutions are constructed independently. Association between them is used as an additional internal validity indicator. Benefit and behavioural segmentation bases are used to illustrate the concept: surfers provided information regarding the importance of aspects of proposed surf destinations and destinations they had previously visited. Segments resulting from both bases are profiled: they notably differ in background information. Significant association between these solutions supports the validity and managerial usefulness for target segment choice for the following targeted marketing action. Using this procedure results in the identification of stable consumer groups, which in turn leads to an improved understanding of customer segments; and thus enables the industry to improve the quality by customizing the product.