An Efficient Clustering Algorithm for Patterns Placement in Walkthrough System

Mining of sequential patterns in walkthrough systems is an interesting data mining problem. It can be envisioned as a tool for forecasting and prediction of the future behavior of user’s traversal patterns. In the past, how to display the object faster in the next time were their concerns. They seldom consider the problem of access times of objects in the storage systems. In this paper, we will consider this problem and solve this by clustering. Clustering methodology is particularly appropriate for the exploration of interrelationships among objects to reduce the access times of objects. We record the user’s path as log-data and store it in database. After a certain period of time, we will process the log-data database for user traversal paths and find out their characteristics, which will be utilized to determine the optimal physical organization of those VRML objects on disks. Meanwhile, we also introduce the relationships among transactions, views and objects. According to these relationships, we suggest the clustering criteria--inter-pattern similarity, which utilize these characteristics to distribute the objects into the appropriate clusters. As a result, the large-scale VRML models could be accessed more efficiently, allowing for a real-time walk-through in the scene. Author for correspondence and also is an instructor of WuFeng Institute of Technology.     

Sensory-motor enhancement in a virtual therapeutic environment

The sensory-motor skills of persons with neuromuscular disabilities have been shown to be enhanced by intensive and repetitive therapeutic interventions. This paper describes a form of low immersion virtual reality and a prototype, open source system that allow a user with significant physical disability to actively interact with computer-generated objects whose behaviors promote a game-like interaction. Unlike fully immersive and haptic virtual reality, this approach frees the user from head-mounted displays and gloves. It extracts the user’s real-time silhouette from the output of a remote video camera and uses that two-dimensional outline to interact with graphical objects on screen. In contrast to video games that have been modified with specialized interfaces, this virtual interaction system promotes the repetitive use of goal directed movements of the arms and body, which are essential to promote cortical reorganization, as well as discourage unwanted changes in muscle tissue that result in contracture. A prototype system demonstrates the potential of low immersion technology to motivate users and encourage participation in therapy. It also offers the potential of accommodating the sensory-motor skills of individuals with very significant impairment. The behaviors of the computer-generated graphics can be altered to allow use by those with very limited range of motion and/or motor control. These behaviors can be adjusted to provide a continuing challenge as the user’s skills improve. This prototype is described in terms of functional capabilities that include a silhouette extraction from a video image, and generation of graphical objects that interact with the silhouette. The work is extended with a discussion of a more sophisticated region of interest detection algorithm that can select specific parts of the body.     

Automatic symbolic compositional verification by learning assumptions

Compositional reasoning aims to improve scalability of verification tools by reducing the original verification task into subproblems. The simplification is typically based on assume-guarantee reasoning principles, and requires user guidance to identify appropriate assumptions for components. In this paper, we propose a fully automated approach to compositional reasoning that consists of automated decomposition using a hypergraph partitioning algorithm for balanced clustering of variables, and discovering assumptions using the L ^* algorithm for active learning of regular languages. We present a symbolic implementation of the learning algorithm, and incorporate it in the model checker NuSmv. In some cases, our experiments demonstrate significant savings in the computational requirements of symbolic model checking. This research was partially supported by ARO grant DAAD19-01-1-0473, and NSF grants ITR/SY 0121431 and CCR0306382.     

OCRS: an interactive object-based image clustering and retrieval system

In this paper, we propose an Interactive Object-based Image Clustering and Retrieval System (OCRS). The system incorporates two major modules: Preprocessing and Object-based Image Retrieval. In preprocessing, an unsupervised segmentation method called WavSeg is used to segment images into meaningful semantic regions (image objects). This is an area where a huge number of image regions are involved. Therefore, we propose a Genetic Algorithm based algorithm to cluster these images objects and thus reduce the search space for object-based image retrieval. In the learning and retrieval module, the Diverse Density algorithm is adopted to analyze the user’s interest and generate the initial hypothesis which provides a prototype for future learning and retrieval. Relevance Feedback technique is incorporated to provide progressive guidance to the learning process. In interacting with user, we propose to use One-Class Support Vector Machine (SVM) to learn the user’s interest and refine the returned result. Performance is evaluated on a large image database and the effectiveness of our retrieval algorithm is demonstrated through comparative studies.

Relational mountain (density) clustering method and web log analysis

The mountain clustering method and the subtractive clustering method are useful methods for finding cluster centers based on local density in object data. These methods have been extended to shell clustering. In this article, we propose a relational mountain clustering method (RMCM), which produces a set of (proto) typical objects as well as a crisp partition of the objects generating the relation, using a new concept that we call relational density. We exemplify RMCM by clustering several relational data sets that come from object data. Finally, RMCM is applied to web log analysis, where it produces useful user profiles from web log data. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 375–392, 2005.     

Databases with uncertainty and lineage

This paper introduces uldbs, an extension of relational databases with simple yet expressive constructs for representing and manipulating both lineage and uncertainty. Uncertain data and data lineage are two important areas of data management that have been considered extensively in isolation, however many applications require the features in tandem. Fundamentally, lineage enables simple and consistent representation of uncertain data, it correlates uncertainty in query results with uncertainty in the input data, and query processing with lineage and uncertainty together presents computational benefits over treating them separately. We show that the uldb representation is complete, and that it permits straightforward implementation of many relational operations. We define two notions of uldb minimality—data-minimal and lineage-minimal—and study minimization of uldb representations under both notions. With lineage, derived relations are no longer self-contained: their uncertainty depends on uncertainty in the base data. We provide an algorithm for the new operation of extracting a database subset in the presence of interconnected uncertainty. We also show how uldbs enable a new approach to query processing in probabilistic databases. Finally, we describe the current state of the Trio system, our implementation of uldbs under development at Stanford. This work was supported by the National Science Foundation under grants IIS-0324431, IIS-1098447, and IIS-9985114, by DARPA Contract #03-000225, and by a grant from the Boeing Corporation.     

A multi-agent based user context Bayesian neural network analysis system

The increasing user mobility demands placed upon IT services necessitates an environment that enables users to access optimal services at any time and in any place. This study presents research conducted to develop a system that is capable of analyzing user IT service patterns and tendencies and provides the necessary service resources by sharing each user’s context information. First, each user’s context information is gathered to provide the multi-agent software training data necessary to describe user operations in a hybrid peer-to-peer (P2P) structured communication environment. Next, the data collected about each user’s mobile device is analyzed through a Bayesian based neural network system to identify the user’s tendency and extract essential service information. This information provides a communication configuration allowing the user access to the best communication service between the user’s mobile device and the local server at any time and in any place, thereby enhancing the ubiquitous computing environment.     

Optimal Design of Object-Oriented Databases in Automatic Information-Control Systems. I. Analysis of Problem Domains

Design of object-oriented databases for automatic information control systems is studied. A formal method of analysis and design of optimal structures for object-oriented databases is developed on the basis of sequential interconnected formalizations of user problem domains, clustering of user information and functional requirements, design and analysis of object models for user requirements and object canonical structure of databases and design of optimal logical structures for object-oriented databases. Methods of analysis of problem domains of database users and construction of effective object canonical database structures in the form of classes, objects, and their relations and satisfying principles of abstraction, encapsulation, modularity, and hierarchy are described.     

<Emphasis Type="Italic">I-Quest</Emphasis>: an <Emphasis Type="Italic">i</Emphasis>ntelligent <Emphasis Type="Italic">que</Emphasis>ry <Emphasis Type="Italic">st</Emphasis>ructuring based on user browsing feedback for semantic retrieval of video data

In spite of significant improvements in video data retrieval, a system has not yet been developed that can adequately respond to a user’s query. Typically, the user has to refine the query many times and view query results until eventually the expected videos are retrieved from the database. The complexity of video data and questionable query structuring by the user aggravates the retrieval process. Most previous research in this area has focused on retrieval based on low-level features. Managing imprecise queries using semantic (high-level) content is no easier than queries based on low-level features due to the absence of a proper continuous distance function. We provide a method to help users search for clips and videos of interest in video databases. The video clips are classified as interesting and uninteresting based on user browsing. The attribute values of clips are classified by commonality, presence, and frequency within each of the two groups to be used in computing the relevance of each clip to the user’s query. In this paper, we provide an intelligent query structuring system, called I-Quest, to rank clips based on user browsing feedback, where a template generation from the set of interesting and uninteresting sets is impossible or yields poor results.

Unification of Four Versions of Program Semantics

Computing Science is a new subject, and we have not yet achieved the unification of theories that should support a proper understanding of its structure. CAR Hoare and He Jifeng, 1998. In this paper we use Priestley duality and Jónsson/Tarski duality to translate between four versions of program semantics: the relational model, predicate transformer semantics, information systems, and powerdomains. Our point of entry is the relational model, a kind of Kripke semantics, in which programs are thought of as input-output relations over a structured state space. Specifically, we present the state space as a certain kind of Priestley space, and programs as certain structure-preserving relations over such a space. We then derive, in circular fashion, a predicate transformer semantics from the relational model, an information system from the predicate transformer semantics, a powerdomain from the information system, and the original relational model back again from the powerdomain. The information system is also shown to be related to Hoare logic. To clarify the intuition behind this approach we present a case study, which is a ‘Priestley version’ of the so-called universal domain due to Plotkin, and we explicate various ideas about properties of programs and predicates in terms of this case study. Received April 1997 / Accepted in revised form February 1998     

Learning implicit user interest hierarchy for context in personalization

To provide a more robust context for personalization, we desire to extract a continuum of general to specific interests of a user, called a user interest hierarchy (UIH). The higher-level interests are more general, while the lower-level interests are more specific. A UIH can represent a user’s interests at different abstraction levels and can be learned from the contents (words/phrases) in a set of web pages bookmarked by a user. We propose a divisive hierarchical clustering (DHC) algorithm to group terms (topics) into a hierarchy where more general interests are represented by a larger set of terms. Our approach does not need user involvement and learns the UIH “implicitly”. To enrich features used in the UIH, we used phrases in addition to words. Our experiment indicates that DHC with the Augmented Expected Mutual Information (AEMI) correlation function and MaxChildren threshold-finding method built more meaningful UIHs than the other combinations on average; using words and phrases as features improved the quality of UIHs.     

Towards personality-based user adaptation: psychologically informed stylistic language generation

Conversation is an essential component of social behavior, one of the primary means by which humans express intentions, beliefs, emotions, attitudes and personality. Thus the development of systems to support natural conversational interaction has been a long term research goal. In natural conversation, humans adapt to one another across many levels of utterance production via processes variously described as linguistic style matching, entrainment, alignment, audience design, and accommodation. A number of recent studies strongly suggest that dialogue systems that adapted to the user in a similar way would be more effective. However, a major research challenge in this area is the ability to dynamically generate user-adaptive utterance variations. As part of a personality-based user adaptation framework, this article describes personage, a highly parameterizable generator which provides a large number of parameters to support adaptation to a user’s linguistic style. We show how we can systematically apply results from psycholinguistic studies that document the linguistic reflexes of personality, in order to develop models to control personage’s parameters, and produce utterances matching particular personality profiles. When we evaluate these outputs with human judges, the results indicate that humans perceive the personality of system utterances in the way that the system intended.     

Random Bichromatic Matchings

Given a graph with edges colored Red and Blue, we study the problem of sampling and approximately counting the number of matchings with exactly k Red edges. We solve the problem of estimating the number of perfect matchings with exactly k Red edges for dense graphs. We study a Markov chain on the space of all matchings of a graph that favors matchings with k Red edges. We show that it is rapidly mixing using non-traditional canonical paths that can backtrack. We show that this chain can be used to sample matchings in the 2-dimensional toroidal lattice of any fixed size ℓ with k Red edges, where the horizontal edges are Red and the vertical edges are Blue. An extended abstract appeared in J.R. Correa, A. Hevia and M.A. Kiwi (eds.) Proceedings of the 7th Latin American Theoretical Informatics Symposium, LNCS 3887, pp. 190–201, Springer, 2006. N. Bhatnagar’s and D. Randall’s research was supported in part by NSF grants CCR-0515105 and DMS-0505505. V.V. Vazirani’s research was supported in part by NSF grants 0311541, 0220343 and CCR-0515186. N. Bhatnagar’s and E. Vigoda’s research was supported in part by NSF grant CCR-0455666.     

Plan recognition for interface agents

Interface agents are computer programs that provide personalized assistance to a user dealing with computer based applications. By understanding the tasks the user performs in a software application an interface agent could be aware of the context that represents the user’s focus of attention at each particular moment. With this purpose, plan recognition aims at identifying the plans or goals of a user from the tasks he (for simplicity, we use “he” to refer to the user, but we do not mean any distinctions about sexes) performs. A prerequisite for the recognition of plans is knowledge of a user’s possible tasks and the combination of these tasks in complex task sequences, which describes typical user behavior. Plan recognition will enable an interface agent to reason about what the user might do next so that it can determine how to assist him. In this work we present the state of the art in Plan Recognition, paying special attention to the features that make it useful to interface agents. These features include the ability to deal with uncertainty, multiple plans, multiple interleaved goals, overloaded tasks, noisy tasks, interruptions and the capability to adapt to a particular user.     

On neuroscience-based informational technologies for authentic models of individual mind

Progress of neuroscience and information technologies tentatively makes possible actual implementation of old ideas to enable individual human being informational individuality with ability of autonomous existence (“life”) in computers. The idea has numerous reflections in science fiction and mass media communications. It seems, that just now computer technologies and understanding of brain mechanisms have attained a level, which makes this idea to be feasible and contemporary. The authentic model of an individual can consist of neurocomputer-based expert system, endowed with multi-media abilities. The system simulates its user, reproducing a kind of an Alter Ego for the user. The simulation ability of the system is being fed into it as a result of a thorough knowledge engineering process, which includes multiple psychological tests and psycho-physical measurements. The alter ego multi-media system is self-adjusted in a process of a permanent day to day dialog with its unique user. As a result it acquires real characters of user’s individuality. The user can authorize use of the system, adjusted to simulate user’s features to represent user in communication with other persons. In this case the system operates in an Alter Homo mode, enabling the user with communication abilities a good deal superior to human ones. The text was submitted by the authors in English.     

Digital photo classification methodology for groups of photographers

Digital cameras have become an essential product when traveling or attending events. Because of its popularity and low cost, it is increasingly likely that more than one camera will be used at an event. The total number of photos captured is also increasing. Although the cost of digital photographs is low, managing numerous digital photos is burdensome to most users. Thus, an intelligent management tool for digital photos is required. In this paper, we propose novel clustering algorithms for concurrent digital photos obtained from multiple cameras. Since previous studies only considered a single user’s photo collection, they are not applicable to concurrent photos obtained from a group of photographers. To handle this situation, we define temporal/spatial combined clustering for the set of group photos taken from different cameras. If photos are submitted from a camera whose user has shown a preference between spatial and temporal clustering, we can obtain customized clustering output from other photo sets according to the reference clustering characteristics. We also propose unsupervised methods for general clustering output. Input concurrent photos are processed without a user’s true clusters, which can be a burden when the number of photos in the true clusters is huge. We tested our methods via more than one thousand photos taken by tourist groups. The final result was satisfactory compared to previous methods based on temporal (spatial) criteria only.     

Prediction of user navigation patterns by mining the temporal web usage evolution

Advances in the data mining technologies have enabled the intelligent Web abilities in various applications by utilizing the hidden user behavior patterns discovered from the Web logs. Intelligent methods for discovering and predicting user’s patterns is important in supporting intelligent Web applications like personalized services. Although numerous studies have been done on Web usage mining, few of them consider the temporal evolution characteristic in discovering web user’s patterns. In this paper, we propose a novel data mining algorithm named Temporal N-Gram (TN-Gram) for constructing prediction models of Web user navigation by considering the temporality property in Web usage evolution. Moreover, three kinds of new measures are proposed for evaluating the temporal evolution of navigation patterns under different time periods. Through experimental evaluation on both of real-life and simulated datasets, the proposed TN-Gram model is shown to outperform other approaches like N-gram modeling in terms of prediction precision, in particular when the web user’s navigating behavior changes significantly with temporal evolution.     

Toward accessible self-service kiosks through intelligent user interfaces

Public self-service kiosks provide key services such as ticket sales, airport check-in and general information. Such kiosks must be universally designed to be used by society at large, irrespective of the individual users’ physical and cognitive abilities, level of education and familiarity with the system. The noble goal of universal accessibility is hard to achieve. This study reports experiences with a universally designed kiosk prototype based on a multimodal intelligent user interface that adapts to the user’s physical characteristics. The user interacts with the system via a tall rectangular touch-sensitive display where the interaction area is adjusted to fit the user’s height. A digital camera is used to measure the user’s approximate reading distance from the display such that the text size can be adjusted accordingly. The user’s touch target accuracy is measured, and the target sizes are increased for users with motor difficulties. A Byzantine visualization technique is employed to exploit unused and unreachable screen real estate to provide the user with additional visual cues. The techniques explored in this study have potential for most public self-service kiosks.     

User Modeling in Spoken Dialogue Systems to Generate Flexible Guidance

We address the issue of appropriate user modeling to generate cooperative responses to users in spoken dialogue systems. Unlike previous studies that have focused on a user’s knowledge, we propose more generalized modeling. We specifically set up three dimensions for user models: the skill level in use of the system, the knowledge level about the target domain, and the degree of urgency. Moreover, the models are automatically derived by decision tree learning using actual dialogue data collected by the system. We obtained reasonable accuracy in classification for all dimensions. Dialogue strategies based on user modeling were implemented on the Kyoto City Bus Information System that was developed at our laboratory. Experimental evaluations revealed that the cooperative responses adapted to each subject type served as good guides for novices without increasing the duration dialogue lasted for skilled users.